Let $G=(V,E)$ be a complete bipartite graph with $2n$ vertices and $M \subset E$ some unknown perfect matching of $G$.

The goal is to determine $M$ by repeatedly choosing some perfect matching $M_i \subset E$ and asking for $|M \cap M_i|=m_i$.

**Question**: What would be a good strategy of choosing the matchings $M_i$ if I want to minimize the times I have to ask?

My first idea was to create a heuristic that assigns to each pair of vertices $(a,b)$ the number $m_{(a,b)}=\max \{m_i \mid (a,b) \in M_i\}$, and maximizing $\sum_{(a,b)} m_{(a,b)}$. The problem is that this algorithm would just choose $M_i = M_1$ everytime, so maybe a certain percentage of the matching $M_i$ should be randomized, I don't know.