The polyhedron
DefinitionDSICCompComp_Supplement_InPlp-dualitymechanism-designp2o-gran-per-chapterp2o-plan-paperp2o-v1revenue-maximization
is the set of solutions satisfying the constraints of the DSIC revenue LP other than the DSIC constraints:
- for all items and ;
- for all , and ;
- for all , and ;
- for all and .
Payments are unconstrained in sign. is the domain over which the partial Lagrangian is maximized.
Formalization Note is read off a full profile whose -th entry is overwritten; each is nonempty because sums to , so this ranges over exactly .
Definition code
import Mathlib
import Definitions.Def_DSICCompComp_Supplement_LPSolution
import Definitions.Def_DSICCompComp_Supplement_devProfile
namespace DSICCompComp
namespace Supplement
/-- Membership in the polyhedron `P(D)` of Appendix C (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, p.35 (pdf p.36)): the constraints of the DSIC revenue LP other than the DSIC
constraints, namely
1. `∑_i x_ij(v) ≤ 1` for all items `j` and `v ∈ supp(D)`;
2. `x_ij(v) ≥ 0` for all `i`, `j` and `v ∈ supp(D)`;
3. `x_ij(∅, v_{-i}) = 0` for all `i`, `j` and `v_{-i} ∈ supp(D_{-i})`;
4. `p_i(∅, v_{-i}) = 0` for all `i` and `v_{-i} ∈ supp(D_{-i})`.
**Formalization Note** `v_{-i}` is read off a full profile `v` (its `i`-th entry is overwritten by
`devProfile`); every `supp(D_i)` is nonempty since `f_i` sums to `1`, so this ranges over exactly
`supp(D_{-i})`. Payments are unconstrained in sign. -/
def InP {n m : ℕ} (E : FiniteSetting n m) (sol : LPSolution E) : Prop :=
(∀ (v : (i : Fin n) → E.S i) (j : Fin m), ∑ i, sol.x (fun k => some (v k)) i j ≤ 1) ∧
(∀ (v : (i : Fin n) → E.S i) (i : Fin n) (j : Fin m), 0 ≤ sol.x (fun k => some (v k)) i j) ∧
(∀ (v : (i : Fin n) → E.S i) (i : Fin n) (j : Fin m), sol.x (devProfile E v i none) i j = 0) ∧
(∀ (v : (i : Fin n) → E.S i) (i : Fin n), sol.p (devProfile E v i none) i = 0)
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, p.35 (pdf p.36)