round_robin_borda_gain_two_goods
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
- 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
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`).
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.
revert rA rB decide
- The tactic `revert rA rB` is a formal Lean detail with no counterpart on paper: it converts the free variables into universal quantifiers so that Lean's typeclass mechanism can synthesize a finite decidability instance (`Fintype.decidableForallFintype`). The verification itself is performed entirely by computational evaluation (`decide`) rather than an algebraic derivation.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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