AFTD Auto-Formalizing Theoretical Domains

round_robin_pne_envy_zero_ef1_of_deviation_certificate

theoremverified

If the deviation certificate of round_robin_two_mul_add_one_deviation_certificate holds for agent i ≠ 0, then at a pure Nash equilibrium of Round-Robin (2n+1 goods, nonnegative additive valuations) agent i is EF1 towards agent 0.

Statement

theorem round_robin_pne_envy_zero_ef1_of_deviation_certificate (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)
    (hcert : ∃ 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 : ℕ))) :
    ∃ 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
step for round_robin_pne_envy_zero_ef1_of_two_mul_add_one (research thread RT-3)
Verified
21 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
Used by 1

The proof, explained

The theorem proves that agent i is EF1 towards agent 0 at a pure Nash equilibrium of the Round-Robin picking sequence game whenever a deviation certificate holds. The certificate specifies a good g in agent 0's bundle and gives either a single deviation whose bundle contains agent 0's bundle minus g, or two deviations whose bundles jointly dominate agent i's bundle and agent 0's bundle minus g. In the single-deviation case, the claim follows from monotonicity of non-negative additive valuations and the equilibrium condition. In the two-deviation case, multiplying the indicator inequality by non-negative weights and summing over all goods gives an inequality on valuations that, combined with the two equilibrium bounds, implies the EF1 condition.

  1. Witness the EF1 property using the item g from the certificate and reduce to additive valuations across two certificate cases.

    We unpack the certificate hypothesis to obtain the good g in agent 0's bundle and supply it as the witness for envy-freeness up to one good (EF1). Unfolding the additive valuation definition transforms the goal into showing that agent i's valuation sum over agent 0's bundle without g is at most agent i's valuation sum over their own bundle. We then case-split on whether the certificate provides a single deviation or a pair of deviations.

    lines 26–30

      have _ := hi
      obtain ⟨g, hg, hcases⟩ := hcert
      refine ⟨g, hg, ?_⟩
      simp only [SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation]
      rcases hcases with ⟨r, hr⟩ | ⟨r₁, r₂, hr₁₂⟩
  2. In the single-deviation case, the EF1 inequality holds by monotonicity on subsets and the Nash equilibrium condition.

    The certificate provides a deviation ranking r for agent i such that agent 0's bundle minus g is a subset of the bundle agent i would receive under r. Since all valuation weights are non-negative, `Finset.sum_le_sum_of_subset_of_nonneg` shows that agent i values the subset at most their deviated bundle. Since the profile is a pure Nash equilibrium, agent i's valuation under deviation r cannot exceed their equilibrium valuation, so the result follows by transitivity.

    lines 31–36

    uses Finset.sum_le_sum_of_subset_of_nonneg

      · have hpne := h i r
        simp only [SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation] at hpne
        have hsub : ∑ x ∈ picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) rank 0 \ {g}, w i x ≤
            ∑ x ∈ picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) (Function.update rank i r) i, w i x :=
          Finset.sum_le_sum_of_subset_of_nonneg hr (fun x _ _ => hw i x)
        linarith
  3. In the two-deviation case, agent i's valuation under either deviation r₁ or r₂ is at most their equilibrium valuation.

    Specializing the pure Nash equilibrium condition to deviations r₁ and r₂ gives the upper bounds v_i(A_i(r₁)) ≤ v_i(A_i) and v_i(A_i(r₂)) ≤ v_i(A_i), rewritten into explicit sums of weights.

    lines 37–39

      · have hpne₁ := h i r₁
        have hpne₂ := h i r₂
        simp only [SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation] at hpne₁ hpne₂
  4. Weighting the indicator inequality by item valuations yields an inequality between the total sums across all goods.

    Using `Finset.sum_le_sum`, it suffices to show the inequality pointwise for each good x. The certificate ensures that the sum of indicators for agent i's bundle and agent 0's bundle minus g is bounded by the sum of indicators for the two deviated bundles. Multiplying this by the non-negative weight w(i, x) preserves the inequality for every item x, which is verified by case analysis on indicator conditions (`split_ifs`) and linear arithmetic (`linarith`).

    lines 40–50

    uses Finset.sum_le_sum

        have hsum : ∑ x : Fin (2 * n + 1),
            ((if x ∈ picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) rank i then w i x else 0) +
             (if x ∈ picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) rank 0 \ {g} then w i x else 0)) ≤
            ∑ x : Fin (2 * n + 1),
            ((if x ∈ picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) (Function.update rank i r₁) i then w i x else 0) +
             (if x ∈ picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) (Function.update rank i r₂) i then w i x else 0)) := by
          apply Finset.sum_le_sum
          intro x _
          have hc := hr₁₂ x
          have hwx := hw i x
          split_ifs at * <;> linarith
  5. Simplifying the weighted sums proves the EF1 condition v_i(A₀ \ {g}) ≤ v_i(A_i).

    Distributing the sums with `Finset.sum_add_distrib`, `Finset.sum_ite_mem`, and `Finset.univ_inter` simplifies the left and right sides to v_i(A_i) + v_i(A₀ \ {g}) ≤ v_i(A_i(r₁)) + v_i(A_i(r₂)). Linear arithmetic then combines this with the two Nash equilibrium bounds to subtract v_i(A_i) and conclude v_i(A₀ \ {g}) ≤ v_i(A_i).

    lines 51–52

    uses Finset.sum_add_distrib, Finset.sum_ite_mem, Finset.univ_inter

        simp only [Finset.sum_add_distrib, Finset.sum_ite_mem, Finset.univ_inter] at hsum
        linarith
