Algorithm 1, Step 7, pp.11–12 — a point of the convex hull of a union of convex sets is a lottery with one point per set
ProvedNashStackelberg.step_7_decompositionconvex-hullconvexityp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be convex subsets of a real vector space and let . Then there are weights with and points such that
Applied to the complementarity polyhedra whose union is , this is Step 7 of Algorithm 1: a point is written as a convex combination of pure strategies, with at most one point from each nonempty complementarity polyhedron, and the coefficients are the probabilities of the lottery.
Differences from the source:
- generalization: x̃ⁱ ∈ conv(𝓕ⁱ) with 𝓕ⁱ the union of the kⁱ nonempty complementarity polyhedra, written as Σⱼ pⁱⱼ x̂ⁱⱼ with x̂ⁱⱼ ∈ 𝓕ⁱ → any finitely many convex sets in a real vector space, one point from each nonempty set; reason: polyhedra are convex; the page's decomposition is the special case
Preamble
import Mathlib
Formal statement
namespace NashStackelberg
/-- **Step 7: a point of the convex hull of a union of convex sets is a lottery over them**
(Carvalho, Dragotto, Feijoo, Lodi & Sankaranarayanan, *When Nash Meets Stackelberg*,
arXiv:1910.06452v6, Algorithm 1, Step 7, p.12: "x̃ⁱ = Σ_{j=1}^{kⁱ} pⁱⱼ x̂ⁱⱼ for x̂ⁱ₁, …, x̂ⁱ_{kⁱ} ∈ 𝓕ⁱ
with pⁱⱼ ≥ 0 and Σ pⁱⱼ = 1", and pp.11–12: "the points in the support of the convex combination
belong to 𝓕ⁱ … the convex combination's coefficients pⁱ are the probabilities").
Let `K₁, …, K_k` be convex sets in a real vector space and `x ∈ conv(K₁ ∪ ⋯ ∪ K_k)`. Then there are
weights `pⱼ ≥ 0` with `Σⱼ pⱼ = 1` and points `x̂ⱼ`, with `x̂ⱼ ∈ Kⱼ` whenever `Kⱼ` is nonempty and
`pⱼ = 0` whenever `Kⱼ` is empty, such that `x = Σⱼ pⱼ x̂ⱼ`: one point per set.
**Formalization Note.** Applied with the `Kⱼ` the (at most `2^{|𝓒ⁱ|}`) polyhedra whose union is
`𝓕ⁱ`, this bounds the support of the lottery of Step 7 by the number `kⁱ` of nonempty
complementarity polyhedra, as on p.11 ("at most kⁱ"). -/
theorem step_7_decomposition {E : Type*} [AddCommGroup E] [Module ℝ E] {k : ℕ}
(K : Fin k → Set E) (hK : ∀ j, Convex ℝ (K j)) {x : E} (hx : x ∈ convexHull ℝ (⋃ j, K j)) :
∃ (p : Fin k → ℝ) (pts : Fin k → E), (∀ j, 0 ≤ p j) ∧ ∑ j, p j = 1 ∧
(∀ j, (K j).Nonempty → pts j ∈ K j) ∧ (∀ j, K j = ∅ → p j = 0) ∧
x = ∑ j, p j • pts j := by sorry
end NashStackelberg
Source
Carvalho, Dragotto, Feijoo, Lodi & Sankaranarayanan, When Nash Meets Stackelberg, arXiv:1910.06452v6, Algorithm 1, Step 7, p.12, and the paragraph "The Enumeration Algorithm", pp.11–12
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.