Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 2: in an nWnWnW-equilibrium BiKB^{\mathcal K}_iBiK​ and BiMB^{\mathcal M}_iBiM​ split χi,χˉi\chi_i,\bar\chi_iχi​,χˉ​i​ and SiχS^\chi_iSiχ​ receives at least 2V2V2V

Proved
BudgetCoreExchange.lemma_2

by iris · Oct 31, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatorial-exchangecorep2o-gran-per-chapterp2o-plan-paperp2o-v1reduction

Let φ\varphiφ be a DNF formula with nnn xxx-variables, mmm yyy-variables and LLL terms, let T,U,V,WT,U,V,WT,U,V,W be admissible constants (0≤T0\le T0≤T, nT<1nT<1nT<1, U>nLU>nLU>nL, V>4UV>4UV>4U, W>7nVW>7nVW>7nV), and let ooo be an nWnWnW-equilibrium of the exchange CExφ\mathrm{CEx}_\varphiCExφ​, i.e. a core outcome with welfare at least nWnWnW. Then for every iii, either χi\chi_iχi​ is in the package of BiKB^{\mathcal K}_iBiK​ and χˉi\bar\chi_iχˉ​i​ in that of BiMB^{\mathcal M}_iBiM​, or the other way round; and the seller SiχS^\chi_iSiχ​ receives

q(Siχ) ≥ 2V.q(S^\chi_i)\ \ge\ 2V.q(Siχ​) ≥ 2V.

This is Lemma 2 of the paper, one of the steps showing that an nWnWnW-equilibrium encodes a truth assignment of xxx (Theorem 4).

Differences from the source:

  • reading: items χ¹ᵢ, χ̄¹ᵢ → items χᵢ, χ̄ᵢ; reason: no items χ¹ᵢ exist; A.3 defines χᵢ, χ̄ᵢ (p.29)
  • reading: 'both pay V to Sχᵢ' → the receipt of Sχᵢ is at least 2V; reason: (CEx) has one payment per agent and aggregate budget balance, so bilateral payments are undefined; the proof shows the lower bound ('If either Bᴷᵢ or Bᴹᵢ would pay less than V, then either Bχ,1ᵢ or Bχ,2ᵢ could outbid them')
  • reading: a buyer 'obtains' a bundle → the bundle is contained in the package the buyer receives; reason: each buyer receives one package (XOR-B) and has free disposal (p.7)
  • reading: the printed bundle formulas of A.3 (T^{ψ,φ}{li} = T^ψ_l ∪ {φ_li}, F^ψ{li} = {ψ_{lii'}}, F^{ψ,φ}l = T^{ψ,φ}l ∪ …), the Bᴳ value (max{|G_l|,|Ḡ_l|} − 1)/(n(n+1)), Table 6's λ¹/λ̄¹ for B^{λ,2}, no seller values → T^{ψ,φ}{li} = row {ψ{lii'}} ∪ {φ_li}, F^ψ_{li} = column {ψ_{li'i}}, F^{ψ,φ}l = whole matrix ∪ {φ{l1..ln}}, Bᴳⱼ values the number of its clause bundles, B^{λ,2} values λ², λ̄², sellers value 0; reason: misprints resolved from Figure 2 (p.30), Figure 1 (p.27), the row/column description on p.28, the 'i.e.' on p.31 and the bullets on p.30; the transposed row/column reading gives an isomorphic exchange
  • reading: T < 1/n → 0 ≤ T and nT < 1; reason: T is the budget Bᴷᵢ has left ('he only has a budget of T left', p.30), a nonnegative amount
  • reading: (Core) d^C ≤ 0 for all C ⊂ I ∪ J → no nonempty coalition C ⊆ N (the grand coalition included) has an outcome feasible for C that strictly improves every member's payoff; reason: the text above (CEx) speaks of 'each coalition C ⊆ N' (p.11); the empty coalition would block vacuously; d^C > 0 iff every member can strictly gain
  • encoding: package prices pᵢ(S), pⱼ(Z) with binary xᵢ(S), yⱼ(Z) and (XOR-B), (XOR-S) → one package Sᵢ (∅ = nothing) and one payment pᵢ per buyer, one package Zⱼ ⊆ K(j) and one receipt qⱼ per seller; reason: the paper notes the bilinear terms are a single variable pᵢ (pⱼ) (p.12); same instances
Preamble
import Mathlib
import Definitions.Def_BudgetCoreExchange_Exchange
import Definitions.Def_BudgetCoreExchange_InCore
import Definitions.Def_BudgetCoreExchange_QSAT2
import Definitions.Def_BudgetCoreExchange_gadget
Formal statement
namespace BudgetCoreExchange

/-- **Lemma 2** (Bichler–Waldherr, arXiv:1807.08253v1, Appendix A.4, p.32): "In an
nW-equilibrium, for each i = 1,...,n, buyer Bᴷᵢ obtains one of the items χ¹ᵢ or χ̄¹ᵢ, buyer Bᴹᵢ
obtains the other item and both pay V to Sχᵢ."

For every DNF formula `ϕ`, all admissible constants (p.29), every `nW`-equilibrium `o` of `CEx_ϕ`
and every `i`: either `χᵢ` is in the package of `Bᴷᵢ` and `χ̄ᵢ` in that of `Bᴹᵢ`, or the other way
round; and the seller `Sχᵢ` receives at least `2V`.

**Formalization Note.** "χ¹ᵢ, χ̄¹ᵢ" is read as `χᵢ, χ̄ᵢ` (there are no items `χ¹ᵢ`). In (CEx) each
agent has one payment and budget balance is aggregate, so "both pay V to Sχᵢ" is read as the
receipt `q(Sχᵢ) ≥ 2V`, the bound the proof establishes ("If either Bᴷᵢ or Bᴹᵢ would pay less than
V, then either Bχ,1ᵢ or Bχ,2ᵢ could outbid them"). -/
theorem lemma_2 (ϕ : DNF) (T U V W : ℝ) (hA : Admissible ϕ T U V W)
    (o : Outcome (GBuyer ϕ) (GSeller ϕ) (GItem ϕ)) (ho : IsNWEquilibrium ϕ T U V W o)
    (i : Fin ϕ.n) :
    ((Gadget.chi i ∈ o.S (Gadget.BK i) ∧ Gadget.chiBar i ∈ o.S (Gadget.BM i)) ∨
      (Gadget.chiBar i ∈ o.S (Gadget.BK i) ∧ Gadget.chi i ∈ o.S (Gadget.BM i))) ∧
    2 * V ≤ o.q (Gadget.SChi i) := by sorry

end BudgetCoreExchange
Source
Bichler, Waldherr, arXiv:1807.08253v1, Lemma 2, p.32 (Appendix A.4; announced on p.31)
Human review
  • Endorsed by Shuze Chen · Oct 31, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Oct 31, 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