Can I read Combinatorial Auctions Do Need Modest Interaction on EtoBox?

Combinatorial Auctions Do Need Modest Interaction by Assadi, Sepehr is a scholarly article available to read on EtoBox.

What is Combinatorial Auctions Do Need Modest Interaction about?

We study the necessity of interaction for obtaining efficient allocations in combinatorial auctions with subadditive bidders. This problem was originally introduced by Dobzinski, Nisan, and Oren (STOC'14) as the following simple market scenario: m items are to be allocated among n bidders in a distributed setting where bidders valuations are private and hence communication is needed to obtain an efficient allocation. The communication happens in rounds: in each round, each bidder, simultaneously with others, broadcasts a message to all parties involved. At the end, the central planner computes an allocation solely based on the communicated messages. Dobzinski et al. showed that (at least some) interaction is necessary for obtaining any efficient allocation: no non-interactive (1-round) protocol with polynomial communication (in the number of items and bidders) can achieve approximation ratio better than Ω(m 1/4 ), while for any r ≥ 1, there exists r -round protocols that achieve O (r • m 1/r +1 ) approximation with polynomial communication; in particular, O (log m) rounds of interaction suffice to obtain an (almost) efficient allocation, i.e., a polylog(m)-approximation. A natural

Author

Assadi, Sepehr

Publisher

ACM Press

Published

2017

Language

EN