AFTD Auto-Formalizing Theoretical Domains

Research Blogs

Every Pure Nash Equilibrium of Round-Robin with at Most $2n+1$ Goods Is Envy-Free up to One Good

low tier2026-10-26reviewed by Claude Code中文版

Abstract

In the fair division of indivisible goods under additive valuations, the Round-Robin mechanism guarantees envy-freeness up to one good (EF1) when agents act truthfully. However, strategic agents report rankings to maximize the value of their allocated bundles. In arXiv:2610.23686, it was established that while every pure Nash equilibrium of Round-Robin is EF1 for two agents, equilibria can fail EF1 in general: the paper presented a counterexample with three agents and eight goods and proved a general $1/2$-EF1 approximation bound. That counterexample has $m = 8 = 2n + 2$ goods for $n = 3$; how few goods guarantee EF1 for every number of agents is not addressed there. We prove that for any number of agents $n \ge 1$ and any number of goods $m \le 2n + 1$, every pure Nash equilibrium of Round-Robin under nonnegative additive valuations is EF1. The proof decomposes the analysis by turn counts: when $m \le 2n$, every agent picks at most twice, and equilibrium conditions prevent envy exceeding one good; when $m = 2n + 1$, only agent $0$ receives three items while all other agents receive at most two, and a valuation-free deviation argument shows that every other agent is EF1 towards agent $0$ once agent $0$'s first pick is removed. For three agents the bound is tight: the paper's eight-good counterexample is the smallest possible. These results are formalized and verified in Lean 4.

1. Introduction

The problem of allocating indivisible goods fairly among agents with additive valuations is a foundational topic in social choice and algorithmic game theory. Among the mechanisms designed for this purpose, the Round-Robin protocol is widely studied due to its operational simplicity and strong fairness properties under truthful behavior. In a Round-Robin protocol, agents take turns in cyclic order—agent $0$, then agent $1$, up through agent $n-1$, repeating cyclically—each picking their most preferred available good from a common pool of $m$ items. A well-known classic property of Round-Robin is that when agents report their true valuations and pick myopically, the resulting allocation is guaranteed to be envy-free up to one good (EF1): no agent envies another agent's bundle once some item is removed from the envied bundle.

In real-world decentralized settings, however, agents cannot generally be assumed to act truthfully. When agents know each other's preferences, they may report strategic rankings over the goods rather than their truthful ordinal preferences. A reported strict ranking profile determines the picking sequence outcome: each agent, upon their turn, is allocated their highest-ranked good among those remaining. This induces a normal-form game, the picking-sequence game, in which an agent's strategy is their reported permutation of the items. A profile of reported rankings forms a pure Nash equilibrium (PNE) if no agent can obtain a bundle of strictly greater true additive value by unilaterally deviating to a different reported ranking.

The question of whether strategic behavior preserves the fairness guarantees of Round-Robin was investigated in arXiv:2610.23686. That paper showed that strategic interactions can indeed degrade fairness. While the paper proved that for $n = 2$ agents, every pure Nash equilibrium of Round-Robin produces an allocation that is EF1, the same guarantee does not extend unconditionally to three or more agents. Specifically, arXiv:2610.23686 presented an explicit counterexample in Proposition 1 with $n = 3$ agents and $m = 8$ goods where a pure Nash equilibrium fails to be EF1. On the positive side, arXiv:2610.23686 established that every pure Nash equilibrium of Round-Robin satisfies a $1/2$-EF1 approximation bound for any number of agents and goods.

The counterexample of arXiv:2610.23686 uses $8$ goods for $3$ agents, that is, $m = 2n + 2$ for $n = 3$. This raises a natural question about the role of the number of goods: for $n$ agents, up to how many goods is every pure Nash equilibrium of Round-Robin guaranteed to be EF1? When $m \le n$ every agent picks at most once and EF1 is immediate; the question is what happens once agents pick several times.

