round_robin_borda_manipulation_gain_nonneg
For every number of goods m and all rankings rA and rB, the real-valued normalized manipulation gain round_robin_borda_manipulation_gain m rA rB is non-negative (at least 0).
Statement
theorem round_robin_borda_manipulation_gain_nonneg (m : ℕ) (rA rB : Fin m ≃ Fin m) :
0 ≤ round_robin_borda_manipulation_gain m rA rB- Source
- Algorithms for Manipulating Sequential Allocation (AAAI 2020)
- Verified
- 11 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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_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_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…
- round_robin_sequenceThe Round-Robin picking sequence (1, 2, ..., n, 1, 2, ...) of length m, with agents numbered 0, ..., n-1.
- borda_bundle_utilityFor a strict ranking r of m goods (where r 0 is the top-ranked good), the additive Borda utility of a bundle of goods S assigns m -…
- 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…
Read back from the Lean
For every natural number m and any two permutations rA, rB of Fin m (represented as equivalences Fin m ≃ Fin m), the round-robin Borda manipulation gain round_robin_borda_manipulation_gain m rA rB is greater than or equal to 0.
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 normalized manipulation gain is defined as the difference between the best-response utility and the truthful utility, divided by m². Because truthful reporting is one of the candidate strategies over which the best-response utility takes the supremum, truthful utility is at most best-response utility, making the numerator non-negative. Since the denominator is a square and thus also non-negative, the quotient is at least zero.
Expanding the definition reduces the goal to showing that (u_best - u_truth) / m² ≥ 0.
Unfolding round_robin_borda_manipulation_gain expresses the normalized gain as the difference between agent A's best-response utility and truthful utility, divided by m².
unfold round_robin_borda_manipulation_gainTruthful Borda utility is bounded above by the best-response utility: u_truth ≤ u_best.
The best-response utility u_best is defined as the supremum of utilities over all possible permutations in the universe of rankings. Because the truthful ranking rA is an element of this universe (by Finset.mem_univ), its utility is bounded above by the supremum (by Finset.le_sup).
uses
Finset.le_sup,Finset.mem_univhave h_le : round_robin_u_truth m rA rB ≤ round_robin_u_best m rA rB := Finset.le_sup (s := Finset.univ) (b := rA) (f := fun rA' => borda_bundle_utility m rA (picking_sequence_outcome (round_robin_sequence 2 m) (fun i => if i = 0 then rA' else rB) 0)) (Finset.mem_univ rA)
The numerator is non-negative in the real numbers: 0 ≤ (u_best : ℝ) - (u_truth : ℝ).
A difference a - b is non-negative if and only if b ≤ a (by sub_nonneg). This follows by casting the integer inequality u_truth ≤ u_best into the real numbers using Nat.cast_le.mpr.
uses
sub_nonneg,Nat.cast_le.mprhave h_sub : 0 ≤ (round_robin_u_best m rA rB : ℝ) - (round_robin_u_truth m rA rB : ℝ) := by rw [sub_nonneg] exact Nat.cast_le.mpr h_le
The quotient (u_best - u_truth) / m² is non-negative.
The quotient of two real numbers is non-negative whenever both the numerator and denominator are non-negative (by div_nonneg). The numerator was shown to be non-negative in the previous step, and the denominator m² is non-negative as the square of a real number (by sq_nonneg).
uses
div_nonneg,sq_nonnegexact div_nonneg h_sub (sq_nonneg (m : ℝ))
Finset.le_sup- An element's value under a function is at most the supremum of that function over any finite set containing the element.
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
sub_nonneg- A difference a - b is non-negative if and only if b ≤ a.
Nat.cast_le.mpr- If m ≤ n for natural numbers, then their casts into an ordered semiring satisfy ↑m ≤ ↑n.
div_nonneg- The quotient of two non-negative elements in a group with zero is non-negative.
sq_nonneg- The square of any element in an ordered semiring is non-negative.
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 normalized strategic manipulation gain is always non-negative. -/theorem round_robin_borda_manipulation_gain_nonneg (m : ℕ) (rA rB : Fin m ≃ Fin m) : 0 ≤ round_robin_borda_manipulation_gain m rA rB := by unfold round_robin_borda_manipulation_gain have h_le : round_robin_u_truth m rA rB ≤ round_robin_u_best m rA rB := Finset.le_sup (s := Finset.univ) (b := rA) (f := fun rA' => borda_bundle_utility m rA (picking_sequence_outcome (round_robin_sequence 2 m) (fun i => if i = 0 then rA' else rB) 0)) (Finset.mem_univ rA) have h_sub : 0 ≤ (round_robin_u_best m rA rB : ℝ) - (round_robin_u_truth m rA rB : ℝ) := by rw [sub_nonneg] exact Nat.cast_le.mpr h_le exact div_nonneg h_sub (sq_nonneg (m : ℝ))