用多臂赌博机方法高效设计满足激励相容的拍卖机制
Achieving PAC Guarantees in Mechanism Design through Multi-Armed Bandits
- 将机制设计中的关键计算转化为多臂赌博机问题
- 实现概率近似正确估计，复杂度从指数级降为O(N log N)
- 可扩展至128人规模，显著优于以往方法
我们解析推导出一类最优解，用于自动机制设计，满足效率、激励相容、期望强预算平衡（SBB）和个体理性（IR）。这些解可通过数量远少于原始变量集的基变量表示。然而，随着玩家数N增加，求解关键项需指数级优化步数。为此，我们将该求解过程转化为多臂赌博机（MAB）问题，提出一种概率近似正确（PAC）估计器，具有渐近最优样本复杂度。该方法将优化复杂度从指数级降至O(N log N)。数值实验表明，本方法能高效计算出具备目标性质的机制，可扩展至最多128名玩家，显著优于先前工作。
原文摘要 · Abstract (English)
We analytically derive a class of optimal solutions to a linear program (LP) for automated mechanism design that satisfies efficiency, incentive compatibility, strong budget balance (SBB), and individual rationality (IR), where SBB and IR are enforced in expectation. These solutions can be expressed using a set of essential variables whose cardinality is exponentially smaller than the total number of variables in the original formulation. However, evaluating a key term in the solutions requires exponentially many optimization steps as the number of players $N$ increases. We address this by translating the evaluation of this term into a multi-armed bandit (MAB) problem and develop a probably approximately correct (PAC) estimator with asymptotically optimal sample complexity. This MAB-based approach reduces the optimization complexity from exponential to $O(N\log N)$. Numerical experiments confirm that our method efficiently computes mechanisms with the target properties, scaling to problems with up to $N=128$ players -- substantially improving over prior work.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。