AFTD Auto-Formalizing Theoretical Domains

round_robin_pne_envy_zero_ef1_of_two_mul_add_one

theoremverified

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
Used by 1

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.

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

    lines 13–14

    uses round_robin_pne_envy_zero_ef1_of_deviation_certificate, round_robin_two_mul_add_one_deviation_certificate

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

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