AFTD Auto-Formalizing Theoretical Domains

round_robin_pne_ef1_of_card_le_two_mul_add_one

theoremverifiedoriginal

With n agents and at most 2n + 1 goods, every pure Nash equilibrium of Round-Robin (nonnegative additive valuations) is EF1. For three agents this is tight: arXiv:2610.23686 Proposition 1 has a non-EF1 equilibrium with eight goods. Whether 2n + 2 goods can break EF1 for every n >= 4 is open.

Statement

theorem round_robin_pne_ef1_of_card_le_two_mul_add_one (n m : ℕ) [NeZero n] (hm : m ≤ 2 * n + 1)
    (w : Fin n → Fin m → ℝ) (hw : ∀ i g, 0 ≤ w i g) (rank : Fin n → Fin m ≃ Fin m)
    (h : is_picking_sequence_pne
      (SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation ⟨w⟩)
      (round_robin_sequence n m) rank) :
    SocialChoice.FairDivision.Indivisible.IsEF1
      (SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation ⟨w⟩)
      (picking_sequence_outcome (round_robin_sequence n m) rank)
Related work
Posed from arXiv:2610.23686 (Proposition 1 and the two-agent theorem); the bound 2n + 1 for every n is new, and it is tight for n = 3 only, by the paper's eight-good instance.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 12

Read back from the Lean

Let $n$ and $m$ be natural numbers with $n \ne 0$, and suppose $m \le 2n + 1$. Let $w : \mathrm{Fin}\ n \to \mathrm{Fin}\ m \to \mathbb{R}$ be a non-negative valuation weight function (i.e., $w(i, g) \ge 0$ for all agents $i$ and items $g$), and let $\mathrm{rank} : \mathrm{Fin}\ n \to (\mathrm{Fin}\ m \simeq \mathrm{Fin}\ m)$ be a profile of rankings (permutations of the $m$ items) for each agent. Assume that $\mathrm{rank}$ is a pure Nash equilibrium (PNE) of the picking sequence game on the round-robin sequence of length $m$ with $n$ agents (where the $t$-th pick is given to agent $t \bmod n$) under the additive valuations induced by $w$; that is, no agent $i$ can unilaterally deviate to another permutation $r$ and achieve a strictly higher valuation for their resulting bundle. Then, the final allocation produced by this round-robin picking sequence under $\mathrm{rank}$ is envy-free up to one good (EF1) with respect to the additive valuations induced by $w$.

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 proof proceeds by case analysis on the number of goods m ≤ 2n + 1. If m ≤ 2n, the outcome is EF1 by an existing result for at most 2n goods. If m = 2n + 1, agent 0 is the only agent to receive three items while every other agent receives at most two items; EF1 towards agent 0 is settled by a specialized lemma, and EF1 towards any other agent follows from the fact that agents who pick at most two items cannot be envied beyond one item.

  1. The theorem holds if the number of goods satisfies m ≤ 2n.

    We split on whether m ≤ 2n. When this holds, the allocation is EF1 directly by the previously proved theorem round_robin_pne_ef1_of_card_le_two_mul.

    lines 9–10

    uses round_robin_pne_ef1_of_card_le_two_mul

      by_cases hm0 : m ≤ 2*n
      · exact round_robin_pne_ef1_of_card_le_two_mul n m hm0 w hw rank h
  2. In the remaining case, the number of goods is exactly m = 2n + 1.

    Since m ≤ 2n + 1 by assumption and m > 2n from the case condition, linear integer arithmetic determines that m = 2n + 1. We substitute 2n + 1 for m throughout the remaining goal.

    lines 11–12

      have hme : m = 2*n+1 := by omega
      subst m
  3. To show EF1, it suffices to show that any agent i does not envy any agent j with a nonempty bundle beyond one good.

    We unpack the definition of EF1 (IsEF1) by introducing distinct agents i and j, along with the assumption that agent j received at least one item.

    line 13

      intro i j hij hnonempty
  4. If j = 0, agent i does not envy agent 0 beyond one good.

    We split on whether j = 0. When j = 0, agent 0 receives three items in total, which is handled specifically by round_robin_pne_envy_zero_ef1_of_two_mul_add_one to show that removing some item from agent 0's bundle eliminates i's envy.

    lines 14–16

    uses round_robin_pne_envy_zero_ef1_of_two_mul_add_one

      by_cases hj : j = 0
      · subst j
        exact round_robin_pne_envy_zero_ef1_of_two_mul_add_one n w hw rank h i hij
  5. If j ≠ 0, agent i does not envy agent j beyond one good.

    When j ≠ 0, agent j appears at most twice in the round-robin sequence of length 2n + 1 (by round_robin_sequence_count_le_two_of_ne_zero). By round_robin_pne_ef1_pair_of_count_le_two, any agent allocated at most two items can never be envied beyond one good by another agent at an equilibrium.

    lines 17–18

    uses round_robin_pne_ef1_pair_of_count_le_two, round_robin_sequence_count_le_two_of_ne_zero

      · exact round_robin_pne_ef1_pair_of_count_le_two n (2*n+1) w hw rank h i j hij
          (round_robin_sequence_count_le_two_of_ne_zero n j hj) hnonempty
round_robin_pne_ef1_of_card_le_two_mul
In the Round-Robin protocol with at most 2n goods, every pure Nash equilibrium allocation is EF1 (envy-free up to one good).
round_robin_pne_envy_zero_ef1_of_two_mul_add_one
In the Round-Robin protocol with 2n + 1 goods, every pure Nash equilibrium allocation satisfies EF1 from any agent i ≠ 0 towards agent 0.
round_robin_pne_ef1_pair_of_count_le_two
In the Round-Robin protocol, at any pure Nash equilibrium, any agent j who receives at most two items is not envied beyond one good by any other agent i.
round_robin_sequence_count_le_two_of_ne_zero
In a round-robin sequence of 2n + 1 items among n agents, every agent j other than agent 0 appears at most twice.

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

theorem round_robin_pne_ef1_of_card_le_two_mul_add_one (n m : ℕ) [NeZero n] (hm : m ≤ 2 * n + 1)    (w : Fin n → Fin m → ℝ) (hw : ∀ i g, 0 ≤ w i g) (rank : Fin n → Fin m ≃ Fin m)    (h : is_picking_sequence_pne      (SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation ⟨w⟩)      (round_robin_sequence n m) rank) :    SocialChoice.FairDivision.Indivisible.IsEF1      (SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation ⟨w⟩)      (picking_sequence_outcome (round_robin_sequence n m) rank) := by  by_cases hm0 : m ≤ 2*n  · exact round_robin_pne_ef1_of_card_le_two_mul n m hm0 w hw rank h  have hme : m = 2*n+1 := by omega  subst m  intro i j hij hnonempty  by_cases hj : j = 0  · subst j    exact round_robin_pne_envy_zero_ef1_of_two_mul_add_one n w hw rank h i hij  · exact round_robin_pne_ef1_pair_of_count_le_two n (2*n+1) w hw rank h i j hij      (round_robin_sequence_count_le_two_of_ne_zero n j hj) hnonempty
See it in the graphDiscuss this resultChallenge it