arXiv:2606.10112cs.GTcs.AI2026-06

用深度学习求解多物品多买家拍卖的最优收益上界,给出可验证的计算证明。

Duality for Optimal Multi-Item, Multi-Bidder Auction Design: Revenue Certificates through Deep Learning

论文配图:Duality for Optimal Multi-Item, Multi-Bidder Auction Design: Revenue Certificates through Deep Learning
图 1 · 摘自论文原文
  • 用神经网络参数化对偶变量,保证流量守恒,实现梯度下降优化。
  • 提出新提升技术,将离散解推广到连续类型,得到可靠收益上界。
  • 首次为复杂拍卖设计提供近优性计算证书,适合机制设计研究者。

多物品、多买家拍卖的收益最优机制设计仍是基础性开放问题,除特定二元类型外,尚无闭式解。本文提出首个直接求解该类拍卖对偶问题的计算框架,结合主导策略激励相容(DSIC),生成可验证的收益上界。方法通过神经网络参数化拉格朗日乘子,结构上保证严格流量守恒,支持梯度下降高效优化可行对偶解。为弥合离散计算与连续类型理论之间的鸿沟,开发一种新颖的提升技术,将粗粒度离散化下的对偶证人映射至细粒度逼近。证明该提升法在连续均匀估值下仍提供有效收益上界;并推广至任意连续分布,表明提升后的对偶解在离散极限下收敛至原始连续问题的收益。通过恢复经典情形的已知解析机制验证框架有效性;对多物品多买家问题,框架显示最优收益与现有最佳DSIC机制间差距极小,提供近优性计算证书。

原文摘要 · Abstract (English)

Characterizing revenue-optimal auctions for multi-item, multi-bidder settings remains a fundamental open problem, with no known closed-form solution existing beyond restrictive binary-type instances. This has motivated interest in computational approaches to optimal auction design. In this paper, we introduce the first computational framework that directly tackles the dual problem for multi-item, multi-bidder auctions and dominant-strategy incentive compatibility (DSIC), generating certified revenue upper bounds. Our approach parametrizes Lagrange multipliers with a structurally guaranteed strict flow-conservation property using neural networks, enabling efficient optimization over feasible dual solutions via gradient descent. To bridge the gap between discrete computational methods and theoretical guarantees for continuous types, we develop a novel lifting technique that maps dual certificates from coarse discretizations to fine refinements. We prove that lifting gives valid revenue upper bounds for multi-item, multi-bidder auctions with continuous uniform valuations. Furthermore, we give a generalized lifting construction for arbitrary continuous distributions and demonstrate that these lifted duals converge to the revenue of the original continuous problem in the discrete limit. We validate this computational framework for the dual auction design problem by recovering known analytical mechanisms for canonical instances. For multi-item multi-bidder problems, our framework establishes a small gap between the optimal revenue and best-known DSIC mechanisms, providing computational certificates of near-optimality.

拍卖设计对偶优化深度学习机制设计

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。