block_snake_two_agent_spe_nel_ef1
For any two agents with positive additive values that are distinct across the items for each agent, every subgame-perfect continuation profile of the two-agent block-snake picking game on 2k+1 objects has a root allocation satisfying both NEL and EF1 in pairwise dominance for the item rankings induced by those values. A continuation profile specifies an allocation of the remaining objects after every distinct-item history and, at every such history, specifies an optimal available next pick given the continuations after all alternatives.
Statement
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)
- Related work
- arXiv:2611.09685, Section 7, question on strategic picking and compensatory fairness (OP-1323); this statement specifies the block-snake sequence and strictly positive additive utility.
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 10
- 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.
- 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…
- 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_existsFor any finite number of items, any two real-valued item functions, and any picking sequence of matching length, there is a valid reverse…
- 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…
- 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…
- 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_validA reverse crossout sequence visits every item once and, at every reversed turn, selects an available item of minimum value for the other…
Read back from the Lean
For any natural number $k$, any utility function $u : \mathrm{Fin}\;2 \to \mathrm{Fin}\;(2k+1) \to \mathbb{R}$, assuming that all utilities are strictly positive ($u(i, x) > 0$ for all $i, x$) and that each agent's utilities for distinct items are strictly distinct ($u(i, x) \neq u(i, y)$ whenever $x \neq y$), and for any outcome function $F : \mathrm{List}\;(\mathrm{Fin}\;(2k+1)) \to \mathrm{Finset}\;(\mathrm{Fin}\;(2k+1))$, if $F$ is a subgame perfect equilibrium (SPE) outcome function for the sequential picking game with utilities $u$ and turn sequence $\mathrm{block\_snake\_seq\_two}(k)$, then the root allocation produced by $F$ (where agent $0$ receives $F([]) $ and agent $1$ receives the complement $\mathrm{Finset.univ} \setminus F([])$) satisfies both:
1. pairwise-dominance no-envy for larger bundles (is_nel_pd): whenever an agent $i$ receives strictly fewer items than agent $j$, then for every item $y$ in agent $j$'s bundle, there exists an injection $f$ from agent $j$'s bundle with $y$ removed into agent $i$'s bundle such that agent $i$ weakly prefers $f(z)$ to $z$ for all $z$ in that reduced bundle; and
2. envy-freeness up to one item with pairwise dominance (is_ef1_pd): for every pair of agents $i, j$, either there exists an injection from agent $j$'s entire bundle into agent $i$'s bundle that pairwise dominates according to agent $i$'s preferences, or there exists an item $y$ in agent $j$'s bundle and an injection from agent $j$'s bundle with $y$ removed into agent $i$'s bundle that pairwise dominates according to agent $i$'s preferences.
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 reducing the subgame-perfect equilibrium (SPE) root allocation to a reverse-crossout allocation. For two agents with strictly positive and distinct additive valuations, the outcome of any SPE is known to coincide with the allocation produced by the reverse-crossout procedure. Since reverse-crossout allocations on the block-snake sequence are independently proven to satisfy non-envious-lower (NEL) and envy-freeness up to one item (EF1) in pairwise dominance, the result follows by substituting this equality.
The block-snake picking sequence for parameter k has length 2k+1. automation
The block-snake sequence for two agents is constructed as a list from a function on Fin (2*k+1), so simplification with its definition directly establishes that its length is 2k+1. This satisfies the length prerequisite for the existence of reverse-crossout sequences.
uses
block_snake_seq_twohave hlen : (block_snake_seq_two k).length = 2*k+1 := by simp [block_snake_seq_two]
There exists a valid reverse-crossout sequence π, and its allocation equals the subgame-perfect equilibrium root allocation.
By picking_reverse_crossout_exists, any sequence of length 2k+1 admits a valid reverse-crossout elimination sequence π. Since the agents' valuations are strictly positive (hu) and distinct on distinct items (hd), picking_two_agent_spe_eq_reverse_crossout proves that the root allocation of the subgame-perfect continuation profile F is identical to the reverse-crossout allocation determined by π.
uses
picking_reverse_crossout_exists,picking_two_agent_spe_eq_reverse_crossoutobtain ⟨π, hπ⟩ := picking_reverse_crossout_exists (2*k+1) u (block_snake_seq_two k) hlen have heq := picking_two_agent_spe_eq_reverse_crossout (2*k+1) u (block_snake_seq_two k) π F hu hd hπ hF
The root allocation of the subgame-perfect equilibrium profile satisfies both NEL and EF1 in pairwise dominance.
Theorem block_snake_reverse_crossout_nel_ef1 states that any reverse-crossout allocation under the block-snake sequence satisfies both non-envious-lower (NEL) and envy-free up to one item (EF1) in pairwise dominance. Rewriting by the equality heq substitutes the subgame-perfect equilibrium root allocation in place of the reverse-crossout allocation, concluding the proof.
uses
block_snake_reverse_crossout_nel_ef1have hmain := block_snake_reverse_crossout_nel_ef1 k u π hπ rw [← heq] exact hmain
block_snake_seq_two- The predefined picking sequence of length 2k+1 for two agents, specifying which agent picks at each turn according to the block-snake protocol.
picking_reverse_crossout_exists- For any picking sequence of length n and any two-agent utility profile, there exists a valid reverse-crossout elimination sequence π.
picking_two_agent_spe_eq_reverse_crossout- In a two-agent picking game where each agent has strictly positive and pairwise distinct values for all items, the root allocation of any subgame-perfect equilibrium coincides with the reverse-crossout allocation.
block_snake_reverse_crossout_nel_ef1- For any two-agent block-snake picking sequence on 2k+1 items, every valid reverse-crossout allocation satisfies non-envious-lower (NEL) and envy-freeness up to one item (EF1) in pairwise dominance.
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 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) := by have hlen : (block_snake_seq_two k).length = 2*k+1 := by simp [block_snake_seq_two] obtain ⟨π, hπ⟩ := picking_reverse_crossout_exists (2*k+1) u (block_snake_seq_two k) hlen have heq := picking_two_agent_spe_eq_reverse_crossout (2*k+1) u (block_snake_seq_two k) π F hu hd hπ hF have hmain := block_snake_reverse_crossout_nel_ef1 k u π hπ rw [← heq] exact hmain