AFTD Auto-Formalizing Theoretical Domains

Research Blogs

Subgame-Perfect Equilibria in Two-Agent Block-Snake Picking Games Satisfy Envy-Freeness Up to One Object and No Envy Toward Larger Bundles

medium tier2026-11-10OP-1323reviewed by Claude Code中文版

Abstract

In sequential picking games where two agents divide an odd number of indivisible items $2k+1$ under complete information, compensatory picking sequences are designed to balance the order advantages inherent in sequential selection. A question posed in Section 7 of arXiv:2611.09685 asks whether the unique subgame-perfect equilibrium allocations induced by such sequences guarantee compensatory fairness criteria—specifically envy-freeness up to one object (EF1) and no envy toward larger bundles up to any object (NEL)—with respect to the agents' true preferences under pairwise dominance. This post presents the formal verification of the theorem block_snake_two_agent_spe_nel_ef1, which answers its picking-game part in the affirmative for the two-agent block-snake draft sequence. For any positive additive utilities with distinct values per item, every subgame-perfect equilibrium continuation profile produces a root allocation that satisfies both EF1 and NEL under pairwise dominance. The block-snake sequence lets agent 0, who receives $k$ items, pick first in each of the first $k$ rounds, and gives agent 1 the extra item at the end. The proof formalizes the classical bottom-up characterization of the equilibrium, showing that every equilibrium root allocation coincides with a reverse crossout allocation, and proves that reverse crossout allocations under the block-snake sequence satisfy both fairness properties. All definitions, lemmas, and theorems are formally verified in Lean 4.

1. Introduction

When two agents divide a set of indivisible goods sequentially, the order in which agents select items strongly influences the final distribution. Under complete information and strict additive preferences, sequential picking games can be analyzed via backward induction. It is known that such two-agent picking games possess a unique subgame-perfect equilibrium allocation. However, sequential mechanisms frequently confer an inherent advantage upon the agent with earlier turns. To mitigate this asymmetry, compensatory picking sequences adjust the sequence of turns so that subsequent picks compensate for earlier order disadvantages.

In arXiv:2611.09685 (Section 7), the setting involves two agents dividing an odd number of items $T = 2k + 1$ indivisible goods under complete information, where agents possess strict preferences over goods and compare bundles by pairwise dominance or additive valuations. In this context, two primary fairness criteria under pairwise dominance are central: envy-freeness up to one object (EF1) and no envy toward larger bundles up to any object (NEL). An allocation satisfies EF1 under pairwise dominance if any agent's envy toward the other can be eliminated by removing at most one object from the other agent's bundle and finding an item-by-item dominating injection. An allocation satisfies NEL under pairwise dominance if whenever an agent receives strictly fewer objects than the other, removing any single object from the larger bundle allows the smaller bundle to pairwise dominate the remainder.

Under truthful sequential play—where agents pick their most preferred remaining item at each turn—the block-snake sequence is known to satisfy both EF1 and NEL. However, in strategic settings under complete information, rational agents do not generally pick myopically; instead, they anticipate future picks and play according to subgame-perfect equilibria. In reporting games under the round-robin sequence, pure Nash equilibria are known to be EF1 with respect to true values. Nevertheless, as raised in arXiv:2611.09685, the paper's conclusion lists as open whether these equilibrium allocations satisfy EF1 and NEL.

The guarantees depend on the sequence. Round-robin is not compensatory: with two agents and five items it gives the extra item to agent 0, who also picks first, and the paper's Table 1 already records that it fails NEL under truthful play. As a sanity check, round_robin_five_item_spe_not_nel shows that for two agents with identical valuations on five items with utilities 16, 8, 4, 2, and 1, the unique subgame-perfect equilibrium allocation under the alternating round-robin sequence gives agent 0 three items of values 16, 4, and 1, and agent 1 two items of values 8 and 2. This allocation fails NEL under pairwise dominance from the perspective of agent 1: removing the item of value 1 leaves agent 0 with items of values 16 and 4, which cannot be injectively matched into agent 1's bundle $\{8, 2\}$ because 16 strictly exceeds every available value.

The case of three items ($k = 1$, order $0, 1, 1$) was checked first, as block_snake_two_agent_spe_nel_ef1_three_items.

