Theorem 4.3 — Mod-Cut&Choose has a pure Nash equilibrium, and every one is MMS and EFX
ProvedStrategicAlloc.CutChoose.theorem_4_3Let be any instance with two agents whose additive valuations are non-negative on the goods of , and let be the Mod-Cut&Choose mechanism (Mechanism 2). Then:
- has at least one pure Nash equilibrium: a bid profile such that no agent has a bid with ;
- for every pure Nash equilibrium , the allocation is MMS and EFX with respect to the true valuations:
Here is agent 's maximin share and EFX is Definition 2.1. Although Mod-Cut&Choose is not truthful, and as an algorithm it does not guarantee more than of the maximin share, its equilibria are exactly as fair as one could ask for two agents.
Formalization Note Agents are 0 (agent 1) and 1 (agent 2). Deviations range over all non-negative bid vectors, and fairness is measured with the true valuations , not with the bids. The mechanism sorts goods by agent 1's bid rather than by as the page's line 2 says (a disclosed correction; see the Mod-Cut&Choose definition).
import Mathlib import Definitions.Def_LittleCharity_MMS_Setting import Definitions.Def_StrategicAlloc_CutChoose_Setting import Definitions.Def_StrategicAlloc_CutChoose_ModCutChoose
namespace StrategicAlloc.CutChoose
/-- Theorem 4.3 (p. 18): for every two-agent instance with additive non-negative valuations,
Mod-Cut&Choose has a pure Nash equilibrium, and every pure Nash equilibrium yields an allocation
that is MMS and EFX with respect to the true valuations `v_1, v_2`. -/
theorem theorem_4_3 {m : ℕ} (v : Fin 2 → Fin m → ℝ) (hv : ∀ i g, 0 ≤ v i g) :
(∃ b, StrategicAlloc.RRFair.IsPNE modCutChoose v b) ∧
∀ b, StrategicAlloc.RRFair.IsPNE modCutChoose v b →
IsApproxMMS 1 v (modCutChoose b) ∧ IsEFX v (modCutChoose b) := by sorry
end StrategicAlloc.CutChoose
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.