论文标题
具有预算限制的分配市场
Assignment Markets with Budget Constraints
论文作者
论文摘要
本文研究了一组不可分割的物品，这些物品将出售给具有艰苦的预算限制的准线性，单位点击估值的竞标者。没有财务限制，Shapley和Shubik（1971）的著名分配市场模型就可以提供一种简单的上升拍卖格式，该格式与激励兼容，并且非常帕累托最佳。但是，这种拍卖模型并不能捕获竞标者面临硬预算限制的可能性。我们设计了一项迭代拍卖，该拍卖取决于需求查询以及易于证实的附加条件，以在预算限制的存在下保持属性。相反，如果这种额外的条件不存在，激励性兼容性和核心稳定性是矛盾的，即使有真实的竞标，我们也无法在简单的升级拍卖中实现强大的帕累托最优性。此外，即使在拍卖师可以获得估值和预算限制的完整信息模型中，问题也是NP-HARD。
This paper studies markets where a set of indivisible items is sold to bidders with quasilinear, unit-demand valuations, subject to a hard budget constraint. Without financial constraints the well-known assignment market model of Shapley and Shubik (1971) allows for a simple ascending auction format that is incentive-compatible, and strongly Pareto-optimal. However, this auction model does not capture the possibility that bidders face hard budget constraints. We design an iterative auction that depends on demand queries and an easily verifiable additional condition to maintain the properties in the presence of budget constraints. If instead this additional condition does not hold, incentive compatibility and core stability are at odds, and we cannot hope to achieve strong Pareto optimality in a simple ascending auction even with truthful bidding. Moreover, even in a complete information model where the auctioneer has access to valuations and budget constraints, the problem is NP-hard.
