Truthfulness in advertising? Approximation mechanisms for knapsack bidders

Martin Bichler and Sören Merting

European Journal of Operational Research, 2018, vol. 270, issue 2, 775-783

Abstract: Quasilinear utility functions are a standard assumption in auction theory allowing for truthful and welfare-maximizing auction mechanisms. However, the literature on advertising markets suggests that the utility model of bidders rather resembles a knapsack problem, where advertisers try to maximize the sum of item values subject to a budget for a marketing campaign. Non-quasilinear environments rarely allow for truthful mechanisms. Nonetheless, some characteristics of the market environment might allow for positive results. In particular, markets are large and bidders typically consider prices as exogenous. We introduce a model of advertising markets, and study whether truthful and prior-free approximation mechanisms with good approximation ratios of the maximal welfare are possible. We analyze the offline mechanism design problem and find a truthful and randomized mechanism with an approximation ratio of only 4. This mechanism draws on a fractional deferred acceptance algorithm and randomized rounding, and it illustrates how the relax-and-round principle can be implemented in this non-quasilinear environment. The article highlights the types of assumptions necessary for truthful mechanisms with good approximation ratios in an important class of non-quasilinear utility functions.

Keywords: Multi-agent systems; Auctions/bidding; Approximation mechanisms (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221718302728
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: https://EconPapers.repec.org/RePEc:eee:ejores:v:270:y:2018:i:2:p:775-783

DOI: 10.1016/j.ejor.2018.04.001

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
Bibliographic data for series maintained by Catherine Liu ().