Incentive compatible budget elicitation in multi-unit auctions
Incentive compatible budget elicitation in multi-unit auctions
复制标题
多单位拍卖中激励兼容的预算激发
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Lirong Xia
中科院分区：
文献类型：
--
作者：
Sayan Bhattacharya;Vincent Conitzer;Kamesh Munagala;Lirong Xia
在本文中，当投标人具有私人估值和私人预算限制时，我们考虑了为多个（同质）单位设计激励兼容拍卖的问题。当只有估值是私人的并且预算是公开的时，Dobzinski等人[8]表明，自适应冠拍着是独特的激励拍卖来实现帕累托的优化。他们进一步表明，这次拍卖并不是私人预算的真实性，因此没有私人预算的确定性帕累托最佳拍卖。我们的主要贡献是展示该拍卖的以下预算单调性财产：当只有一个无限分区的商品时，投标人就无法通过报告小于事实的预算来改善其效用。这意味着在不可能预算过度报告预算时（例如，必须预先出示资金时），自适应弯曲拍卖是激励兼容的。我们还可以使报告更大的预算次优，并对拍卖进行了少量的随机修改。无论哪种情况，这都使经过修改的拍卖帕累托（Pareto）与私人预算具有最佳状态。我们还表明，预算单调性财产不适合拍卖货物的不可分割的单位，显示出可分裂和不可分割的案件之间的鲜明对比。在这种情况下，预算单调性属性也意味着其他改进的结果。为了最大化收入，相同的拍卖可以提高由于艾布拉姆斯[1]的最佳竞争比率，而渐近地接近了最佳单价拍卖的性能。最后，我们考虑贝叶斯环境中收入最大化（或社会福利）的问题。除了私人预算限制外，我们还允许投标人具有公共规模限制（基于他们愿意购买的商品数量）。我们向最佳的贝叶斯兼容机制显示了一个简单的多个计算时间5.83- approximation，该机制可在主要策略中实现。我们的技术再次至关重要的是需要通过随机分组来防止投标人过度报告预算的能力。我们通过设计解决问题的LP松弛方案来显示近似结果，这可能是独立的。
In this paper, we consider the problem of designing incentive compatible auctions for multiple (homogeneous) units of a good, when bidders have private valuations and private budget constraints. When only the valuations are private and the budgets are public, Dobzinski et al [8] show that the adaptive clinching auction is the unique incentive-compatible auction achieving Pareto-optimality. They further show that this auction is not truthful with private budgets, so that there is no deterministic Pareto-optimal auction with private budgets. Our main contribution is to show the following Budget Monotonicity property of this auction: When there is only one infinitely divisible good, a bidder cannot improve her utility by reporting a budget smaller than the truth. This implies that the adaptive clinching auction is incentive compatible when over-reporting the budget is not possible (for instance, when funds must be shown upfront). We can also make reporting larger budgets suboptimal with a small randomized modification to the auction. In either case, this makes the modified auction Pareto-optimal with private budgets. We also show that the Budget Monotonicity property does not hold for auctioning indivisible units of the good, showing a sharp contrast between the divisible and indivisible cases. The Budget Monotonicity property also implies other improved results in this context. For revenue maximization, the same auction improves the best-known competitive ratio due to Abrams [1] by a factor of 4, and asymptotically approaches the performance of the optimal single-price auction. Finally, we consider the problem of revenue maximization (or social welfare) in a Bayesian setting. We allow the bidders have public size constraints (on the amount of good they are willing to buy) in addition to private budget constraints. We show a simple poly-time computable 5.83-approximation to the optimal Bayesian incentive compatible mechanism, that is implementable in dominant strategies. Our technique again crucially needs the ability to prevent bidders from over-reporting budgets via randomization. We show the approximation result via designing a rounding scheme for an LP relaxation of the problem, which may be of independent interest.