Lemma B.2 — tree sizes after Rounding (a) on zero-price trees
ProvedSatiationFisherNSW.lemma_B_2approximation-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. After step (a) of rounding, each zero-price tree component has agents and goods for some .
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 B.2 (Garg, Hoefer, Mehlhorn, arXiv:1707.04428v3, p.34): after step (a) of rounding,
each zero-price tree component `T` has `k_T + 1` agents and `k_T` goods for some `k_T ≥ 0`.
**Formalization Note** `T` ranges over the tree components of the forest after preprocessing
whose agents all lie in `B₀` (`IsZeroPriceTree`); its goods at the end of Rounding (a) are
`remainingGoodsOf T`. Unsold zero-price goods are isolated vertices without an agent and are not
tree components of the procedure.
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_B_2
{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.IsZeroPriceTree I.market x p T) :
(R.agentsOf I.market x p T).card = (R.remainingGoodsOf I.market x p T).card + 1 := 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 B.2, p.34; procedure, pp.33–34
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.