round_robin_pne_ef1_pair_of_count_le_two
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
- is_picking_sequence_pneA profile of reported strict rankings is a pure Nash equilibrium of the picking-sequence mechanism if no agent can obtain a bundle of…
- picking_sequence_outcomeThe allocation returned by the picking-sequence mechanism PS_π: agents act in the order seq, and at each turn the active agent takes its…
- round_robin_sequenceThe Round-Robin picking sequence (1, 2, ..., n, 1, 2, ...) of length m, with agents numbered 0, ..., n-1.
- SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuationLift an additive valuation to an abstract
Valuation.(w.toValuation).val i S = Σ_{g ∈ S} w.weight i g. - round_robin_pne_ef1_of_card_le_two_mulWith n agents and at most 2n goods (every agent picks at most twice), every pure Nash equilibrium of Round-Robin, for nonnegative additive…
- SocialChoice.FairDivision.Indivisible.ValuationAn abstract valuation assigns a real value to each agent-bundle pair.
val i Sis the value agentiassigns to bundleS. Lives in… - SocialChoice.FairDivision.Indivisible.AdditiveValuationAn additive valuation is determined by per-item weights.
weight i gis the value agentiassigns to goodgindividually. The bundle… - picking_turnOne turn of a picking-sequence mechanism: the active agent i receives the first good of its reported ranking l (best first) that is not…
- Used by 3
- round_robin_three_agents_seven_goods_pne_ef1With three agents and seven goods, every pure Nash equilibrium of Round-Robin (nonnegative additive valuations) is EF1; so the eight-good…
- round_robin_pne_ef1_of_card_le_two_mul_add_oneWith n agents and at most 2n + 1 goods, every pure Nash equilibrium of Round-Robin (nonnegative additive valuations) is EF1. For three…
- round_robin_pne_envy_zero_ef1_of_two_mul_add_oneWith n agents and 2n + 1 goods, in every pure Nash equilibrium of Round-Robin (nonnegative additive valuations) every agent i ≠ 0 is EF1…
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.
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.
uses
Finset.sum_nonnegsimp 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)
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).
uses
Finset.card_le_one.mp,Finset.sum_emptyby_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 _
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.
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_lengthrw [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
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.
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
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.
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
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.
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
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`.
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]
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.
uses
Finset.single_le_sumhave 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
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 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