Lemma 3: in an -equilibrium obtains or
ProvedBudgetCoreExchange.lemma_3combinatorial-exchangecorep2o-gran-per-chapterp2o-plan-paperp2o-v1reduction
Let be a DNF formula with -variables, -variables and terms, let be admissible constants (, , , , ), and let be an -equilibrium of the exchange , i.e. a core outcome with welfare at least . Then for every the package of contains one of his bundles
This is Lemma 3 of the paper, one of the steps showing that an -equilibrium encodes a truth assignment of (Theorem 4).
Differences from the source:
- reading: 'obtains all his required items from sellers Sψ and Sλ' → the package of Bᴹᵢ contains Mᵢ or M̄ᵢ; reason: the required items are those of the bundle he values (p.30); the χ-item it contains is the one Lemma 2 gives him, so this is the same claim
- 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 3** (Bichler–Waldherr, arXiv:1807.08253v1, Appendix A.4, p.32): "In an
nW-equilibrium, for i = 1,...,n buyer Bᴹᵢ obtains all his required items from sellers Sψ and Sλ."
For every DNF formula `ϕ`, all admissible constants (p.29), every `nW`-equilibrium `o` of `CEx_ϕ`
and every `i`, the package of `Bᴹᵢ` contains one of his bundles
`Mᵢ = {χᵢ, λ¹ᵢ, λ²ᵢ} ∪ ⋃_{xᵢ ∈ C_l} F^ψ_{li}` or `M̄ᵢ = {χ̄ᵢ, λ̄¹ᵢ, λ̄²ᵢ} ∪ ⋃_{x̄ᵢ ∈ C_l} F^ψ_{li}`.
**Formalization Note.** "All his required items" are the items of one of the two bundles `Bᴹᵢ`
values (p.30); with Lemma 2, it is the one whose `χ`-item is not held by `Bᴷᵢ`. -/
theorem lemma_3 (ϕ : 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.Mb i ⊆ o.S (Gadget.BM i) ∨ Gadget.Mbar i ⊆ o.S (Gadget.BM i) := by sorry
end BudgetCoreExchange
Source
Bichler, Waldherr, arXiv:1807.08253v1, Lemma 3, p.32 (Appendix A.4; announced on p.31)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.