5 papers
Tight Liquid Welfare Guarantees for Auctions with Budgets via LP Duality
Twan Kroll, Guido Schäfer, Artem Tsikiridis
We study the efficiency of auctions with budget-constrained bidders and derive tight price of anarchy (PoA) bounds for coarse correlated equilibria (CCE). To this end, we develop a…
Mechanism Design with Outliers and Predictions
Argyrios Deligkas, Eduard Eiben, Sophie Klumper +2
We initiate the study of mechanism design with outliers, where the designer can discard agents from the social cost objective. This setting is particularly relevant when some a…
Optimal Type-Dependent Liquid Welfare Guarantees for Autobidding Agents with Budgets
Riccardo Colini-Baldeschi, Sophie Klumper, Twan Kroll +3
Online advertising systems have recently transitioned to autobidding, allowing advertisers to delegate bidding decisions to automated agents. Each advertiser directs their agent to…
Online Budget-Feasible Mechanism Design with Predictions
Georgios Amanatidis, Evangelos Markakis, Christodoulos Santorinaios +3
Augmenting the input of algorithms with predictions is an algorithm design paradigm that suggests leveraging a (possibly erroneous) prediction to improve worst-case performance gua…
The Effectiveness of Golden Tickets and Wooden Spoons for Budget-Feasible Mechanisms
Bart de Keijzer, Guido Schäfer, Artem Tsikiridis +1
One of the main challenges in mechanism design is to carefully engineer incentives ensuring truthfulness while maintaining strong social welfare approximation guarantees. But these…