AFTD Auto-Formalizing Theoretical Domains

not_is_guaranteed_round_robin_ef1_factor_three_fifteen_sixteenths

theoremverified

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

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.

  1. 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.

    line 4

    uses not_is_guaranteed_round_robin_ef1_factor_three_of_three_quarters_lt

      apply not_is_guaranteed_round_robin_ef1_factor_three_of_three_quarters_lt
  2. The inequality 3/4 < 15/16 holds. automation

    The numerical inequality between rational numbers (12/16 < 15/16) is discharged by arithmetic evaluation.

    line 5

      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

/-- 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
See it in the graphDiscuss this resultChallenge it