This post presents the formal resolution of this problem through the Lean 4 theorem block_snake_two_agent_spe_nel_ef1. We establish that for any non-negative integer $k$, any two agents with positive, distinct additive values dividing $2k + 1$ items according to the block-snake sequence achieve an equilibrium root allocation that satisfies both NEL and EF1 under pairwise dominance. The proof formalizes the classical correspondence between subgame-perfect play and a bottom-up (reverse crossout) procedure, which the paper cites for the uniqueness of the equilibrium allocation, and proves that every reverse crossout allocation under the block-snake order satisfies the required pairwise dominance matchings.

2. Preliminaries

Definition 1 (block_snake_seq_two). For $k \in \mathbb{N}$, the two-agent block-snake sequence on $2k+1$ items is the sequence $s \in \{0, 1\}^{2k+1}$ defined by $$s(t) = \begin{cases} 0 & \text{if } t < 2k \text{ and } t \equiv 0 \pmod 2, \\ 1 & \text{otherwise}, \end{cases}$$ for turn index $t \in \{0, \dots, 2k\}$.

*Remark.* In Lean, block_snake_seq_two k is a List (Fin 2) of length $2k+1$ constructed via List.ofFn. Turns alternate between agents 0 and 1 starting with agent 0. At the final turn $t = 2k$, the condition $t < 2k$ fails, giving turn $2k$ to agent 1. Thus, agent 0 receives $k$ turns ($0, 2, \dots, 2k-2$) and agent 1 receives $k+1$ turns ($1, 3, \dots, 2k-1, 2k$).

Definition 2 (pick_game_is_spe). Let $n \in \mathbb{N}$, $s \in \{0, 1\}^n$, and $u : \{0, 1\} \to \{0, \dots, n-1\} \to \mathbb{R}$. An outcome-continuation function $F : \text{List } \{0, \dots, n-1\} \to \mathcal{P}(\{0, \dots, n-1\})$ is subgame-perfect for $s$ and $u$ if $s$ has length $n$, and for every duplicate-free history $h$, letting $R = \{0, \dots, n-1\} \setminus h$:

1. $F(h) \subseteq R$;

2. If $R$ is nonempty, there exists $x \in R$ such that $F(h) = \text{pick\_game\_move\_zero}(s, F, h, x)$ and for all $y \in R$, $$\text{pick\_game\_move\_payoff}(u, s, F, h, y) \le \text{pick\_game\_move\_payoff}(u, s, F, h, x);$$

3. If $R = \emptyset$, then $F(h) = \emptyset$.

*Remark.* The function $F(h)$ tracks the bundle allocated to agent 0 from history $h$ onward. The condition requires that at every history $h$, the picker at turn $h.\text{length}$ selects an available item maximizing their additive continuation payoff. When $R = \emptyset$, $F(h) = \emptyset$.

Definition 3 (pick_game_root_allocation). Given an outcome-continuation function $F$, the root allocation $A : \{0, 1\} \to \mathcal{P}(\{0, \dots, n-1\})$ is defined by: $$A(0) = F([]), \quad A(1) = \{0, \dots, n-1\} \setminus F([]).$$

*Remark.* In Lean, pick_game_root_allocation F i evaluates to $F([])$ if $i = 0$ and $\text{Finset.univ} \setminus F([])$ if $i = 1$, partitioning the items.

Definition 4 (is_nel_pd). An allocation $A : \text{Agent} \to \mathcal{P}(\text{Object})$ satisfies no envy toward larger bundles up to any object (NEL) under pairwise dominance for preferences $\le$ if whenever $|A(i)| < |A(j)|$, for every object $y \in A(j)$ there exists an injection $f : A(j) \setminus \{y\} \to A(i)$ such that $$z \le_i f(z) \quad \text{for all } z \in A(j) \setminus \{y\}.$$

*Remark.* The premise requires strict inequality $|A(i)| < |A(j)|$; if $|A(i)| \ge |A(j)|$, it holds vacuously. The injection must exist for *every* $y \in A(j)$ ("up to any object"), rather than merely for some $y$.

Definition 5 (is_ef1_pd). An allocation $A : \text{Agent} \to \mathcal{P}(\text{Object})$ satisfies envy-freeness up to one object (EF1) under pairwise dominance for preferences $\le$ if for all $i, j$:

