hide
Free keywords:
Computer Science, Computer Science and Game Theory, cs.GT,Computer Science, Data Structures and Algorithms, cs.DS
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 welfare can be achieved this way, giving bounds on
the welfare at equilibrium. Recently, however, criticism has been raised that
equilibria are hard to compute and therefore unlikely to be attained.
In this paper, we take a different perspective. We study simple best-response
dynamics. That is, agents are activated one after the other and each activated
agent updates his strategy myopically to a best response against the other
agents' current strategies. 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
remain in states of good welfare after each agent has updated his bid at least
once.
In more detail, we show that if agents have fractionally subadditive
valuations, natural dynamics reach and remain in a state that provides a $1/3$
approximation to the optimal welfare after each agent has updated his bid at
least once. For subadditive valuations, we can guarantee a $\Omega(1/\log m)$
approximation in case of $m$ items that applies after each agent has updated
his bid at least once and at any point after that. The latter bound is
complemented by a negative result, showing that no kind of best-response
dynamics can guarantee more than a $o(\log \log m/\log m)$ fraction of the
optimal social welfare.