Finset.sum_le_sum_of_subset_of_nonneg
If s ⊆ t and f is non-negative on all elements of t \ s, then the sum of f over s is at most the sum of f over t.
Finset.sum_le_sum
If f(x) ≤ g(x) for every element x in a finite set s, then ∑ x ∈ s, f(x) ≤ ∑ x ∈ s, g(x).
Finset.sum_add_distrib
The sum of a sum over a finite set distributes into the sum of the individual sums: ∑ x ∈ s, (f(x) + g(x)) = ∑ x ∈ s, f(x) + ∑ x ∈ s, g(x).
Finset.sum_ite_mem
Summing an indicator-weighted function over s for membership in t equals the sum of the function over the intersection s ∩ t.
Finset.univ_inter
For any subset s of a finite type, the intersection of the universal set with s is s.

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_deviation_certificate (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)    (hcert : ∃ 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 : ℕ))) :    ∃ 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  have _ := hi  obtain ⟨g, hg, hcases⟩ := hcert  refine ⟨g, hg, ?_⟩  simp only [SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation]  rcases hcases with ⟨r, hr⟩ | ⟨r₁, r₂, hr₁₂⟩  · have hpne := h i r    simp only [SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation] at hpne    have hsub : ∑ x ∈ picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) rank 0 \ {g}, w i x ≤        ∑ x ∈ picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) (Function.update rank i r) i, w i x :=      Finset.sum_le_sum_of_subset_of_nonneg hr (fun x _ _ => hw i x)    linarith  · have hpne₁ := h i r₁    have hpne₂ := h i r₂    simp only [SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation] at hpne₁ hpne₂    have hsum : ∑ x : Fin (2 * n + 1),        ((if x ∈ picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) rank i then w i x else 0) +         (if x ∈ picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) rank 0 \ {g} then w i x else 0)) ≤        ∑ x : Fin (2 * n + 1),        ((if x ∈ picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) (Function.update rank i r₁) i then w i x else 0) +         (if x ∈ picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) (Function.update rank i r₂) i then w i x else 0)) := by      apply Finset.sum_le_sum      intro x _      have hc := hr₁₂ x      have hwx := hw i x      split_ifs at * <;> linarith    simp only [Finset.sum_add_distrib, Finset.sum_ite_mem, Finset.univ_inter] at hsum    linarith
See it in the graphDiscuss this resultChallenge it