Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma B.1 — coupling local choices into at most 1 + Σ(k_j − 1) global orders with the same expected payments

Proved
ExactAutobid.Equilibria.lemma_B_1

by Shuze Chen · Nov 10, 2026 · Mathlib 0df444a (Lean v4.33.1)

auction-equilibriaautobiddingcomputational-complexityfixpp2o-gran-per-chapterp2o-plan-paperp2o-v1

Consider mmm local choice locations with kj≥1k_j \ge 1kj​≥1 choices at location jjj, a map combining every tuple c=(c1,…,cm)c = (c_1,\dots,c_m)c=(c1​,…,cm​) of local choices into a valid global order comb(c)\mathrm{comb}(c)comb(c), and bidder payments additive over the local choices, payi(comb(c))=∑jfij(cj)\mathrm{pay}_i(\mathrm{comb}(c)) = \sum_j f_{ij}(c_j)payi​(comb(c))=∑j​fij​(cj​). Then for any prescribed local marginal distributions μ1,…,μm\mu_1, \dots, \mu_mμ1​,…,μm​ there are s≤1+∑j=1m(kj−1)s \le 1 + \sum_{j=1}^m (k_j - 1)s≤1+∑j=1m​(kj​−1) tuples t1,…,tst_1, \dots, t_st1​,…,ts​ and weights wℓ≥0w_\ell \ge 0wℓ​≥0 summing to one with marginals μj\mu_jμj​ at every location, whose global orders comb(tℓ)\mathrm{comb}(t_\ell)comb(tℓ​) are valid and give the same expected payments:

∑ℓ=1swℓ payi(comb(tℓ))=∑j=1m∑cμj(c) fij(c).\sum_{\ell=1}^{s} w_\ell\, \mathrm{pay}_i(\mathrm{comb}(t_\ell)) = \sum_{j=1}^m \sum_{c} \mu_j(c)\, f_{ij}(c).ℓ=1∑s​wℓ​payi​(comb(tℓ​))=j=1∑m​c∑​μj​(c)fij​(c).

This is the coupling that turns the local tie choices of the GSP gadgets into a single distribution over legal global orders with polynomial support.

Differences from the source:

  • encoding: realized by at most 1 + Σ(k_j − 1) global orders → a weighted list of s ≤ 1 + Σ_j (k_j − 1) local-choice tuples t_ℓ, whose combined orders comb(t_ℓ) form the support, with the prescribed marginals; reason: the orders realized are the images of the listed tuples
  • encoding: with the same expected payments → Σ_ℓ w_ℓ pay_i(comb(t_ℓ)) = Σ_j Σ_c μ_j(c) f_ij(c) for every bidder i; reason: the expected payment under any coupling of the marginals
Preamble
import Mathlib
Formal statement
namespace ExactAutobid.Equilibria

/-- **Lemma B.1 (Coupling Local Choices, [HLN26]).** Let there be `m` local choice locations with
`k_j ≥ 1` choices at location `j`, such that every tuple of local choices combines into a valid
global order, and every bidder's payment is a sum of functions of the individual local choices.
Then any prescribed local marginal distributions are realized by at most `1 + Σ_j (k_j − 1)`
global orders, with the same expected payments. -/
theorem lemma_B_1 {O ι : Type} (valid : O → Prop) (pay : ι → O → ℝ) (m : ℕ) (k : Fin m → ℕ)
    (hk : ∀ j, 1 ≤ k j) (comb : ((j : Fin m) → Fin (k j)) → O) (hcomb : ∀ c, valid (comb c))
    (f : ι → (j : Fin m) → Fin (k j) → ℝ) (hpay : ∀ i c, pay i (comb c) = ∑ j, f i j (c j))
    (μ : (j : Fin m) → Fin (k j) → ℝ) (hμ0 : ∀ j c, 0 ≤ μ j c) (hμ1 : ∀ j, ∑ c, μ j c = 1) :
    ∃ (s : ℕ) (t : Fin s → (j : Fin m) → Fin (k j)) (w : Fin s → ℝ),
      s ≤ 1 + ∑ j, (k j - 1) ∧ (∀ l, 0 ≤ w l) ∧ ∑ l, w l = 1 ∧
      (∀ j c, ∑ l ∈ Finset.univ.filter (fun l => t l j = c), w l = μ j c) ∧
      (∀ l, valid (comb (t l))) ∧
      ∀ i, ∑ l, w l * pay i (comb (t l)) = ∑ j, ∑ c, μ j c * f i j c := by sorry

end ExactAutobid.Equilibria
Source
Huang, Liu, Yan, On the Complexity of Exact Autobidding Equilibria, arXiv:2611.04475 (sha256 270d1b74…), p. 58 (PDF 60), Lemma B.1
Human review
  • Endorsed by Community (Bot) · Nov 11, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Nov 11, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me