Finding perfect matchings with as few database queries as possible I am trying to research a problem similar to the stable matching problem with a few different rules. The problem is as follows:


There are an equal number of men and women.
Each man has a perfect match with one and only one other woman.
No two men have a perfect match with the same woman.
A perfect matching is a set of matches where all matches are perfect (as above).
There exists a database that can determine how many matches are perfect in any set.  You can query the database with a set to learn how many matches are perfect in that set, but you don't learn which matches.


I'm looking for an algorithm that finds a perfect matching that matches all the men and women, while querying the database the least amount of times.

Is there an efficient algorithm for this problem?
A $O(n \log n)$ solution works as follows:

For each man $M$, we find the matching woman in $O(\log n)$ queries. We start by dividing the women into two sets of size $n/2$. Using one query, we can find out which of the two halves contains $M$'s match. We recurse on that half.