Lemma 4.4 — preprocessing keeps at least half of each valuation
ProvedSatiationFisherNSW.lemma_4_4approximation-algorithmsfisher-marketmarket-equilibriumnash-social-welfarep2o-gran-per-chapterp2o-plan-paperp2o-v1
Under the standing assumptions of §4.1 (an instance with , a money-clearing Fisher market, a thrifty and modest equilibrium , normalized valuations), consider any run of the rounding procedure and the trees of . After preprocessing:
- the valuation of each root agent is at least ;
- the valuation of every other agent is at least ;
- if good has child agents and , then keeps a child agent.
Here , and the valuation after preprocessing is the same expression summed over the goods still adjacent to .
Formalization Note "Root agents" after preprocessing are the original roots and the agents cut off from their parent good.
Differences from the source:
- reading: a demand bundle maximizes over bundles with , bundles having (p.6) → the maximum is taken over all with , without the box ; reason: with the box Lemma 4.3(a) fails (one agent, one item, , , , would be an equilibrium in which the uncapped agent spends ); the paper computes the maximal utility as (proof of Lemma 3.5, p.14), the unboxed maximum; unit supply is enforced by
- reading: an allocation has for every good (p.6) → only (Definition 2.1 (3)); reason: Definition 2.1 (3) and (5) force when , and Proposition 3.1 (Property 1) has
- encoding: is an MBB good of if , with for buyers interested in a zero-price good and (p.6) → and for all ; reason: no in ; the same MBB goods for every buyer with some positive value; it differs only for a buyer whose values are all , who then buys nothing (such a buyer violates money clearing, and in the goal makes every product )
- encoding: modest supply (p.6) → when , else ; reason: at the paper's is , while Lean's is
- encoding: "we normalize and " for and "assume that and fulfill these conditions directly" (p.24) → hypothesis
IsNormalized: every buyer outside has MBB ratio ; reason: the paper's own convention; every normalized instance arises this way and the rescaling preserves money clearing, and the equilibrium - encoding: the procedure of §4.1.2 (pp.26–27) and Appendix B (pp.33–34), with arbitrary root choice and tie-breaks, run recursively → a relation
RoundingRun.IsValidon the choices (an orientation of the allocation forest from root agents, a largest child per good, a greedy pick per agent), the kept child forced by the threshold, and the output defined from the recursion path; reason: the choices are exactly those the paper leaves free, and every valid run is covered; the recursion of Rounding (b) assigns the picked goods along the path to their parents and every other remaining good to its child agent - encoding: "the valuation" after preprocessing → over the goods adjacent to in the forest after preprocessing; reason: the fractional allocation restricted to the edges that are not cut
Preamble
import Mathlib import Definitions.Def_SatiationFisherNSW_NSWInstance import Definitions.Def_SatiationFisherNSW_RoundingRun open scoped Classical
Formal statement
namespace SatiationFisherNSW
/-- Lemma 4.4 (Garg, Hoefer, Mehlhorn, arXiv:1707.04428v3, p.27): after preprocessing, the
valuation of each root agent `r` is at least `v_r(x)/2`; for all other agents `i` the valuation
is at least `v_i(x)`; and if good `j` has child agents and `p_j > 1`, then `j` keeps a child
agent.
**Formalization Note** The lemma concerns the trees in `(B \ B₀) × (G \ G₀)` (p.26), so the
agents are those outside `B₀`. The valuation after preprocessing is
`min(c_i, Σ_j u_{ij} x_{ij})` over the goods still adjacent to `i` (`ppUtility`); `v_i(x)` is
`min(c_i, Σ_j u_{ij} x_{ij})` over all goods. A root after preprocessing is an original root or
an agent cut off from its parent good (`IsPPRoot`).
The standing assumptions of §4.1 are hypotheses: `v_{ij} ≤ c_i`
(p.23, "Henceforth"), the market of the instance (`u = v`, `m_i = d_j = 1`) is money clearing
(p.24, "for the remainder of this section"), `(x, p)` is a thrifty and modest equilibrium of it,
and the valuations are normalized according to `p` (MBB ratio `1` for every buyer outside `B₀`,
p.24).
A run of the procedure is any valid choice of roots, largest children and picks
(`RoundingRun.IsValid`); the statement holds for every run. -/
theorem lemma_4_4
{B G : Type*} [Fintype B] [Fintype G] (I : NSWInstance B G)
(hvc : ∀ i j, I.v i j ≤ I.c i) (hMC : I.market.IsMoneyClearing)
(x : B → G → ℝ) (p : G → ℝ) (hEq : I.market.IsEquilibrium x p) (hN : I.IsNormalized p)
(R : RoundingRun B G) (hR : R.IsValid I.market x p) :
(∀ i, ¬ I.market.InB0 p i →
(R.IsPPRoot I.market x p i → I.market.utility i (x i) / 2 ≤ R.ppUtility I.market x p i) ∧
(¬ R.IsPPRoot I.market x p i → I.market.utility i (x i) ≤ R.ppUtility I.market x p i)) ∧
(∀ j, 1 < p j → (∃ i, R.parentGood i = some j) →
R.keptChild I.market x p j ≠ none) := by sorry
end SatiationFisherNSW
Source
Garg, Hoefer, Mehlhorn, Satiation in Fisher markets and approximation of Nash social welfare, arXiv:1707.04428v3 (31 Jul 2019), https://arxiv.org/abs/1707.04428v3, Lemma 4.4, p.27; procedure, pp.26–27
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.