<p>This is simply the <a href="http://en.wikipedia.org/wiki/Stable_marriage_problem" rel="nofollow">Stable Marriage Problem</a>, 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:</p>

<blockquote>
  <p>The Gale–Shapley algorithm involves a number of "rounds" (or
  "iterations").</p>
  
  <p>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.</p>
  
  <p>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).</p>
  
  <p>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).</p>
  
  <p>This algorithm guarantees that:</p>
  
  <p><strong>Everyone gets married.</strong></p>
  
  <p>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.</p>
  
  <p><strong>The marriages are stable.</strong></p>
  
  <p>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.</p>
</blockquote>

<p>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. </p>

<p>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.</p>

CC BY-SA 3.0
2014-04-04T22:32:05.230Z
Another point is, that m might be bigger than f. However I will check, whether it can be applied, thank you very much.
Chris
CC BY-SA 3.0
2014-04-04T21:24:17.050Z
2014-04-04T21:48:41.817Z
2014-04-04T21:48:41.817Z
Phylliida
<p>I am asking myself whether there is an polynomial algorithm for the following problem:</p>

<p>Given:</p>

<pre><code>- m persons (think of them as "men")
- w persons (think of them as "women")

- t-talking sessions
- a function 
     f: (w, m) -&gt; {-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) -&gt; {-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.
</code></pre>

<p>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.</p>

<p>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?</p>

<ds.algorithms>
Pairing algorithm for simple speed dating problem
Chris
# Pairing algorithm for simple speed dating problem

(Asked by: username_0 on 2014-04-04)

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?

**Tags:** ds.algorithms

---

## 1 answers

### Answer by username_1 on 2014-04-04. Score: 1

This is simply the [Stable Marriage Problem](http://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_0**: Another point is, that m might be bigger than f. However I will check, whether it can be applied, thank you very much.  

---

