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$.
The parties must find some pair of vertices $u\in X\setminus(A\cup B)$ and $[v]\in Y\setminus(A\cup B)$, that represent some edge of $G_m$ that is _not_ in the subgraph induced by $A\cup B$.

Is this game known, and is there a good lower bound on the amount of communication required?

---

The decision version is trivial (Alice sends "YES" to Bob).
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, a random choice of one element from each of $X\setminus A$ and $Y\setminus A$ to send gives a randomized one-way protocol with vanishing error and cost $O(\lg m)$.
In contrast, a straightforward set disjointness lower bound applied to the complements would predict $\Omega(m)$ bits being required, so the obvious attempt to reduce from set disjointness does not work.
The implicit description of edges seems to be introducing an ingredient that I do not recognise in communication games.