AFTD Auto-Formalizing Theoretical Domains

round_robin_borda_gain_two_goods

theoremverified

For m = 2 goods, agent A's best-response Borda utility equals her truthful utility for every pair of rankings (U_best = U_truth).

Statement

theorem round_robin_borda_gain_two_goods (rA rB : Fin 2 ≃ Fin 2) :
    round_robin_u_best 2 rA rB = round_robin_u_truth 2 rA rB
Source
OP-1439
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
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 1

Read back from the Lean

For all preference orders (equivalences) $r_A, r_B : \mathrm{Fin}\,2 \simeq \mathrm{Fin}\,2$, the maximum Borda utility that agent 0 can achieve by reporting any preference order $r_A' : \mathrm{Fin}\,2 \simeq \mathrm{Fin}\,2$ in a 2-player round-robin picking sequence of 2 goods (where agent 1 reports $r_B$) is equal to the Borda utility agent 0 receives when reporting truthfully ($r_A$).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

For two goods and two agents in an alternating draft, the space of possible preference rankings is extremely small: each agent has only $2! = 2$ rankings, yielding just 4 profile pairs in total. The proof abstracts over all pairs of rankings and establishes the identity by exhaustive finite computation (`decide`).

  1. Agent A's best-response Borda utility equals her truthful utility for every pair of rankings. automation

    The proof proceeds by finite case exhaustion. Generalizing the arbitrary rankings $r_A$ and $r_B$ (`revert rA rB`) rephrases the goal as a universal quantification over the finite type of permutations $\mathrm{Fin}\,2 \simeq \mathrm{Fin}\,2$. Since there are only $2! = 2$ permutations of two goods, there are only $2 \times 2 = 4$ possible profile pairs $(r_A, r_B)$. The automated decision procedure (`decide`) computes the round-robin draft outcome and resulting Borda utilities across all four cases, confirming that agent A's truthful utility matches her optimal strategic utility in every scenario.

    lines 4–5

      revert rA rB
      decide

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- For m = 2 goods, agent A cannot gain by manipulation in the alternating draft. -/theorem round_robin_borda_gain_two_goods (rA rB : Fin 2 ≃ Fin 2) :    round_robin_u_best 2 rA rB = round_robin_u_truth 2 rA rB := by  revert rA rB  decide
See it in the graphDiscuss this resultChallenge it