2
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ It sounds like an exercise, in which case I would say it's known. What are your thoughts? Can you solve it using polynomially many queries? $\endgroup$
    – Yuval Filmus
    Jun 21, 2016 at 5:08
  • $\begingroup$ Its actually not an exercise. The problem is a simplified version of the game show called Are You the One? excerpt: " Each episode ends with a matching ceremony where the couples will be told how many perfect matches they have, but not which matches are correct" $\endgroup$
    – Jake B
    Jun 21, 2016 at 12:56
  • 1
    $\begingroup$ hmm you changed the rules in a significant way $\endgroup$
    – Abr001am
    Jun 21, 2016 at 19:07
  • $\begingroup$ 1. Please don't change the question in a way that invalidates existing answers. That is rude to answerers. Instead, you should read the answers, contemplate to see what you can learn based on them, and then ask a new question is necessary. 2. After your change it's no longer clear what the problem is. You say we cna query the database, but you don't say what the database will respond with. What do we learn based on doing that query? Anyway, if you're going to impose a new restriction on the kinds of queries you allow, you need to ask a new question. $\endgroup$
    – D.W. ♦
    Jun 22, 2016 at 0:06
  • $\begingroup$ What is the difference between changing the rules and clarifying? I appreciate the answers that were given and recieved invaluable insight from them but I was clarifying the constraints that I thought were clear. If someone doesnt understand my problem and answers it does that mean im not allowed to edit it? In which case why have an edit button with reason in the first place? $\endgroup$
    – Jake B
    Jun 22, 2016 at 2:14

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Does anybody know a lower bound? I have a feeling that you might shave of some loglogs by asking about more men in parallel. $\endgroup$
    – adrianN
    Jun 21, 2016 at 9:10
  • 1
    $\begingroup$ There is an easy $\Omega(n)$ lower bound since you're recovering $\Omega(n\log n)$ bits of information, and you get $O(\log n)$ bits from each query. Your queries only give you one bit of information, which is why you need $\Omega(n\log n)$ of them. $\endgroup$
    – Yuval Filmus
    Jun 21, 2016 at 11:17
  • $\begingroup$ In this paper the authors examine a similar problem with a slightly different oracle and get $\Theta(n \log \log n)$ in the randomized setting. I believe that one can also solve this problem quicker than $\Theta(n\log n)$. $\endgroup$
    – adrianN
    Jun 21, 2016 at 11:40
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ adrianN took my advice and showed how to solve it much faster than $O(n^2)$. $\endgroup$
    – Yuval Filmus
    Jun 22, 2016 at 7:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.