@inproceedings{d0c1355ba14e4ef4a3778633a09238e5,
title = "Truthfulness and approximation with value-maximizing bidders",
abstract = "In many markets bidders want to maximize value rather than payoff. This is different to the quasi-linear utility functions, and leads to different strategies and outcomes. We refer to bidders who maximize value as value bidders. While simple single-object auction formats are truthful for value bidders, standard multi-object auction formats allow for manipulation. It is straightforward to show that there cannot be a truthful and revenue-maximizing deterministic auction mechanism with value bidders and general valuations. Using approximation as a means to achieve truthfulness, we study truthful approximation mechanisms for value bidders. We show that the approximation ratio that can be achieved with a deterministic and truthful approximation mechanism with n bidders and m items cannot be higher than 1/n for general valuations. For randomized approximation mechanisms there is a framework with a ratio of O(√m/ϵ3) with probability at least 1 − ϵ, for 0 < ϵ < 1.",
keywords = "Approximation mechanisms, Revenue, Truthfulness, Value bidders",
author = "Salman Fadaei and Martin Bichler",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2016.; 9th International Symposium on Algorithmic Game Theory, SAGT 2016 ; Conference date: 19-09-2016 Through 21-09-2016",
year = "2016",
doi = "10.1007/978-3-662-53354-3_19",
language = "English",
isbn = "9783662533536",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "235--246",
editor = "Martin Gairing and Rahul Savani",
booktitle = "Algorithmic Game Theory - 9th International Symposium, SAGT 2016, Proceedings",
}