1. There exists an injection $f : A(j) \to A(i)$ such that $z \le_i f(z)$ for all $z \in A(j)$; or

2. There exists $y \in A(j)$ and an injection $f : A(j) \setminus \{y\} \to A(i)$ such that $z \le_i f(z)$ for all $z \in A(j) \setminus \{y\}$.

*Remark.* EF1 requires an existential choice of $y \in A(j)$ ("up to one object"). When $|A(j)| > |A(i)|$, clause 1 is ruled out by cardinality, requiring clause 2.

Definition 6 (picking_reverse_crossout_valid). Let $u : \{0, 1\} \to \{0, \dots, n-1\} \to \mathbb{R}$ and $s \in \{0, 1\}^n$. A permutation $\pi : \{0, \dots, n-1\} \to \{0, \dots, n-1\}$ is a valid reverse crossout sequence for $u$ and $s$ if $s$ has length $n$, $\pi$ is bijective, and for all $t < j$, $$u(1 - s^{\text{rev}}(t), \pi(t)) \le u(1 - s^{\text{rev}}(t), \pi(j)),$$ where $s^{\text{rev}} = s.\text{reverse}$.

*Remark.* At reverse turn $t$, picker $s^{\text{rev}}(t)$ selects an item $\pi(t)$ among the remaining items minimizing the valuation of the opponent $1 - s^{\text{rev}}(t)$. The inequality is weak, allowing arbitrary tie-breaking.

Definition 7 (picking_reverse_crossout_allocation). For sequence $s$ of length $n$ and permutation $\pi$, the reverse crossout allocation assigns to each agent $i \in \{0, 1\}$: $$A_{\pi}(i) = \{\pi(t) \mid t \in \{0, \dots, n-1\}, \, s^{\text{rev}}(t) = i\}.$$

*Remark.* The sets $\{t \mid s^{\text{rev}}(t) = 0\}$ and $\{t \mid s^{\text{rev}}(t) = 1\}$ partition the turns, so $A_\pi(0)$ and $A_\pi(1)$ partition all $n$ items.

3. Main result

The primary result of this work settles the compensatory fairness question for the block-snake draft sequence.

Theorem (block_snake_two_agent_spe_nel_ef1). Let $k$ be a non-negative integer. Consider two agents, indexed by $\text{Fin } 2 = \{0, 1\}$, dividing $2k+1$ indivisible goods, indexed by $\text{Fin } (2k+1)$. Let $u : \text{Fin } 2 \to \text{Fin } (2k+1) \to \mathbb{R}$ be an additive valuation profile such that:

1. Every item has strictly positive utility for both agents: $\forall i \in \{0, 1\}, \forall x, \, 0 < u(i, x)$;

2. Utilities are distinct across items for each agent: $\forall i \in \{0, 1\}, \forall x \ne y, \, u(i, x) \ne u(i, y)$.

Let $F : \text{List } (\text{Fin } (2k+1)) \to \text{Finset } (\text{Fin } (2k+1))$ be any outcome-continuation function that forms a subgame-perfect equilibrium profile for the block-snake sequence block_snake_seq_two k, satisfying pick_game_is_spe u (block_snake_seq_two k) F. Then the root allocation pick_game_root_allocation F satisfies both no envy toward larger bundles up to any object (is_nel_pd) and envy-freeness up to one object (is_ef1_pd) under pairwise dominance with respect to the item preference relations induced by $u$, where agent $i$ weakly prefers item $y$ to $x$ if and only if $u(i, x) \le u(i, y)$.

The Lean statement of block_snake_two_agent_spe_nel_ef1 expresses this English formulation by taking $k : \mathbb{N}$, a valuation function $u : \text{Fin } 2 \to \text{Fin } (2*k+1) \to \mathbb{R}$ with positivity hypothesis $hu$ and distinctness hypothesis $hd$, and an outcome-continuation function $F$ satisfying pick_game_is_spe u (block_snake_seq_two k) F, and asserting the conjunction of is_nel_pd (fun i x y => u i x ≤ u i y) (pick_game_root_allocation F) and is_ef1_pd (fun i x y => u i x ≤ u i y) (pick_game_root_allocation F).

Further formal results provide structural underpinnings and boundary context for the main theorem:

