Lemma A.9 — Lagrangian at a useful dual
ProvedSecondBestTrade.HalfEfficiency.lagrangian_virtual_surplusalgorithmic-game-theorymechanism-designp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix a useful dual . Every transfer coefficient in (A.5) vanishes. For every feasible allocation rule and unrestricted signed transfer rule ,
This removes payments from the useful-dual objective while retaining the full allocation expression, not just its maximum.
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: buyer payments and seller receipts have opposite utility signs → one signed-payment carrier with seller transfer equal to minus its receipt; reason: this is a bijective change of payment coordinates; the original mechanism still has nonnegative payments and receipts
Preamble
import Mathlib import Definitions.Def_SecondBestTrade_HalfEfficiency_Lagrangian open scoped BigOperators NNReal open MeasureTheory set_option autoImplicit false noncomputable section
Formal statement
namespace SecondBestTrade.HalfEfficiency
/-- Lemma A.9, printed p. 25 (PDF p. 26). -/
theorem lagrangian_virtual_surplus (N : Market) (z : Dual N) (hz : useful N z) :
coefficientsVanish N z ∧
∀ m : SignedMechanism N, feasible N m.q →
lagrangian N z m = (1 + (z.tau : ℝ)) *
expect N (fun v => ∑ e, virtualGain N z v e * m.q v e) := by sorry
end SecondBestTrade.HalfEfficiency
Source
Dirk Bergemann, Yang Cai, Kangning Wang, Jinzhao Wu, Renzhe Xu, STOC 2027 submission #529 (October 2026), Lemma A.9 — Lagrangian at a useful dual, printed p. 25 (PDF p. 26)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.