Theorem A.3 — Round-Robin has a pure Nash equilibrium in every instance with additive valuations
ProvedStrategicAlloc.RRExists.theorem_A_3Let be any instance with agents, goods and additive valuations with non-negative values ; values may be zero and may tie. Then Round-Robin (Mechanism 1, lexicographic tie-breaking of bids) has at least one pure Nash equilibrium:
This extends the existence result of Aziz, Goldberg and Walsh (Theorem A.2), which needs positive values and strict preferences, to general additive valuations. Combined with Theorem 3.3 of the same paper (every PNE of Round-Robin is EF1 with respect to the true valuations), it shows that Round-Robin always has equilibria and that all of them are fair in the EF1 sense.
Formalization Note Agents are Fin n with [NeZero n], goods Fin m. The equilibrium is over bid vectors in with deviations over all such vectors, and the bundle values are the true . No positivity or strictness is assumed: those are exactly what the theorem removes from Theorem A.2.
import Mathlib import Definitions.Def_StrategicAlloc_RRExists_Setting
namespace StrategicAlloc.RRExists
/-- Theorem A.3 (p. 24): for every instance with additive non-negative valuations, Round-Robin
(Mechanism 1, lexicographic tie-breaking) has at least one pure Nash equilibrium. -/
theorem theorem_A_3 {n m : ℕ} [NeZero n] (v : Fin n → Fin m → ℝ) (hv : ∀ i g, 0 ≤ v i g) :
∃ b : Fin n → Fin m → ℝ, StrategicAlloc.RRFair.IsPNE StrategicAlloc.RRFair.roundRobin v b := by sorry
end StrategicAlloc.RRExists
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.