Mechanism Design for Auctions with Externalities on Budgets

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.