AFTD Auto-Formalizing Theoretical Domains

round_robin_u_best

def

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

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