round_robin_two_mul_add_one_deviation_certificate
Round-Robin with n agents and 2n+1 goods, any reports, agent i ≠ 0: for some good g of agent 0's bundle B_0 (its first pick a1), either some deviation r of agent i alone gets i all of B_0 ∖ {g}, or two deviations r1, r2 of agent i give bundles D1, D2 that together cover B_i + (B_0 ∖ {g}) with multiplicity (every good counted in B_i and in B_0 ∖ {g} is counted at least as often in D1 and D2). A valuation-free certificate for EF1 of i towards agent 0 at an equilibrium.
Statement
theorem round_robin_two_mul_add_one_deviation_certificate (n : ℕ) [NeZero n] (rank : Fin n → Fin (2 * n + 1) ≃ Fin (2 * n + 1)) (i : Fin n) (hi : i ≠ 0) : ∃ g ∈ picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) rank 0, (∃ r : Fin (2 * n + 1) ≃ Fin (2 * n + 1), picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) rank 0 \ {g} ⊆ picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) (Function.update rank i r) i) ∨ (∃ r₁ r₂ : Fin (2 * n + 1) ≃ Fin (2 * n + 1), ∀ x : Fin (2 * n + 1), (if x ∈ picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) rank i then 1 else 0) + (if x ∈ picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) rank 0 \ {g} then 1 else 0) ≤ (if x ∈ picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) (Function.update rank i r₁) i then 1 else 0) + (if x ∈ picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) (Function.update rank i r₂) i then 1 else 0 : ℕ))
- Source
- step for round_robin_pne_envy_zero_ef1_of_two_mul_add_one (research thread RT-3, the threshold question from arXiv:2610.23686 Proposition 1)
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 13
- 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.
- picking_prefix_state_alloc_card_eqAfter s turns of a picking sequence with at most as many turns as goods, exactly min s (length seq) goods have been allocated (in…
- picking_prefix_state_alloc_monoThe set of allocated goods is monotone in the number of turns: if s <= t then the goods allocated after s turns are allocated after t turns.
- round_robin_sequence_getElem?_eqThe t-th turn (for t < m) of the Round-Robin sequence of n agents is agent t mod n.
- picking_prefix_state_succ_stepTurn s of a picking sequence with s < length seq and s < m: if the active agent is a, there is a good p, not allocated after s turns, such…
- picking_prefix_state_card_diff_step_of_neSuppose two runs of a picking sequence (differing only in agent i's ranking) have allocated sets at time s that differ in at most one…
- picking_prefix_two_named_first_dev_bundleIn a picking sequence with at most as many turns as goods, suppose agent i acts at turns t1 < t2 and nowhere in between, x is unallocated…
- round_robin_two_mul_add_one_window_traceRound-Robin with n agents and 2n+1 goods: change only agent i's report to r. Then at every time s between i's first turn and i's second…
- round_robin_two_mul_add_one_outcome_structureRound-Robin with n agents and 2n+1 goods, any reports: there are goods a2, a3 (agent 0's picks at turns n and 2n) and b1, b2 (agent i's…
- round_robin_two_mul_add_one_cover_pairsRound-Robin with n agents and 2n+1 goods, agent i ≠ 0: let a1 be agent 0's top-ranked good, a2 and a3 the goods it picks at turns n and…
- picking_sequence_outcome_pairwise_disjointDistinct agents never receive the same good under a picking sequence: the bundles are pairwise disjoint.
- picking_prefix_stateThe state of a picking-sequence run after its first s turns: the bundle map together with the set of already allocated items, obtained by…
- Used by 1
- 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…
The proof, explained
The proof establishes a valuation-free certificate of envy-freeness up to one good (EF1) for agent i against agent 0 by designating agent 0's initial pick a1 as the good to drop, leaving B_0 ∖ {a1} = {a2, a3}. It invokes a structural dichotomy (round_robin_two_mul_add_one_cover_pairs) showing that agent i can either obtain both {a2, a3} with a single deviation, or cover {a2, a3, b1, b2} across two deviations. In the single-deviation case, the remaining bundle B_0 ∖ {a1} is directly covered. In the two-deviation case, because agent i and agent 0 have disjoint bundles, every good in B_i ∪ (B_0 ∖ {a1}) has multiplicity 1, so covering their union pointwise implies covering them with multiplicity via a boolean indicator inequality.
For mutually disjoint propositions P and Q, if P ∨ Q implies R ∨ S, then the sum of their indicator functions is at most the sum of the indicator functions of R and S. automation
By case-splitting on the truth values of P, Q, R, and S, if neither P nor Q holds, the left-hand side is 0 ≤ RHS. If one of P or Q holds (both cannot hold as ¬(P ∧ Q)), the left-hand side is 1; then P ∨ Q holds, which implies R ∨ S, ensuring at least one of R or S holds and the right-hand side is at least 1. Exhaustive truth-table checking via simp_all closes all cases.
private lemma indicator_cover (P Q R S : Prop) [Decidable P] [Decidable Q] [Decidable R] [Decidable S] (hd : ¬(P ∧ Q)) (hc : P ∨ Q → R ∨ S) : (if P then 1 else 0) + (if Q then 1 else 0) ≤ (if R then 1 else 0) + (if S then 1 else 0 : ℕ) := by by_cases hP : P <;> by_cases hQ : Q <;> by_cases hR : R <;> by_cases hS : S <;> simp_all
Agent 0 receives three distinct goods {a1, a2, a3} and agent i receives two distinct goods {b1, b2}.
Applying round_robin_two_mul_add_one_outcome_structure establishes that agent 0's bundle consists of its first pick a1 = rank(0)(0), round-2 pick a2, and round-3 pick a3, while agent i (i ≠ 0) receives two picks b1 and b2.
uses
round_robin_two_mul_add_one_outcome_structureclassical obtain ⟨a2,a3,b1,b2,hf2,hm2,hf3,hm3,hB0,hBi,h02,h03,h23,h12,_,_⟩ := round_robin_two_mul_add_one_outcome_structure n rank i hi let a1 := rank 0 ⟨0,by omega⟩
Removing agent 0's first pick a1 from its bundle leaves exactly the remaining two goods {a2, a3}. automation
Substituting B_0 = {a1, a2, a3} and taking the set difference with {a1} yields {a2, a3}, since a1 is distinct from a2 and a3. Aesop completes the set-theoretic equivalence.
uses
Finset.mem_sdiff,Finset.mem_insert,Finset.mem_singletonhave hremove : picking_sequence_outcome (round_robin_sequence n (2*n+1)) rank 0 \ {a1} = {a2,a3} := by rw [hB0] ext x simp only [Finset.mem_sdiff,Finset.mem_insert,Finset.mem_singleton] dsimp only [a1] aesop
The first pick a1 belongs to agent 0's bundle and serves as the witness good g.
We instantiate the existential quantifier for the removed good g with a1, and verify that a1 ∈ B_0 = {a1, a2, a3} by membership in an inserted set.
uses
Finset.mem_insert_selfrefine ⟨a1,?_,?_⟩ · rw [hB0] exact Finset.mem_insert_self _ _
If agent i can secure both {a2, a3} in a single deviation, the first alternative of the certificate holds.
By round_robin_two_mul_add_one_cover_pairs, agent i either has a single deviation r securing {a2, a3}, or two deviations covering all four goods {a2, a3, b1, b2}. In the former case, because B_0 ∖ {a1} = {a2, a3}, deviation r secures all of B_0 ∖ {a1}.
uses
round_robin_two_mul_add_one_cover_pairs,Or.inlrcases round_robin_two_mul_add_one_cover_pairs n rank i hi a1 a2 a3 b1 b2 rfl ⟨hf2,hm2⟩ ⟨hf3,hm3⟩ hB0 hBi ⟨h02,h03,h23⟩ with ⟨r,hr⟩ | ⟨r₁,r₂,hr⟩ · exact Or.inl ⟨r,by rw [hremove]; exact hr⟩
In the two-deviation case, the union of the two deviated bundles covers B_i ∪ (B_0 ∖ {a1}).
From the second alternative of round_robin_two_mul_add_one_cover_pairs, deviations r1 and r2 satisfy {a2, a3, b1, b2} ⊆ D1 ∪ D2. Since B_i = {b1, b2} and B_0 ∖ {a1} = {a2, a3}, every element of B_i ∪ (B_0 ∖ {a1}) belongs to D1 ∪ D2.
uses
Or.inr,Finset.mem_union,Finset.mem_insert,Finset.mem_singleton· refine Or.inr ⟨r₁,r₂,?_⟩ have hcov : picking_sequence_outcome (round_robin_sequence n (2*n+1)) rank i ∪ (picking_sequence_outcome (round_robin_sequence n (2*n+1)) rank 0 \ {a1}) ⊆ picking_sequence_outcome (round_robin_sequence n (2*n+1)) (Function.update rank i r₁) i ∪ picking_sequence_outcome (round_robin_sequence n (2*n+1)) (Function.update rank i r₂) i := by rw [hBi,hremove] intro x hx apply hr simp only [Finset.mem_union,Finset.mem_insert,Finset.mem_singleton] at hx ⊢ tauto
For every good x, the multiplicity of x in B_i plus B_0 ∖ {a1} is at most its multiplicity in D1 plus D2.
Because i ≠ 0, picking_sequence_outcome_pairwise_disjoint ensures B_i and B_0 are disjoint, so no good belongs to both B_i and B_0 ∖ {a1}. Together with the union coverage B_i ∪ (B_0 ∖ {a1}) ⊆ D1 ∪ D2, indicator_cover applied pointwise to each good x yields the indicator inequality (multiplicity bound).
uses
picking_sequence_outcome_pairwise_disjoint,Finset.disjoint_left.mp,Finset.mem_sdiff.mp,Finset.mem_union.mp,Finset.mem_union.mpr,indicator_coverhave hd := picking_sequence_outcome_pairwise_disjoint (round_robin_sequence n (2*n+1)) rank hi intro x have hdis : ¬(x ∈ picking_sequence_outcome (round_robin_sequence n (2*n+1)) rank i ∧ x ∈ picking_sequence_outcome (round_robin_sequence n (2*n+1)) rank 0 \ {a1}) := by rintro ⟨hxi,hx0⟩ exact Finset.disjoint_left.mp hd hxi (Finset.mem_sdiff.mp hx0).1 have hc : x ∈ picking_sequence_outcome (round_robin_sequence n (2*n+1)) rank i ∨ x ∈ picking_sequence_outcome (round_robin_sequence n (2*n+1)) rank 0 \ {a1} → x ∈ picking_sequence_outcome (round_robin_sequence n (2*n+1)) (Function.update rank i r₁) i ∨ x ∈ picking_sequence_outcome (round_robin_sequence n (2*n+1)) (Function.update rank i r₂) i := fun hh => Finset.mem_union.mp (hcov (Finset.mem_union.mpr hh)) exact indicator_cover _ _ _ _ hdis hc
indicator_cover- If P and Q are mutually exclusive propositions (¬(P ∧ Q)) and P ∨ Q implies R ∨ S, then the sum of indicators of P and Q is at most the sum of indicators of R and S.
round_robin_two_mul_add_one_outcome_structure- In a round-robin picking sequence with n agents and 2n+1 goods, agent 0 receives three distinct goods {a1, a2, a3} and any agent i ≠ 0 receives two distinct goods {b1, b2}.
Finset.mem_sdiff- An element belongs to the set difference s ∖ t if and only if it belongs to s and does not belong to t.
Finset.mem_insert- An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton- An element belongs to the singleton {a} if and only if it equals a.
Finset.mem_insert_self- An element a belongs to insert a s.
round_robin_two_mul_add_one_cover_pairs- In round-robin with 2n+1 goods, either agent i has a deviation securing both {a2, a3}, or two deviations whose combined bundles cover {a2, a3, b1, b2}.
Or.inl- From a proof of A, infer the disjunction A ∨ B.
Or.inr- From a proof of B, infer the disjunction A ∨ B.
Finset.mem_union- An element belongs to the union s ∪ t if and only if it belongs to s or to t.
picking_sequence_outcome_pairwise_disjoint- In any picking sequence, the bundles allocated to distinct agents are disjoint.
Finset.disjoint_left.mp- If two sets are disjoint, any element in the first set is not in the second set.
Finset.mem_sdiff.mp- If an element belongs to s ∖ t, it belongs to s and not to t.
Finset.mem_union.mp- If an element belongs to s ∪ t, it belongs to s or to t.
Finset.mem_union.mpr- If an element belongs to s or to t, it belongs to s ∪ t.
- The private helper lemma indicator_cover establishes the indicator inequality by exhausting all 16 truth-value combinations across four propositions using simp_all.
- In step 3, simplifying the set difference B₀ ∖ {a₁} to {a₂, a₃} is closed automatically by aesop using the distinctness of the picks.
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.
private lemma indicator_cover (P Q R S : Prop) [Decidable P] [Decidable Q] [Decidable R] [Decidable S] (hd : ¬(P ∧ Q)) (hc : P ∨ Q → R ∨ S) : (if P then 1 else 0) + (if Q then 1 else 0) ≤ (if R then 1 else 0) + (if S then 1 else 0 : ℕ) := by by_cases hP : P <;> by_cases hQ : Q <;> by_cases hR : R <;> by_cases hS : S <;> simp_alltheorem round_robin_two_mul_add_one_deviation_certificate (n : ℕ) [NeZero n] (rank : Fin n → Fin (2 * n + 1) ≃ Fin (2 * n + 1)) (i : Fin n) (hi : i ≠ 0) : ∃ g ∈ picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) rank 0, (∃ r : Fin (2 * n + 1) ≃ Fin (2 * n + 1), picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) rank 0 \ {g} ⊆ picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) (Function.update rank i r) i) ∨ (∃ r₁ r₂ : Fin (2 * n + 1) ≃ Fin (2 * n + 1), ∀ x : Fin (2 * n + 1), (if x ∈ picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) rank i then 1 else 0) + (if x ∈ picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) rank 0 \ {g} then 1 else 0) ≤ (if x ∈ picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) (Function.update rank i r₁) i then 1 else 0) + (if x ∈ picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) (Function.update rank i r₂) i then 1 else 0 : ℕ)) := by classical obtain ⟨a2,a3,b1,b2,hf2,hm2,hf3,hm3,hB0,hBi,h02,h03,h23,h12,_,_⟩ := round_robin_two_mul_add_one_outcome_structure n rank i hi let a1 := rank 0 ⟨0,by omega⟩ have hremove : picking_sequence_outcome (round_robin_sequence n (2*n+1)) rank 0 \ {a1} = {a2,a3} := by rw [hB0] ext x simp only [Finset.mem_sdiff,Finset.mem_insert,Finset.mem_singleton] dsimp only [a1] aesop refine ⟨a1,?_,?_⟩ · rw [hB0] exact Finset.mem_insert_self _ _ rcases round_robin_two_mul_add_one_cover_pairs n rank i hi a1 a2 a3 b1 b2 rfl ⟨hf2,hm2⟩ ⟨hf3,hm3⟩ hB0 hBi ⟨h02,h03,h23⟩ with ⟨r,hr⟩ | ⟨r₁,r₂,hr⟩ · exact Or.inl ⟨r,by rw [hremove]; exact hr⟩ · refine Or.inr ⟨r₁,r₂,?_⟩ have hcov : picking_sequence_outcome (round_robin_sequence n (2*n+1)) rank i ∪ (picking_sequence_outcome (round_robin_sequence n (2*n+1)) rank 0 \ {a1}) ⊆ picking_sequence_outcome (round_robin_sequence n (2*n+1)) (Function.update rank i r₁) i ∪ picking_sequence_outcome (round_robin_sequence n (2*n+1)) (Function.update rank i r₂) i := by rw [hBi,hremove] intro x hx apply hr simp only [Finset.mem_union,Finset.mem_insert,Finset.mem_singleton] at hx ⊢ tauto have hd := picking_sequence_outcome_pairwise_disjoint (round_robin_sequence n (2*n+1)) rank hi intro x have hdis : ¬(x ∈ picking_sequence_outcome (round_robin_sequence n (2*n+1)) rank i ∧ x ∈ picking_sequence_outcome (round_robin_sequence n (2*n+1)) rank 0 \ {a1}) := by rintro ⟨hxi,hx0⟩ exact Finset.disjoint_left.mp hd hxi (Finset.mem_sdiff.mp hx0).1 have hc : x ∈ picking_sequence_outcome (round_robin_sequence n (2*n+1)) rank i ∨ x ∈ picking_sequence_outcome (round_robin_sequence n (2*n+1)) rank 0 \ {a1} → x ∈ picking_sequence_outcome (round_robin_sequence n (2*n+1)) (Function.update rank i r₁) i ∨ x ∈ picking_sequence_outcome (round_robin_sequence n (2*n+1)) (Function.update rank i r₂) i := fun hh => Finset.mem_union.mp (hcov (Finset.mem_union.mpr hh)) exact indicator_cover _ _ _ _ hdis hc