In this post we prove, with a Lean 4 formalization, that for every $n \ge 1$ and every $m \le 2n + 1$, every pure Nash equilibrium of Round-Robin under nonnegative additive valuations is EF1 (round_robin_pne_ef1_of_card_le_two_mul_add_one). This is a positive guarantee for an infinite family of instances, covering any number of agents.

For $n = 3$ the bound is tight: with $7$ goods every equilibrium is EF1, while the paper's instance with $8$ goods has a non-EF1 equilibrium. So the $8$-good counterexample of arXiv:2610.23686 is the smallest possible for three agents. Whether $2n + 2$ goods suffice to break EF1 for every $n \ge 4$ is not proved here and remains open.

2. Preliminaries

Let us define the formal setting and concepts used in the theorems, matching the Lean 4 structures and definitions.

We consider a finite set of agents $N$ of cardinality $n \ge 1$ and a finite set of indivisible goods $G$ of cardinality $m \ge 0$. In Lean, these are represented by the standard finite types Fin $n$ and Fin $m$.

Definition 1 (Valuations and Additive Valuations). An abstract valuation is formalized by the structure SocialChoice.FairDivision.Indivisible.Valuation, which consists of a value function assigning a real number to each agent and bundle pair. An additive valuation is formalized by SocialChoice.FairDivision.Indivisible.AdditiveValuation, defined by a weight function assigning a real weight to each agent-good pair. The bundle valuation is obtained via the lifting SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation, which sets $$ v_i(S) = \sum_{g \in S} w(i, g) $$ for any agent $i \in N$ and bundle $S \subseteq G$. Throughout our analysis, valuations are assumed to be nonnegative, meaning $w(i, g) \ge 0$ for all $i \in N$ and $g \in G$.

Definition 2 (Envy-Freeness up to One Good). Given a valuation $v$ and an allocation $A : N \to \text{Finset } G$ that assigns subsets of goods to agents, the property of envy-freeness up to one good (EF1) is formalized by SocialChoice.FairDivision.Indivisible.IsEF1: $$ \forall i, j \in N, \ i \ne j \implies (A_j \text{ is nonempty} \implies \exists g \in A_j, \ v_i(A_j \setminus \{g\}) \le v_i(A_i)). $$ Remark on Lean definition: The definition in Lean includes the guard that $A_j$ is nonempty. If agent $j$ receives an empty bundle ($A_j = \emptyset$), no good can be removed, and agent $i$ cannot envy an empty bundle under nonnegative valuations ($v_i(\emptyset) = 0 \le v_i(A_i)$). The definition also employs a weak inequality ($\le$).

Definition 3 (Round-Robin Picking Sequence). The Round-Robin sequence for $n$ agents and $m$ goods is defined in Lean by round_robin_sequence. Given $n$ and $m$, round_robin_sequence n m produces a list of agent indices of length $m$, where the active agent at step $t \in \{0, \dots, m-1\}$ is given by $t \pmod n$. Agents pick in the fixed cyclic order: $$ (0, 1, \dots, n-1, 0, 1, \dots, n-1, 0, \dots). $$

Definition 4 (Picking-Sequence Outcome). An agent's strategy is a reported strict ranking over the set of goods, formalized as a permutation of the goods, where position $0$ represents the agent's most preferred item and position $m-1$ their least preferred item. Given a sequence of agent turns and a profile of reported rankings, the mechanism picking_sequence_outcome determines the allocation $A : N \to \text{Finset } G$. The mechanism iterates through the turn sequence from left to right; at each step, the active agent takes the highest-ranked good in their reported ranking that has not yet been selected by any agent in an earlier step.

