论文标题
简单的组合拍卖具有预算限制
Simple combinatorial auctions with budget constraints
论文作者
论文摘要
我们研究了简单组合拍卖的效率，以分配一组项目为一组代理，具有私人的次要估值功能和预算限制。我们考虑的类包括所有拍卖，这些拍卖会独立地分配给提交最高出价的代理商，并要求仅针对所有代理商的投标付款。该课程的两个众所周知的例子是同时的第一和第二价格拍卖。我们专注于诱发战略游戏的纯平衡，并使用液体福利作为我们的效率基准，我们在此类拍卖中的任何拍卖的无政府状态价格显示了2个上限，以及对所有拍卖规则的稳定性的紧密相应下降，其稳定性是均值的稳定性。这意味着2个紧密的限制是众所周知的同时首次和第二个价格拍卖的稳定价格，这是该班级的成员。此外，我们显示了整个班级的下限，用于更复杂的拍卖（例如VCG），以及假定预算是常识而不是私人信息的设置。
We study the efficiency of simple combinatorial auctions for the allocation of a set of items to a set of agents, with private subadditive valuation functions and budget constraints. The class we consider includes all auctions that allocate each item independently to the agent that submits the highest bid for it, and requests a payment that depends on the bids of all agents only for this item. Two well-known examples of this class are the simultaneous first and second price auctions. We focus on the pure equilibria of the induced strategic games, and using the liquid welfare as our efficiency benchmark, we show an upper bound of 2 on the price of anarchy for any auction in this class, as well as a tight corresponding lower bound on the price of stability for all auctions whose payment rules are convex combinations of the bids. This implies a tight bound of 2 on the price of stability of the well-known simultaneous first and second price auctions, which are members of the class. Additionally, we show lower bounds for the whole class, for more complex auctions (like VCG), and for settings where the budgets are assumed to be common knowledge rather than private information.
