round_robin_borda_manipulation_gain
The real-valued normalized strategic manipulation gain ((round_robin_u_best m rA rB : ℝ) - (round_robin_u_truth m rA rB : ℝ)) / (m : ℝ)^2 for agent A in the two-agent alternating Round-Robin draft of m goods, returning a real number.
Statement
noncomputable def round_robin_borda_manipulation_gain (m : ℕ) (rA rB : Fin m ≃ Fin m) : ℝ
- Defined in
- Algorithms for Manipulating Sequential Allocation (AAAI 2020)
- Verified
- 11 Nov 2026
- Axioms
- none listed
- Built on 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…
- Used by 3
- 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_manipulation_gain_nonnegFor every number of goods m and all rankings rA and rB, the real-valued normalized manipulation gain round_robin_borda_manipulation_gain m…
- round_robin_expected_manipulation_gain_two_eq_zeroFor m = 2 goods, the expected real-valued normalized strategic manipulation gain round_robin_expected_manipulation_gain 2 equals 0.
Read back from the Lean
Given a natural number m (representing the number of items) and two permutations rA, rB : Fin m ≃ Fin m (representing the preference rankings of agent A (agent 0) and agent B (agent 1) over Fin m), round_robin_borda_manipulation_gain m rA rB is the real number defined as:
((round_robin_u_best m rA rB : ℝ) - (round_robin_u_truth m rA rB : ℝ)) / (m : ℝ)^2
That is, the difference between agent A's maximum achievable Borda utility by misreporting a preference ranking rA' and agent A's Borda utility under truthful reporting rA (with agent B reporting rB), normalized by m^2, in a 2-agent round-robin picking sequence of length m.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Normalized Borda strategic manipulation gain (U_best - U_truth) / m^2 in ℝ for agent A in alternating draft. -/ noncomputable def round_robin_borda_manipulation_gain (m : ℕ) (rA rB : Fin m ≃ Fin m) : ℝ := ((round_robin_u_best m rA rB : ℝ) - (round_robin_u_truth m rA rB : ℝ)) / (m : ℝ)^2