Best-response dynamics in combinatorial auctions with item

• 成果类型: Article
• 署名作者: Dutting, Paul; Kesselheim, Thomas
• 署名单位: University of London; London School Economics & Political Science; University of Bonn
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2020.09.006
• 发表日期: 2022
• 页码: 428-448
• 关键词: Algorithmic game theory; combinatorial auctions; Item bidding; best-response dynamics

摘要

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.