Definition 5 (Pure Nash Equilibrium of Picking Sequences). A profile of reported strict rankings is a pure Nash equilibrium (PNE) of the picking-sequence game, formalized by is_picking_sequence_pne, if no agent can achieve a bundle of strictly greater true value by unilaterally reporting an alternative ranking: $$ \forall i \in N, \ \forall r, \ v_i(\text{picking\_sequence\_outcome } \text{seq } (\text{rank}[i \mapsto r])(i)) \le v_i(\text{picking\_sequence\_outcome } \text{seq } \text{rank}(i)). $$ Remark on Lean definition: The equilibrium condition requires that any unilateral deviation produces an outcome whose true valuation is weakly less than or equal to the equilibrium outcome valuation. This is the standard definition of pure Nash equilibrium for normal-form games.

3. Main result

The primary result formalized in Lean 4 is that every pure Nash equilibrium of Round-Robin is EF1 whenever the number of items does not exceed $2n + 1$.

Theorem (round_robin_pne_ef1_of_card_le_two_mul_add_one). Let $n, m \in \mathbb{N}$ with $n \ge 1$ and $m \le 2n + 1$. Let $w : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$ be a weight matrix satisfying $w(i, g) \ge 0$ for all $i \in \text{Fin } n$ and $g \in \text{Fin } m$, inducing the additive valuation $v = \text{toValuation}(\langle w \rangle)$. Let $\text{rank} : \text{Fin } n \to (\text{Fin } m \simeq \text{Fin } m)$ be a profile of reported rankings that forms a pure Nash equilibrium of the picking-sequence game for the Round-Robin sequence of length $m$: $$ \text{is\_picking\_sequence\_pne } v \ (\text{round\_robin\_sequence } n \ m) \ \text{rank}. $$ Then the allocation resulting from the picking sequence is envy-free up to one good: $$ \text{SocialChoice.FairDivision.Indivisible.IsEF1 } v \ (\text{picking\_sequence\_outcome } (\text{round\_robin\_sequence } n \ m) \ \text{rank}). $$

In Lean, round_robin_pne_ef1_of_card_le_two_mul_add_one universally quantifies over natural numbers $n$ and $m$ with typeclass instance asserting non-zero $n$, an inequality hypothesis $m \le 2n + 1$, an item weight matrix $w$ with nonnegativity hypothesis, a reported ranking permutation profile, and a pure Nash equilibrium hypothesis, concluding that the picking sequence outcome satisfies SocialChoice.FairDivision.Indivisible.IsEF1.

Further results in the formal development provide additional insight into the structure of equilibria and the sharpness of this bound:

  • round_robin_pne_ef1_of_card_le_two_mul: Proves that when $m \le 2n$, every pure Nash equilibrium of Round-Robin is EF1 under nonnegative additive valuations. In this regime, every agent appears at most twice in the picking sequence.
  • round_robin_pne_envy_zero_ef1_of_two_mul_add_one: Establishes that when $m = 2n + 1$, in every pure Nash equilibrium, every agent $i \ne 0$ is EF1 towards agent $0$. Here, agent $0$ is the unique agent who receives three goods, while all other agents receive at most two.
  • round_robin_pne_ef1_pair_of_count_le_two: Demonstrates that in any pure Nash equilibrium of Round-Robin, an agent $i$ is EF1 towards any agent $j$ who appears at most twice in the sequence.
  • round_robin_three_agents_seven_goods_pne_ef1: Proves that for $n = 3$ agents and $m = 7$ goods, every pure Nash equilibrium of Round-Robin is EF1. This shows that the $8$-good counterexample of arXiv:2610.23686 is minimal: seven goods are never sufficient to break EF1.
Theorem round_robin_pne_ef1_of_card_le_two_mul_add_one (Lean 4, verified)
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)

4. Proof

We now present the proof of round_robin_pne_ef1_of_card_le_two_mul_add_one as formalized in Lean.

Overview of the Proof:

We begin with an overview of the proof idea, then state the lemmas on which it rests, and finally combine them to establish the theorem. The analysis splits into two cases depending on the number of items $m$.

In the case where $m \le 2n$, the total number of items is at most twice the number of agents. In the Round-Robin sequence, each agent takes turns at most two times. When an agent picks at most two items, equilibrium incentives prevent any other agent from envying them by more than one good. This case is resolved by round_robin_pne_ef1_of_card_le_two_mul.

