AFTD Auto-Formalizing Theoretical Domains

round_robin_pne_ef1_pair_of_count_le_two

theoremverified

In a pure Nash equilibrium of Round-Robin (nonnegative additive valuations), every agent i is EF1 towards every other agent j that appears at most twice in the picking sequence and receives at least one good.

Statement

theorem round_robin_pne_ef1_pair_of_count_le_two (n m : ℕ) [NeZero n]
    (w : Fin n → Fin m → ℝ) (hw : ∀ i g, 0 ≤ w i g) (rank : Fin n → Fin m ≃ Fin m)
    (h : is_picking_sequence_pne
      (SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation ⟨w⟩)
      (round_robin_sequence n m) rank)
    (i j : Fin n) (hij : i ≠ j) (hj : (round_robin_sequence n m).count j ≤ 2)
    (hne : (picking_sequence_outcome (round_robin_sequence n m) rank j).Nonempty) :
    ∃ g ∈ picking_sequence_outcome (round_robin_sequence n m) rank j,
      (SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation ⟨w⟩).val i
          (picking_sequence_outcome (round_robin_sequence n m) rank j \ {g}) ≤
        (SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation ⟨w⟩).val i
          (picking_sequence_outcome (round_robin_sequence n m) rank i)
Source
Step for round_robin_pne_ef1_of_card_le_two_mul_add_one (thread RT-3): the argument of round_robin_pne_ef1_of_card_le_two_mul needs only that j picks at most twice.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
Used by 3

Read back from the Lean

