AFTD Auto-Formalizing Theoretical Domains

round_robin_pne_not_ef1_three_agents_eight_goods

theoremverifiedformalization

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

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.

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

    lines 1–8

    uses Equiv.refl

    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 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⟩
    
  2. 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}.

    lines 10–13

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

    lines 16–22

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

    lines 33–37

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

    lines 38–44

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

    lines 45–49

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

    lines 50–53

        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.

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

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