Complexity of two-party maximum
Write $x = (x_h,x_l)$ and $y = (y_h,y_l)$, where $x_h,y_h$ are the high-order parts.
Alice sends $x_h$ to Bob ($n/2$ bits). Bob sends Alice two bits, indicating which of the following holds: $x_h &gt; y_h$, $x_h = y_h$, $x_h &lt; y_h$. The protocol then proceeds as follows:

If $x_h &gt; y_h$, then Alice sends Bob $x_l$ ($n/2$ bits).
If $x_h &lt; y_h$, then Bob sends Alice $y$ ($n$ bits).
If $x_h = y_h$, then Alice sends Bob $x_l$, and Bob sends Alice $y_l$ ($n$ bits).

In total, at most $\frac{3}{2}n+2$ bits are sent (assuming $n$ is even).