Deterministic Budget-Feasible Clock Auctions

In the budget-feasible mechanism design problem, an auctioneer with a strict budget constraint is looking to acquire services from a set of self-interested providers. The auctioneer aims to design a polynomial-time strategy-proof mechanism that maximizes the value of the services she acquires, subject to the sum of payments to providers falling within her budget. This problem has attracted a great deal of attention due to its combination of practical relevance and theoretical depth. In “Deterministic Budget-Feasible Clock Auctions,” Balkanski, Garimidi, Gkatzelis, Schoepflin, and Tan provide the first such deterministic mechanism that achieves a constant-factor approximation for instances where the auctioneer’s valuation function is submodular. Moreover, this mechanism achieves an improved approximation even compared with previously known randomized mechanisms, and it takes the form of a clock auction, implying a suite of important properties that make this auction much more practical.