English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In a combinatorial auction with item bidding, agents participate in multiplesingle-item second-price auctions at once. As some items might be substitutes,agents need to strategize in order to maximize their utilities. A number ofresults indicate that high welfare can be achieved this way, giving bounds onthe welfare at equilibrium. Recently, however, criticism has been raised thatequilibria are hard to compute and therefore unlikely to be attained.  In this paper, we take a different perspective. We study simple best-responsedynamics. That is, agents are activated one after the other and each activatedagent updates his strategy myopically to a best response against the otheragents' current strategies. Often these dynamics may take exponentially longbefore they converge or they may not converge at all. However, as we show,convergence is not even necessary for good welfare guarantees. Given thatagents' bid updates are aggressive enough but not too aggressive, the game willremain in states of good welfare after each agent has updated his bid at leastonce.  In more detail, we show that if agents have fractionally subadditivevaluations, 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 atleast once. For subadditive valuations, we can guarantee an $\Omega(1/\log m)$approximation in case of $m$ items that applies after each agent has updatedhis bid at least once and at any point after that. The latter bound iscomplemented by a negative result, showing that no kind of best-responsedynamics can guarantee more than an $o(\log \log m/\log m)$ fraction of theoptimal social welfare.

Best-Response Dynamics in Combinatorial Auctions with Item Bidding