Theorem C.4 — DSIC duality: revenue -virtual welfare, equality iff slackness, and the optimal pair
OpenDSICCompComp.Supplement.theorem_C_4Consider the finite-support setting of Appendix C: independent bidders and items, bidder 's values drawn from with finite support and PMF , joint PMF on , and a non-participation type . Let be the feasible set of the DSIC revenue LP, the polyhedron of its non-DSIC constraints, the partial Lagrangian that Lagrangifies the DSIC constraints, and the virtual value function of Definition C.3.
Theorem.
- If satisfies flow conservation, then for all the revenue of is at most the virtual welfare of with respect to :
- For such and , equality holds if and only if for all bidders , values , reports and profiles with , the corresponding DSIC constraint binds.
- If is a revenue-optimal DSIC/IR mechanism (an optimal solution of the LP) and is an optimal dual solution (a minimizer of over ), then the revenue of equals the virtual welfare of with respect to , and
This is the DSIC analogue of the Cai–Devanur–Weinberg duality framework: because there is a DSIC constraint for every profile of the other bidders, the flow may depend on . The paper uses it, through a discretization limit, to upper-bound the optimal DSIC revenue in the proof of Theorem 4.1.
Formalization Note A dual solution is lam i v w with a full profile and none . Part 3 does not assume flow conservation of , nor strong duality.
Differences from the source:
- generalization: D_i = ×_j D_ij with values in ℝ≥0^m and finite support → an arbitrary positive PMF f_i on an arbitrary finite set S_i ⊆ ℝ^m; reason: neither independence of items within a bidder nor nonnegativity of values is used; the page's setting is the special case of product PMFs on nonnegative vectors
- reading: λ^{v_{-i}}_i(v_i, v'_i), 'the Lagrange multiplier corresponding to the DSIC constraint' → λ ≥ 0 as a hypothesis of parts 1–2, and the dual minimized over λ ≥ 0 in part 3; reason: multipliers of inequality constraints are nonnegative and the proof uses it ('the terms ... multiplied by dual variables is nonnegative'); flow conservation of λ* is not assumed (the paper derives it by Lemma C.2)
- encoding: λ^{v_{-i}}_i(v_i, v'i) for i, v{-i}, v_i ∈ supp(D_i), v'i ∈ supp(D_i) ∪ {∅} → lam i v w with v ∈ supp(D) the full profile and w : Option (S i); reason: a bijective re-indexing ((v{-i}, v_i) ↔ v)
- encoding: variables x_ij(v), p_i(v) at v ∈ supp(D) and at (∅, v_{-i}) → x, p defined on all report profiles in ×_i (S_i ∪ {∅}); reason: the extra variables (two or more ∅ entries) occur in no constraint, objective or Lagrangian
- encoding: g(λ) = max_{(x,p)∈P(D)} L(λ, x, p) → the supremum in EReal; reason: it equals the maximum when finite and represents +∞ when L is unbounded above (Lemma C.2)
- encoding: Φ^λ defined for flow-conserving λ → the same formula for every λ; reason: it is used only with flow-conserving λ in parts 1–2, and in part 3 λ* conserves flow by Lemma C.2
- encoding: (x*, p*) ∈ argmax_{(x,p)∈P(D)} Σ_v f(v) Σ_i x_i(v)·Φ^{λ*}_i(v) → (x*, p*) ∈ P(D) and its virtual welfare is ≥ that of every (x, p) ∈ P(D); reason: the definition of argmax
- encoding: 'the corresponding DSIC constraint binds' → dsicSlack E sol v i w = 0; reason: dsicSlack is the difference of the two sides of that constraint
import Mathlib import Definitions.Def_DSICCompComp_Supplement_FlowConservation import Definitions.Def_DSICCompComp_Supplement_virtualWelfare import Definitions.Def_DSICCompComp_Supplement_IsOptimalDual import Definitions.Def_DSICCompComp_Supplement_IsRevenueOptimal
namespace DSICCompComp
namespace Supplement
/-- Theorem C.4 (Ryu–Weinberg–Xue, *The DSIC Competition Complexity of Additive Buyers over Independent Items*, STOC 2027
submission, manuscript of Nov. 3, 2026, sha256 bf61bfdb…,
Theorem C.4, p.36 (pdf p.37)): if `λ` satisfies flow conservation, then for all `(x, p) ∈ P⁺(D)`,
the revenue of `(x, p)` is at most the virtual welfare of `x` with respect to `Φ^λ`:
`E[∑_i p_i(v)] ≤ E[∑_i x_i(v)·Φ^λ_i(v)]`. Equality holds if and only if for all bidders `i`, values
`v_i ∈ supp(D_i)`, `v'_i ∈ supp(D_i) ∪ {∅}` and profiles `v_{-i}` with `λ^{v_{-i}}_i(v_i, v'_i) > 0`, the
corresponding DSIC constraint binds. If `(x*, p*)` is a revenue-optimal DSIC/IR mechanism and `λ*` is
an optimal dual solution, then the revenue of `(x*, p*)` coincides with the virtual welfare of `x*`
with respect to `Φ^{λ*}` and `(x*, p*) ∈ argmax_{(x,p) ∈ P(D)} ∑_{v} f(v)·∑_i x_i(v)·Φ^{λ*}_i(v)`.
**Formalization Note** The three conjuncts are the three sentences. Dual variables are Lagrange
multipliers of inequality constraints, so `λ ≥ 0` is part of the setting in the first two parts, and
the dual is minimized over `λ ≥ 0` in the third; flow conservation of `λ*` is not assumed in the third
part (the paper derives it from optimality, Lemma C.2). Dual solutions are encoded as in
`FlowConservation`: `lam i v w = λ^{v_{-i}}_i(v_i, w)`. -/
theorem theorem_C_4 {n m : ℕ} (E : FiniteSetting n m) :
(∀ lam : (i : Fin n) → ((k : Fin n) → E.S k) → Option (E.S i) → ℝ,
(∀ i v w, 0 ≤ lam i v w) → FlowConservation E lam →
∀ sol : LPSolution E, InPPlus E sol → lpRevenue E sol ≤ virtualWelfare E lam sol) ∧
(∀ lam : (i : Fin n) → ((k : Fin n) → E.S k) → Option (E.S i) → ℝ,
(∀ i v w, 0 ≤ lam i v w) → FlowConservation E lam →
∀ sol : LPSolution E, InPPlus E sol →
(lpRevenue E sol = virtualWelfare E lam sol ↔
∀ (i : Fin n) (v : (k : Fin n) → E.S k) (w : Option (E.S i)),
0 < lam i v w → dsicSlack E sol v i w = 0)) ∧
(∀ (solStar : LPSolution E)
(lamStar : (i : Fin n) → ((k : Fin n) → E.S k) → Option (E.S i) → ℝ),
IsRevenueOptimal E solStar → IsOptimalDual E lamStar →
lpRevenue E solStar = virtualWelfare E lamStar solStar ∧
InP E solStar ∧
∀ sol : LPSolution E, InP E sol →
virtualWelfare E lamStar sol ≤ virtualWelfare E lamStar solStar) := by sorry
end Supplement
end DSICCompComp