Lemma 4.5 — tree sizes after Rounding (a), and goods of price above
ProvedSatiationFisherNSW.lemma_4_5approximation-algorithmsfisher-marketmarket-equilibriumnash-social-welfarep2o-gran-per-chapterp2o-plan-paperp2o-v1
Under the standing assumptions of §4.1, consider any run of the rounding procedure and a tree component of after step (a) of rounding. Then has agents and goods for some .
Moreover, suppose agent of is assigned a good with during step (a) of rounding. Then
- spends all its money on : ;
- is the only agent that spends money on : for ;
- the valuation of after rounding is exactly ;
- : no agent of is capped in .
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 - reading: "each tree component " after step (a) of rounding → the tree components of the forest after preprocessing that contain an agent, with the number of their goods that kept a child (the goods left after step (a)); reason: the goods assigned in step (a) are leaves, so removing them changes no component's agents; components without an agent are single unsold zero-price goods, which the procedure never roots
Preamble
import Mathlib import Definitions.Def_SatiationFisherNSW_NSWInstance import Definitions.Def_SatiationFisherNSW_RoundingRun open scoped Classical
Formal statement
namespace SatiationFisherNSW
/-- Lemma 4.5 (Garg, Hoefer, Mehlhorn, arXiv:1707.04428v3, p.27): after step (a) of rounding,
each tree component `T` has `k_T + 1` agents and `k_T` goods for some `k_T ≥ 0`. Suppose agent
`i` in `T` is assigned a good `j` with `p_j > 1` during step (a) of rounding. Then `i` spends all
its money on `j`, and `i` is the only agent that spends money on `j`. Moreover, the valuation of
`i` after rounding is `p_j`, and `B_c ∩ T = ∅`.
**Formalization Note** `T` ranges over the tree components of the forest after preprocessing
whose agents lie outside `B₀` (`IsPriceTree`); its goods at the end of Rounding (a) are
`remainingGoodsOf T` (the goods assigned in step (a) are leaves and do not affect the agents of
a component). "Assigned during step (a)" means: `j`'s parent agent is `i` and `j` kept no child.
"Spends all its money" is `p_j x_{ij} = m_i = 1`; "the only agent that spends money on `j`" is
`p_j x_{i'j} = 0` for `i' ≠ i`. The valuation after rounding is `v_i` of the output allocation,
and `B_c` is the set of capped buyers in `(x, p)`.
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_5
{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)
(T : (R.ppGraph I.market x p).ConnectedComponent) (hT : R.IsPriceTree I.market x p T) :
(R.agentsOf I.market x p T).card = (R.remainingGoodsOf I.market x p T).card + 1 ∧
∀ i ∈ R.agentsOf I.market x p T, ∀ j, R.parentAgent j = some i →
R.keptChild I.market x p j = none → 1 < p j →
p j * x i j = 1 ∧ (∀ i', i' ≠ i → p j * x i' j = 0) ∧
I.val i (R.output I.market x p) = p j ∧
∀ a ∈ R.agentsOf I.market x p T, ¬ I.market.IsCapped x a := 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.5, p.27; procedure, pp.26–27
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.