AFTD Auto-Formalizing Theoretical Domains

round_robin_expected_manipulation_gain

def

The real-valued expected normalized strategic manipulation gain, returning a real number defined as the sum over all ranking pairs p in (Fin m ≃ Fin m) × (Fin m ≃ Fin m) of round_robin_borda_manipulation_gain m p.1 p.2, divided by ((Fintype.card (Fin m ≃ Fin m))^2 : ℝ).

Statement

noncomputable def round_robin_expected_manipulation_gain (m : ℕ) : ℝ
Defined in
A Social Welfare Optimal Sequential Allocation Procedure
Verified
11 Nov 2026
Axioms
none listed
Built on 1
  • 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…
Used by 1

Read back from the Lean

round_robin_expected_manipulation_gain m defines the expected manipulation gain (a real number) for the first agent (agent 0) in a two-agent round-robin allocation of m items under Borda utilities, averaged uniformly over all pairs of preferences $(r_A, r_B) \in (\mathrm{Fin}\ m \simeq \mathrm{Fin}\ m)^2$. Specifically, for a given $m \in \mathbb{N}$: 1. Preferences are permutations $r : \mathrm{Fin}\ m \simeq \mathrm{Fin}\ m$ mapping ranks $0, \dots, m-1$ to items. The Borda utility of an item $g$ under ranking $r$ is $m - r^{-1}(g)$ (giving $m$ to the top choice down to $1$ to the last choice), and the utility of a bundle $S \subseteq \mathrm{Fin}\ m$ is $\sum_{g \in S} (m - r^{-1}(g))$. 2. In the round-robin procedure of length $m$, agents 0 and 1 alternate turns ($0, 1, 0, 1, \dots$). At each turn, the designated agent receives their highest-ranked remaining item according to their reported preference. 3. For a preference profile $(r_A, r_B)$: - round_robin_u_truth m rA rB is the Borda utility agent 0 obtains under true preference $r_A$ when both agents report truthfully. - round_robin_u_best m rA rB is the maximum Borda utility agent 0 can achieve (evaluated under true preference $r_A$) by strategically reporting any ranking $r_A' \in \mathrm{Fin}\ m \simeq \mathrm{Fin}\ m$, assuming agent 1 reports $r_B$. - round_robin_borda_manipulation_gain m rA rB is the normalized manipulation gain: $\frac{u_{\text{best}} - u_{\text{truth}}}{m^2}$. 4. round_robin_expected_manipulation_gain m is the arithmetic mean of this normalized manipulation gain over all $(m!)^2$ possible preference pairs $(r_A, r_B) \in (\mathrm{Fin}\ m \simeq \mathrm{Fin}\ m) \times (\mathrm{Fin}\ m \simeq \mathrm{Fin}\ m)$, computed by dividing the sum over all pairs by $(m!)^2 = (\#(\mathrm{Fin}\ m \simeq \mathrm{Fin}\ m))^2$.

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

/-- Expected normalized manipulation gain in ℝ under independent uniform random rankings of m goods. -/
noncomputable def round_robin_expected_manipulation_gain (m : ℕ) : ℝ :=
  (∑ p : (Fin m ≃ Fin m) × (Fin m ≃ Fin m), round_robin_borda_manipulation_gain m p.1 p.2) /
    ((Fintype.card (Fin m ≃ Fin m))^2 : ℝ)
See it in the graphDiscuss this resultChallenge it