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.