Truthfulness and approximation with value-maximizing bidders

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/ϵ³) with probability at least 1 − ϵ, for 0 < ϵ < 1.