picking_reverse_crossout_exists
For any finite number of items, any two real-valued item functions, and any picking sequence of matching length, there is a valid reverse crossout sequence.
Statement
theorem picking_reverse_crossout_exists (n : ℕ) (u : Fin 2 → Fin n → ℝ) (s : List (Fin 2)) (hs : s.length = n) :
∃ π : Fin n → Fin n, picking_reverse_crossout_valid u s π- Source
- Reverse crossout representation of two-agent sequential picking; see https://cdn.aaai.org/ojs/8697/8697-13-12225-1-2-20201228.pdf Theorem 1.
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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…
- 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…
The proof, explained
The theorem shows that for any picking sequence of length n and any two agent utility functions, a valid reverse crossout sequence exists. The argument first proves an auxiliary lemma by induction on set size: for any sequence of item evaluation functions, items can be greedily arranged into a list where each element minimizes the current evaluation function among all remaining elements. Applying this lemma to the full set of n items with evaluation functions defined by the opponent's utility at each reversed turn yields a duplicate-free list of length n, which directly induces the required bijective reverse crossout permutation.
The greedy ordering lemma holds when the set s is empty (k = 0).
We proceed by induction on the set size k. In the base case k = 0, the assumption |s| = 0 implies s = ∅ by Finset.card_eq_zero. The empty list has no duplicates, its set of elements is empty, and the ordering condition is vacuously satisfied since no index j satisfies j < 0.
uses
Finset.card_eq_zeroinduction' k with k ih · intro s hs g rw [Finset.card_eq_zero] at hs subst hs use [] simp
In the inductive step with |s| = k + 1, there exists a minimal element x ∈ s under g(0, ·), and the induction hypothesis applies to s \ {x}.
Since |s| = k + 1 > 0, the set s is nonempty by Finset.card_pos and Nat.succ_pos. By Finset.exists_min_image, we pick an element x ∈ s minimizing g(0, ·) on s. Removing x leaves s' = s \ {x} with |s'| = k (via Finset.card_erase_of_mem and Nat.succ_sub_one). We apply the induction hypothesis to s' using the shifted cost functions t ↦ g(t + 1, ·), obtaining a duplicate-free list l' of all elements of s' satisfying the greedy ordering condition for the shifted functions.
uses
Finset.card_pos,Nat.succ_pos,Finset.exists_min_image,Finset.card_erase_of_mem,Nat.succ_sub_one· intro s hs g have hne : s.Nonempty := by rw [← Finset.card_pos, hs] exact Nat.succ_pos k obtain ⟨x, hx, hxmin⟩ := Finset.exists_min_image s (g 0) hne let s' := s.erase x have hs' : s'.card = k := by rw [Finset.card_erase_of_mem hx, hs, Nat.succ_sub_one] obtain ⟨l', hnodup', htoFinset', horder'⟩ := ih s' hs' (fun t => g (t + 1))
Prepending x to l' yields a duplicate-free list x :: l' whose elements are exactly s.
Because x was erased from s, it does not belong to s' = l'.toFinset (by List.mem_toFinset.mpr and Finset.mem_erase), so x ∉ l'. Thus x :: l' has no duplicates by List.nodup_cons.mpr. Furthermore, List.toFinset_cons and Finset.insert_erase show that the elements of x :: l' form {x} ∪ (s \ {x}) = s.
uses
List.mem_toFinset.mpr,Finset.mem_erase,List.toFinset_cons,Finset.insert_erase,List.nodup_cons.mprhave hx_not_mem : x ∉ l' := by intro h have : x ∈ l'.toFinset := List.mem_toFinset.mpr h rw [htoFinset', Finset.mem_erase] at this exact this.1 rfl have htoFinset : (x :: l').toFinset = s := by rw [List.toFinset_cons, htoFinset', Finset.insert_erase hx] have hnodup : (x :: l').Nodup := List.nodup_cons.mpr ⟨hx_not_mem, hnodup'⟩ refine ⟨x :: l', hnodup, htoFinset, ?_⟩
The ordering condition g(t, (x :: l')[t]) ≤ g(t, (x :: l')[j]) holds when t = 0.
Given indices t < j < length(x :: l'), we consider the case t = 0. Since 0 < j, we have j = j' + 1 for some j' < length(l') by Nat.exists_eq_succ_of_ne_zero, ne_of_gt, and Nat.succ_lt_succ_iff.mp. The 0-th element of x :: l' is x, while the (j' + 1)-th element is l'[j']. Since l'[j'] ∈ l' (by List.get_mem and List.mem_toFinset.mpr), it belongs to s' and therefore to s by Finset.mem_of_mem_erase. Because x minimizes g(0, ·) across all of s, g(0, x) ≤ g(0, l'[j']).
uses
Nat.exists_eq_succ_of_ne_zero,ne_of_gt,Nat.succ_lt_succ_iff.mp,List.get_mem,List.mem_toFinset.mpr,Finset.mem_of_mem_eraseintro t j htj hj cases t with | zero => obtain ⟨j', rfl⟩ := Nat.exists_eq_succ_of_ne_zero (ne_of_gt htj) have hj' : j' < l'.length := Nat.succ_lt_succ_iff.mp hj have h1 : (x :: l').get ⟨0, htj.trans hj⟩ = x := rfl have h2 : (x :: l').get ⟨j' + 1, hj⟩ = l'.get ⟨j', hj'⟩ := rfl rw [h1, h2] apply hxmin have hmem : l'.get ⟨j', hj'⟩ ∈ l' := List.get_mem l' ⟨j', hj'⟩ have : l'.get ⟨j', hj'⟩ ∈ l'.toFinset := List.mem_toFinset.mpr hmem rw [htoFinset'] at this exact Finset.mem_of_mem_erase this
The ordering condition g(t, (x :: l')[t]) ≤ g(t, (x :: l')[j]) holds when t > 0.
When t = t' + 1, the condition t < j gives 0 < j by Nat.zero_lt_of_lt, so j = j' + 1 with t' < j' < length(l') by Nat.exists_eq_succ_of_ne_zero, ne_of_gt, and Nat.succ_lt_succ_iff.mp. The elements at positions t' + 1 and j' + 1 in x :: l' are l'[t'] and l'[j']. The required inequality g(t' + 1, l'[t']) ≤ g(t' + 1, l'[j']) is then given directly by the ordering property of l' under the shifted evaluation function t ↦ g(t + 1, ·).
uses
Nat.exists_eq_succ_of_ne_zero,ne_of_gt,Nat.zero_lt_of_lt,Nat.succ_lt_succ_iff.mp| succ t' => obtain ⟨j', rfl⟩ := Nat.exists_eq_succ_of_ne_zero (ne_of_gt (Nat.zero_lt_of_lt htj)) have htj' : t' < j' := Nat.succ_lt_succ_iff.mp htj have hj' : j' < l'.length := Nat.succ_lt_succ_iff.mp hj have h1 : (x :: l').get ⟨t' + 1, htj.trans hj⟩ = l'.get ⟨t', htj'.trans hj'⟩ := rfl have h2 : (x :: l').get ⟨j' + 1, hj⟩ = l'.get ⟨j', hj'⟩ := rfl rw [h1, h2] exact horder' t' j' htj' hj'The greedy list ordering lemma yields a list of all n items ordered according to the reverse crossout objective, defining a candidate permutation π.
We define the cost function g(t, x) as the utility of item x to the opponent of the agent acting at step t in the reversed picking sequence s (agent 1 if s_rev[t] = 0, and agent 0 otherwise). Applying picking_reverse_crossout_exists_list_min_order to the full set of items Finset.univ of cardinality n (via Finset.card_fin) produces a duplicate-free list l of all items with the greedy ordering property. Its length is n by List.toFinset_card_of_nodup and Finset.card_fin. We define the candidate permutation π by setting π(t) to be the t-th element of l.
uses
picking_reverse_crossout_exists_list_min_order,Finset.card_fin,List.toFinset_card_of_noduplet g : ℕ → Fin n → ℝ := fun t x => u (if s.reverse.getD t 0 = 0 then 1 else 0) x obtain ⟨l, hnodup, htoFinset, horder⟩ := picking_reverse_crossout_exists_list_min_order n (Finset.univ : Finset (Fin n)) (Finset.card_fin n) g have hlen : l.length = n := by rw [← List.toFinset_card_of_nodup hnodup, htoFinset, Finset.card_fin] let π : Fin n → Fin n := fun t => l.get ⟨t.val, hlen.symm ▸ t.isLt⟩ use π
The candidate map π is a bijection, and the sequence length condition holds.
The picking sequence length hs : s.length = n holds by hypothesis. For π, bijectivity on the finite type Fin n follows from injectivity via Finite.injective_iff_bijective.mp. If π(a) = π(b), then l[a] = l[b]; because l has no duplicates, List.Nodup.get_inj_iff implies that the indices a and b must be equal, which translates to equality in Fin n via Fin.mk.inj and Fin.ext.
uses
Finite.injective_iff_bijective.mp,List.Nodup.get_inj_iff,Fin.ext,Fin.mk.injrefine ⟨hs, ?_, ?_⟩ · apply Finite.injective_iff_bijective.mp intro a b hab dsimp [π] at hab have hinj := (List.Nodup.get_inj_iff hnodup).mp hab exact Fin.ext (Fin.mk.inj hinj)
The permutation π satisfies the reverse crossout greedy inequality.
For any t < j in Fin n, their numerical values satisfy t.val < j.val < length(l). The ordering property of l guarantees that g(t.val, l[t.val]) ≤ g(t.val, l[j.val]). Unfolding the definition of g, this means that the opponent at step t in the reversed sequence evaluates π(t) at least as unfavorably as π(j), which is precisely the reverse crossout validity condition.
· intro t j htj have hj : j.val < l.length := by rw [hlen]; exact j.isLt have htj_val : t.val < j.val := htj have hle := horder t.val j.val htj_val hj dsimp [g] at hle exact hle
Finset.card_eq_zero- A finite set has cardinality 0 if and only if it is empty.
Finset.card_pos- A finite set has strictly positive cardinality if and only if it is nonempty.
Nat.succ_pos- For any natural number n, its successor n + 1 is strictly positive.
Finset.exists_min_image- Any nonempty finite set contains an element that minimizes a given real-valued function.
Finset.card_erase_of_mem- Erasing an element from a finite set decreases its cardinality by 1.
Nat.succ_sub_one- Subtracting 1 from the successor of n yields n.
List.mem_toFinset.mpr- If an element belongs to a list, it belongs to the finite set of that list's elements.
Finset.mem_erase- An element a belongs to s \ {b} if and only if a ≠ b and a ∈ s.
List.toFinset_cons- The set of elements of a :: l is the insertion of a into the set of elements of l.
Finset.insert_erase- Inserting an element into the set obtained by erasing it recovers the original set.
List.nodup_cons.mpr- If a ∉ l and l has no duplicates, then a :: l has no duplicates.
Nat.exists_eq_succ_of_ne_zero- Every non-zero natural number is the successor of some natural number.
ne_of_gt- If b < a, then a ≠ b.
Nat.succ_lt_succ_iff.mp- If a + 1 < b + 1, then a < b.
List.get_mem- The element of a list at any valid index belongs to the list.
Finset.mem_of_mem_erase- If an element belongs to s \ {a}, then it belongs to s.
Nat.zero_lt_of_lt- If a < b for natural numbers, then 0 < b.
picking_reverse_crossout_exists_list_min_order- For any finite set of size k and sequence of evaluation functions g(t, ·), there exists a duplicate-free list of all elements such that earlier elements minimize g(t, ·) compared to all later elements.
Finset.card_fin- The cardinality of the standard finite set Fin n is n.
List.toFinset_card_of_nodup- If a list has no duplicates, its length equals the cardinality of its underlying set of elements.
Finite.injective_iff_bijective.mp- An injective map from a finite type to itself is bijective.
List.Nodup.get_inj_iff- In a duplicate-free list, two indexed elements are equal if and only if their index positions are equal.
Fin.ext- Two elements of Fin n are equal if and only if their underlying natural values are equal.
Fin.mk.inj- If two Fin elements constructed from values and bounds are equal, their underlying values are equal.
- The proof relies on an auxiliary lemma, `picking_reverse_crossout_exists_list_min_order`, which establishes the greedy ordering by induction on the size of the set.
- In step 1, the tactic `simp` closes the base case by discharging all three conjunctions for the empty list simultaneously: nodup holds, the finset is empty, and the index inequality is vacuously true because no natural number satisfies j < 0.
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.
lemma picking_reverse_crossout_exists_list_min_order {α : Type*} [DecidableEq α] (k : ℕ) : ∀ (s : Finset α) (_hs : s.card = k) (g : ℕ → α → ℝ), ∃ l : List α, l.Nodup ∧ l.toFinset = s ∧ ∀ (t j : ℕ) (htj : t < j) (hj : j < l.length), g t (l.get ⟨t, htj.trans hj⟩) ≤ g t (l.get ⟨j, hj⟩) := by induction' k with k ih · intro s hs g rw [Finset.card_eq_zero] at hs subst hs use [] simp · intro s hs g have hne : s.Nonempty := by rw [← Finset.card_pos, hs] exact Nat.succ_pos k obtain ⟨x, hx, hxmin⟩ := Finset.exists_min_image s (g 0) hne let s' := s.erase x have hs' : s'.card = k := by rw [Finset.card_erase_of_mem hx, hs, Nat.succ_sub_one] obtain ⟨l', hnodup', htoFinset', horder'⟩ := ih s' hs' (fun t => g (t + 1)) have hx_not_mem : x ∉ l' := by intro h have : x ∈ l'.toFinset := List.mem_toFinset.mpr h rw [htoFinset', Finset.mem_erase] at this exact this.1 rfl have htoFinset : (x :: l').toFinset = s := by rw [List.toFinset_cons, htoFinset', Finset.insert_erase hx] have hnodup : (x :: l').Nodup := List.nodup_cons.mpr ⟨hx_not_mem, hnodup'⟩ refine ⟨x :: l', hnodup, htoFinset, ?_⟩ intro t j htj hj cases t with | zero => obtain ⟨j', rfl⟩ := Nat.exists_eq_succ_of_ne_zero (ne_of_gt htj) have hj' : j' < l'.length := Nat.succ_lt_succ_iff.mp hj have h1 : (x :: l').get ⟨0, htj.trans hj⟩ = x := rfl have h2 : (x :: l').get ⟨j' + 1, hj⟩ = l'.get ⟨j', hj'⟩ := rfl rw [h1, h2] apply hxmin have hmem : l'.get ⟨j', hj'⟩ ∈ l' := List.get_mem l' ⟨j', hj'⟩ have : l'.get ⟨j', hj'⟩ ∈ l'.toFinset := List.mem_toFinset.mpr hmem rw [htoFinset'] at this exact Finset.mem_of_mem_erase this | succ t' => obtain ⟨j', rfl⟩ := Nat.exists_eq_succ_of_ne_zero (ne_of_gt (Nat.zero_lt_of_lt htj)) have htj' : t' < j' := Nat.succ_lt_succ_iff.mp htj have hj' : j' < l'.length := Nat.succ_lt_succ_iff.mp hj have h1 : (x :: l').get ⟨t' + 1, htj.trans hj⟩ = l'.get ⟨t', htj'.trans hj'⟩ := rfl have h2 : (x :: l').get ⟨j' + 1, hj⟩ = l'.get ⟨j', hj'⟩ := rfl rw [h1, h2] exact horder' t' j' htj' hj'theorem picking_reverse_crossout_exists (n : ℕ) (u : Fin 2 → Fin n → ℝ) (s : List (Fin 2)) (hs : s.length = n) : ∃ π : Fin n → Fin n, picking_reverse_crossout_valid u s π := by let g : ℕ → Fin n → ℝ := fun t x => u (if s.reverse.getD t 0 = 0 then 1 else 0) x obtain ⟨l, hnodup, htoFinset, horder⟩ := picking_reverse_crossout_exists_list_min_order n (Finset.univ : Finset (Fin n)) (Finset.card_fin n) g have hlen : l.length = n := by rw [← List.toFinset_card_of_nodup hnodup, htoFinset, Finset.card_fin] let π : Fin n → Fin n := fun t => l.get ⟨t.val, hlen.symm ▸ t.isLt⟩ use π refine ⟨hs, ?_, ?_⟩ · apply Finite.injective_iff_bijective.mp intro a b hab dsimp [π] at hab have hinj := (List.Nodup.get_inj_iff hnodup).mp hab exact Fin.ext (Fin.mk.inj hinj) · intro t j htj have hj : j.val < l.length := by rw [hlen]; exact j.isLt have htj_val : t.val < j.val := htj have hle := horder t.val j.val htj_val hj dsimp [g] at hle exact hle