Economics at your fingertips  

Truthfulness with value-maximizing bidders: On the limits of approximation in combinatorial markets

Salman Fadaei and Martin Bichler

European Journal of Operational Research, 2017, vol. 260, issue 2, 767-777

Abstract: 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)
Date: 2017
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

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link:

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 ().

Page updated 2018-02-24
Handle: RePEc:eee:ejores:v:260:y:2017:i:2:p:767-777