AFTD Auto-Formalizing Theoretical Domains

picking_reverse_crossout_exists

theoremverified

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.

  1. 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.

    lines 6–11

    uses Finset.card_eq_zero

      induction' k with k ih
      · intro s hs g
        rw [Finset.card_eq_zero] at hs
        subst hs
        use []
        simp
  2. 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.

    lines 12–20

    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))
  3. 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.

    lines 21–29

    uses List.mem_toFinset.mpr, Finset.mem_erase, List.toFinset_cons, Finset.insert_erase, List.nodup_cons.mpr

        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, ?_⟩
  4. 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']).

    lines 30–42

    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_erase

        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
  5. 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, ·).

    lines 43–50

    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'
  6. 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.

    lines 54–60

    uses picking_reverse_crossout_exists_list_min_order, Finset.card_fin, List.toFinset_card_of_nodup

      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 π
  7. 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.

    lines 61–66

    uses Finite.injective_iff_bijective.mp, List.Nodup.get_inj_iff, Fin.ext, Fin.mk.inj

      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)
  8. 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.

    lines 67–72

      · 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.

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

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
See it in the graphDiscuss this resultChallenge it