picking_two_agent_spe_eq_reverse_crossout
In a finite two-agent sequential picking game with any fixed order and positive additive item values distinct for each agent, every subgame-perfect continuation profile has the same root allocation as any valid reverse crossout sequence: reverse the picking order and repeatedly give the current picker a remaining item least valued by the other player.
Statement
theorem picking_two_agent_spe_eq_reverse_crossout (n : ℕ) (u : Fin 2 → Fin n → ℝ) (s : List (Fin 2))
(π : Fin n → Fin n) (F : List (Fin n) → Finset (Fin n))
(hu : ∀ i x, 0 < u i x) (hd : ∀ i x y, x ≠ y → u i x ≠ u i y)
(hπ : picking_reverse_crossout_valid u s π) (hF : pick_game_is_spe u s F) :
picking_reverse_crossout_allocation s π = pick_game_root_allocation F- Formalizes
- Strategic Behavior when Allocating Indivisible Goods Sequentially, Theorem 1, https://cdn.aaai.org/ojs/8697/8697-13-12225-1-2-20201228.pdf; expressed through history-dependent continuation profiles and positive additive values.
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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…
- 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.
- pick_game_move_payoffThe mover’s additive payoff from the current remaining objects if the specified item is chosen, followed by the given continuations: agent…
- pick_game_move_zeroFor a history and a legal next choice, the resulting agent-0 continuation bundle consists of the selected object together with the…
- Used by 1
- 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…
Read back from the Lean
For any natural number $n$, utility functions $u : \text{Fin } 2 \to \text{Fin } n \to \mathbb{R}$, turn sequence $s : \text{List } (\text{Fin } 2)$, item permutation $\pi : \text{Fin } n \to \text{Fin } n$, and continuation outcome function $F : \text{List } (\text{Fin } n) \to \text{Finset } (\text{Fin } n)$, assume:
1. $u$ is strictly positive: for every agent $i \in \text{Fin } 2$ and item $x \in \text{Fin } n$, $u(i, x) > 0$.
2. $u$ has no ties: for every agent $i \in \text{Fin } 2$ and items $x \ne y \in \text{Fin } n$, $u(i, x) \ne u(i, y)$.
3. $\pi$ is a valid reverse cross-out elimination ordering (picking_reverse_crossout_valid u s π):
- $s$ has length $n$;
- $\pi$ is bijective;
- for all $t, j \in \text{Fin } n$ with $t < j$, the opponent of agent $s.\text{reverse}[t]$ weakly prefers item $\pi(j)$ to item $\pi(t)$ (that is, $\pi(t)$ is a least-preferred item among $\{\pi(t), \dots, \pi(n-1)\}$ for the agent other than $s.\text{reverse}[t]$).
4. $F$ describes a subgame perfect equilibrium (pick_game_is_spe u s F):
- $s$ has length $n$;
- for every duplicate-free history $h : \text{List } (\text{Fin } n)$, letting $R = \text{Finset.univ} \setminus h.\text{toFinset}$ be the set of remaining items:
- $F(h) \subseteq R$;
- if $R$ is nonempty, there exists $x \in R$ such that $F(h)$ equals the items assigned to agent $0$ if $x$ is picked next, and picking $x$ maximizes the current player's payoff among all choices $y \in R$;
- if $R$ is empty, $F(h) = \emptyset$.
Then the item allocation produced by the reverse cross-out procedure equals the subgame perfect equilibrium allocation at the root:
picking_reverse_crossout_allocation s π = pick_game_root_allocation F,
meaning that for each agent $i \in \text{Fin } 2$, the set of items $\{\pi(t) \mid t \in \text{Fin } n, s.\text{reverse}[t] = i\}$ equals the set of items allocated to agent $i$ under $F$ at the empty history ($F([]) $ for agent $0$, and $\text{Finset.univ} \setminus F([])$ for agent $1$).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
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.
Lean’s trace was cut to the first 400 of 432 tactics.
def pk2_oth (l : Fin 2) : Fin 2 := if l = 0 then 1 else 0theorem pk2_fin2 (a : Fin 2) (h : a ≠ 0) : a = 1 := by fin_cases a <;> simp_alltheorem pk2_oth_of_ne (l p : Fin 2) (h : l ≠ p) : pk2_oth l = p := by fin_cases l <;> fin_cases p <;> simp_all [pk2_oth]noncomputable def pk2_amin {α : Type*} [Nonempty α] (w : α → ℝ) (T : Finset α) : α := Classical.epsilon (fun x => x ∈ T ∧ ∀ y ∈ T, w x ≤ w y)theorem pk2_amin_spec {α : Type*} [Nonempty α] (w : α → ℝ) (T : Finset α) (hT : T.Nonempty) : pk2_amin w T ∈ T ∧ ∀ y ∈ T, w (pk2_amin w T) ≤ w y := by obtain ⟨x, hx, hmin⟩ := T.exists_min_image w hT exact Classical.epsilon_spec (p := fun x => x ∈ T ∧ ∀ y ∈ T, w x ≤ w y) ⟨x, hx, hmin⟩theorem pk2_amin_eq {α : Type*} [Nonempty α] (w : α → ℝ) (hw : Function.Injective w) (T : Finset α) (x : α) (hx : x ∈ T) (hmin : ∀ y ∈ T, w x ≤ w y) : pk2_amin w T = x := by have h := pk2_amin_spec w T ⟨x, hx⟩ exact hw (le_antisymm (h.2 x hx) (hmin _ h.1))theorem pk2_amin_erase {α : Type*} [DecidableEq α] [Nonempty α] (w : α → ℝ) (hw : Function.Injective w) (T : Finset α) (hT : T.Nonempty) (z : α) (hz : z ≠ pk2_amin w T) : pk2_amin w (T.erase z) = pk2_amin w T := by have h := pk2_amin_spec w T hT exact pk2_amin_eq w hw _ _ (Finset.mem_erase.mpr ⟨fun h' => hz h'.symm, h.1⟩) (fun y hy => h.2 y (Finset.mem_of_mem_erase hy))noncomputable def pk2_co {α : Type*} [DecidableEq α] [Nonempty α] (u : Fin 2 → α → ℝ) : List (Fin 2) → Finset α → Fin 2 → Finset α | [], _, _ => ∅ | l :: r, T, i => (if l = i then {pk2_amin (u (pk2_oth l)) T} else ∅) ∪ pk2_co u r (T.erase (pk2_amin (u (pk2_oth l)) T)) inoncomputable def pk2_lo {α : Type*} [DecidableEq α] [Nonempty α] (u : Fin 2 → α → ℝ) : List (Fin 2) → Finset α → α | [], T => Classical.epsilon (· ∈ T) | l :: r, T => pk2_lo u r (T.erase (pk2_amin (u (pk2_oth l)) T))sectionvariable {α : Type*} [DecidableEq α] [Nonempty α] (u : Fin 2 → α → ℝ)theorem pk2_co_subset : ∀ (r : List (Fin 2)) (T : Finset α) (i : Fin 2), r.length ≤ T.card → pk2_co u r T i ⊆ T | [], T, i, _ => by simp [pk2_co] | l :: r, T, i, h => by have hT : T.Nonempty := Finset.card_pos.mp (by simp at h; omega) have he := (pk2_amin_spec (u (pk2_oth l)) T hT).1 have ih := pk2_co_subset r (T.erase (pk2_amin (u (pk2_oth l)) T)) i (by rw [Finset.card_erase_of_mem he]; simp at h; omega) simp only [pk2_co] apply Finset.union_subset · split_ifs <;> simp [he] · exact ih.trans (Finset.erase_subset _ _)theorem pk2_co_disj : ∀ (r : List (Fin 2)) (T : Finset α), r.length ≤ T.card → Disjoint (pk2_co u r T 0) (pk2_co u r T 1) | [], T, _ => by simp [pk2_co] | l :: r, T, h => by have hT : T.Nonempty := Finset.card_pos.mp (by simp at h; omega) simp only [pk2_co] set e := pk2_amin (u (pk2_oth l)) T have he : e ∈ T := (pk2_amin_spec (u (pk2_oth l)) T hT).1 have hc : r.length ≤ (T.erase e).card := by rw [Finset.card_erase_of_mem he]; simp at h; omega have ih := pk2_co_disj r (T.erase e) hc have s0 := pk2_co_subset u r (T.erase e) 0 hc have s1 := pk2_co_subset u r (T.erase e) 1 hc have n0 : e ∉ pk2_co u r (T.erase e) 0 := fun h' => by simpa using s0 h' have n1 : e ∉ pk2_co u r (T.erase e) 1 := fun h' => by simpa using s1 h' have hl : l = 0 ∨ l = 1 := by fin_cases l <;> simp rcases hl with rfl | rfl <;> simp [Finset.disjoint_union_left, Finset.disjoint_union_right, ih, n0, n1]theorem pk2_co_union : ∀ (r : List (Fin 2)) (T : Finset α), r.length = T.card → pk2_co u r T 0 ∪ pk2_co u r T 1 = T | [], T, h => by simp at h; simp [pk2_co, Finset.card_eq_zero.mp h.symm] | l :: r, T, h => by have hT : T.Nonempty := Finset.card_pos.mp (by simp at h; omega) simp only [pk2_co] set e := pk2_amin (u (pk2_oth l)) T have he : e ∈ T := (pk2_amin_spec (u (pk2_oth l)) T hT).1 have hc : r.length = (T.erase e).card := by rw [Finset.card_erase_of_mem he]; simp at h; omega have ih := pk2_co_union r (T.erase e) hc have key : insert e (T.erase e) = T := Finset.insert_erase he have hl : l = 0 ∨ l = 1 := by fin_cases l <;> simp rcases hl with rfl | rfl · simp only [if_true, show ¬ ((0 : Fin 2) = 1) by decide, if_false, Finset.empty_union] rw [Finset.union_assoc, ih, ← Finset.insert_eq, key] · simp only [if_true, show ¬ ((1 : Fin 2) = 0) by decide, if_false, Finset.empty_union] rw [Finset.union_left_comm, ih, ← Finset.insert_eq, key]theorem pk2_lo_mem : ∀ (r : List (Fin 2)) (T : Finset α), T.card = r.length + 1 → pk2_lo u r T ∈ T | [], T, h => by simp only [pk2_lo] obtain ⟨a, ha⟩ := Finset.card_eq_one.mp (by simpa using h) exact Classical.epsilon_spec (p := (· ∈ T)) ⟨a, by simp [ha]⟩ | l :: r, T, h => by have hT : T.Nonempty := Finset.card_pos.mp (by omega) have he := (pk2_amin_spec (u (pk2_oth l)) T hT).1 simp only [pk2_lo] exact Finset.mem_of_mem_erase (pk2_lo_mem r _ (by rw [Finset.card_erase_of_mem he]; simp at h ⊢; omega))variable (hinj : ∀ j, Function.Injective (u j))include hinjtheorem pk2_co_append (p : Fin 2) : ∀ (r : List (Fin 2)) (T : Finset α) (i : Fin 2), T.card = r.length + 1 → pk2_co u (r ++ [p]) T i = pk2_co u r (T.erase (pk2_lo u r T)) i ∪ (if p = i then {pk2_lo u r T} else ∅) | [], T, i, h => by obtain ⟨a, ha⟩ := Finset.card_eq_one.mp (by simpa using h) subst ha have h1 : pk2_amin (u (pk2_oth p)) {a} = a := by have := (pk2_amin_spec (u (pk2_oth p)) {a} (by simp)).1 simpa using this have h2 : pk2_lo u [] {a} = a := by simp only [pk2_lo] have := Classical.epsilon_spec (p := (· ∈ ({a} : Finset α))) ⟨a, by simp⟩ simpa using this simp [pk2_co, h1, h2] | l :: r, T, i, h => by have hT : T.Nonempty := Finset.card_pos.mp (by omega) set e := pk2_amin (u (pk2_oth l)) T with he_def have he : e ∈ T := (pk2_amin_spec (u (pk2_oth l)) T hT).1 have hc : (T.erase e).card = r.length + 1 := by rw [Finset.card_erase_of_mem he]; simp at h; omega have ih := pk2_co_append p r (T.erase e) i hc have hL : pk2_lo u (l :: r) T = pk2_lo u r (T.erase e) := by simp only [pk2_lo, e] have hLmem := pk2_lo_mem u r (T.erase e) hc have hLe : pk2_lo u r (T.erase e) ≠ e := (Finset.mem_erase.mp hLmem).1 have hamin : pk2_amin (u (pk2_oth l)) (T.erase (pk2_lo u r (T.erase e))) = e := pk2_amin_erase _ (hinj _) T hT _ hLe rw [List.cons_append] simp only [pk2_co] rw [← he_def, ih, hL, hamin, Finset.erase_right_comm, Finset.union_assoc]/-- the mover's bundle after choosing `y` with the crossout continuation -/noncomputable def pk2_B (r : List (Fin 2)) (T : Finset α) (p : Fin 2) (y : α) : Finset α := insert y (pk2_co u r (T.erase y) p)omit hinj intheorem pk2_B_sub (r : List (Fin 2)) (T : Finset α) (p : Fin 2) (y : α) (hy : y ∈ T) (h : T.card = r.length + 1) : pk2_B u r T p y ⊆ T ∧ y ∉ pk2_co u r (T.erase y) p := by have hs := pk2_co_subset u r (T.erase y) p (by rw [Finset.card_erase_of_mem hy]; omega) refine ⟨Finset.insert_subset hy (hs.trans (Finset.erase_subset _ _)), fun h' => by simpa using hs h'⟩theorem pk2_exchange (p : Fin 2) : ∀ (r : List (Fin 2)) (T : Finset α) (y : α), T.card = r.length + 1 → y ∈ T → (∑ z ∈ pk2_B u r T p y, u p z) < (∑ z ∈ pk2_B u r T p (pk2_lo u r T), u p z) ∨ pk2_B u r T p y = pk2_B u r T p (pk2_lo u r T) | [], T, y, h, hy => by right obtain ⟨a, ha⟩ := Finset.card_eq_one.mp (by simpa using h) subst ha have h2 : pk2_lo u [] {a} = a := by simp only [pk2_lo] have := Classical.epsilon_spec (p := (· ∈ ({a} : Finset α))) ⟨a, by simp⟩ simpa using this rw [h2, Finset.mem_singleton.mp hy] | l :: r, T, y, h, hy => by have hT : T.Nonempty := ⟨y, hy⟩ set e := pk2_amin (u (pk2_oth l)) T with he_def have hspec := pk2_amin_spec (u (pk2_oth l)) T hT have he : e ∈ T := hspec.1 set T' := T.erase e with hT' have hc : T'.card = r.length + 1 := by rw [hT', Finset.card_erase_of_mem he]; simp at h; omega set L := pk2_lo u r T' with hLdef have hL : pk2_lo u (l :: r) T = L := by simp only [pk2_lo, e, T', L] have hLmem : L ∈ T' := pk2_lo_mem u r T' hc have hLe : L ≠ e := (Finset.mem_erase.mp hLmem).1 -- B for an item z ≠ e have hBz : ∀ z ∈ T, z ≠ e → pk2_B u (l :: r) T p z = if l = p then insert e (pk2_B u r T' p z) else pk2_B u r T' p z := by intro z hz hze have ham : pk2_amin (u (pk2_oth l)) (T.erase z) = e := pk2_amin_erase _ (hinj _) T hT _ hze simp only [pk2_B, pk2_co, ham] rw [Finset.erase_right_comm] split_ifs · rw [Finset.singleton_union, Finset.insert_comm] · rw [Finset.empty_union] have hBsub : ∀ z ∈ T', pk2_B u r T' p z ⊆ T' := fun z hz => (pk2_B_sub u r T' p z hz hc).1 have heB : ∀ z ∈ T', e ∉ pk2_B u r T' p z := fun z hz h' => by have := hBsub z hz h'; simp [T'] at this rw [hL, hBz L (Finset.mem_of_mem_erase hLmem) hLe] by_cases hye : y ≠ e · have hyT' : y ∈ T' := Finset.mem_erase.mpr ⟨hye, hy⟩ rw [hBz y hy hye] rcases pk2_exchange p r T' y hc hyT' with hlt | heq · left split_ifs · rw [Finset.sum_insert (heB y hyT'), Finset.sum_insert (heB L hLmem)]; linarith · exact hlt · right; rw [heq] · push Not at hye subst hye set e' := pk2_amin (u (pk2_oth l)) T' with he'_def have hT'ne : T'.Nonempty := ⟨L, hLmem⟩ have he' : e' ∈ T' := (pk2_amin_spec (u (pk2_oth l)) T' hT'ne).1 have hBe : pk2_B u (l :: r) T p e = insert e (if l = p then pk2_B u r T' p e' else pk2_co u r (T'.erase e') p) := by simp only [pk2_B, pk2_co, ← hT', ← he'_def] split_ifs · rw [Finset.singleton_union] · rw [Finset.empty_union] rw [hBe] by_cases hlp : l = p · simp only [hlp, if_true] by_cases he'L : e' = L · right; rw [he'L] · have he'T : e' ∈ T' := he' rcases pk2_exchange p r T' e' hc he'T with hlt | heq · left rw [Finset.sum_insert (heB e' he'T), Finset.sum_insert (heB L hLmem)]; linarith · right; rw [heq] · simp only [hlp, if_false] have hop : pk2_oth l = p := pk2_oth_of_ne l p hlp left have he'sub := pk2_B_sub u r T' p e' he' hc have heco : e ∉ pk2_co u r (T'.erase e') p := fun h' => by have := pk2_co_subset u r (T'.erase e') p (by rw [Finset.card_erase_of_mem he']; omega) h' simp [T'] at this rw [Finset.sum_insert heco] have hlt1 : u p e < u p e' := by have hle : u (pk2_oth l) e ≤ u (pk2_oth l) e' := hspec.2 e' (Finset.mem_of_mem_erase he') rw [hop] at hle have hne : e' ≠ e := (Finset.mem_erase.mp he').1 exact lt_of_le_of_ne hle (fun h' => hne ((hinj p) h').symm) have hB' : (∑ z ∈ pk2_B u r T' p e', u p z) = u p e' + ∑ z ∈ pk2_co u r (T'.erase e') p, u p z := by rw [pk2_B, Finset.sum_insert he'sub.2] have hle2 : (∑ z ∈ pk2_B u r T' p e', u p z) ≤ ∑ z ∈ pk2_B u r T' p L, u p z := by rcases pk2_exchange p r T' e' hc he' with hlt | heq · exact hlt.le · rw [heq] linarithendsectionvariable {α : Type*} [DecidableEq α] [Nonempty α] (u : Fin 2 → α → ℝ)theorem pk2_compl (r : List (Fin 2)) (T : Finset α) (h : r.length = T.card) : T \ pk2_co u r T 0 = pk2_co u r T 1 ∧ T \ pk2_co u r T 1 = pk2_co u r T 0 := by have hu := pk2_co_union u r T h have hd := pk2_co_disj u r T h.le have e0 : T \ pk2_co u r T 0 = (pk2_co u r T 0 ∪ pk2_co u r T 1) \ pk2_co u r T 0 := by rw [hu] have e1 : T \ pk2_co u r T 1 = (pk2_co u r T 0 ∪ pk2_co u r T 1) \ pk2_co u r T 1 := by rw [hu] constructor · rw [e0, Finset.union_sdiff_left, Finset.sdiff_eq_self_of_disjoint hd.symm] · rw [e1, Finset.union_sdiff_right, Finset.sdiff_eq_self_of_disjoint hd]theorem pk2_co0_eq (r : List (Fin 2)) (T : Finset α) (y : α) (hy : y ∈ T) (h : T.card = r.length + 1) : pk2_co u r (T.erase y) 0 = T \ pk2_B u r T 1 y := by have hc : r.length = (T.erase y).card := by rw [Finset.card_erase_of_mem hy]; omega rw [pk2_B, Finset.sdiff_insert, ← Finset.erase_sdiff_comm, (pk2_compl u r _ hc).2]theorem pk2_sdiff_co0 (r : List (Fin 2)) (T : Finset α) (y : α) (hy : y ∈ T) (h : T.card = r.length + 1) : T \ pk2_co u r (T.erase y) 0 = pk2_B u r T 1 y := by have hc : r.length = (T.erase y).card := by rw [Finset.card_erase_of_mem hy]; omega have hs := pk2_co_subset u r (T.erase y) 0 hc.le have hy0 : y ∉ pk2_co u r (T.erase y) 0 := fun h' => by simpa using hs h' have e : T \ pk2_co u r (T.erase y) 0 = insert y (T.erase y) \ pk2_co u r (T.erase y) 0 := by rw [Finset.insert_erase hy] rw [e, Finset.insert_sdiff_of_notMem _ hy0, (pk2_compl u r _ hc).1, pk2_B]endtheorem pk2_spe_eq {n : ℕ} [Nonempty (Fin n)] (u : Fin 2 → Fin n → ℝ) (hinj : ∀ j, Function.Injective (u j)) (s : List (Fin 2)) (F : List (Fin n) → Finset (Fin n)) (hF : pick_game_is_spe u s F) : ∀ k, ∀ h : List (Fin n), h.Nodup → h.length + k = n → F h = pk2_co u (s.drop h.length).reverse (Finset.univ \ h.toFinset) 0 := by have hs : s.length = n := hF.1 intro k induction k with | zero => intro h hnd hlen have hspe := hF.2 h hnd simp only at hspe have hcard : h.toFinset.card = n := by rw [List.toFinset_card_of_nodup hnd]; omega have huniv : h.toFinset = Finset.univ := Finset.eq_univ_of_card _ (by simpa using hcard) rw [huniv, Finset.sdiff_self] at hspe ⊢ rw [if_neg (by simp)] at hspe rw [hspe.2, List.drop_eq_nil_of_le (by omega)] simp [pk2_co] | succ k ih => intro h hnd hlen have hspe := hF.2 h hnd simp only at hspe set R := Finset.univ \ h.toFinset with hR have hRcard : R.card = k + 1 := by rw [hR, Finset.card_sdiff_of_subset (Finset.subset_univ _), Finset.card_univ, Fintype.card_fin, List.toFinset_card_of_nodup hnd] omega have hRne : R.Nonempty := Finset.card_pos.mp (by omega) obtain ⟨-, hif⟩ := hspe rw [if_pos hRne] at hif obtain ⟨x, hxR, hFx, hmax⟩ := hif have hlt : h.length < s.length := by omega set p := s.getD h.length 0 with hp have hp' : s[h.length] = p := by rw [hp, List.getD_eq_getElem _ _ hlt] set r' := (s.drop (h.length + 1)).reverse with hr' have hr'len : r'.length = k := by simp [hr']; omega have hdrop : (s.drop h.length).reverse = r' ++ [p] := by rw [List.drop_eq_getElem_cons hlt, List.reverse_cons, hp'] -- continuation after each move have hcont : ∀ y ∈ R, F (h ++ [y]) = pk2_co u r' (R.erase y) 0 := by intro y hy have hyh : y ∉ h := by simpa [hR] using hy have hnd' : (h ++ [y]).Nodup := hnd.append (List.nodup_singleton y) (List.disjoint_singleton.mpr hyh) rw [ih (h ++ [y]) hnd' (by simp only [List.length_append, List.length_singleton]; omega)] congr 1 · simp [hr'] · rw [hR, List.toFinset_append]; ext z; simp have hpay : ∀ y ∈ R, pick_game_move_payoff u s F h y = ∑ z ∈ pk2_B u r' R p y, u p z := by intro y hy simp only [pick_game_move_payoff, pick_game_move_zero, ← hp, ← hR, hcont y hy] by_cases hp0 : p = 0 · simp only [hp0, if_true, pk2_B] · have hp1 : p = 1 := pk2_fin2 p hp0 simp only [hp0, if_false] rw [pk2_sdiff_co0 u r' R y hy (by omega), hp1] set L := pk2_lo u r' R have hLmem : L ∈ R := pk2_lo_mem u r' R (by omega) have hB : pk2_B u r' R p x = pk2_B u r' R p L := by rcases pk2_exchange u hinj p r' R x (by omega) hxR with hlt' | heq · have := hmax L hLmem rw [hpay L hLmem, hpay x hxR] at this linarith · exact heq rw [hFx, hdrop, pk2_co_append u hinj p r' R 0 (by omega)] simp only [pick_game_move_zero, ← hp, hcont x hxR] by_cases hp0 : p = 0 · have := hB simp only [hp0, pk2_B] at this simp only [hp0, if_true] rw [this, Finset.union_comm, ← Finset.insert_eq] · have hp1 : p = 1 := pk2_fin2 p hp0 simp only [hp0, if_false, Finset.union_empty] rw [pk2_co0_eq u r' R x hxR (by omega), pk2_co0_eq u r' R L hLmem (by omega), ← hp1, hB]theorem pk2_crossout_link {n : ℕ} [Nonempty (Fin n)] (u : Fin 2 → Fin n → ℝ) (hinj : ∀ j, Function.Injective (u j)) (s : List (Fin 2)) (π : Fin n → Fin n) (hπ : picking_reverse_crossout_valid u s π) (i : Fin 2) : ∀ m, m ≤ n → pk2_co u (s.reverse.drop (n - m)) ((Finset.univ.filter fun t : Fin n => n - m ≤ t.val).image π) i = (Finset.univ.filter fun t : Fin n => n - m ≤ t.val ∧ s.reverse.getD t.val 0 = i).image π := by obtain ⟨hs, hbij, hval⟩ := hπ have hrl : s.reverse.length = n := by simp [hs] intro m induction m with | zero => intro _ rw [Nat.sub_zero, List.drop_eq_nil_of_le (by omega)] have : (Finset.univ.filter fun t : Fin n => n ≤ t.val ∧ s.reverse.getD t.val 0 = i) = ∅ := by ext t; simp rw [this]; simp [pk2_co] | succ m ih => intro hm have ih' := ih (by omega) set t0 := n - (m + 1) with ht0 have ht0lt : t0 < n := by omega set T0 : Fin n := ⟨t0, ht0lt⟩ have hdrop : s.reverse.drop t0 = s.reverse[t0] :: s.reverse.drop (n - m) := by rw [List.drop_eq_getElem_cons (by omega)]; congr 2; omega have hget : s.reverse.getD t0 0 = s.reverse[t0] := List.getD_eq_getElem _ _ (by omega) set T := (Finset.univ.filter fun t : Fin n => t0 ≤ t.val).image π with hT have hamin : pk2_amin (u (pk2_oth s.reverse[t0])) T = π T0 := by apply pk2_amin_eq _ (hinj _) · exact Finset.mem_image.mpr ⟨T0, by simp [T0], rfl⟩ · intro y hy obtain ⟨j, hj, rfl⟩ := Finset.mem_image.mp hy simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hj rcases Nat.eq_or_lt_of_le hj with h' | h' · have : T0 = j := Fin.ext h' rw [this] · have := hval T0 j (by simp [Fin.lt_def, T0]; omega) simp only [T0] at this rw [hget] at this simpa [pk2_oth] using this have herase : T.erase (π T0) = (Finset.univ.filter fun t : Fin n => n - m ≤ t.val).image π := by rw [hT, ← Finset.image_erase hbij.1] congr 1 ext t; simp [Fin.ext_iff, T0]; omega rw [hdrop] simp only [pk2_co] rw [hamin, herase, ih'] ext z simp only [Finset.mem_union, Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and] constructor · rintro (hz | ⟨t, ⟨ht1, ht2⟩, rfl⟩) · split_ifs at hz with hi · rw [Finset.mem_singleton] at hz exact ⟨T0, ⟨le_refl _, by show s.reverse.getD t0 0 = i; rw [hget, hi]⟩, hz.symm⟩ · simp at hz · exact ⟨t, ⟨by omega, ht2⟩, rfl⟩ · rintro ⟨t, ⟨ht1, ht2⟩, rfl⟩ rcases Nat.eq_or_lt_of_le ht1 with h' | h' · left have : T0 = t := Fin.ext h' subst this have hi : s.reverse[t0] = i := by rw [← hget]; exact ht2 simp [hi] · right; exact ⟨t, ⟨by omega, ht2⟩, rfl⟩theorem picking_two_agent_spe_eq_reverse_crossout (n : ℕ) (u : Fin 2 → Fin n → ℝ) (s : List (Fin 2)) (π : Fin n → Fin n) (F : List (Fin n) → Finset (Fin n)) (hu : ∀ i x, 0 < u i x) (hd : ∀ i x y, x ≠ y → u i x ≠ u i y) (hπ : picking_reverse_crossout_valid u s π) (hF : pick_game_is_spe u s F) : picking_reverse_crossout_allocation s π = pick_game_root_allocation F := by rcases Nat.eq_zero_or_pos n with rfl | hn · funext i; ext x; exact x.elim0 haveI : Nonempty (Fin n) := ⟨⟨0, hn⟩⟩ have hinj : ∀ j, Function.Injective (u j) := fun j x y hxy => by by_contra hne; exact hd j x y hne hxy have hs : s.length = n := hπ.1 have hroot := pk2_spe_eq u hinj s F hF n [] List.nodup_nil (by simp) simp only [List.length_nil, List.drop_zero, List.toFinset_nil, Finset.sdiff_empty] at hroot have hlink := pk2_crossout_link u hinj s π hπ funext i have hl := hlink i n le_rfl simp only [Nat.sub_self, List.drop_zero, zero_le, true_and, Finset.filter_true_of_mem, Finset.mem_univ, implies_true] at hl rw [Finset.image_univ_of_surjective hπ.2.1.2] at hl unfold picking_reverse_crossout_allocation pick_game_root_allocation rw [← hl] split_ifs with hi · subst hi; exact hroot.symm · have hi1 : i = 1 := pk2_fin2 i hi subst hi1 rw [hroot, (pk2_compl u s.reverse Finset.univ (by simp [hs])).1]