not_is_guaranteed_round_robin_ef1_factor_three_fifteen_sixteenths
15/16 is not a guaranteed EF1 factor for Round-Robin pure Nash equilibria with three agents: there exists an 8-good additive instance whose pure Nash equilibrium outcome is not (15/16)-EF1.
Statement
theorem not_is_guaranteed_round_robin_ef1_factor_three_fifteen_sixteenths :
¬ is_guaranteed_round_robin_ef1_factor 3 (15 / 16)- Source
- arXiv:2610.23686, Prop. 1 and Sec. 6
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- is_guaranteed_round_robin_ef1_factorA factor α is guaranteed for n agents under Round-Robin if for every number of goods m, every nonnegative additive valuation profile w,…
- round_robin_three_agents_pne_not_alpha_ef1_of_three_quarters_ltWith three agents and eight goods, there is an instance with nonnegative additive valuations and a pure Nash equilibrium of Round-Robin…
- not_is_guaranteed_round_robin_ef1_factor_three_of_three_quarters_ltFor three agents, no factor strictly greater than 3/4 is guaranteed for Round-Robin pure Nash equilibria.
Read back from the Lean
The theorem asserts the negation of is_guaranteed_round_robin_ef1_factor 3 (15 / 16).
That is, it is not the case that for 3 agents, every pure Nash equilibrium ranking profile in a round-robin picking game with non-negative additive valuations guarantees an allocation that is $(15/16)$-EF1 (envy-free up to one good with approximation factor $15/16$).
Equivalently, there exists some number of goods $m \in \mathbb{N}$, a profile of non-negative additive valuation weights $w : \mathrm{Fin}\ 3 \to \mathrm{Fin}\ m \to \mathbb{R}$, and a profile of rankings $\mathrm{rank} : \mathrm{Fin}\ 3 \to (\mathrm{Fin}\ m \simeq \mathrm{Fin}\ m)$ such that:
1. $\mathrm{rank}$ is a pure Nash equilibrium of the round-robin picking sequence (no agent $i$ can unilaterally change their reported ranking to obtain a bundle with strictly higher value according to their additive valuation), yet
2. The resulting allocation is not $(15/16)$-EF1: there exist distinct agents $i, j \in \mathrm{Fin}\ 3$ where agent $j$'s allocated bundle $A(j)$ is nonempty, and for all goods $g \in A(j)$, $(15/16) \cdot v_i(A(j) \setminus \{g\}) > v_i(A(i))$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem is established by appealing to a known general impossibility bound, which shows that no approximation factor strictly greater than 3/4 is guaranteed for Round-Robin pure Nash equilibria with three agents. Since 15/16 > 3/4, the claim follows immediately by rational arithmetic.
It suffices to show that 3/4 < 15/16.
By not_is_guaranteed_round_robin_ef1_factor_three_of_three_quarters_lt, no factor α strictly greater than 3/4 is guaranteed to achieve EF1 for three agents under Round-Robin pure Nash equilibria. Specialising this theorem to α = 15/16 reduces the goal to confirming that 3/4 < 15/16.
uses
not_is_guaranteed_round_robin_ef1_factor_three_of_three_quarters_ltapply not_is_guaranteed_round_robin_ef1_factor_three_of_three_quarters_ltThe inequality 3/4 < 15/16 holds. automation
The numerical inequality between rational numbers (12/16 < 15/16) is discharged by arithmetic evaluation.
norm_num
not_is_guaranteed_round_robin_ef1_factor_three_of_three_quarters_lt- For three agents, any factor α > 3/4 is not a guaranteed EF1 factor for Round-Robin pure Nash equilibria.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 15/16 is not a guaranteed EF1 factor for Round-Robin pure Nash equilibria with three agents. -/theorem not_is_guaranteed_round_robin_ef1_factor_three_fifteen_sixteenths : ¬ is_guaranteed_round_robin_ef1_factor 3 (15 / 16) := by apply not_is_guaranteed_round_robin_ef1_factor_three_of_three_quarters_lt norm_num