Finite-support setting of the DSIC duality framework
DefinitionDSICCompComp_Supplement_FiniteSettinglp-dualitymechanism-designp2o-gran-per-chapterp2o-plan-paperp2o-v1revenue-maximization
The duality framework of Appendix C considers bidders and items, where bidder draws her value vector from a distribution with finite support and probability mass function , positive on with . Bidders are independent (not necessarily identical), so the value profile has law with support .
Formalization Note Bidders are Fin n and items Fin m. Each is a finite set of real vectors and is an arbitrary positive PMF on it: the page's (independent items within a bidder) and nonnegativity of values are not imposed, since nothing in the framework uses them.
Definition code
import Mathlib namespace DSICCompComp namespace Supplement /-- The finite-support setting of the DSIC duality framework (Ryu–Weinberg–Xue, *The DSIC Competition Complexity of Additive Buyers over Independent Items*, STOC 2027 submission, manuscript of Nov. 3, 2026, sha256 bf61bfdb…, Appendix C, pp.34–35 (pdf pp.35–36) and footnote 15): `n` bidders and `m` items; bidder `i`'s value vector `v_i = (v_i1, …, v_im)` is drawn from a distribution `D_i` with finite support `supp(D_i) = S i` and PMF `f_i = f i`, positive on `S i` and summing to `1`; bidders are independent, so the value profile has law `D = ×_i D_i` (see `jointPMF`). **Formalization Note** Bidders are `Fin n` and items `Fin m` (0-based). Values are real vectors and `f_i` is an arbitrary positive PMF on the finite set `S i`; the page's `D_i = ×_j D_ij` (independent items within a bidder) and nonnegative values are not imposed. -/ structure FiniteSetting (n m : ℕ) where /-- `supp(D_i)`, the finite set of bidder `i`'s possible value vectors. -/ S : Fin n → Finset (Fin m → ℝ) /-- `f_i`, the PMF of `D_i` on `supp(D_i)`. -/ f : (i : Fin n) → S i → ℝ f_pos : ∀ i v, 0 < f i v f_sum : ∀ i, ∑ v, f i v = 1 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…), Appendix C, pp.34–35 (pdf pp.35–36) and footnote 15