  We consider the following communication problem: Alice and Bob each have some
valuation functions $v_1(\cdot)$ and $v_2(\cdot)$ over subsets of $m$ items,
and their goal is to partition the items into $S, \bar{S}$ in a way that
maximizes the welfare, $v_1(S) + v_2(\bar{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 $\varepsilon > 0$, any simultaneous, randomized protocol that
decides whether the welfare of the optimal partition is $\geq 1$ or $\leq 3/4 -
1/108+\varepsilon$ 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 ($\leq
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.
