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?