round_robin_expected_manipulation_gain_two_eq_zero
For m = 2 goods, the expected real-valued normalized strategic manipulation gain round_robin_expected_manipulation_gain 2 equals 0.
Statement
theorem round_robin_expected_manipulation_gain_two_eq_zero :
round_robin_expected_manipulation_gain 2 = 0- Source
- OP-1439
- Verified
- 11 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- round_robin_expected_manipulation_gainThe real-valued expected normalized strategic manipulation gain, returning a real number defined as the sum over all ranking pairs p in…
- round_robin_borda_gain_two_goodsFor m = 2 goods, agent A's best-response Borda utility equals her truthful utility for every pair of rankings (U_best = U_truth).
- round_robin_u_bestIn the alternating Round-Robin picking sequence ABAB...AB of m goods, agent A's best-response Borda utility U_best is the maximum of A's…
- round_robin_borda_manipulation_gainThe real-valued normalized strategic manipulation gain ((round_robin_u_best m rA rB : ℝ) - (round_robin_u_truth m rA rB : ℝ)) / (m : ℝ)^2…
- round_robin_u_truthIn the alternating Round-Robin picking sequence ABAB...AB of m goods, agent A's truthful Borda utility U_truth when both agents A and B…
Read back from the Lean
The expected manipulation gain under the round-robin procedure for $m = 2$ items, round_robin_expected_manipulation_gain 2, is equal to 0 (where the expectation is taken uniformly over all pairs of preference orderings $(r_A, r_B) \in (\text{Fin } 2 \simeq \text{Fin } 2) \times (\text{Fin } 2 \simeq \text{Fin } 2)$).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The expected manipulation gain is defined as the average manipulation gain over all pairs of agent preference rankings. For two goods, the best achievable Borda utility equals the utility from reporting truthfully (`round_robin_borda_gain_two_goods`), so the manipulation gain vanishes for every profile. Since every term in the average is zero, the expected manipulation gain is zero.
The expected manipulation gain is expressed as the average Borda manipulation gain over all preference pairs $(r_A, r_B)$.
Unfolding the definition of `round_robin_expected_manipulation_gain` replaces the left-hand side with the sum of `round_robin_borda_manipulation_gain 2 p.1 p.2` over all pairs of permutations $p \in (\text{Fin } 2 \simeq \text{Fin } 2)^2$, divided by the square of the number of permutations.
unfold round_robin_expected_manipulation_gainFor every pair of preference rankings $(r_A, r_B)$, the manipulation gain is zero.
Decomposing the pair into individual rankings $r_A$ and $r_B$ and unfolding `round_robin_borda_manipulation_gain`, the gain is defined as $(u_{\text{best}} - u_{\text{truth}}) / 2^2$. By `round_robin_borda_gain_two_goods`, the best achievable utility $u_{\text{best}}$ equals the truthful utility $u_{\text{truth}}$, so the numerator is $(u_{\text{truth}} - u_{\text{truth}}) = 0$, making the quotient $0$.
uses
round_robin_borda_gain_two_goodshave h : ∀ p : (Fin 2 ≃ Fin 2) × (Fin 2 ≃ Fin 2), round_robin_borda_manipulation_gain 2 p.1 p.2 = 0 := by rintro ⟨rA, rB⟩ unfold round_robin_borda_manipulation_gain rw [round_robin_borda_gain_two_goods rA rB] simp
The expected manipulation gain is zero. automation
Since the manipulation gain is zero for every profile $p$, every summand in the average is zero. The simplifier evaluates the sum of zeros and the division to obtain $0$.
simp [h]
round_robin_borda_gain_two_goods- For two goods, an agent's best achievable round-robin Borda utility equals their utility from truthful reporting, regardless of the preference rankings $r_A$ and $r_B$.
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.
/-- The expected normalized manipulation gain is zero for m = 2 goods. -/theorem round_robin_expected_manipulation_gain_two_eq_zero : round_robin_expected_manipulation_gain 2 = 0 := by unfold round_robin_expected_manipulation_gain have h : ∀ p : (Fin 2 ≃ Fin 2) × (Fin 2 ≃ Fin 2), round_robin_borda_manipulation_gain 2 p.1 p.2 = 0 := by rintro ⟨rA, rB⟩ unfold round_robin_borda_manipulation_gain rw [round_robin_borda_gain_two_goods rA rB] simp simp [h]