two_agent_welfare_regret
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