AFTD Auto-Formalizing Theoretical Domains

round_robin_borda_manipulation_gain_nonneg

theoremverified

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.

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

    line 4

      unfold round_robin_borda_manipulation_gain
  2. Truthful 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).

    lines 5–8

    uses Finset.le_sup, Finset.mem_univ

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

    lines 9–11

    uses sub_nonneg, Nat.cast_le.mpr

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

    line 12

    uses div_nonneg, sq_nonneg

      exact 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

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