Question: 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?

Answer: 
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.
Here is how to solve this in time $O(n^2)$, where $n$ is the number of women (or men). For each man and each woman, ask the database how many matches does the set consisting only of the two of them contain.

Presumably you can solve this much faster than $O(n^2)$, but this gives you something to start with.