AFTD Auto-Formalizing Theoretical Domains

two_agent_welfare_regret

def

Given a number of goods m : ℕ, a drafting schedule s : Fin m → Fin 2 of length m, and valuations v : Fin 2 → Fin m → ℝ, the utilitarian welfare regret is the first-best optimal welfare minus the utilitarian welfare of sincere drafting under schedule s.

Statement

noncomputable def two_agent_welfare_regret (m : ℕ) (s : Fin m → Fin 2) (v : Fin 2 → Fin m → ℝ) : ℝ
Defined in
Kalinowski et al., IJCAI 2013
Verified
11 Nov 2026
Axioms
none listed
Built on 2
  • two_agent_draft_welfareGiven a number of goods m : ℕ, a drafting schedule s : Fin m → Fin 2 of length m, and a valuation profile v : Fin 2 → Fin m → ℝ, the…
  • two_agent_first_best_welfareThe first-best utilitarian welfare for two agents over m goods, defined as the sum over all goods of the maximum value assigned by either…
Used by 1
  • two_agent_welfare_regret_nonnegFor any number of goods m : ℕ, any drafting schedule s : Fin m → Fin 2 of length m, and any nonnegative valuation profile v : Fin 2 → Fin…

Read back from the Lean

Given a number of items $m : ℕ$, a draft sequence $s : \text{Fin } m \to \text{Fin } 2$ indicating which agent picks at each turn, and valuation functions $v : \text{Fin } 2 \to \text{Fin } m \to ℝ$ specifying the values of each item for each of the two agents, two_agent_welfare_regret m s v is defined as the real number equal to the first-best social welfare minus the welfare achieved by the draft rule: $$\text{two\_agent\_first\_best\_welfare } m\ v - \text{two\_agent\_draft\_welfare } m\ s\ v$$ Specifically: - The first-best welfare is $\sum_{g : \text{Fin } m} \max(v\ 0\ g, v\ 1\ g)$. - The draft welfare is $\sum_{i : \text{Fin } 2} \sum_{g \in A_i} v\ i\ g$, where $A_i$ is the bundle of items allocated to agent $i$ under the sequential draft mechanism starting with the full set of items $\text{Fin } m$, where at each step the agent $s(t)$ selects the remaining item that maximizes their valuation $v(s(t), \cdot)$, with ties broken in favor of larger item indices in $\text{Fin } m$.

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

/-- The utilitarian welfare regret of a two-agent draft schedule s : Fin m → Fin 2 relative to the first-best allocation. -/
noncomputable def two_agent_welfare_regret (m : ℕ) (s : Fin m → Fin 2) (v : Fin 2 → Fin m → ℝ) : ℝ :=
  two_agent_first_best_welfare m v - two_agent_draft_welfare m s v
See it in the graphDiscuss this resultChallenge it