round_robin_pne_not_ef1_three_agents_eight_goods
There is an instance with 3 agents, 8 goods and strictly positive additive valuations, and a pure Nash equilibrium of the Round-Robin mechanism (sequence 1,2,3,1,2,3,1,2) whose outcome is not EF1. Witness: goods a,b,c,x,y,z,p,q; agents 1 and 3 value every good 1, agent 2 values a,b,c at 8, x,y,z at 5 and p,q at 2; reports a>b>c>x>y>z>p>q, x>y>z>a>b>c>p>q and p>x>y>q>z>a>b>c.
Statement
theorem round_robin_pne_not_ef1_three_agents_eight_goods :
∃ (w : Fin 3 → Fin 8 → ℝ) (rank : Fin 3 → Fin 8 ≃ Fin 8),
(∀ i g, 0 < w i g) ∧
is_picking_sequence_pne
(SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation ⟨w⟩)
(round_robin_sequence 3 8) rank ∧
¬ SocialChoice.FairDivision.Indivisible.IsEF1
(SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation ⟨w⟩)
(picking_sequence_outcome (round_robin_sequence 3 8) rank)- Formalizes
- arXiv:2610.23686 (Revisiting the Fairness of Pure Nash Equilibria of Round-Robin), Proposition 1; goods a,b,c,x,y,z,p,q are 0..7 and agents 1,2,3 are 0,1,2.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 10
- is_picking_sequence_pneA profile of reported strict rankings is a pure Nash equilibrium of the picking-sequence mechanism if no agent can obtain a bundle of…
- picking_sequence_outcomeThe allocation returned by the picking-sequence mechanism PS_π: agents act in the order seq, and at each turn the active agent takes its…
- round_robin_sequenceThe Round-Robin picking sequence (1, 2, ..., n, 1, 2, ...) of length m, with agents numbered 0, ..., n-1.
- SocialChoice.FairDivision.Indivisible.ValuationAn abstract valuation assigns a real value to each agent-bundle pair.
val i Sis the value agentiassigns to bundleS. Lives in… - SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuationLift an additive valuation to an abstract
Valuation.(w.toValuation).val i S = Σ_{g ∈ S} w.weight i g. - SocialChoice.FairDivision.Indivisible.AdditiveValuationAn additive valuation is determined by per-item weights.
weight i gis the value agentiassigns to goodgindividually. The bundle… - SocialChoice.FairDivision.Indivisible.IsEF1Envy-free up to one good (EF1): for any envied bundle, removing *some* item from it eliminates the envy.…
- picking_sequence_outcome_update_memWhatever ranking r agent i reports, its bundle is the bundle of agent i in one of the runs of picking_runs_any: a finite set of candidate…
- picking_runs_anyThe final states of a picking-sequence run in which agent i may take any available good at its turns while every other agent follows its…
- g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
The proof, explained
The theorem constructs an explicit 3-agent, 8-good fair division instance where agents 0 and 2 value all goods at 1, while agent 1 values goods {0,1,2} at 8, goods {3,4,5} at 5, and goods {6,7} at 2. Under the specified reported rankings, the round-robin mechanism assigns goods {0,1,2} to agent 0, {3,4,5} to agent 1, and {6,7} to agent 2; an exhaustive simulation of all unilateral deviations verifies that this profile is a pure Nash equilibrium. Finally, the allocation violates EF1 because agent 1 values their own bundle at 15 but values agent 0's bundle at 16 even after removing any single good.
The valuations and ranking profile for the 3 agents and 8 goods are defined, with the rankings verified to be permutations.
We define weights rr_pne_example_weight such that agent 1 values goods {0, 1, 2} at 8, goods {3, 4, 5} at 5, and goods {6, 7} at 2, while agents 0 and 2 value all goods at 1. The ranking profile rr_pne_example_rank gives agent 0 the identity ranking via Equiv.refl, and gives agents 1 and 2 explicit permutations whose inverses are verified by finite table evaluation using decide.
uses
Equiv.refldef rr_pne_example_weight : Fin 3 → Fin 8 → ℕ := fun i g => if i = 1 then ![8, 8, 8, 5, 5, 5, 2, 2] g else 1 def rr_pne_example_rank : Fin 3 → Fin 8 ≃ Fin 8 | 0 => Equiv.refl _ | 1 => ⟨![3, 4, 5, 0, 1, 2, 6, 7], ![3, 4, 5, 0, 1, 2, 6, 7], by decide, by decide⟩ | 2 => ⟨![6, 3, 4, 7, 5, 0, 1, 2], ![5, 6, 7, 1, 2, 4, 0, 3], by decide, by decide⟩
The round-robin picking sequence under this ranking profile produces the allocation ({0, 1, 2}, {3, 4, 5}, {6, 7}). automation
The round-robin sequence (0, 1, 2, 0, 1, 2, 0, 1) is evaluated turn by turn: at each turn, the designated agent takes their most preferred good among those still available according to their reported ranking. Lean's kernel computation (decide +kernel) executes this simulation to establish that agent 0 receives {0, 1, 2}, agent 1 receives {3, 4, 5}, and agent 2 receives {6, 7}.
theorem rr_pne_example_outcome : picking_sequence_outcome (round_robin_sequence 3 8) rr_pne_example_rank = ![{0, 1, 2}, {3, 4, 5}, {6, 7}] := by decide +kernel
No agent can obtain a bundle of strictly greater total weight by any sequence of picks against the other agents' fixed rankings. automation
The function picking_runs_any explores all possible bundles an agent could obtain by making arbitrary choices at their turns while the remaining agents follow their prescribed rankings. Lean's kernel computation (decide +kernel) exhaustively evaluates all reachable bundles for every agent and verifies that their total weight never exceeds the weight of their assigned bundle in the round-robin outcome.
theorem rr_pne_example_runs_le : ∀ i : Fin 3, ∀ S ∈ (picking_runs_any (List.finRange 8) i (fun a => List.ofFn (rr_pne_example_rank a)) (round_robin_sequence 3 8) (fun _ => ∅, ∅)).map (fun st => st.1 i), ∑ g ∈ S, rr_pne_example_weight i g ≤ ∑ g ∈ picking_sequence_outcome (round_robin_sequence 3 8) rr_pne_example_rank i, rr_pne_example_weight i g := by decide +kernel
The specified candidate weights and ranking profile satisfy the requirement of having strictly positive valuations.
We instantiate the existential witnesses with rr_pne_example_weight (cast to ℝ) and rr_pne_example_rank. For every agent i and good g, the integer weight is 8, 5, 2, or 1, all of which are strictly positive by finite check (decide); casting to ℝ preserves strict positivity.
refine ⟨fun i g => (rr_pne_example_weight i g : ℝ), rr_pne_example_rank, ?_, ?_, ?_⟩ · intro i g have : 0 < rr_pne_example_weight i g := by revert i g; decide show (0 : ℝ) < (rr_pne_example_weight i g : ℝ) exact_mod_cast this
The ranking profile forms a pure Nash equilibrium of the round-robin picking sequence.
For any agent i and any alternative ranking r, picking_sequence_outcome_update_mem shows that the bundle received by agent i under this deviation is an element of the set of reachable bundles generated by picking_runs_any. By rr_pne_example_runs_le, every such bundle has total weight at most that of the outcome bundle. Rewriting the additive valuations into sums of weights and casting from ℕ to ℝ shows that agent i cannot achieve higher value by deviating.
uses
picking_sequence_outcome_update_mem,List.mem_finRange,rr_pne_example_runs_le,Nat.cast_sum· intro i r have hmem := picking_sequence_outcome_update_mem (List.finRange 8) List.mem_finRange (round_robin_sequence 3 8) rr_pne_example_rank i r have key := rr_pne_example_runs_le i _ hmem simp only [SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation] rw [← Nat.cast_sum, ← Nat.cast_sum] exact_mod_cast key
If the outcome allocation were EF1, agent 1 would not envy agent 0 after removing some single good from agent 0's bundle.
Assuming for contradiction that the allocation is EF1, we instantiate the EF1 condition for agent 1 envying agent 0. Since agent 0's bundle {0, 1, 2} is non-empty by rr_pne_example_outcome, there must exist some good g ∈ {0, 1, 2} such that agent 1 values {0, 1, 2} \ {g} at most agent 1's valuation of their own bundle {3, 4, 5}. Unfolding the additive valuations and casting from ℝ to ℕ expresses this inequality in natural numbers.
uses
rr_pne_example_outcome,Nat.cast_sum,Nat.cast_le· intro h obtain ⟨g, hg, hle⟩ := h 1 0 (by decide) (by rw [rr_pne_example_outcome]; decide) simp only [SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation] at hle rw [← Nat.cast_sum, ← Nat.cast_sum, Nat.cast_le, rr_pne_example_outcome] at hle rw [rr_pne_example_outcome] at hg
The EF1 condition fails, completing the proof by contradiction.
Agent 1 values each good in {0, 1, 2} at 8 and each good in {3, 4, 5} at 5. Removing any single good g from {0, 1, 2} leaves two goods of total value 8 + 8 = 16, which strictly exceeds agent 1's bundle value of 5 + 5 + 5 = 15. Since 16 ≤ 15 is false for all g ∈ {0, 1, 2}, exhaustive evaluation (decide) refutes the existence of such a good g, contradicting the EF1 hypothesis.
have : ∀ g ∈ ({0, 1, 2} : Finset (Fin 8)), ¬ (∑ x ∈ ({0, 1, 2} : Finset (Fin 8)) \ {g}, rr_pne_example_weight 1 x ≤ ∑ x ∈ ({3, 4, 5} : Finset (Fin 8)), rr_pne_example_weight 1 x) := by decide exact this g hg hle
Equiv.refl- The identity permutation on any type.
rr_pne_example_outcome- Under the round-robin sequence and the specified ranking profile, the outcome allocation assigns {0, 1, 2} to agent 0, {3, 4, 5} to agent 1, and {6, 7} to agent 2.
rr_pne_example_runs_le- For each agent, every bundle reachable by any deviation against the fixed rankings has sum of weights at most the sum of weights of the outcome bundle.
picking_sequence_outcome_update_mem- For any deviation by an agent, the resulting bundle received by that agent is contained in the set of all reachable bundles computed by picking_runs_any.
List.mem_finRange- Every element of Fin n belongs to the exhaustive list List.finRange n.
Nat.cast_sum- The natural cast of a finite sum of natural numbers to a ring equals the sum of the cast terms.
Nat.cast_le- For natural numbers m and n, their casts to a linearly ordered ring satisfy ↑m ≤ ↑n if and only if m ≤ n.
- Steps 2 and 3 rely on kernel evaluation (`decide +kernel`) with an increased recursion depth limit to simulate the entire round-robin picking sequence and exhaustively check all deviation branches.
- In the Lean formalization, agents and goods use 0-based indexing (`Fin 3` and `Fin 8`). Specifically, agent 1 in Lean corresponds to agent 2 in the informal theorem statement, and agent 0 corresponds to agent 1.
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.
def rr_pne_example_weight : Fin 3 → Fin 8 → ℕ := fun i g => if i = 1 then ![8, 8, 8, 5, 5, 5, 2, 2] g else 1def rr_pne_example_rank : Fin 3 → Fin 8 ≃ Fin 8 | 0 => Equiv.refl _ | 1 => ⟨![3, 4, 5, 0, 1, 2, 6, 7], ![3, 4, 5, 0, 1, 2, 6, 7], by decide, by decide⟩ | 2 => ⟨![6, 3, 4, 7, 5, 0, 1, 2], ![5, 6, 7, 1, 2, 4, 0, 3], by decide, by decide⟩set_option maxRecDepth 100000 intheorem rr_pne_example_outcome : picking_sequence_outcome (round_robin_sequence 3 8) rr_pne_example_rank = ![{0, 1, 2}, {3, 4, 5}, {6, 7}] := by decide +kernelset_option maxRecDepth 100000 intheorem rr_pne_example_runs_le : ∀ i : Fin 3, ∀ S ∈ (picking_runs_any (List.finRange 8) i (fun a => List.ofFn (rr_pne_example_rank a)) (round_robin_sequence 3 8) (fun _ => ∅, ∅)).map (fun st => st.1 i), ∑ g ∈ S, rr_pne_example_weight i g ≤ ∑ g ∈ picking_sequence_outcome (round_robin_sequence 3 8) rr_pne_example_rank i, rr_pne_example_weight i g := by decide +kerneltheorem round_robin_pne_not_ef1_three_agents_eight_goods : ∃ (w : Fin 3 → Fin 8 → ℝ) (rank : Fin 3 → Fin 8 ≃ Fin 8), (∀ i g, 0 < w i g) ∧ is_picking_sequence_pne (SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation ⟨w⟩) (round_robin_sequence 3 8) rank ∧ ¬ SocialChoice.FairDivision.Indivisible.IsEF1 (SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation ⟨w⟩) (picking_sequence_outcome (round_robin_sequence 3 8) rank) := by refine ⟨fun i g => (rr_pne_example_weight i g : ℝ), rr_pne_example_rank, ?_, ?_, ?_⟩ · intro i g have : 0 < rr_pne_example_weight i g := by revert i g; decide show (0 : ℝ) < (rr_pne_example_weight i g : ℝ) exact_mod_cast this · intro i r have hmem := picking_sequence_outcome_update_mem (List.finRange 8) List.mem_finRange (round_robin_sequence 3 8) rr_pne_example_rank i r have key := rr_pne_example_runs_le i _ hmem simp only [SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation] rw [← Nat.cast_sum, ← Nat.cast_sum] exact_mod_cast key · intro h obtain ⟨g, hg, hle⟩ := h 1 0 (by decide) (by rw [rr_pne_example_outcome]; decide) simp only [SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation] at hle rw [← Nat.cast_sum, ← Nat.cast_sum, Nat.cast_le, rr_pne_example_outcome] at hle rw [rr_pne_example_outcome] at hg have : ∀ g ∈ ({0, 1, 2} : Finset (Fin 8)), ¬ (∑ x ∈ ({0, 1, 2} : Finset (Fin 8)) \ {g}, rr_pne_example_weight 1 x ≤ ∑ x ∈ ({3, 4, 5} : Finset (Fin 8)), rr_pne_example_weight 1 x) := by decide exact this g hg hle