Best-response dynamics in combinatorial auctions with item bidding

Paul Dütting and Thomas Kesselheim

LSE Research Online Documents on Economics from London School of Economics and Political Science, LSE Library

Abstract: In a combinatorial auction with item bidding, agents participate in multiple single-item second-price auctions at once. As some items might be substitutes, agents need to strategize in order to maximize their utilities. A number of results indicate that high social welfare can be achieved this way, giving bounds on the welfare at equilibrium. Recently, however, criticism has been raised that equilibria of this game are hard to compute and therefore unlikely to be attained. In this paper, we take a different perspective by studying simple best-response dynamics. Often these dynamics may take exponentially long before they converge or they may not converge at all. However, as we show, convergence is not even necessary for good welfare guarantees. Given that agents’ bid updates are aggressive enough but not too aggressive, the game will reach and remain in states of high welfare after each agent has updated his bid at least once.

Keywords: algorithmic game theory; combinatorial auctions; item bidding; best-response dynamics (search for similar items in EconPapers)
JEL-codes: J1 (search for similar items in EconPapers)
Pages: 21 pages
Date: 2020-10-01
New Economics Papers: this item is included in nep-des, nep-gth, nep-mic and nep-ore
References: View references in EconPapers View complete reference list from CitEc
Citations:

Published in Games and Economic Behavior, 1, October, 2020. ISSN: 0899-8256

Downloads: (external link)
http://eprints.lse.ac.uk/106607/ Open access version. (application/pdf)

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:ehl:lserod:106607

Access Statistics for this paper

More papers in LSE Research Online Documents on Economics from London School of Economics and Political Science, LSE Library LSE Library Portugal Street London, WC2A 2HD, U.K.. Contact information at EDIRC.
Bibliographic data for series maintained by LSERO Manager ().