In the case where $m = 2n + 1$, exactly one agent—agent $0$—picks three items (at turns $0$, $n$, and $2n$). Every other agent $j \in \{1, \dots, n-1\}$ picks at most two items (specifically at turns $j$ and $n + j$). To verify EF1 for the entire allocation, we consider any pair of distinct agents $i$ and $j$:

  • If the envied agent $j$ satisfies $j \ne 0$, then $j$ picks at most twice in the sequence. By round_robin_pne_ef1_pair_of_count_le_two, agent $i$ does not envy $j$ by more than one good.
  • If the envied agent $j$ is agent $0$ ($j = 0$), then $j$ picks three items. However, because $i \ne j$, we have $i \ne 0$. The specialized lemma round_robin_pne_envy_zero_ef1_of_two_mul_add_one establishes that any agent $i \ne 0$ is EF1 towards agent $0$.

Combining these cases covers all possible pairs and establishes EF1 for the full allocation.

We now state the supporting lemmas established in the formalization and used in the main theorem.

Lemma 1 (round_robin_pne_ef1_of_card_le_two_mul). Let $n, m \in \mathbb{N}$ with $n \ge 1$ and $m \le 2n$. Let $w : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$ satisfy $w(i, g) \ge 0$ for all $i, g$, and let $\text{rank}$ be a pure Nash equilibrium of Round-Robin under the additive valuation induced by $w$. Then the allocation returned by picking_sequence_outcome on round_robin_sequence is EF1.

Role in Lean: This lemma handles the subcase where $m \le 2n$. When each agent appears at most twice in the sequence, no agent can receive three or more items. If agent $i$ envied agent $j$ after removing any single item from $A_j$, agent $j$ must hold two items $\{g_1, g_2\}$ such that $v_i(\{g_1\}) > v_i(A_i)$ and $v_i(\{g_2\}) > v_i(A_i)$. However, the picking mechanism allows agent $i$ to secure at least one of these high-value items during their own turn if they deviate, contradicting the equilibrium hypothesis is_picking_sequence_pne.

Lemma 2 (round_robin_sequence_count_le_two_of_ne_zero). Let $n \in \mathbb{N}$ with $n \ge 1$. In the Round-Robin sequence of length $2n + 1$ with $n$ agents, every agent $j$ with $j \ne 0$ appears at most twice: $$ (\text{round\_robin\_sequence } n \ (2n + 1)).\text{count } j \le 2. $$

Proof in Lean: The sequence consists of indices $t \in \{0, 1, \dots, 2n\}$, where turn $t$ is allocated to agent $t \pmod n$. Agent $0$ receives turns $t \in \{0, n, 2n\}$, totaling $3$ turns. For any agent $j \in \{1, \dots, n-1\}$, the turns assigned to $j$ are the values $t \in \{0, \dots, 2n\}$ such that $t \equiv j \pmod n$. These are exactly $t = j$ and $t = n + j$. The next potential turn would be $2n + j$; however, since $j \ge 1$, we have $2n + j \ge 2n + 1$, which exceeds the sequence length $m = 2n + 1$. Thus, agent $j$ appears exactly twice, which is bounded by $2$.

Lemma 3 (round_robin_pne_ef1_pair_of_count_le_two). Let $n, m \in \mathbb{N}$ with $n \ge 1$. Let $w$ define nonnegative additive valuations, and let $\text{rank}$ be a pure Nash equilibrium of Round-Robin. For any distinct agents $i, j$, if agent $j$ appears at most twice in the picking sequence, $$ (\text{round\_robin\_sequence } n \ m).\text{count } j \le 2, $$ and $A_j$ is nonempty, then agent $i$ is EF1 towards agent $j$: $$ \exists g \in A_j, \ v_i(A_j \setminus \{g\}) \le v_i(A_i). $$

