Ex-post utility of bidder with values reporting
DefinitionDSICCompComp_Supplement_interimIntegrandcompetition-complexitymechanism-designp2o-gran-per-chapterp2o-plan-paperp2o-v1revenue-maximization
Consider additive bidders and items, and a mechanism with ex-post allocation rule (the probability that bidder receives item ) and payment rule . For a bidder , her true value vector , a report and a value profile whose entries other than the -th give the reports of the other bidders, the bidder's ex-post utility is
Its expectation over is the interim utility that appears in the Bayesian incentive compatibility and individual rationality constraints.
Formalization Note Mechanisms are the published MultiItemRev.MultiBuyer.MechanismN n (Fin m); bidders and items are 0-based. The profile is Function.update v i vi', so the -th entry of v is ignored.
Definition code
import Mathlib
import Definitions.Def_MultiItemRev_MultiBuyer_Model
open scoped NNReal
namespace DSICCompComp
namespace Supplement
/-- The ex-post utility of bidder `i` with true values `v_i` (here `vi`) when she reports `v'_i`
(here `vi'`) and the other bidders report `v_{-i}`, read off a full profile `v`:
`∑_j x_ij(v'_i, v_{-i}) · v_ij − p_i(v'_i, v_{-i})` (Ryu–Weinberg–Xue, *The DSIC Competition Complexity of Additive Buyers over Independent Items*, STOC 2027
submission, manuscript of Nov. 3, 2026, sha256 bf61bfdb…,
Section 2, BIC and BIR, pp.5–6 (pdf pp.6–7)). Its expectation over `v_{-i} ∼ D^{n-1}` is the
interim utility in the BIC/BIR constraints.
**Formalization Note** Mechanisms are the published `MultiItemRev.MultiBuyer.MechanismN n (Fin m)`
(`q v i j` = probability that bidder `i` gets item `j`, `s v i` = her payment); bidders and items
are 0-based. The deviation profile `(v'_i, v_{-i})` is `Function.update v i vi'`, so the `i`-th
coordinate of `v` is ignored; values are in `ℝ≥0`. -/
def interimIntegrand {n m : ℕ} (M : MultiItemRev.MultiBuyer.MechanismN n (Fin m)) (i : Fin n)
(vi vi' : Fin m → ℝ≥0) (v : Fin n → Fin m → ℝ≥0) : ℝ :=
∑ j, M.q (Function.update v i vi') i j * (vi j : ℝ) - M.s (Function.update v i vi') i
end Supplement
end DSICCompComp
Source
Ryu–Weinberg–Xue, The DSIC Competition Complexity of Additive Buyers over Independent Items, STOC 2027 submission (manuscript of Nov. 3, 2026, sha256 bf61bfdb…), Section 2, BIC and BIR, pp.5–6 (pdf pp.6–7)