For any natural numbers $n$ and $m$ with $n > 0$, any non-negative weights $w : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$ (with $\forall i, g,\ 0 \le w(i, g)$), and any profile of agent ranking orders $\text{rank} : \text{Fin } n \to (\text{Fin } m \simeq \text{Fin } m)$: If $\text{rank}$ is a pure-strategy Nash equilibrium for the round-robin picking sequence $\text{round\_robin\_sequence } n\ m$ under the additive valuation induced by $w$ (meaning no agent can achieve a higher valuation for their allocated bundle by unilaterally changing their ranking permutation), then for any distinct agents $i, j \in \text{Fin } n$ ($i \ne j$) such that: 1. Agent $j$ appears at most 2 times in the round-robin sequence, and 2. Agent $j$'s allocated bundle under the picking sequence outcome is non-empty, there exists a good $g$ in agent $j$'s allocated bundle such that agent $i$'s valuation of agent $j$'s bundle without $g$ is less than or equal to agent $i$'s valuation of agent $i$'s own allocated bundle (i.e., agent $i$ is envy-free up to one item towards agent $j$).

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 analyzing the size of agent j's bundle A j relative to their turns in the sequence. If |A j| ≤ 1, removing the single good leaves the empty set, which trivially satisfies EF1 since valuations are non-negative. If |A j| > 1, then |A j| = 2 and agent j appears twice, while before agent i's first turn, agent j has received at most one item. This ensures that some item b ∈ A j is completely unallocated when agent i first picks, so agent i could deviate to rank b first and secure it; by pure Nash equilibrium, agent i's bundle must be worth at least as much as this deviation, and removing the other item a ∈ A j leaves {b}, establishing EF1.

  1. Setup notation and establish non-negativity of valuation sums.

    Unfold the additive valuation into sums over bundles, and define shorthand for the round-robin sequence `seq`, the agents' preference lists `L`, the initial empty allocation state `init`, and the resulting bundles `A`. Using `Finset.sum_nonneg`, note that because every individual good has a non-negative weight for agent i, the sum of weights over any subset of goods is non-negative.

    lines 13–20

    uses Finset.sum_nonneg

      simp only [SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation]
      set seq := round_robin_sequence n m with hseq
      set L : Fin n → List (Fin m) := fun a => List.ofFn (rank a) with hL
      set init : (Fin n → Finset (Fin m)) × Finset (Fin m) := (fun _ => ∅, ∅) with hinit
      have hA : ∀ a, picking_sequence_outcome seq rank a =
          (seq.foldl (fun st a => picking_turn (L a) a st) init).1 a := fun a => rfl
      set A := picking_sequence_outcome seq rank with hAdef
      have hpos : ∀ S : Finset (Fin m), 0 ≤ ∑ g ∈ S, w i g := fun S => Finset.sum_nonneg (fun g _ => hw i g)
  2. If agent j receives at most one item, agent i is EF1 towards agent j.

    Perform a case split on whether |A j| ≤ 1. Since A j is assumed nonempty, it contains an item g. Removing g leaves A j \ {g} = ∅ by `Finset.card_le_one.mp`. The value of the empty set is 0 by `Finset.sum_empty`, which is at most the non-negative value v_i(A i).

    lines 21–31

    uses Finset.card_le_one.mp, Finset.sum_empty

      by_cases hc : (A j).card ≤ 1
      · obtain ⟨g, hg⟩ := hne
        refine ⟨g, hg, ?_⟩
        have : A j \ {g} = ∅ := by
          ext x
          simp only [Finset.mem_sdiff, Finset.mem_singleton, Finset.notMem_empty, iff_false, not_and,
            not_not]
          intro hx
          exact Finset.card_le_one.mp hc x hx g hg
        rw [this, Finset.sum_empty]
        exact hpos _
  3. In the case |A j| > 1, agent j receives exactly two items, the number of goods exceeds the number of agents (n < m), and agent i's first turn is within the sequence.

    In the remaining case |A j| > 1, since the number of items received by an agent cannot exceed the number of times they appear in the sequence (`rr_l1_card_foldl`), we have 2 ≤ |A j| ≤ count(j, seq) ≤ 2, so |A j| = 2 and count(j, seq) = 2. If m ≤ n, the entire sequence would be a prefix of length at most n, where every agent appears at most once (`rr_l1_count_take_le_one`), which would force count(j, seq) ≤ 1, a contradiction; hence n < m. Therefore, agent i's first turn occurs at index i < n < m = seq.length.

    lines 32–47

    uses not_le, rr_l1_card_foldl, not_lt, rr_l1_count_take_le_one, le_rfl, List.take_of_length_le, rr_l1_seq_length

      rw [not_le] at hc
      -- the count of `j` in the sequence bounds its bundle
      have hinit_inv : rr_l1_inv init := by
        refine ⟨fun a => by simp [hinit], fun g hg => by simp [hinit] at hg, fun a b _ => by simp [hinit]⟩
      have hcardA : (A j).card ≤ seq.count j := by
        have := rr_l1_card_foldl L seq j init
        simpa [hinit, hA] using this
      have hcount2 : seq.count j ≤ 2 := hj
      -- so agents get their first turn before the sequence ends: n < m
      have hnm : n < m := by
        by_contra hcon
        rw [not_lt] at hcon
        have hle := rr_l1_count_take_le_one n m n le_rfl j
        rw [← hseq, List.take_of_length_le (by rw [hseq, rr_l1_seq_length]; exact hcon)] at hle
        omega
      have hi_lt : i.val < seq.length := by rw [rr_l1_seq_length]; omega
  4. Before agent i's first turn, agent j has received at most one item, and bundle allocations grow monotonically.

    Let st0 be the allocation state right before agent i's first turn (after the prefix `seq.take i.val`). In this prefix of length i < n, agent j appears at most once by `rr_l1_count_take_le_one`, so agent j holds at most one item in st0 by `rr_l1_card_foldl`. Decomposing the sequence into this prefix, turn i, and the suffix, monotonicity (`rr_l1_mono_foldl`) ensures that every agent's bundle at st0 is a subset of their final bundle A.

    lines 48–65

    uses rr_l1_card_foldl, rr_l1_count_take_le_one, List.drop_eq_getElem_cons, List.take_append_drop, Fin.ext, rr_l1_seq_getElem, Nat.mod_eq_of_lt, List.foldl_append, rr_l1_mono_foldl

      -- the state before agent i's first turn
      set st0 := (seq.take i.val).foldl (fun st a => picking_turn (L a) a st) init with hst0
      have hst0_card : (st0.1 j).card ≤ 1 := by
        have h1 := rr_l1_card_foldl L (seq.take i.val) j init
        rw [← hst0] at h1
        have h0 : (init.1 j).card = 0 := by simp [hinit]
        have h2 := rr_l1_count_take_le_one n m i.val i.isLt.le j
        rw [← hseq] at h2
        omega
      have hsplit : seq = seq.take i.val ++ (seq[i.val] :: seq.drop (i.val + 1)) := by
        rw [← List.drop_eq_getElem_cons hi_lt, List.take_append_drop]
      have hseqi : seq[i.val] = i := by
        apply Fin.ext
        rw [rr_l1_seq_getElem, Nat.mod_eq_of_lt i.isLt]
      have hrest : ∀ a, st0.1 a ⊆ A a := by
        intro a
        rw [hA, hsplit, List.foldl_append]
        exact rr_l1_mono_foldl L _ a st0
  5. There exists an item b ∈ A j that is completely unallocated before agent i's first turn.

    Since |A j| ≥ 2 while j has at most one item at st0, there is some item b ∈ A j not held by j at st0. If b were held by any other agent a ≠ j at st0, monotonicity would place b in A a at the end, contradicting the disjointness of bundles in the final state invariant (`rr_l1_inv_foldl`, `Finset.disjoint_left.mp`). Thus b has not been picked by any agent prior to turn i.

    lines 66–84

    uses Finset.card_le_card, rr_l1_inv_foldl, Finset.disjoint_left.mp

      -- a good of `A j` not yet taken before agent i's first turn
      obtain ⟨b, hbA, hb0⟩ : ∃ b ∈ A j, b ∉ st0.1 j := by
        by_contra hcon
        have hsub0 : A j ⊆ st0.1 j := fun x hx => by
          by_contra hx'
          exact hcon ⟨x, hx, hx'⟩
        have := Finset.card_le_card hsub0
        omega
      have hinvA : rr_l1_inv (seq.foldl (fun st a => picking_turn (L a) a st) init) :=
        rr_l1_inv_foldl L seq init hinit_inv
      have hinv0 : rr_l1_inv st0 := rr_l1_inv_foldl L _ init hinit_inv
      have hbfree : b ∉ st0.2 := by
        intro hb
        obtain ⟨a, ha⟩ := hinv0.2.1 b hb
        by_cases haj : a = j
        · subst haj; exact hb0 ha
        · have hd := hinvA.2.2 a j haj
          rw [← hA, ← hA] at hd
          exact Finset.disjoint_left.mp hd (hrest a ha) hbA
  6. If agent i deviates by ranking item b first, agent i is guaranteed to receive item b.

    Consider the deviated ranking r' for agent i that swaps b to the top position using `Equiv.swap`. Because agent i has no turns in the prefix before index i, updating i's ranking leaves the process up to st0 unchanged (`rr_l1_foldl_update`). At turn i, item b is available and ranked highest, so agent i picks b. By monotonicity (`rr_l1_mono_foldl`), b remains in agent i's bundle in the final outcome under this deviation.

    lines 85–117

    uses Equiv.swap, Function.update_of_ne, rr_l1_foldl_update, List.foldl_cons, rr_l1_mono_foldl, List.ofFn_succ, List.find?_cons, Function.update_self, Finset.mem_insert_self, List.mem_iff_getElem.mp, congrArg, List.getElem_take, rr_l1_seq_getElem, List.length_take, Nat.mod_eq_of_lt

      -- the deviation: rank `b` first
      have hm0 : 0 < m := by omega
      set r' : Fin m ≃ Fin m := Equiv.swap ⟨0, hm0⟩ b with hr'
      have hr'0 : r' ⟨0, hm0⟩ = b := by simp [hr']
      have hdev : b ∈ picking_sequence_outcome seq (Function.update rank i r') i := by
        have hL' : (fun st a => picking_turn (List.ofFn (Function.update rank i r' a)) a st) =
            (fun st a => picking_turn (Function.update L i (List.ofFn r') a) a st) := by
          funext st a
          by_cases ha : a = i
          · subst ha; simp
          · simp [Function.update_of_ne ha, hL]
        show b ∈ (seq.foldl (fun st a => picking_turn (List.ofFn (Function.update rank i r' a)) a st) init).1 i
        rw [hL', hsplit, List.foldl_append, rr_l1_foldl_update L _ i _ ?_ init, List.foldl_cons, hseqi]
        · rw [← hst0]
          apply rr_l1_mono_foldl
          obtain ⟨m', rfl⟩ : ∃ m', m = m' + 1 := ⟨m - 1, by omega⟩
          have hfind : (List.ofFn r').find? (fun g => decide (g ∉ st0.2)) = some b := by
            rw [List.ofFn_succ, List.find?_cons]
            have : r' 0 = b := hr'0
            rw [this]
            simp [hbfree]
          simp only [Function.update_self, picking_turn, hfind, Function.update_self]
          exact Finset.mem_insert_self _ _
        · intro x hx
          obtain ⟨t, ht, rfl⟩ := List.mem_iff_getElem.mp hx
          intro hti
          have h1 := congrArg Fin.val hti
          have h2 : ((seq.take i.val)[t]'ht).val = t % n := by
            rw [List.getElem_take]; exact rr_l1_seq_getElem n m t _
          rw [h2] at h1
          simp only [List.length_take] at ht
          rw [Nat.mod_eq_of_lt (by omega)] at h1
          omega
  7. There is another item a ∈ A j distinct from b, and removing a leaves precisely the singleton {b}.

    Because |A j| > 1, there exists an item a ∈ A j distinct from b (`Finset.exists_mem_ne`). Since |A j| ≤ 2, A j contains no elements other than a and b (any third element would make |A j| ≥ 3, impossible by `Finset.card_le_card`). Therefore, removing a yields A j \ {a} = {b} (`Finset.eq_singleton_iff_unique_mem.mpr`), whose valuation is w(i, b) by `Finset.sum_singleton`.

    lines 118–134

    uses Finset.exists_mem_ne, Finset.eq_singleton_iff_unique_mem.mpr, Finset.mem_sdiff, Ne.symm, Finset.card_le_card, Finset.card_insert_of_notMem, Finset.card_singleton, Finset.sum_singleton

      -- conclude with the other good of `A j`
      obtain ⟨a, haA, hab⟩ := Finset.exists_mem_ne hc b
      refine ⟨a, haA, ?_⟩
      have hsub : A j \ {a} = {b} := by
        apply Finset.eq_singleton_iff_unique_mem.mpr
        refine ⟨Finset.mem_sdiff.mpr ⟨hbA, by simpa using Ne.symm hab⟩, fun x hx => ?_⟩
        obtain ⟨hxA, hxa⟩ := Finset.mem_sdiff.mp hx
        by_contra hxb
        have h3 : ({a, b, x} : Finset (Fin m)) ⊆ A j := by
          intro y hy
          simp only [Finset.mem_insert, Finset.mem_singleton] at hy
          rcases hy with rfl | rfl | rfl <;> assumption
        have h4 := Finset.card_le_card h3
        rw [Finset.card_insert_of_notMem (by simp [hab, Ne.symm (show x ≠ a by simpa using hxa)]),
          Finset.card_insert_of_notMem (by simpa using Ne.symm hxb), Finset.card_singleton] at h4
        omega
      rw [hsub, Finset.sum_singleton]
  8. By the Nash equilibrium condition, agent i values their own bundle at least as much as A j \ {a}, satisfying EF1.

    By the pure Nash equilibrium assumption h, agent i's equilibrium valuation v_i(A i) is at least their valuation under the deviation r'. Since all item weights are non-negative, the single item b is worth at most the entire deviated bundle (`Finset.single_le_sum`). Transitivity gives v_i(A j \ {a}) = w(i, b) ≤ v_i(A i), completing the proof.

    lines 135–139

    uses Finset.single_le_sum

      have hpne := h i r'
      simp only [SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation] at hpne
      have hb_le : w i b ≤ ∑ g ∈ picking_sequence_outcome seq (Function.update rank i r') i, w i g :=
        Finset.single_le_sum (fun g _ => hw i g) hdev
      exact hb_le.trans hpne
Finset.sum_nonneg
A finite sum of non-negative elements is non-negative.
Finset.card_le_one.mp
If a finite set has cardinality at most 1, any two elements in it are equal.
Finset.sum_empty
The sum of a function over the empty set is zero.
not_le
For a linear order, not less than or equal is strictly greater than.
rr_l1_card_foldl
In the round-robin process, the number of items allocated to an agent after a sequence of turns is at most their initial bundle size plus the number of times they appear in the sequence.
not_lt
For a linear order, not strictly less than is greater than or equal to.
rr_l1_count_take_le_one
In a round-robin sequence of n agents, any prefix of length at most n contains each agent at most once.
le_rfl
Less than or equal is reflexive: a ≤ a.
List.take_of_length_le
Taking k elements from a list whose length is at most k returns the entire list.
rr_l1_seq_length
The round-robin sequence for n agents and m items has length m.
List.drop_eq_getElem_cons
Dropping i elements from a list of length greater than i yields the i-th element followed by dropping i + 1 elements.
List.take_append_drop
Appending the prefix of length i to the suffix after index i reconstructs the original list.
Fin.ext
Two elements of Fin n are equal if their underlying natural values are equal.
rr_l1_seq_getElem
The agent at index t in the round-robin sequence is t mod n.
Nat.mod_eq_of_lt
For natural numbers a < b, a mod b = a.
List.foldl_append
Folding over an appended list is equivalent to folding over the first part and then folding over the second.
rr_l1_mono_foldl
In the round-robin process, each agent's bundle grows monotonically as further turns are executed.
Finset.card_le_card
If one finite set is a subset of another, its cardinality is less than or equal to the other's cardinality.
rr_l1_inv_foldl
The round-robin state invariant (bundles are pairwise disjoint and contained in the set of allocated items) is preserved under folding turns.
Finset.disjoint_left.mp
If two sets are disjoint and an element belongs to the first, it does not belong to the second.
Equiv.swap
The permutation that swaps two specified elements and leaves all other elements fixed.
Function.update_of_ne
Updating a function at a point a' does not change its value at any distinct point a ≠ a'.
rr_l1_foldl_update
If agent i does not appear in a turn sequence, updating agent i's preference list does not affect the outcome of folding those turns.
List.foldl_cons
Folding over a list with head a and tail l applies the step function to the accumulator and a, then folds over l.
List.ofFn_succ
Converting a function on Fin (n + 1) to a list yields its value at 0 followed by the list of remaining values.
List.find?_cons
Searching for a satisfying element in a non-empty list evaluates the predicate on the head, returning it if true, or continuing to search the tail.
Function.update_self
Evaluating an updated function at the updated point returns the new value.
Finset.mem_insert_self
An element belongs to the set obtained by inserting it into a finite set.
List.mem_iff_getElem.mp
An element is a member of a list if and only if it occurs at some valid 0-based index.
congrArg
Applying a function to equal inputs yields equal outputs.
List.getElem_take
The i-th element of a prefix of length j is the i-th element of the original list.
List.length_take
The length of a prefix of length i is the minimum of i and the list's total length.
Finset.exists_mem_ne
Any finite set with cardinality strictly greater than 1 contains an element distinct from any given element.
Finset.eq_singleton_iff_unique_mem.mpr
A finite set s is equal to the singleton {a} if and only if a ∈ s and every element of s equals a.
Finset.mem_sdiff
An element is in the set difference s \ t if and only if it is in s and not in t.
Ne.symm
Inequality is symmetric: a ≠ b implies b ≠ a.
Finset.card_insert_of_notMem
Inserting an element not in s into s increases its cardinality by 1.
Finset.card_singleton
The cardinality of any singleton set is 1.
Finset.sum_singleton
The sum of a function over a singleton {a} is its value at a.
Finset.single_le_sum
For non-negative terms, any single term in a finite sum is less than or equal to the total sum.

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

theorem round_robin_pne_ef1_pair_of_count_le_two (n m : ℕ) [NeZero n]    (w : Fin n → Fin m → ℝ) (hw : ∀ i g, 0 ≤ w i g) (rank : Fin n → Fin m ≃ Fin m)    (h : is_picking_sequence_pne      (SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation ⟨w⟩)      (round_robin_sequence n m) rank)    (i j : Fin n) (hij : i ≠ j) (hj : (round_robin_sequence n m).count j ≤ 2)    (hne : (picking_sequence_outcome (round_robin_sequence n m) rank j).Nonempty) :    ∃ g ∈ picking_sequence_outcome (round_robin_sequence n m) rank j,      (SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation ⟨w⟩).val i          (picking_sequence_outcome (round_robin_sequence n m) rank j \ {g}) ≤        (SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation ⟨w⟩).val i          (picking_sequence_outcome (round_robin_sequence n m) rank i) := by  simp only [SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation]  set seq := round_robin_sequence n m with hseq  set L : Fin n → List (Fin m) := fun a => List.ofFn (rank a) with hL  set init : (Fin n → Finset (Fin m)) × Finset (Fin m) := (fun _ => ∅, ∅) with hinit  have hA : ∀ a, picking_sequence_outcome seq rank a =      (seq.foldl (fun st a => picking_turn (L a) a st) init).1 a := fun a => rfl  set A := picking_sequence_outcome seq rank with hAdef  have hpos : ∀ S : Finset (Fin m), 0 ≤ ∑ g ∈ S, w i g := fun S => Finset.sum_nonneg (fun g _ => hw i g)  by_cases hc : (A j).card ≤ 1  · obtain ⟨g, hg⟩ := hne    refine ⟨g, hg, ?_⟩    have : A j \ {g} = ∅ := by      ext x      simp only [Finset.mem_sdiff, Finset.mem_singleton, Finset.notMem_empty, iff_false, not_and,        not_not]      intro hx      exact Finset.card_le_one.mp hc x hx g hg    rw [this, Finset.sum_empty]    exact hpos _  rw [not_le] at hc  -- the count of `j` in the sequence bounds its bundle  have hinit_inv : rr_l1_inv init := by    refine ⟨fun a => by simp [hinit], fun g hg => by simp [hinit] at hg, fun a b _ => by simp [hinit]⟩  have hcardA : (A j).card ≤ seq.count j := by    have := rr_l1_card_foldl L seq j init    simpa [hinit, hA] using this  have hcount2 : seq.count j ≤ 2 := hj  -- so agents get their first turn before the sequence ends: n < m  have hnm : n < m := by    by_contra hcon    rw [not_lt] at hcon    have hle := rr_l1_count_take_le_one n m n le_rfl j    rw [← hseq, List.take_of_length_le (by rw [hseq, rr_l1_seq_length]; exact hcon)] at hle    omega  have hi_lt : i.val < seq.length := by rw [rr_l1_seq_length]; omega  -- the state before agent i's first turn  set st0 := (seq.take i.val).foldl (fun st a => picking_turn (L a) a st) init with hst0  have hst0_card : (st0.1 j).card ≤ 1 := by    have h1 := rr_l1_card_foldl L (seq.take i.val) j init    rw [← hst0] at h1    have h0 : (init.1 j).card = 0 := by simp [hinit]    have h2 := rr_l1_count_take_le_one n m i.val i.isLt.le j    rw [← hseq] at h2    omega  have hsplit : seq = seq.take i.val ++ (seq[i.val] :: seq.drop (i.val + 1)) := by    rw [← List.drop_eq_getElem_cons hi_lt, List.take_append_drop]  have hseqi : seq[i.val] = i := by    apply Fin.ext    rw [rr_l1_seq_getElem, Nat.mod_eq_of_lt i.isLt]  have hrest : ∀ a, st0.1 a ⊆ A a := by    intro a    rw [hA, hsplit, List.foldl_append]    exact rr_l1_mono_foldl L _ a st0  -- a good of `A j` not yet taken before agent i's first turn  obtain ⟨b, hbA, hb0⟩ : ∃ b ∈ A j, b ∉ st0.1 j := by    by_contra hcon    have hsub0 : A j ⊆ st0.1 j := fun x hx => by      by_contra hx'      exact hcon ⟨x, hx, hx'⟩    have := Finset.card_le_card hsub0    omega  have hinvA : rr_l1_inv (seq.foldl (fun st a => picking_turn (L a) a st) init) :=    rr_l1_inv_foldl L seq init hinit_inv  have hinv0 : rr_l1_inv st0 := rr_l1_inv_foldl L _ init hinit_inv  have hbfree : b ∉ st0.2 := by    intro hb    obtain ⟨a, ha⟩ := hinv0.2.1 b hb    by_cases haj : a = j    · subst haj; exact hb0 ha    · have hd := hinvA.2.2 a j haj      rw [← hA, ← hA] at hd      exact Finset.disjoint_left.mp hd (hrest a ha) hbA  -- the deviation: rank `b` first  have hm0 : 0 < m := by omega  set r' : Fin m ≃ Fin m := Equiv.swap ⟨0, hm0⟩ b with hr'  have hr'0 : r' ⟨0, hm0⟩ = b := by simp [hr']  have hdev : b ∈ picking_sequence_outcome seq (Function.update rank i r') i := by    have hL' : (fun st a => picking_turn (List.ofFn (Function.update rank i r' a)) a st) =        (fun st a => picking_turn (Function.update L i (List.ofFn r') a) a st) := by      funext st a      by_cases ha : a = i      · subst ha; simp      · simp [Function.update_of_ne ha, hL]    show b ∈ (seq.foldl (fun st a => picking_turn (List.ofFn (Function.update rank i r' a)) a st) init).1 i    rw [hL', hsplit, List.foldl_append, rr_l1_foldl_update L _ i _ ?_ init, List.foldl_cons, hseqi]    · rw [← hst0]      apply rr_l1_mono_foldl      obtain ⟨m', rfl⟩ : ∃ m', m = m' + 1 := ⟨m - 1, by omega⟩      have hfind : (List.ofFn r').find? (fun g => decide (g ∉ st0.2)) = some b := by        rw [List.ofFn_succ, List.find?_cons]        have : r' 0 = b := hr'0        rw [this]        simp [hbfree]      simp only [Function.update_self, picking_turn, hfind, Function.update_self]      exact Finset.mem_insert_self _ _    · intro x hx      obtain ⟨t, ht, rfl⟩ := List.mem_iff_getElem.mp hx      intro hti      have h1 := congrArg Fin.val hti      have h2 : ((seq.take i.val)[t]'ht).val = t % n := by        rw [List.getElem_take]; exact rr_l1_seq_getElem n m t _      rw [h2] at h1      simp only [List.length_take] at ht      rw [Nat.mod_eq_of_lt (by omega)] at h1      omega  -- conclude with the other good of `A j`  obtain ⟨a, haA, hab⟩ := Finset.exists_mem_ne hc b  refine ⟨a, haA, ?_⟩  have hsub : A j \ {a} = {b} := by    apply Finset.eq_singleton_iff_unique_mem.mpr    refine ⟨Finset.mem_sdiff.mpr ⟨hbA, by simpa using Ne.symm hab⟩, fun x hx => ?_⟩    obtain ⟨hxA, hxa⟩ := Finset.mem_sdiff.mp hx    by_contra hxb    have h3 : ({a, b, x} : Finset (Fin m)) ⊆ A j := by      intro y hy      simp only [Finset.mem_insert, Finset.mem_singleton] at hy      rcases hy with rfl | rfl | rfl <;> assumption    have h4 := Finset.card_le_card h3    rw [Finset.card_insert_of_notMem (by simp [hab, Ne.symm (show x ≠ a by simpa using hxa)]),      Finset.card_insert_of_notMem (by simpa using Ne.symm hxb), Finset.card_singleton] at h4    omega  rw [hsub, Finset.sum_singleton]  have hpne := h i r'  simp only [SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation] at hpne  have hb_le : w i b ≤ ∑ g ∈ picking_sequence_outcome seq (Function.update rank i r') i, w i g :=    Finset.single_le_sum (fun g _ => hw i g) hdev  exact hb_le.trans hpne
See it in the graphDiscuss this resultChallenge it