round_robin_pne_envy_zero_ef1_of_two_mul_add_one
With n agents and 2n + 1 goods, in every pure Nash equilibrium of Round-Robin (nonnegative additive valuations) every agent i ≠ 0 is EF1 towards agent 0, the only agent with three goods. With round_robin_pne_ef1_pair_of_count_le_two and round_robin_sequence_count_le_two_of_ne_zero this is the m = 2n + 1 case of round_robin_pne_ef1_of_card_le_two_mul_add_one.
Statement
theorem round_robin_pne_envy_zero_ef1_of_two_mul_add_one (n : ℕ) [NeZero n]
(w : Fin n → Fin (2 * n + 1) → ℝ) (hw : ∀ i g, 0 ≤ w i g)
(rank : Fin n → Fin (2 * n + 1) ≃ Fin (2 * n + 1))
(h : is_picking_sequence_pne
(SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation ⟨w⟩)
(round_robin_sequence n (2 * n + 1)) rank)
(i : Fin n) (hi : i ≠ 0) :
∃ g ∈ picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) rank 0,
(SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation ⟨w⟩).val i
(picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) rank 0 \ {g}) ≤
(SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation ⟨w⟩).val i
(picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) rank i)- Source
- The remaining case of the conjecture round_robin_pne_ef1_of_card_le_two_mul_add_one (thread RT-3); exact for n = 3 by exp 1515, sampled for n = 4..6 by exp 1598.
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- 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_pair_of_count_le_twoIn a pure Nash equilibrium of Round-Robin (nonnegative additive valuations), every agent i is EF1 towards every other agent j that appears…
- round_robin_two_mul_add_one_deviation_certificateRound-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…
- round_robin_pne_envy_zero_ef1_of_deviation_certificateIf the deviation certificate of round_robin_two_mul_add_one_deviation_certificate holds for agent i ≠ 0, then at a pure Nash equilibrium…
- SocialChoice.FairDivision.Indivisible.AdditiveValuationAn additive valuation is determined by per-item weights.
weight i gis the value agentiassigns to goodgindividually. The bundle… - 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…
- Used by 1
- 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…
The proof, explained
To show that every agent i ≠ 0 is EF1 towards agent 0 in a pure Nash equilibrium of Round-Robin with 2n + 1 goods, the proof applies a general reduction lemma that deduces EF1 from the existence of a deviation certificate. The required certificate—a unilateral deviation or a pair of deviations that covers agent 0's bundle minus one item—is supplied by an existence theorem specific to 2n + 1 goods.
Agent i does not envy agent 0 after removing some good g from agent 0's bundle.
The lemma round_robin_pne_envy_zero_ef1_of_deviation_certificate establishes EF1 towards agent 0 provided agent i has a deviation certificate (a single or double deviation that can recover agent 0's bundle minus one item). Supplying the certificate guaranteed by round_robin_two_mul_add_one_deviation_certificate completes the proof.
uses
round_robin_pne_envy_zero_ef1_of_deviation_certificate,round_robin_two_mul_add_one_deviation_certificateexact round_robin_pne_envy_zero_ef1_of_deviation_certificate n w hw rank h i hi (round_robin_two_mul_add_one_deviation_certificate n rank i hi)
round_robin_pne_envy_zero_ef1_of_deviation_certificate- In a pure Nash equilibrium of the round-robin picking sequence with additive valuations, if agent i ≠ 0 has a deviation certificate (a single deviation or pair of deviations covering agent 0's bundle minus some item g), then agent i satisfies EF1 towards agent 0 with respect to g.
round_robin_two_mul_add_one_deviation_certificate- In a round-robin picking sequence with n agents and 2n + 1 goods, for any ranking profile and any agent i ≠ 0, there exists a good g in agent 0's bundle and a deviation certificate (a single deviation or a pair of deviations covering agent 0's bundle minus g).
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_envy_zero_ef1_of_two_mul_add_one (n : ℕ) [NeZero n] (w : Fin n → Fin (2 * n + 1) → ℝ) (hw : ∀ i g, 0 ≤ w i g) (rank : Fin n → Fin (2 * n + 1) ≃ Fin (2 * n + 1)) (h : is_picking_sequence_pne (SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation ⟨w⟩) (round_robin_sequence n (2 * n + 1)) rank) (i : Fin n) (hi : i ≠ 0) : ∃ g ∈ picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) rank 0, (SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation ⟨w⟩).val i (picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) rank 0 \ {g}) ≤ (SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation ⟨w⟩).val i (picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) rank i) := by exact round_robin_pne_envy_zero_ef1_of_deviation_certificate n w hw rank h i hi (round_robin_two_mul_add_one_deviation_certificate n rank i hi)