The Simple Economics of Approximately Optimal Auctions
The Simple Economics of Approximately Optimal Auctions
复制标题
近似最优拍卖的简单经济学
DOI：
10.1109/focs.2013.73
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Jason D. Hartline
中科院分区：
文献类型：
--
作者：
S. Alaei;Hu Fu;Nima Haghpanah;Jason D. Hartline
利润通过边际收益最大化而最优化的直觉是微观经济学的指导原则。在具有准线性效用和单维偏好的经典拍卖理论中，BR89证明了M81的最优拍卖实际上是边际收益的最优。特别是迈尔森的虚拟价值，正是一个适当的收入曲线的衍生物。本文考虑了在代理人具有多维和非线性偏好的环境中的机制设计。了解这些环境下的好拍卖被认为是贝叶斯最优机制设计的主要挑战。在这些环境中，最大化边际收益可能不是最优的，而且，有时没有直接的方法来实现边际收益最大化机制。我们的贡献有三个方面：我们的特点的设置，边际收入最大化是最佳的（通过确定一个重要的条件，我们称之为收入线性），我们给出了简单的程序，实现边际收入最大化的一般，我们表明，边际收入最大化是近似最优的。我们的近似因子在量化环境离理想环境有多远的项中平滑地退化（即，边际收益最大化是最优的）。由于边际收益机制是最佳的研究单维代理，我们的推广立即扩展了许多近似结果单维代理更一般的喜好。最后，贝叶斯算法机制设计中最大的开放问题之一是开发在代理类型空间的大小上不是蛮力的方法（通常是多维代理的维度上的指数）。我们的方法确定了一个子问题，例如，对于具有从产品分布中提取的值的单位需求代理，启用在维度上为多项式的近似机制。
The intuition that profit is optimized by maximizing marginal revenue is a guiding principle in microeconomics. In the classical auction theory for agents with quasi-linear utility and single-dimensional preferences, BR89 show that the optimal auction of M81 is in fact optimizing marginal revenue. In particular Myerson's virtual values are exactly the derivative of an appropriate revenue curve. This paper considers mechanism design in environments where the agents have multi-dimensional and non-linear preferences. Understanding good auctions for these environments is considered to be the main challenge in Bayesian optimal mechanism design. In these environments maximizing marginal revenue may not be optimal, and furthermore, there is sometimes no direct way to implement the marginal revenue maximization mechanism. Our contributions are three fold: we characterize the settings for which marginal revenue maximization is optimal (by identifying an important condition that we call revenue linearity), we give simple procedures for implementing marginal revenue maximization in general, and we show that marginal revenue maximization is approximately optimal. Our approximation factor smoothly degrades in a term that quantifies how far the environment is from an ideal one (i.e., where marginal revenue maximization is optimal). Because the marginal revenue mechanism is optimal for well-studied single-dimensional agents, our generalization immediately extends many approximation results for single-dimensional agents to more general preferences. Finally, one of the biggest open questions in Bayesian algorithmic mechanism design is in developing methodologies that are not brute-force in size of the agent type space (usually exponential in the dimension for multi-dimensional agents). Our methods identify a sub problem that, e.g., for unit-demand agents with values drawn from product distributions, enables approximation mechanisms that are polynomial in the dimension.