round_robin_u_truth
In 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 report their true rankings rA and rB.
Statement
def round_robin_u_truth (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
round_robin_u_truth is a definition that takes a natural number m and two permutations rA and rB of Fin m (representing the preference rankings over m items of agent 0 and agent 1, respectively), and returns a natural number (ℕ).
The value returned is the Borda utility obtained by agent 0 (evaluated under ranking rA) from the bundle allocated to agent 0 in a round-robin picking game of length m between 2 agents:
1. The picking sequence is of length m, where at each turn t (for t = 0, …, m - 1), agent t % 2 picks an item.
2. Agent 0 picks according to ranking rA, and agent 1 picks according to ranking rB. In each turn, the active agent selects the first item in their preference list (ordered as [rank(0), rank(1), …, rank(m - 1)]) that has not yet been selected by either agent.
3. The Borda utility of the resulting bundle S of items allocated to agent 0 is defined with respect to rA as the sum over all items g ∈ S of m - rA⁻¹(g).
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
/-- Truthful Borda utility of agent A under alternating Round-Robin draft ABAB...AB. -/ def round_robin_u_truth (m : ℕ) (rA rB : 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)