Truthfulness with value-maximizing bidders: On the limits of approximation in combinatorial markets
Salman Fadaei and
European Journal of Operational Research, 2017, vol. 260, issue 2, 767-777
In some markets bidders want to maximize value subject to a budget constraint rather than payoff. This is different to the quasilinear utility functions typically assumed in auction theory 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, 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. Approximation has been used as remedy to achieve truthfulness on other mechanism design problems, and we study which approximation ratios we can get from truthful mechanisms. We show that the approximation ratio that can be achieved with a deterministic and truthful approximation mechanism with n bidders cannot be higher than 1/n for general valuations. For randomized approximation mechanisms there is a framework with a ratio that is tight.
Keywords: Auctions/bidding; Game theory; Approximation mechanisms (search for similar items in EconPapers)
References: View references in EconPapers View complete reference list from CitEc
Citations View citations in EconPapers (1) Track citations by RSS feed
Downloads: (external link)
Full text for ScienceDirect subscribers only
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:260:y:2017:i:2:p:767-777
Access Statistics for this article
European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati
More articles in European Journal of Operational Research from Elsevier
Series data maintained by Dana Niculescu ().