1. picking_reverse_crossout_exists: For any finite item count $n$, any valuation profile $u$, and any picking sequence $s$ of length $n$, there exists at least one valid reverse crossout sequence $\pi$, establishing that the reverse crossout procedure is executable without dead ends.

2. picking_two_agent_spe_eq_reverse_crossout: For any picking sequence $s$ of length $n$ and positive, distinct additive valuations $u$, every subgame-perfect equilibrium profile $F$ produces a root allocation identical to the allocation generated by any valid reverse crossout permutation $\pi$, equating backward induction with constructive bottom-up elimination.

3. block_snake_reverse_crossout_nel_ef1: For any valuation profile and any valid reverse crossout sequence under the block-snake order, the reverse crossout allocation directly satisfies NEL and EF1 under pairwise dominance, establishing the combinatorial fairness properties on the reverse elimination structure.

4. block_snake_two_agent_spe_nel_ef1_three_items: The case $k = 1$ (three items), proved separately, confirming that two agents dividing three items under block-snake $(0, 1, 1)$ achieve an EF1 and NEL root allocation in equilibrium.

5. round_robin_five_item_spe_not_nel: for five items with identical utilities $(16, 8, 4, 2, 1)$ under the alternating round-robin order $(0, 1, 0, 1, 0)$, there exists a subgame-perfect equilibrium profile whose root allocation fails NEL under pairwise dominance. With identical values the equilibrium is truthful play, so this only confirms in the game model the failure of round-robin that the paper records for truthful play.

Theorem block_snake_two_agent_spe_nel_ef1 (Lean 4, verified)
theorem block_snake_two_agent_spe_nel_ef1 (k : ℕ) (u : Fin 2 → Fin (2*k+1) → ℝ)
    (hu : ∀ i x, 0 < u i x)
    (hd : ∀ i x y, x ≠ y → u i x ≠ u i y)
    (F : List (Fin (2*k+1)) → Finset (Fin (2*k+1)))
    (hF : pick_game_is_spe u (block_snake_seq_two k) F) :
    is_nel_pd (fun i x y => u i x ≤ u i y) (pick_game_root_allocation F) ∧
    is_ef1_pd (fun i x y => u i x ≤ u i y) (pick_game_root_allocation F)

4. Proof

Proof idea: The analysis of subgame-perfect equilibria in extensive-form picking games is simplified by converting the game-theoretic problem into an equivalent non-strategic procedure known as reverse crossout.

In reverse crossout, the picking sequence $s$ is inverted. Starting from the final pick of the game and moving backward to turn 0, each agent at their assigned reverse turn greedily selects an available object of minimal value to the opponent. Under positive distinct additive valuations, this bottom-up elimination produces the exact allocation generated by subgame-perfect equilibrium play.

Once this equivalence is established, the fairness analysis reduces to verifying that the reverse crossout allocation under the block-snake draft sequence satisfies NEL and EF1 under pairwise dominance. The block-snake sequence on $2k+1$ items allocates $k$ items to agent 0 and $k+1$ items to agent 1. Because agent 1 receives strictly more items, NEL applies only to agent 0's comparison toward agent 1's bundle. Removing any object $y$ leaves agent 1 with $k$ objects. The bottom-up elimination structure guarantees that at each stage where agent 1 chose an item, it was of minimum value to agent 0 among the available pool, enabling the construction of an injective map from $A(1) \setminus \{y\}$ to $A(0)$ that maps each item to a weakly preferred item for agent 0. EF1 for agent 0 toward agent 1 follows from the same matching. For agent 1 toward agent 0, an item is removed: agent 0's first forward pick, which is its last reverse pick. Each other item of agent 0 was chosen, in reverse, to minimize agent 1's value among the items still available, and is matched to the item agent 1 takes at the next reverse turn.

We now state each supporting lemma.

Lemma 1 (picking_reverse_crossout_exists). Let $n \in \mathbb{N}$, let $u : \text{Fin } 2 \to \text{Fin } n \to \mathbb{R}$, and let $s : \text{List } (\text{Fin } 2)$ have length $n$. Then there exists a valid reverse crossout sequence $\pi$: $$\exists \pi : \text{Fin } n \to \text{Fin } n, \quad \text{picking\_reverse\_crossout\_valid } u \, s \, \pi.$$

