Determining a specific perfect matching $M$ by repeatedly asking for $|M \cap M_i|$ for other perfect matchings $M_i$

Question

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.

Answer 1

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.