首页|Best-response dynamics in combinatorial auctions with item
Best-response dynamics in combinatorial auctions with item
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Elsevier
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.
Algorithmic game theoryCombinatorial auctionsItem biddingBest-response dynamics
NSTL
Elsevier