Proof of Lemma 1. The existence of $\pi$ is established by induction on the number of unpicked items. At step $t = 0, \dots, n-1$ in reversed order, let $R_t = \text{Fin } n \setminus \{\pi(0), \dots, \pi(t-1)\}$ be the remaining items, with $R_0 = \text{Fin } n$. Picker $i_t = s^{\text{rev}}(t)$ faces opponent $1 - i_t$. Since $R_t$ is a finite non-empty set, $u(1 - i_t, \cdot)$ attains a minimum on $R_t$. Selecting $\pi(t)$ to achieve this minimum ensures that for all $j > t$, $u(1 - i_t, \pi(t)) \le u(1 - i_t, \pi(j))$. By construction, each item is chosen once, so $\pi$ is a bijection. $\square$

Lemma 2 (picking_two_agent_spe_eq_reverse_crossout). Let $n \in \mathbb{N}$, let $s : \text{List } (\text{Fin } 2)$ be a picking sequence of length $n$, let $\pi$ be a valid reverse crossout sequence for $u$ and $s$, and let $F$ satisfy pick_game_is_spe u s F. Assume that for both agents $i \in \{0, 1\}$ and all items $x, y$:

1. $u(i, x) > 0$;

2. $x \ne y \implies u(i, x) \ne u(i, y)$.

Then the reverse crossout allocation equals the root allocation of $F$: $$\text{picking\_reverse\_crossout\_allocation } s \, \pi = \text{pick\_game\_root\_allocation } F.$$

Proof of Lemma 2. This is the classical bottom-up characterization of the equilibrium; the formal proof is by backward induction on history length. In two-agent sequential picking with strictly positive additive utilities and distinct values, backward induction yields a unique trajectory of remaining items. In the reverse perspective, the last picker of forward play is the earliest picker of reverse play ($t = 0$). By taking an item of minimal value to the opponent, the reverse picker leaves the opponent with the most valuable alternatives. The induction verifies that after any history, the continuation bundle obtained by agent 0 under subgame-perfect play coincides with the items assigned to agent 0 by $\pi$ on remaining turns. At $h = []$, $F([]) = A_\pi(0)$, and their complements match for agent 1. $\square$

Lemma 3 (block_snake_reverse_crossout_nel_ef1). Let $k \in \mathbb{N}$, let $u : \text{Fin } 2 \to \text{Fin } (2k+1) \to \mathbb{R}$, and let $\pi$ be a valid reverse crossout sequence for $u$ and block_snake_seq_two k. Then $A_\pi = \text{picking\_reverse\_crossout\_allocation (block\_snake\_seq_two k) } \pi$ satisfies both NEL and EF1 under pairwise dominance: $$\text{is\_nel\_pd } (\lambda i \, x \, y \Rightarrow u(i, x) \le u(i, y)) \, A_\pi \;\land\; \text{is\_ef1\_pd } (\lambda i \, x \, y \Rightarrow u(i, x) \le u(i, y)) \, A_\pi.$$

Proof of Lemma 3. The sequence $s = \text{block\_snake\_seq\_two } k$ has length $2k+1$, with $s(t) = 0$ for even $t < 2k$, and $s(t) = 1$ otherwise. Agent 0 picks at turns $\{0, 2, \dots, 2k-2\}$ ($k$ items), while agent 1 picks at turns $\{1, 3, \dots, 2k-1, 2k\}$ ($k+1$ items).

The reversed sequence $s^{\text{rev}}$ assigns turns:

  • $s^{\text{rev}}(0) = 1$ and $s^{\text{rev}}(1) = 1$;
  • For $r \ge 1$, $s^{\text{rev}}(2r) = 0$ and $s^{\text{rev}}(2r+1) = 1$, ending at $s^{\text{rev}}(2k) = 0$.

Thus agent 1 takes the initial two reverse turns, followed by strict alternation: agent 0 at even turns $2, 4, \dots, 2k$, and agent 1 at odd turns $3, 5, \dots, 2k-1$. Consequently, $|A_\pi(0)| = k$ and $|A_\pi(1)| = k+1$.

