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.



Determining a specific perfect matching $M$ by repeatedly asking for $|M \cap M_i|$ for other perfect matchings $M_i$
This is a variant of the Mastermind game, a classical problem of black-box optimization. This problem (reformulated with permutations instead of perfect matchings, but it's exactly the same) is addressed here : <https://www.sciencedirect.com/science/article/pii/0196677486900131>


They give a polynomial-time algorithm with $O(n \log(n))$ queries, and conjecture that it is optimal in number of queries.


