Lemma 1: in an -equilibrium every obtains a bundle it values at
ProvedBudgetCoreExchange.lemma_1combinatorial-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 or for some clause .
This is Lemma 1 of the paper, one of the steps showing that an -equilibrium encodes a truth assignment of (Theorem 4).
Differences from the source:
- 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 1** (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 bundles he values at W."
For every DNF formula `ϕ`, all admissible constants `T, U, V, W` (p.29), every `nW`-equilibrium
`o` of `CEx_ϕ` and every `i`, the package of `Bᴷᵢ` contains `K_l = {χᵢ} ∪ T^{ψ,φ}_{li}` or
`K̄_l = {χ̄ᵢ} ∪ T^{ψ,φ}_{li}` for some clause `l`.
**Formalization Note.** "Obtains a bundle" means the bundle is contained in the package the buyer
receives (free disposal); this is the same as the buyer's value being `W`. -/
theorem lemma_1 (ϕ : 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) :
∃ l : Fin ϕ.numTerms,
Gadget.Kb l i ⊆ o.S (Gadget.BK i) ∨ Gadget.Kbar l i ⊆ o.S (Gadget.BK i) := by sorry
end BudgetCoreExchange
Source
Bichler, Waldherr, arXiv:1807.08253v1, Lemma 1, 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.