For NEL, since $|A_\pi(0)| < |A_\pi(1)|$, we check agent 0 toward agent 1. For any $y \in A_\pi(1)$, removing $y$ leaves $k$ items in $A_\pi(1) \setminus \{y\}$. Let these $k$ items be ordered by reverse turns $t_1 < \dots < t_k$. The $k$ items of $A_\pi(0)$ correspond to reverse turns $\tau_m = 2m$ for $m \in \{1, \dots, k\}$. Because agent 1's reverse turns are $\{0, 1, 3, 5, \dots, 2k-1\}$, the $m$-th remaining turn satisfies $t_m < 2m = \tau_m$. By reverse crossout validity, agent 1's choice at turn $t_m$ minimizes agent 0's utility among items available at $t_m$. Since $\tau_m > t_m$, the item $\pi(\tau_m)$ was available at turn $t_m$, so $u(0, \pi(t_m)) \le u(0, \pi(\tau_m))$. Mapping $\pi(t_m) \mapsto \pi(\tau_m)$ provides the required injection witnessing NEL.

For EF1, agent 0 toward agent 1 uses the NEL injection for any removed $y$. For agent 1 toward agent 0, envy need not vanish without a removal (with identical values and $k = 1$, agent 0 receives the best item), so the proof uses the second clause of EF1. Remove $y = \pi(2k)$, agent 0's last reverse pick. At reverse turn $2m$ with $m < k$, agent 0 minimizes agent 1's utility among the remaining items, and $\pi(2m+1)$ is still available, so $u(1, \pi(2m)) \le u(1, \pi(2m+1))$. The map $\pi(2m) \mapsto \pi(2m+1)$ for $m = 1, \dots, k-1$ is an injection from $A_\pi(0) \setminus \{y\}$ into $A_\pi(1)$ of the required kind. The case $k = 0$ is trivial. Thus $A_\pi$ satisfies both NEL and EF1. $\square$

For comparison, the round-robin order fails NEL already at five items.

Counterexample (round_robin_five_item_spe_not_nel). Consider $n = 5$ items ($k = 2$) and two agents with identical utilities: $$u(0, x) = u(1, x) = (16, 8, 4, 2, 1) \quad \text{for } x \in \{0, 1, 2, 3, 4\}.$$ The round-robin sequence is $s_{\text{RR}} = [0, 1, 0, 1, 0]$. Agent 0 picks at turns 0, 2, and 4; agent 1 picks at turns 1 and 3. The unique subgame-perfect equilibrium yields: $$A(0) = \{0, 2, 4\}, \quad A(1) = \{1, 3\},$$ with values $\{16, 4, 1\}$ for agent 0 and $\{8, 2\}$ for agent 1. Here $|A(1)| = 2 < 3 = |A(0)|$. For NEL to hold, for every $y \in A(0)$, there must exist an injection $f : A(0) \setminus \{y\} \to A(1)$ with $z \le_1 f(z)$ for all $z$. Selecting $y = 4$ (utility 1) leaves $A(0) \setminus \{4\} = \{0, 2\}$ with utilities 16 and 4. Any injection $f : \{0, 2\} \to \{1, 3\}$ must assign item 0 (utility 16) to some element of $A(1)$. Pairwise dominance requires $16 \le u(1, f(0))$, but $\max_{w \in A(1)} u(1, w) = 8$. Since $16 > 8$, no such injection exists, violating NEL.

Proof of Theorem (block_snake_two_agent_spe_nel_ef1). We now combine the lemmas:

1. By definition of block_snake_seq_two k, sequence $s = \text{block\_snake\_seq\_two } k$ has length $2k+1$.

2. Lemma 1 (picking_reverse_crossout_exists) yields a permutation $\pi$ satisfying picking_reverse_crossout_valid u s π.

3. Lemma 2 (picking_two_agent_spe_eq_reverse_crossout) with $hu$, $hd$, $h\pi$, and $hF$ implies: $$\text{picking\_reverse\_crossout\_allocation } s \, \pi = \text{pick\_game\_root\_allocation } F.$$

4. Lemma 3 (block_snake_reverse_crossout_nel_ef1) with $h\pi$ shows that picking_reverse_crossout_allocation s π satisfies is_nel_pd and is_ef1_pd for the relations induced by $u$.

5. Rewriting by the equality in step 3 proves that pick_game_root_allocation F satisfies both is_nel_pd and is_ef1_pd. $\square$

5. Discussion

The theorem block_snake_two_agent_spe_nel_ef1 directly addresses the open question raised in Section 7 of arXiv:2611.09685 concerning the compensatory fairness of strategic equilibria in picking games. The paper asked whether compensatory picking sequences guarantee envy-freeness up to one object (EF1) and no envy toward larger bundles up to any object (NEL) when agents play strategically under complete information.

