Let $X_m=[m]=\{0,1,\dots,m-1\}$ and let $Y_m=[2m]\setminus [m]$. Given is a complete bipartite graph $G_m$, with parts $X_m$ and $Y_m$ and edges $\{x,y\}$ for every $x\in X_m$ and $y\in Y_m$. Alice and Bob are given subsets $A$ and $B$ of $[2m]$, with $|A|=a$ and $|B|=b$, and further these subsets are small relative to $m$, in the sense that $a < b \le m$. For convenience, let $C = A\cup B$. The parties must agree on a common pair of vertices $u\in X_m$ and $v\in Y_m$, that represent some edge of $G_m$ that is not in the subgraph induced by $C$, in other words so that either $u \not\in C$ or $v\not\in C$.
Is this game known, and is there a good lower bound on the amount of communication required?
The size condition guarantees that the decision version is trivial (Alice sends "YES" to Bob): since $|C|<2m$ there is always some vertex that is not held by either party, so it together with any vertex in the other part forms a non-edge of $G_m[C]$. Since $a$ is small relative to $m$, Alice can send a description of $A$ to Bob using $\lceil\lg\binom{2m}{a}\rceil = O(a\lg m)$ bits. Furthermore, Alice sending a random element from $X\setminus A$ and one from $Y\setminus A$ gives a randomized one-way protocol with vanishing error (at least in some parameter regimes) and cost $O(\lg m)$. In contrast, a set disjointness lower bound applied to the complements of $A$ and $B$ would predict $\Omega(m)$ bits being required, contradicting the trivial upper bound, so a straightforward reduction from set disjointness does not work (of course, a less direct reduction might work). The implicit description of edges seems to be introducing an ingredient that I do not recognise from the usual communication games.
