0
$\begingroup$

I am asking myself whether there is an polynomial algorithm for the following problem:

Given:

- m persons (think of them as "men")
- w persons (think of them as "women")

- t-talking sessions
- a function 
     f: (w, m) -> {-1,0,1,2}, which is preference of a specific woman to talk with a specific man: -1 means, that the woman does not want to talk to this man, if possible.
     g: (m, w) -> {-1,0,1,2}, which is preference of a specific man to talk with a specific woman: -1 means, that the man does not want to talk to this woman, if possible.

Target: Accomplish the "best" dating plan, meaning a pairing function for each talking session, which maximizes by summing over all dates using this function: m, w -> max(f(m,w),g(w,m)). During the talking sessions noone should date a person he has met before.

Is there a greedy algorithm for this problem, e.g. by matching the most loved-person with the most preferred person having the least number of talks?

$\endgroup$
1
$\begingroup$

This is simply the Stable Marriage Problem, where rankings go from -1 to 2 instead of 1 to n. Thus it's almost a subset of the problem solved by the Gale–Shapley algorithm. Quoting from Wikipedia:

The Gale–Shapley algorithm involves a number of "rounds" (or "iterations").

In the first round, first a) each unengaged man proposes to the woman he prefers most, and then b) each woman replies "maybe" to her suitor she most prefers and "no" to all other suitors. She is then provisionally "engaged" to the suitor she most prefers so far, and that suitor is likewise provisionally engaged to her.

In each subsequent round, first a) each unengaged man proposes to the most-preferred woman to whom he has not yet proposed (regardless of whether the woman is already engaged), and then b) each woman replies "maybe" to her suitor she most prefers (whether her existing provisional partner or someone else) and rejects the rest (again, perhaps including her current provisional partner).

The provisional nature of engagements preserves the right of an already-engaged woman to "trade up" (and, in the process, to "jilt" her until-then partner).

This algorithm guarantees that:

Everyone gets married.

Once a woman becomes engaged, she is always engaged to someone. So, at the end, there cannot be a man and a woman both unengaged, as he must have proposed to her at some point (since a man will eventually propose to everyone, if necessary) and, being unengaged, she would have had to have said yes.

The marriages are stable.

Let Alice be a woman and Bob be a man who are both engaged, but not to each other. Upon completion of the algorithm, it is not possible for both Alice and Bob to prefer each other over their current partners. If Bob prefers Alice to his current partner, he must have proposed to Alice before he proposed to his current partner. If Alice accepted his proposal, yet is not married to him at the end, she must have dumped him for someone she likes more, and therefore doesn't like Bob more than her current partner. If Alice rejected his proposal, she was already with someone she liked more than Bob.

It's not greedy, so I'm not totally answering the question, but it works. It's probably easier if you convert the problem to the marriage problem by changing the -1...2 to 1-n (by picking randomly higher preferences in the case of ties) before processing, I think.

Edit: Nevermind, this doesn't have the least number of talks either I think, but I figured it was still worth bringing up. Really it depends on whether those talking preferences are known beforehand (and we are optimizing the pairings, in which case this algorithm works), or whether those talking preferences aren't known until a talking session begins - in which case this algorithm isn't applicable at all. I mean you could just set everyone up with everyone else, compute these values, then run the algorithm above, but it's certainly not optimal.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Another point is, that m might be bigger than f. However I will check, whether it can be applied, thank you very much. $\endgroup$ – Chris Apr 4 '14 at 22:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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