round_robin_pne_ef1_of_card_le_two_mul_add_one
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
- 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.IsEF1Envy-free up to one good (EF1): for any envied bundle, removing *some* item from it eliminates the envy.…
- SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuationLift an additive valuation to an abstract
Valuation.(w.toValuation).val i S = Σ_{g ∈ S} w.weight i g. - round_robin_pne_ef1_of_card_le_two_mulWith n agents and at most 2n goods (every agent picks at most twice), every pure Nash equilibrium of Round-Robin, for nonnegative additive…
- round_robin_three_agents_seven_goods_pne_ef1With three agents and seven goods, every pure Nash equilibrium of Round-Robin (nonnegative additive valuations) is EF1; so the eight-good…
- round_robin_pne_envy_zero_ef1_of_two_mul_add_oneWith n agents and 2n + 1 goods, in every pure Nash equilibrium of Round-Robin (nonnegative additive valuations) every agent i ≠ 0 is EF1…
- round_robin_sequence_count_le_two_of_ne_zeroIn the Round-Robin sequence of n agents and 2n + 1 goods, every agent other than agent 0 picks at most twice.
- round_robin_pne_ef1_pair_of_count_le_twoIn a pure Nash equilibrium of Round-Robin (nonnegative additive valuations), every agent i is EF1 towards every other agent j that appears…
- 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.ValuationAn abstract valuation assigns a real value to each agent-bundle pair.
val i Sis the value agentiassigns to bundleS. Lives in…
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.
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.
uses
round_robin_pne_ef1_of_card_le_two_mulby_cases hm0 : m ≤ 2*n · exact round_robin_pne_ef1_of_card_le_two_mul n m hm0 w hw rank h
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.
have hme : m = 2*n+1 := by omega subst m
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.
intro i j hij hnonemptyIf 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.
uses
round_robin_pne_envy_zero_ef1_of_two_mul_add_oneby_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
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.
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
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.
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