Pure Nash Equilibria of Round-Robin Eliminate Envy up to One Good Towards Any Agent Appearing at Most Twice
low tier2026-10-19reviewed by Claude Code中文版
Abstract
Does every pure Nash equilibrium of the Round-Robin picking mechanism guarantee envy-freeness up to one good (EF1) when agents have nonnegative additive valuations? While a published claim asserted that all pure Nash equilibria of Round-Robin are EF1, a recent counterexample with three agents and eight goods showed that this general assertion is false. We show that the property survives in part: in any pure Nash equilibrium of the Round-Robin mechanism with nonnegative additive valuations, an agent experiences envy up to at most one good towards any other agent who appears at most twice in the picking sequence. The proof proceeds by analyzing the bundle of the target agent and the partial allocation before the evaluating agent's initial turn. If the target receives at most one item, envy is trivially EF1 by removing that item. If the target receives two items, the number of goods strictly exceeds the number of agents, and at least one item allocated to the target remains unallocated prior to the evaluating agent's initial turn. By deviating to place that unallocated item at the top position of their reported ranking, the evaluating agent secures it; pure Nash equilibrium ensures their equilibrium bundle is worth at least this item, bounding envy towards the target once the other item is removed. This implies that all equilibria with at most $2n$ goods are EF1. These results have been formalized and verified in Lean 4.
1. Introduction
In the fair division of indivisible goods among strategic agents, the Round-Robin mechanism is one of the most prominent protocols. In this mechanism, agents are ordered cyclically and take turns selecting a single remaining item according to their reported preferences. When agents are non-strategic and report their true preferences truthfully, Round-Robin produces an allocation that satisfies envy-freeness up to one good (EF1) under additive valuations: after removing at most one good from any agent's bundle, no other agent envies them.
However, truthful reporting is generally not a dominant strategy in sequential allocation mechanisms. When agents behave strategically, they may misreport their preferences to manipulate the sequence of selections and secure a more preferred bundle. This strategic interaction induces a normal-form game in which each agent submits a strict ranking over the set of goods, and the mechanism allocates items by repeatedly assigning to the active agent their highest-ranked available item. A central question in algorithmic game theory and social choice is whether the desirable fairness properties of Round-Robin survive strategic play. Specifically, does every pure Nash equilibrium (PNE)—a profile of reported rankings from which no agent can strictly increase their true bundle valuation by unilaterally altering their report—guarantee an EF1 allocation?
A published claim in the literature asserted that every pure Nash equilibrium of the Round-Robin mechanism with nonnegative additive valuations produces an EF1 allocation. However, this assertion was recently refuted by a counterexample with three agents and eight goods in which a pure Nash equilibrium fails to satisfy EF1. In that counterexample, the agent who experiences excessive envy envies an agent who picks three items during the sequence.
This refutation left open the question of the exact scope and boundary of fairness in Round-Robin equilibria. Prior work established that when the total number of goods $m$ satisfies $m \le 2n$, every pure Nash equilibrium is indeed EF1, formalized as round_robin_pne_ef1_of_card_le_two_mul. In that restricted regime, the total number of rounds is at most two, so every agent receives at most two turns in the picking sequence. This raises a fundamental structural question: is the failure of EF1 an emergent global defect of equilibria with large numbers of goods, or does the equilibrium condition protect agents pairwise against envy towards specific participants based on their individual turn counts?
This post presents the formalized theorem round_robin_pne_ef1_pair_of_count_le_two, which resolves this question by showing that the published claim survives on an agent-by-agent basis. Specifically, in any pure Nash equilibrium of Round-Robin with nonnegative additive valuations and an arbitrary number of goods $m$, an evaluating agent $i$ is guaranteed to satisfy the EF1 condition towards any target agent $j$ who appears at most twice in the picking sequence.
This result establishes that envy violating the EF1 condition can never be directed towards an agent who picks at most twice, regardless of the total number of goods $m$ or the total number of agents $n$. Any counterexample to EF1 must necessarily feature an envied agent who receives three or more items. The pairwise theorem immediately implies the global EF1 guarantee round_robin_pne_ef1_of_card_le_two_mul when $m \le 2n$, and isolates the precise mechanism needed to analyze the boundary case of $m = 2n + 1$ goods.
2. Preliminaries
We formalize the strategic fair division setting following the Lean definitions in the material. Throughout, let $n$ and $m$ be positive integers representing the number of agents and goods, respectively. In Lean, agents are represented by the finite type $\text{Fin } n$ with a non-zero constraint, and goods are represented by $\text{Fin } m$.
Definition 1 (Valuations and Additive Valuations). An abstract valuation is defined by the structure SocialChoice.FairDivision.Indivisible.Valuation, which consists of a valuation function: $$v : N \to \mathcal{P}(G) \to \mathbb{R}$$ assigning a real value $v_i(S)$ to each agent $i \in N$ and bundle $S \subseteq G$. An additive valuation is defined by the structure SocialChoice.FairDivision.Indivisible.AdditiveValuation, parameterized by per-item weights $w : N \to G \to \mathbb{R}$, where $w(i, g)$ denotes the weight agent $i$ assigns to item $g$. The definition SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation lifts an additive valuation to an abstract valuation via: $$v_i(S) = \sum_{g \in S} w(i, g).$$ The valuation weights are assumed to be non-negative: for all $i \in N$ and $g \in G$, $w(i, g) \ge 0$.
Remark 1. By convention, the empty sum evaluates to zero, so $v_i(\emptyset) = 0$ for every agent $i$. Non-negativity of weights ensures weak monotonicity: if $S \subseteq T \subseteq G$, then $v_i(S) \le v_i(T)$. Valuations are defined for all subsets of $G$, and valuations vary across agents while the item weights $w$ remain fixed throughout the game.
Definition 2 (Picking Turn and Mechanism Outcome). The state of the allocation process is a pair $(A, U) \in (N \to \mathcal{P}(G)) \times \mathcal{P}(G)$, where $A(i)$ is the bundle currently held by agent $i$, and $U = \bigcup_{i \in N} A(i)$ is the set of all items allocated so far. Each turn of the mechanism is governed by picking_turn: given a reported preference list $l \in \text{List } G$, an active agent $i \in N$, and a state $st = (A, U)$, the function searches $l$ for the headmost item $g$ satisfying $g \notin U$. If such an item $g$ exists, the state is updated to $(A[i \mapsto A(i) \cup \{g\}], U \cup \{g\})$; if every item in $l$ is already in $U$, the state remains $st$.
Given a sequence of agent turns $seq \in \text{List } N$ and a reported ranking profile $rank : N \to (\text{Fin } m \simeq G)$, where $rank(i)$ is an equivalence specifying agent $i$'s ranking (index $0$ being the top item), the outcome of the mechanism is defined by picking_sequence_outcome: $$\text{picking\_sequence\_outcome}(seq, rank) = \left( seq.\text{foldl } \left( \lambda st\ a \implies \text{picking\_turn } (\text{List.ofFn } (rank(a)))\ a\ st \right) (\lambda \_ \implies \emptyset, \emptyset) \right).1$$ which returns the final bundle allocation $A : N \to \mathcal{P}(G)$.
Remark 2. The ranking of each agent is formalized as an equivalence $\text{Fin } m \simeq G$, which guarantees that reported rankings are strict permutations of the set of goods. The mechanism operates deterministically by folding picking_turn across $seq$ from the initial state $(\lambda \_ \implies \emptyset, \emptyset)$.
Definition 3 (Round-Robin Picking Sequence). The Round-Robin sequence of length $m$ over $n$ agents is defined by round_robin_sequence: $$\text{round\_robin\_sequence } n\ m = \text{List.ofFn } \left( \lambda (t : \text{Fin } m) \implies \langle t.val \bmod n, \dots \rangle \right).$$ Turn $t \in \{0, 1, \dots, m-1\}$ is assigned to agent $t \bmod n \in \text{Fin } n$.
Remark 3. The picking sequence is completely fixed by the parameters $n$ and $m$. Agents appear in the cyclic order $0, 1, \dots, n-1, 0, 1, \dots$ until all $m$ goods have been assigned turns.
Definition 4 (Pure Nash Equilibrium). A profile of reported strict rankings $rank : N \to (\text{Fin } m \simeq G)$ is a pure Nash equilibrium of the picking-sequence mechanism, denoted is_picking_sequence_pne, if no agent can achieve a bundle of strictly higher true value by unilaterally deviating to another reported ranking. Formally, for all $i \in N$ and all deviations $r : \text{Fin } m \simeq G$: $$v_i(\text{picking\_sequence\_outcome}(seq, rank[i \mapsto r])(i)) \le v_i(\text{picking\_sequence\_outcome}(seq, rank)(i)).$$
Remark 4. The equilibrium condition is stated using a weak inequality on valuations, meaning that agent $i$'s equilibrium bundle weakly dominates any bundle achievable via unilateral deviation. The sequence $seq$ and the opponents' rankings $rank(j)$ for $j \ne i$ are held fixed.
Definition 5 (Envy-Freeness Up to One Good). Given an allocation $A : N \to \mathcal{P}(G)$ and a valuation profile $v$, an agent $i \in N$ is envy-free up to one good (EF1) towards agent $j \in N$ if either $A(j) = \emptyset$ or there exists a good $g \in A(j)$ such that: $$v_i(A(j) \setminus \{g\}) \le v_i(A(i)).$$ The allocation $A$ satisfies EF1, denoted SocialChoice.FairDivision.Indivisible.IsEF1, if this inequality holds for all pairs of agents $i, j \in N$.
Remark 5. When $A(j) = \emptyset$, removing a good is not needed: $v_i(\emptyset) = 0 \le v_i(A(i))$ holds by non-negativity. When $A(j)$ is nonempty, EF1 requires the existence of at least one good $g \in A(j)$ whose elimination removes envy.
3. Main result
The main theorem characterizes the pairwise envy experienced towards any agent who appears at most twice in the Round-Robin sequence.
Theorem 1 (round_robin_pne_ef1_pair_of_count_le_two). Let $n, m \ge 1$ be natural numbers. Let $w : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$ be a matrix of non-negative item weights, and let $v = \text{SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation } \langle w \rangle$ be the associated additive valuation profile. Let $seq = \text{round\_robin\_sequence } n\ m$ be the Round-Robin picking sequence. Let $rank : \text{Fin } n \to \text{Fin } m \simeq \text{Fin } m$ be a reported ranking profile that is a pure Nash equilibrium, satisfying is_picking_sequence_pne $v\ seq\ rank$.
Let $i, j \in \text{Fin } n$ be two distinct agents such that:
1. agent $j$ appears at most twice in the picking sequence: $$seq.\text{count } j \le 2;$$ 2. agent $j$'s allocated bundle $A(j) = \text{picking\_sequence\_outcome}(seq, rank)(j)$ is nonempty.
Then agent $i$ is envy-free up to one good towards agent $j$: there exists an item $g \in A(j)$ such that $$v_i(A(j) \setminus \{g\}) \le v_i(A(i)).$$
In Lean, the theorem statement reads the English assertion by taking $n$ and $m$ as natural numbers with non-zero $n$, item weights $w$ satisfying non-negativity, reported rankings as equivalences, and hypothesis h asserting is_picking_sequence_pne, universally quantifying over distinct agents $i$ and $j$, turn count bound hj : (round_robin_sequence n m).count j ≤ 2, and nonemptiness of $A(j)$, and concluding with the existential assertion that there exists an item in $A(j)$ whose removal eliminates envy.
What further results add:
The pairwise guarantee established in Theorem 1 directly yields the global fairness result for small instances. In any Round-Robin sequence of length $m \le 2n$, each of the $n$ agents appears at most twice, because the sequence consists of at most two complete cycles $(0, 1, \dots, n-1)$. Applying Theorem 1 to all pairs of agents yields:
Corollary 1 (round_robin_pne_ef1_of_card_le_two_mul). Let $n, m \ge 1$ with $m \le 2n$. Let $w : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$ be non-negative item weights and let $rank$ be a pure Nash equilibrium of the Round-Robin mechanism. Then the resulting allocation satisfies SocialChoice.FairDivision.Indivisible.IsEF1: every agent is envy-free up to one good towards every other agent.
Furthermore, Theorem 1 delineates the exact boundary of the known counterexample. That construction demonstrated that a pure Nash equilibrium of Round-Robin can fail to be EF1 with $n = 3$ agents and $m = 8 = 2n + 2$ goods. In that counterexample, the envied agent receives three items. Theorem 1 shows that this feature is necessary: envy violating EF1 can never be directed towards an agent who picks at most two items.
Finally, Theorem 1 serves as the central inductive step for analyzing the intermediate regime $m = 2n + 1$. When $m = 2n + 1$, exactly one agent (agent $0$) appears three times, while every other agent appears at most twice. Theorem 1 immediately guarantees that no agent can experience envy violating EF1 towards any agent $j \in \{1, \dots, n-1\}$, isolating agent $0$ as the sole potential target of excessive envy.
theorem round_robin_pne_ef1_pair_of_count_le_two (n m : ℕ) [NeZero n]
(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)
(i j : Fin n) (hij : i ≠ j) (hj : (round_robin_sequence n m).count j ≤ 2)
(hne : (picking_sequence_outcome (round_robin_sequence n m) rank j).Nonempty) :
∃ g ∈ picking_sequence_outcome (round_robin_sequence n m) rank j,
(SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation ⟨w⟩).val i
(picking_sequence_outcome (round_robin_sequence n m) rank j \ {g}) ≤
(SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation ⟨w⟩).val i
(picking_sequence_outcome (round_robin_sequence n m) rank i)4. Proof
We begin with an overview of the proof idea, followed by the supporting lemmas formalized in Lean, and finally the complete step-by-step argument.
Proof Idea. Let $seq = \text{round\_robin\_sequence } n\ m$, $L(a) = \text{List.ofFn } (rank(a))$, and let $A = \text{picking\_sequence\_outcome}(seq, rank)$ be the final allocation. If $|A(j)| \le 1$, the bundle contains at most one item. Removing this item leaves the empty set, which has value zero. Since item weights are non-negative, agent $i$'s bundle valuation is at least zero, so EF1 holds immediately.
If $|A(j)| > 1$, then since an agent cannot obtain more items than their number of appearances in the picking sequence, and agent $j$ appears at most twice, we must have $|A(j)| = 2$ and $seq.\text{count } j = 2$. This equality forces $n < m$, because if $m \le n$, the sequence has length $m \le n$, and in any prefix of length at most $n$ every agent appears at most once, which would force $seq.\text{count } j \le 1$.
Because $n < m$, agent $i$'s initial turn occurs at index $i.val < n < m$, which lies strictly within the sequence. Let $st_0$ be the intermediate allocation state immediately prior to agent $i$'s initial turn, obtained after the prefix $seq.\text{take } i.val$. In this prefix of length $i.val < n$, agent $j$ appears at most once, so agent $j$ holds at most one item in $st_0$.
Since $|A(j)| = 2$, there exists an item $b \in A(j)$ that agent $j$ does not hold in $st_0$. By the invariant that bundles remain disjoint and expand monotonically throughout the execution, item $b$ cannot be held by any other agent either in $st_0$; hence item $b$ is completely unallocated prior to agent $i$'s initial turn.
Agent $i$ can unilaterally deviate to a reported ranking $r'$ that places item $b$ at position $0$. Because agent $i$ does not appear in the prefix prior to index $i.val$, updating agent $i$'s ranking leaves the execution up to state $st_0$ completely unchanged. At turn $i.val$, agent $i$ acts: since item $b$ is available and placed at position $0$, agent $i$ immediately selects $b$. By monotonicity of allocation accumulation, item $b$ remains in agent $i$'s final bundle under this deviation.
By the pure Nash equilibrium condition, agent $i$'s equilibrium valuation $v_i(A(i))$ must be at least their valuation under this deviation, which is at least $w(i, b)$ by non-negativity of weights. Finally, since $|A(j)| = 2$ and $b \in A(j)$, there is another item $a \in A(j)$ distinct from $b$. Removing $a$ leaves the singleton $A(j) \setminus \{a\} = \{b\}$, whose value to agent $i$ is exactly $w(i, b) \le v_i(A(i))$. This establishes EF1.
Supporting Lemmas. The argument rests on six structural lemmas:
Lemma 1 (Non-negativity of Bundle Valuations). For any agent $i \in \text{Fin } n$ and any subset $S \subseteq \text{Fin } m$, $$0 \le \sum_{g \in S} w(i, g) = v_i(S).$$ Lean settles this by summing non-negative weights over the finite set $S$.
Lemma 2 (Bundle Size Bounded by Appearance Count). In any picking sequence execution starting from an initial state $(A_{init}, U_{init})$, for any agent $k$, the number of items added to $k$'s bundle during a sequence $seq$ is at most $seq.\text{count } k$: $$|A(k)| \le |A_{init}(k)| + seq.\text{count } k.$$ In particular, starting from the empty initial state $init = (\lambda \_ \implies \emptyset, \emptyset)$, the final bundle satisfies $|A(k)| \le seq.\text{count } k$. Lean settles this by induction on the sequence using the turn-count bound for folds.
Lemma 3 (Appearance Count in Prefixes of Length at Most $n$). Let $n, m \ge 1$ and $seq = \text{round\_robin\_sequence } n\ m$. For any prefix length $k \le n$ and any agent $k' \in \text{Fin } n$, $$(seq.\text{take } k).\text{count } k' \le 1.$$ Proof: The prefix of length $k \le n$ consists of turns $t \in \{0, \dots, k-1\}$. At each turn $t$, the assigned agent is $t \bmod n$. Since $t < k \le n$, $t \bmod n = t$. The sequence of turns is $[0, 1, \dots, k-1]$, which contains pairwise distinct elements. Hence any agent $k'$ appears at most once in this prefix. Lean settles this by the property that indices in the initial block are distinct modulo $n$.
Lemma 4 (Mechanism Invariants and Monotonicity). The mechanism state $st = (A, U)$ satisfies an invariant asserting that:
- for all agents $a$, $A(a) \subseteq U$;
- for all items $g \in U$, there exists an agent $a$ such that $g \in A(a)$;
- for all distinct agents $a \ne b$, $A(a) \cap A(b) = \emptyset$.
The empty initial state $init$ satisfies this invariant. The invariant is preserved by each application of picking_turn and by fold operations over sequences. Furthermore, allocations grow monotonically: for any sequence and intermediate state, each agent's bundle at the intermediate state is a subset of their bundle at the final state.
Lemma 5 (Prefix Invariance Under Unilateral Deviation). Let $seq_1 \in \text{List } (\text{Fin } n)$ be a prefix of the sequence in which agent $i$ does not appear. For any deviation $r' : \text{Fin } m \simeq \text{Fin } m$, folding picking_turn across $seq_1$ under the updated ranking profile $rank[i \mapsto r']$ yields the identical intermediate state as under $rank$. Lean settles this by observing that the preference list of agent $i$ is never queried on turns assigned to other agents.
Lemma 6 (Two-Element Difference is a Singleton). If $S$ is a finite set with $|S| \le 2$ and $a, b \in S$ are distinct elements, then $S \setminus \{a\} = \{b\}$. Proof: Clearly $b \in S \setminus \{a\}$ because $b \in S$ and $b \ne a$. If there existed any element $x \in S \setminus \{a\}$ with $x \ne b$, then $\{a, b, x\}$ would be a subset of $S$ containing three distinct elements, implying $|S| \ge 3$, which contradicts $|S| \le 2$. Lean settles this by verifying the subset inclusions and cardinality constraints.
Step-by-Step Proof of Theorem 1. We now combine these lemmas following the formalized proof of round_robin_pne_ef1_pair_of_count_le_two.
Let $seq = \text{round\_robin\_sequence } n\ m$, $L(a) = \text{List.ofFn } (rank(a))$, and $init = (\lambda \_ \implies \emptyset, \emptyset)$. Let $A(a) = \text{picking\_sequence\_outcome}(seq, rank)(a)$. By Lemma 1, for any set $S \subseteq \text{Fin } m$, $v_i(S) \ge 0$.
Case 1: $|A(j)| \le 1$. Since $A(j)$ is nonempty by hypothesis hne, there exists an element $g \in A(j)$. Because $|A(j)| \le 1$, removing $g$ leaves $A(j) \setminus \{g\} = \emptyset$. The valuation of the empty set is $v_i(\emptyset) = 0$. By Lemma 1, $0 \le v_i(A(i))$. Therefore $v_i(A(j) \setminus \{g\}) \le v_i(A(i))$, which proves the claim for Case 1.
Case 2: $|A(j)| > 1$. We have $|A(j)| \ge 2$. By Lemma 2, $|A(j)| \le seq.\text{count } j$. Since $seq.\text{count } j \le 2$ by hypothesis hj, we obtain: $$2 \le |A(j)| \le seq.\text{count } j \le 2,$$ which forces $|A(j)| = 2$ and $seq.\text{count } j = 2$.
We establish $n < m$. Suppose for contradiction that $m \le n$. Then the length of $seq$, which is $m$, is at most $n$. By Lemma 3 with $k = m \le n$, we have: $$seq.\text{count } j = (seq.\text{take } m).\text{count } j \le 1,$$ which contradicts $seq.\text{count } j = 2$. Thus $n < m$.
Since $n < m$, agent $i$'s index satisfies $i.val < n < m = seq.\text{length}$. We decompose the sequence into: $$seq = seq.\text{take } i.val ++ (seq[i.val] :: seq.\text{drop } (i.val + 1)).$$ By definition of the sequence, the agent acting at index $i.val$ is $i.val \bmod n = i$.
Let $st_0$ be the intermediate state after the prefix $seq.\text{take } i.val$: $$st_0 = (seq.\text{take } i.val).\text{foldl } (\lambda st\ a \implies \text{picking\_turn } (L(a))\ a\ st)\ init.$$ Because $i.val < n$, Lemma 3 implies that $(seq.\text{take } i.val).\text{count } j \le 1$. Applying Lemma 2 to this prefix yields $|st_0.1(j)| \le 1$.
By Lemma 4 (monotonicity), intermediate allocations are subsets of final allocations: $st_0.1(a) \subseteq A(a)$ for every agent $a$. Since $|A(j)| = 2$ and $|st_0.1(j)| \le 1$, there exists an item $b \in A(j)$ such that $b \notin st_0.1(j)$.
We show that item $b$ is completely unallocated at state $st_0$, meaning $b \notin st_0.2$. Suppose for contradiction that $b \in st_0.2$. By Lemma 4, the allocation invariant holds at $st_0$, so there exists an agent $a$ such that $b \in st_0.1(a)$. If $a = j$, this contradicts $b \notin st_0.1(j)$. If $a \ne j$, then by monotonicity $b \in st_0.1(a) \subseteq A(a)$. But $b \in A(j)$, which implies $b \in A(a) \cap A(j)$. However, the final invariant ensures that $A(a)$ and $A(j)$ are disjoint, yielding a contradiction. Therefore $b \notin st_0.2$.
Now consider the unilateral deviation for agent $i$. Since $m > n \ge 1$, we have $m > 0$. Let $r' : \text{Fin } m \simeq \text{Fin } m$ be the permutation that swaps index $0$ with item $b$. Thus $r'(0) = b$.
In the prefix $seq.\text{take } i.val$, every turn $t < i.val < n$ is assigned to agent $t \bmod n = t \ne i.val$. Hence agent $i$ does not appear in $seq.\text{take } i.val$. By Lemma 5, running the sequence under $rank[i \mapsto r']$ up to index $i.val$ results in the identical intermediate state $st_0$.
At index $i.val$, agent $i$ acts. In picking_turn, the preference list has $r'(0) = b$ at its head. Since $b \notin st_0.2$, the linear search finds $b$ at position $0$. Agent $i$ receives item $b$, updating their bundle to $st_0.1(i) \cup \{b\}$. By monotonicity applied to the remaining suffix $seq.\text{drop } (i.val + 1)$, item $b$ remains in agent $i$'s bundle in the final outcome under deviation $r'$: $$b \in \text{picking\_sequence\_outcome}(seq, rank[i \mapsto r'])(i).$$
By Lemma 1 and non-negativity of weights, the single item $b$ is bounded by the total value of the deviated bundle: $$w(i, b) \le v_i(\text{picking\_sequence\_outcome}(seq, rank[i \mapsto r'])(i)).$$ By the pure Nash equilibrium hypothesis $h$ (is_picking_sequence_pne), agent $i$'s equilibrium bundle weakly dominates the deviated bundle: $$v_i(\text{picking\_sequence\_outcome}(seq, rank[i \mapsto r'])(i)) \le v_i(A(i)).$$ Combining these inequalities gives $w(i, b) \le v_i(A(i))$.
Finally, since $|A(j)| = 2$ and $b \in A(j)$, there exists an item $a \in A(j)$ with $a \ne b$. By Lemma 6, $A(j) \setminus \{a\} = \{b\}$. The valuation of this reduced bundle is: $$v_i(A(j) \setminus \{a\}) = v_i(\{b\}) = w(i, b).$$ Since $w(i, b) \le v_i(A(i))$, we conclude that $v_i(A(j) \setminus \{a\}) \le v_i(A(i))$. This proves the existence of an item $a \in A(j)$ satisfying the EF1 condition, completing the proof of Theorem 1.
5. Discussion
The result round_robin_pne_ef1_pair_of_count_le_two establishes that in any pure Nash equilibrium of the Round-Robin mechanism with nonnegative additive valuations, an agent's envy towards any participant who picks at most twice is always bounded by EF1. This isolates the precise structural condition under which the published claim of universal EF1 fairness remains valid.
Relation to the Published Claim and the Refutation. The published literature previously asserted that all pure Nash equilibria of Round-Robin are EF1 under additive valuations. This assertion was refuted by a recent construction of an equilibrium counterexample with three agents and eight goods that violates EF1. In that counterexample, the envied agent receives three goods. Theorem 1 shows that this feature is unavoidable: no counterexample can exist in which the envied agent receives two or fewer goods.
Furthermore, when the total number of goods satisfies $m \le 2n$, the Round-Robin sequence consists of at most two complete cycles, ensuring that every agent appears at most twice. Thus, Theorem 1 immediately implies round_robin_pne_ef1_of_card_le_two_mul, establishing that every pure Nash equilibrium with $m \le 2n$ goods is globally EF1.
What the Result Does Not Cover. Theorem 1 does not cover pairs of agents $(i, j)$ where the target agent $j$ appears three or more times in the sequence. For such agents, the proof technique encounters an essential barrier: when $|A(j)| \ge 3$, agent $j$ holds at least two items, and removing a single item $a \in A(j)$ does not reduce the residual bundle to a singleton $\{b\}$. Consequently, deviating to capture a single unallocated item $b$ is no longer sufficient to upper-bound the value of $A(j) \setminus \{a\}$. The known counterexample confirms that this barrier is mathematical, not merely proof-technical: when an agent receives three or more goods, equilibria can indeed produce envy that exceeds EF1.
The Boundary Case and Next Questions. Between the confirmed EF1 regime ($m \le 2n$) and the eight goods of the three-agent counterexample lies the boundary case of $m = 2n + 1$ goods; for $n \ge 4$ no counterexample with $2n + 2$ goods is known. In a Round-Robin sequence of length $2n + 1$, agent $0$ appears three times (at turns $0$, $n$, and $2n$), while every other agent $j \in \{1, \dots, n-1\}$ appears exactly twice.
Theorem 1 applies directly to all targets $j \ge 1$, guaranteeing that no agent envies any agent $j \in \{1, \dots, n-1\}$ by more than one good. Therefore, in the $m = 2n + 1$ regime, excessive envy can only ever be directed towards agent $0$. This reduces the global EF1 question for the $2n + 1$ goods setting entirely to analyzing envy towards agent $0$. That question has since been settled: every pure Nash equilibrium with at most $2n + 1$ goods is EF1 (round_robin_pne_ef1_of_card_le_two_mul_add_one, posted on 26 October 2026).
Beyond the Round-Robin protocol, a natural question is whether analogous turn-count bounds govern pure Nash equilibria in other sequential picking mechanisms, such as the snake draft or arbitrary picking sequences.
Why it is research-level
- Shows the published claim corrected by arXiv:2610.23686 survives in part: at every Round-Robin pure Nash equilibrium, envy towards any agent with at most two goods is already EF1, for any number of agents (so every equilibrium with at most 2n goods is EF1, while the paper's counterexample has three agents and eight goods)
Lean declarations
- 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…
- 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…
- picking_turnOne turn of a picking-sequence mechanism: the active agent i receives the first good of its reported ranking l (best first) that is not…
- 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.
- 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…
Each one elaborated against Mathlib, and #print axioms returned
nothing outside Classical.choice · Quot.sound · propext.
Drafted by gemini-3.8-flash from the knowledgebase, checked against it, and reviewed by Claude Code. Only the Lean is verified; the prose is a reading of it.