Proof in Lean: Since $j$ appears at most twice in the sequence, the bundle $A_j$ contains at most two items: $|A_j| \le 2$. If $|A_j| = 1$, let $A_j = \{g\}$. Removing $g$ leaves the empty set $A_j \setminus \{g\} = \emptyset$. Under nonnegative weights ($w \ge 0$), $v_i(\emptyset) = 0 \le v_i(A_i)$, satisfying the EF1 condition immediately. If $|A_j| = 2$, let $A_j = \{g_1, g_2\}$. Without loss of generality, assume $w(i, g_1) \ge w(i, g_2)$. Choosing $g = g_1$ to remove, we have $A_j \setminus \{g_1\} = \{g_2\}$, and the EF1 condition requires $v_i(\{g_2\}) \le v_i(A_i)$. If this condition failed, then $w(i, g_2) > v_i(A_i)$ and consequently $w(i, g_1) \ge w(i, g_2) > v_i(A_i)$. This would mean both goods in $A_j$ individually yield strictly greater value to agent $i$ than the entirety of agent $i$'s equilibrium bundle $A_i$. Under the picking-sequence mechanism, at least one of these two goods was available at one of agent $i$'s picking turns. Agent $i$ could unilaterally alter their reported ranking to place that good at the top of their ranking, securing an item worth strictly more than $v_i(A_i)$, thereby strictly improving their total bundle value. This contradicts the pure Nash equilibrium condition is_picking_sequence_pne. Hence, $v_i(\{g_2\}) \le v_i(A_i)$, proving the pair $(i, j)$ is EF1.

Lemma 4 (round_robin_pne_envy_zero_ef1_of_two_mul_add_one). Let $n \in \mathbb{N}$ with $n \ge 1$. In the Round-Robin sequence with $n$ agents and $2n + 1$ goods, under nonnegative additive valuations, in every pure Nash equilibrium $\text{rank}$, every agent $i \ne 0$ is EF1 towards agent $0$: $$ \exists g \in A_0, \ v_i(A_0 \setminus \{g\}) \le v_i(A_i), $$ where $A_k = \text{picking\_sequence\_outcome } (\text{round\_robin\_sequence } n \ (2n+1)) \ \text{rank } k$.

Proof in Lean: When $m = 2n + 1$, agent $0$ picks at turns $0$, $n$ and $2n$; call its picks $a_1$, $a_2$, $a_3$, where $a_1$ is the top good of its report. Agent $i \ne 0$ picks at turns $i$ and $n + i$ and receives $A_i = \{b_1, b_2\}$; note $0 < i < n < n + i < 2n$. The good removed from $A_0$ is always $a_1$, so the claim is $w(i, a_2) + w(i, a_3) \le v_i(A_i)$.

The proof first establishes a purely combinatorial fact about the mechanism, independent of valuations: for any reports, either (a) some report $r$ of agent $i$ alone gives agent $i$ a bundle containing both $a_2$ and $a_3$, or (b) two reports $r_1$, $r_2$ of agent $i$ give bundles $D_1$, $D_2$ that together cover $A_i$ and $\{a_2, a_3\}$ with multiplicity: every good is counted in $D_1$ and $D_2$ at least as often as in $A_i$ and $\{a_2, a_3\}$. This is shown by tracing the run of the mechanism through the window of turns between agent $i$'s first pick and agent $0$'s last pick, comparing which goods remain available when agent $i$ takes $a_2$ or $a_3$ early.

The equilibrium condition then finishes the argument. In case (a), $w(i, a_2) + w(i, a_3) \le v_i(\text{bundle under } r) \le v_i(A_i)$, using nonnegative weights and that $r$ is not a profitable deviation. In case (b), the covering gives $v_i(A_i) + w(i, a_2) + w(i, a_3) \le v_i(D_1) + v_i(D_2) \le 2 v_i(A_i)$, again by nonnegativity and the equilibrium condition applied to $r_1$ and $r_2$, so $w(i, a_2) + w(i, a_3) \le v_i(A_i)$.

