Theorem 5.3 — Duality
ProvedSecondBestTrade.HalfEfficiency.dualityalgorithmic-game-theorymechanism-designp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1
For every useful dual , let . Then
and the minimum is attained by a useful dual.
The lower envelope is over exactly the nonnegative useful-flow domain. An explicit minimizing witness accompanies the infimum equality; compactness is not assumed.
Differences from the source:
- encoding: finite agent, trade and support sets with product-prior expectations → Fin labels, an injective nonnegative-vector support embedding, and finite product-weighted sums; reason: bijections cover every finite source market, and summing an overwritten own coordinate multiplies by its total probability one
- encoding: attained minimum of useful dual objectives → real infimum equality together with a useful dual attaining SB and the universal lower bound; reason: the witness and the bound make this exactly the minimum assertion, including nonemptiness and boundedness
Preamble
import Mathlib import Definitions.Def_SecondBestTrade_HalfEfficiency_Dual open scoped BigOperators NNReal open MeasureTheory set_option autoImplicit false noncomputable section
Formal statement
namespace SecondBestTrade.HalfEfficiency
/-- Theorem 5.3, printed p. 9 (PDF p. 10). -/
theorem duality (N : Market) :
(∀ z : Dual N, useful N z → SB N ≤ dualObjective N z) ∧
SB N = sInf {r | ∃ z : Dual N, useful N z ∧ r = dualObjective N z} ∧
∃ z : Dual N, useful N z ∧ dualObjective N z = SB N := by sorry
end SecondBestTrade.HalfEfficiency
Source
Dirk Bergemann, Yang Cai, Kangning Wang, Jinzhao Wu, Renzhe Xu, STOC 2027 submission #529 (October 2026), Theorem 5.3 — Duality, printed p. 9 (PDF p. 10)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.