AFTD Auto-Formalizing Theoretical Domains

round_robin_u_truth

def

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

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