Finance
April 2017
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 logm 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.