round_robin_u_best
In 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 true Borda utility over all m! ranking reports that A can submit, after observing B's true ranking rB.
Statement
def round_robin_u_best (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 3
- 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 -…
- round_robin_sequenceThe Round-Robin picking sequence (1, 2, ..., n, 1, 2, ...) of length m, with agents numbered 0, ..., n-1.
- 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…
- Used by 4
- 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_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_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_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
A definition taking a natural number m (the number of items) and two permutations rA, rB : Fin m ≃ Fin m (representing the preference rankings of two agents, where rank 0 is the top choice and rank m - 1 is the bottom choice), which returns the maximum (supremum over all rA' : Fin m ≃ Fin m) Borda utility that agent 0 (agent A) can obtain under their true preferences rA by strategically reporting preference order rA', assuming agent 1 (agent B) reports rB, in an alternating round-robin item-picking sequence of length m.
Specifically:
- The picking sequence is of length m, where at turn t ∈ {0, ..., m - 1}, agent t % 2 picks their most preferred item among those not yet chosen, according to preference rA' if t % 2 = 0 and rB if t % 2 = 1.
- The bundle received by agent 0 is the set of items chosen by agent 0 over the sequence.
- The Borda utility of a bundle S according to rA is the sum over g ∈ S of m - (rA.symm g : ℕ).
- The function returns the maximum of this utility over all possible permutations rA'.
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
/-- Maximum Borda utility of agent A over all m! ranking reports against truthful agent B in alternating Round-Robin draft. -/ def round_robin_u_best (m : ℕ) (rA rB : Fin m ≃ Fin m) : ℕ := Finset.univ.sup (fun rA' : Fin m ≃ Fin m => borda_bundle_utility m rA (picking_sequence_outcome (round_robin_sequence 2 m) (fun i => if i = 0 then rA' else rB) 0))