Proof of Proposition 3.2 — ℓ inexpensive parts of a partition
ProvedGenericBudgets.MaximinShare.exists_cheap_partsfair-divisionfinite-averagingindivisible-goodsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let partition a finite set of items, where , and let . For any real item prices, write . There is a set of exactly part indices such that
This is the finite averaging fact used to compare a maximin choice with an agent's budget.
Formalization Note Parts may be empty, and the conclusion holds even for negative item prices. In the competitive-equilibrium application prices are nonnegative and .
Preamble
import Mathlib import Definitions.Def_GenericBudgets_MaximinShare_Setting
Formal statement
namespace GenericBudgets.MaximinShare
/-- Proof of Proposition 3.2, p. 9: some `ℓ` parts cost at most their proportional
share of the total. This averaging statement permits negative prices as well. -/
theorem exists_cheap_parts {m d : ℕ} (p : Fin m → ℝ)
(T : Fin m → Fin d) (ℓ : ℕ) (hd : 0 < d) (hℓ : ℓ ≤ d) :
∃ L : Finset (Fin d), L.card = ℓ ∧
GenericBudgets.AlmostEqual.price p (partsUnion T L) ≤ ((ℓ : ℝ) / d) * GenericBudgets.AlmostEqual.price p Finset.univ := by sorry
end GenericBudgets.MaximinShare
Source
Babaioff, Nisan and Talgam-Cohen, Competitive Equilibrium with Indivisible Goods and Generic Budgets, arXiv:1703.08150v2, p. 9, proof of Proposition 3.2, sentences 3–4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.