2017/04/11 by Braverman, Mark, Mao, Jieming, Weinberg, S. Matthew
#Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1704.03547
We consider the following communication problem: Alice 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 [Fei06,DS06]. 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 log m additional bits of communication via a trivial reduction. Surprisingly, the allocation problem is provably easier for simultaneous protocols. Specifically, we show: 1) There exists a simultaneous, randomized protocol with polynomial communication that selects a partition whose expected welfare is at least 3/4 of the optimum. This matches the guarantee of the best interactive, randomized protocol with polynomial communication. 2) For all ε > 0, any simultaneous, randomized protocol 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 exponential communication. This provides a separation between the attainable approximation guarantees via interactive (3/4) versus simultaneous (≤ 3/4-1/108) protocols with polynomial communication. In other words, this trivial reduction from decision to allocation problems provably requires the extra round of communication.