人工货币与分开销售:消费者剩余的3-近似算法
Artificial Currency and Separate Selling: A 3-Approximation for Consumer Surplus
Yang Cai, Yingkai Li, Jinzhao Wu
AI 速读 基于摘要
作者研究不可分物品分配中净消费者剩余最大化,证明分开销售与人工货币机制中较优者可在任意贝叶斯-纳什均衡下达到最优消费者剩余的3-近似。
cs.GT
查看原文摘要
We study the allocation of indivisible items to buyers with additive values drawn from independent distributions. The objective is consumer surplus net of burnt payments. We consider artificial-currency mechanisms: buyers receive personalized budgets of a currency worthless outside the mechanism and use them to bid across items. The better of separate selling and artificial-currency mechanisms provides a 3-approximation to optimal consumer surplus. The guarantee holds at every Bayes--Nash equilibrium, without equilibrium selection. Both branches are necessary: either alone may capture only a vanishing share of the optimum. The proof decomposes benchmark surplus into a stable part captured by artificial currency and a variation covered by separate selling.