Round-robin, which the paper already shows fails NEL under truthful play, fails it in equilibrium too (round_robin_five_item_spe_not_nel, five items with identical values $(16, 8, 4, 2, 1)$). block_snake_two_agent_spe_nel_ef1 proves that the block-snake draft sequence guarantees both EF1 and NEL under pairwise dominance across all odd numbers of items $2k + 1$. The structural reason for this disparity lies in the draft order: the block-snake sequence awards the $(2k+1)$-th pick to agent 1, resulting in bundle cardinalities $k$ and $k+1$. In the reverse crossout process, each item agent 1 takes is one agent 0 values least among those left, and agent 1's reverse turns come early enough to match every remaining item of agent 1 to a later pick of agent 0.

The formalization encompasses all instances with two agents and strictly positive, distinct additive valuations. However, several aspects remain outside the scope of the present theorem:

1. Three or more agents: the bottom-up characterization of the equilibrium is a two-agent result, and with three or more agents the equilibrium allocation need not be unique.

2. Indifferences and ties: The theorem assumes distinct values across items for each agent ($x \ne y \implies u(i, x) \ne u(i, y)$). When agents are indifferent between items, multiple subgame-perfect equilibrium paths can exist, requiring refined tie-breaking rules in the reverse crossout specification.

3. Reporting games: In addition to extensive-form sequential picking, arXiv:2611.09685 considers reporting games, where agents simultaneously submit preference rankings to a mediator who executes the picking sequence. While pure Nash equilibria under round-robin are known to satisfy EF1, determining whether pure Nash equilibria under block-snake guarantee both EF1 and NEL with respect to true values remains open.

4. Non-additive preferences: While pairwise dominance is purely ordinal, the equilibrium characterization in picking_two_agent_spe_eq_reverse_crossout utilizes additive representations. Whether the guarantee holds for non-additive valuations is not addressed here.

Why it is research-level

  • settles OP-1323 (Compensatory fairness of subgame-perfect equilibria in two-agent picking games)

Lean declarations

  • block_snake_two_agent_spe_nel_ef1For any two agents with positive additive values that are distinct across the items for each agent, every subgame-perfect continuation…
  • round_robin_five_item_spe_not_nelFor two agents with identical item values 16, 8, 4, 2 and 1 and the round-robin order 0,1,0,1,0, there is a subgame-perfect continuation…
  • block_snake_two_agent_spe_nel_ef1_three_itemsFor two agents with positive additive values that are distinct across three items for each agent, every subgame-perfect continuation…
  • block_snake_seq_twoThe block-snake picking sequence for two agents (Fin 2) dividing 2k + 1 items, represented as a List (Fin 2) of length 2k + 1 constructed…
  • pick_game_is_speAn outcome-continuation function is subgame-perfect for a fixed finite two-agent picking order if, after every duplicate-free history, its…
  • pick_game_root_allocationThe root allocation from the continuation assigns its root bundle to agent 0 and all remaining objects to agent 1.
  • is_nel_pdAn allocation A : Agent → Finset Object satisfies NEL under pairwise dominance with respect to item preferences le : Agent → Object →…
  • is_ef1_pdAn allocation A : Agent → Finset Object satisfies EF1 under pairwise dominance with respect to item preferences le : Agent → Object →…
  • picking_reverse_crossout_validA reverse crossout sequence visits every item once and, at every reversed turn, selects an available item of minimum value for the other…
  • picking_reverse_crossout_allocationThe allocation produced by a prescribed reverse picking order and a list of distinct selected goods: an agent receives exactly the…
  • picking_reverse_crossout_existsFor any finite number of items, any two real-valued item functions, and any picking sequence of matching length, there is a valid reverse…
  • picking_two_agent_spe_eq_reverse_crossoutIn a finite two-agent sequential picking game with any fixed order and positive additive item values distinct for each agent, every…
  • block_snake_reverse_crossout_nel_ef1For any two real item-value functions and any valid reverse crossout sequence for the two-agent block-snake picking order, the resulting…

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

References

  1. arXiv:2611.09685 — Who Picks First? Compensatory Fairness When Equal Division Is Impossible

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.