On simultaneous two-player combinatorial auctions

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Scopus citations


We consider the following communication problem: Al-ice and Bob each have some valuation functions v1 and v2 over subsets of m items, and their goal is to partition the items into S; S in a way that maximizes the welfare, v1(S)+v2( S). We study both the allocation problem, which asks for a welfare-maximizing partition and the decision problem, which asks whether or not there exists a partition guaranteeing certain welfare, for binary XOS valuations. For interactive protocols with poly(m) communication, a tight 3/4-approximation is known for both [29, 23]. For interactive protocols, the allocation problem is provably harder than the decision problem: any solution to the allocation problem implies a solution to the decision problem with one additional round and logm additional bits of communication via a trivial reduction. Surprisingly, the allocation problem is provably easier for simultaneous protocols. Specifically, we show: There exists a simultaneous, randomized protocol with polynomial communication that selects a par-tition whose expected welfare is at least 3=4 of the optimum. This matches the guarantee of the best interactive, randomized protocol with polynomial communication. For all ϵ > 0, any simultaneous, randomized proto-col that decides whether the welfare of the optimal partition is ≥ 1 or ≤ 3/4 -1=108 + ϵ correctly with probability > 1/2 + 1=poly(m) requires ex-ponential communication. This provides a separa-tion between the attainable approximation guar-antees via interactive (3=4) versus simultaneous (- 3/4 1/108) protocols with polynomial com-munication. In other words, this trivial reduction from decision to allocation problems provably requires the extra round of communication. We further discuss the implications of our results for the design of truthful combinatorial auctions in general, and extensions to general XOS valuations. In particular, our protocol for the allocation problem implies a new style of truthful mechanisms.

Original languageEnglish (US)
Title of host publication29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
EditorsArtur Czumaj
PublisherAssociation for Computing Machinery
Number of pages18
ISBN (Electronic)9781611975031
StatePublished - 2018
Event29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 - New Orleans, United States
Duration: Jan 7 2018Jan 10 2018

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


Other29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
Country/TerritoryUnited States
CityNew Orleans

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics


Dive into the research topics of 'On simultaneous two-player combinatorial auctions'. Together they form a unique fingerprint.

Cite this