Title: Mechanism Design for Auctions with Externalities on Budgets Show Chinese title

Title: 具有预算外部性的拍卖机制设计

Abstract: This paper studies mechanism design for auctions with externalities on budgets, a novel setting where the budgets that bidders commit are adjusted due to the externality of the competitors' allocation outcomes-a departure from traditional auctions with fixed budgets. This setting is motivated by real-world scenarios, for example, participants may increase their budgets in response to competitors' obtained items. We initially propose a general framework with homogeneous externalities to capture the interdependence between budget updates and allocation, formalized through a budget response function that links each bidder's effective budget to the amount of items won by others. The main contribution of this paper is to propose a truthful and individual rational auction mechanism for this novel auction setting, which achieves an approximation ratio of $1/3$ with respect to the liquid welfare. This mechanism is inspired by the uniform-price auction, in which an appropriate uniform price is selected to allocate items, ensuring the monotonicity of the allocation rule while accounting for budget adjustments. Additionally, this mechanism guarantees a constant approximation ratio by setting a purchase limit. Complementing this result, we establish an upper bound: no truthful mechanism can achieve an approximation ratio better than $1/2$. This work offers a new perspective to study the impact of externalities on auctions, providing an approach to handle budget externalities in multi-agent systems. Show Chinese abstract

Abstract: 本文研究了存在预算外部性的拍卖机制设计，这是一个新的场景，其中竞标者的预算会因竞争对手的分配结果而调整——这与传统固定预算的拍卖不同。 这种设置源于现实场景，例如，参与者可能会因竞争对手获得物品而增加自己的预算。 我们最初提出一个具有同质外部性的通用框架，以捕捉预算更新与分配之间的相互依赖关系，通过一个预算响应函数进行形式化，该函数将每个竞标者的有效预算与其他人赢得的物品数量联系起来。 本文的主要贡献是为这种新型拍卖设置提出一种诚实且个体理性的拍卖机制，其相对于液体福利的近似比为$1/3$。 该机制受到统一价格拍卖的启发，在该拍卖中选择一个适当的统一价格来分配物品，确保分配规则的单调性，同时考虑预算调整。 此外，通过设置购买上限，该机制保证了一个常数近似比。 作为这一结果的补充，我们建立了上界：没有任何诚实机制能实现优于$1/2$的近似比。 这项工作提供了一个新的视角来研究外部性对拍卖的影响，为处理多智能体系统中的预算外部性提供了一种方法。