← 研踪 PaperTrailarXiv:2608.01693 · v3
Money Burning Mechanism Design: From Welfare to Surplus
首次提交 2026-08-03 12:45
版本更新 2026-11-03 00:17
雷达观测 2026-11-04 23:41
摘要
We study mechanism design for consumer-surplus maximization, where the objective is the total value generated minus the payments charged to agents. This objective captures settings in which incentives rely on costly actions, such as waiting or effort, whose costs are lost rather than transferred. We settle the welfare-approximation question of Hartline and Roughgarden [HR08] by determining the exact worst-case loss from money burning in general multidimensional environments. For $n$ agents with arbitrary nonnegative valuations over a finite outcome space, we give a universally truthful, ex-post individually rational mechanism with nonnegative payments whose expected consumer surplus is at least a $1/H_n$ fraction of optimal welfare for every valuation profile, where $H_n=\sum_{k=1}^n 1/k$. The mechanism requires no knowledge of the agents' value distributions. Nevertheless, the factor $H_n$ is worst-case optimal, including its constant, even for a single-item auction with a known i.i.d.\ prior and Bayesian incentive compatibility. Thus, the optimal worst-case loss is exactly the same for arbitrary multidimensional preferences as for a single item: neither the number of goods nor the complexity of preferences increases this loss. We further give black-box reductions from welfare approximation to consumer-surplus maximization. On valuation domains closed under scaling, any truthful, ex-post individually rational $α$-approximation for welfare with nonnegative payments yields an $O(α\log n)$-approximation for surplus while preserving these incentive properties. For known finite-support product priors and exact interim-value access, a Bayesian reduction converts arbitrary allocation algorithms, even nontruthful ones, into Bayesian incentive-compatible, ex-post individually rational mechanisms with nonnegative payments and an $H_n+\varepsilon$ loss for every $\varepsilon>0$.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v3 · 2026-11-03 00:17 · 最新观测版本
Money Burning Mechanism Design: From Welfare to Surplus
We study mechanism design for consumer-surplus maximization, where the objective is the total value generated minus the payments charged to agents. This objective captures settings in which incentives rely on costly actions, such as waiting or effort, whose costs are lost rather than transferred. We settle the welfare-approximation question of Hartline and Roughgarden [HR08] by determining the exact worst-case loss from money burning in general multidimensional environments. For $n$ agents with arbitrary nonnegative valuations over a finite outcome space, we give a universally truthful, ex-post individually rational mechanism with nonnegative payments whose expected consumer surplus is at least a $1/H_n$ fraction of optimal welfare for every valuation profile, where $H_n=\sum_{k=1}^n 1/k$. The mechanism requires no knowledge of the agents' value distributions. Nevertheless, the factor $H_n$ is worst-case optimal, including its constant, even for a single-item auction with a known i.i.d.\ prior and Bayesian incentive compatibility. Thus, the optimal worst-case loss is exactly the same for arbitrary multidimensional preferences as for a single item: neither the number of goods nor the complexity of preferences increases this loss. We further give black-box reductions from welfare approximation to consumer-surplus maximization. On valuation domains closed under scaling, any truthful, ex-post individually rational $α$-approximation for welfare with nonnegative payments yields an $O(α\log n)$-approximation for surplus while preserving these incentive properties. For known finite-support product priors and exact interim-value access, a Bayesian reduction converts arbitrary allocation algorithms, even nontruthful ones, into Bayesian incentive-compatible, ex-post individually rational mechanisms with nonnegative payments and an $H_n+\varepsilon$ loss for every $\varepsilon>0$.
查看此版本解读 →查看此版本原文 ↗