round_robin_pne_envy_zero_ef1_of_deviation_certificate
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
- 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.ValuationAn abstract valuation assigns a real value to each agent-bundle pair.
val i Sis the value agentiassigns to bundleS. Lives in… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - 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.AdditiveValuation.toValuationLift an additive valuation to an abstract
Valuation.(w.toValuation).val i S = Σ_{g ∈ S} w.weight i g. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- 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 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.
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.
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₁₂⟩
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.
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
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.
· have hpne₁ := h i r₁ have hpne₂ := h i r₂ simp only [SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation] at hpne₁ hpne₂
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`).
uses
Finset.sum_le_sumhave 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
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).
uses
Finset.sum_add_distrib,Finset.sum_ite_mem,Finset.univ_intersimp 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.
- The hypothesis `hi : i ≠ 0` is kept in scope (`have _ := hi` on line 26) but is not explicitly invoked in the calculation, as the certificate hypothesis `hcert` already provides the necessary deviation rankings for agent `i`.
- On line 50, `split_ifs at * <;> linarith` discharges the pointwise inequality by splitting across the combinations of set-membership conditions for an item and verifying each case by linear real arithmetic.
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_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