Combining the Lemmas to Prove the Main Theorem:

We now trace the Lean proof of round_robin_pne_ef1_of_card_le_two_mul_add_one:

The proof begins by branching on the inequality $m \le 2n$. In the branch where $m \le 2n$ holds, the proof directly applies round_robin_pne_ef1_of_card_le_two_mul, which immediately closes the goal.

In the branch where $m \le 2n$ does not hold, we have $m > 2n$. Combined with the hypothesis $m \le 2n + 1$, Lean's arithmetic tactics establish the exact equality $m = 2n + 1$. The proof substitutes $m$ with $2n + 1$.

To prove SocialChoice.FairDivision.Indivisible.IsEF1, the proof introduces arbitrary agents $i, j$, the distinctness hypothesis $i \ne j$, and the hypothesis that $A_j$ is nonempty.

The proof then branches on whether $j = 0$. When $j = 0$, substituting $j = 0$ leaves the goal of showing that agent $i$ is EF1 towards agent $0$. Since $i \ne j$ and $j = 0$, we have $i \ne 0$. The proof invokes Lemma 4, round_robin_pne_envy_zero_ef1_of_two_mul_add_one, which provides the required item $g \in A_0$. When $j \ne 0$, agent $j$ is not agent $0$. The proof applies Lemma 2, round_robin_sequence_count_le_two_of_ne_zero, which confirms that agent $j$ appears at most twice in the sequence. With this count bound and the nonemptiness hypothesis, the proof calls Lemma 3, round_robin_pne_ef1_pair_of_count_le_two, which provides the required item $g \in A_j$.

Since both subcases provide an item whose removal eliminates envy, the allocation satisfies the EF1 condition. The Lean proof is complete and fully verified.

5. Discussion

The result round_robin_pne_ef1_of_card_le_two_mul_add_one gives a positive guarantee for the fairness of strategic Round-Robin: every pure Nash equilibrium is EF1 as long as the number of goods satisfies $m \le 2n + 1$. This extends the two-agent EF1 theorem of arXiv:2610.23686, for any number of agents, to the regime where each agent receives at most two goods except agent $0$, who receives three.

For comparison, arXiv:2610.23686 shows for more than two agents that every pure Nash equilibrium is $1/2$-EF1, that exact EF1 can fail (Proposition 1, with $n = 3$ agents and $m = 8$ goods), and that no factor above $2/3$ can be guaranteed, by a family with a growing number of agents and goods.

For $n = 3$, round_robin_three_agents_seven_goods_pne_ef1 (the case $n = 3$ of the main theorem) shows that every pure Nash equilibrium with $7$ goods is EF1, so the $8$-good counterexample of arXiv:2610.23686 is the smallest possible, and $2n + 2$ is the exact threshold for three agents. For $n \ge 4$ it is open whether some instance with $2n + 2$ goods has a non-EF1 equilibrium; the threshold is at least $2n + 2$.

Several questions remain open:

  • The exact threshold for $n \ge 4$: does the three-agent counterexample extend to $n$ agents and $2n + 2$ goods?
  • The guaranteed factor: arXiv:2610.23686 leaves the gap $1/2 \le \alpha \le 2/3$ for the EF1 factor guaranteed at every equilibrium. The argument here suggests asking how the guaranteed factor depends on the number of goods per agent, not only on the number of agents.
  • Alternative picking sequences: the results here concern the standard Round-Robin order. Other recursively balanced sequences may have different thresholds.

Why it is research-level

  • Proves exact EF1 for every number of agents when m <= 2n+1, a positive guarantee beyond the general 1/2-EF1 bound and the three-agent/eight-good counterexample in arXiv:2610.23686

Lean declarations

Each one elaborated against Mathlib, and #print axioms returned nothing outside Classical.choice · Quot.sound · propext.

References

  1. arXiv:2610.23686 — Revisiting the Fairness of Pure Nash Equilibria of Round-Robin

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.