Talk:Stable marriage problem

Strategy?

I guess that if this were a marriage game then the best strategy for a guy would be to ask quickly and ask often. For a girl (who is not allowed to ask remember)? It seems girls can have no nothing better than they are given. Bummer! --Paddy3118 09:45, 6 August 2010 (UTC)

Yet the girl is the one that is allowed to change her mind over and over agiain, not that bad I would say. Kind of like in real life, :D --<Jofur> 10:12, 6 August 2010 (UTC)

Offtopic banter can be enjoyable in talk pages and IRC, but remember it's a public place, and be wary of escalation. :) --Michael Mol 14:21, 6 August 2010 (UTC)

You might like to find space to duck :-)
I guess girls who ditch the rules and ask the guys win big time. --Paddy3118 12:35, 6 August 2010 (UTC)

True that a girl who ask her first choice would have him, but the total sum may suffer since he may be much happier somewhere else. This is shown with the stability test, no pair where both want each other more than their partner, e.g. even if Ben wants Ada more than his wife Ellen, Ellen should not have the same values or the sort has failed.

This bring up old memories from those classes in national economy, where one thing was how to calculate the maximum sum of ‘usefulness’ that any resource could do in a society. And that is neither “all to one”, or “equal to all”. Resources where according o the maximization thesis to be spread so that their total sum is maximized, e.g. alls individual needs for different resources valued against their specific needs and available resources… I think I just connected it into the Knapsack series… --<Jofur> 12:59, 6 August 2010 (UTC)

Test

Just found this site which has two testcases and expected results. I modified the Python solution: <lang python> if True:

   ## Sphere online judge dataset from: http://www.spoj.pl/problems/STABLEMP/
   ## (But they print couples in reversed order)
   galprefers = dict( (x.strip().split()[0], x.strip().split()[1:])
                      for x in  1 3 4 2 1 6 7 5
                                   2 6 4 2 3 5 1 7
                                   3 6 3 5 7 2 4 1
                                   4 1 6 3 2 4 7 5
                                   5 1 6 5 3 4 7 2
                                   6 1 7 3 4 5 6 2
                                   7 5 6 2 4 3 7 1.split('\n') )
   guyprefers =  dict( (x.strip().split()[0], x.strip().split()[1:])
                      for x in  1 4 5 3 7 2 6 1
                                   2 5 6 4 7 3 2 1
                                   3 1 6 5 4 3 7 2
                                   4 3 5 6 7 2 4 1
                                   5 1 7 6 4 3 5 2
                                   6 6 3 7 5 2 4 1
                                   7 1 7 4 2 6 5 3.split('\n') )
   guys = sorted(guyprefers.keys())
   gals = sorted(galprefers.keys())

</lang> Which then went on to provide the correct result. (I was relying on the check() function before. --Paddy3118 14:04, 6 August 2010 (UTC)

Stability Check

The stability check seems to be giving at least two entries some problems in what to report. --Paddy3118 16:02, 18 August 2010 (UTC)

Can you be more specific about what the problem is? For the PicoLisp solution you wrote "checkCouples routines output is not clear". What is not clear, the wording? Or the logic? --Abu 12:02, 20 August 2010 (UTC)

Hi Abu, What is not clear is that the wording given in the check message is equivalent to the stability criterion which is that

"No male would rather be with another female where that other female would also prefer that male over her current partner"

You need the logic to search for the above but would only need to state that

"X, and Y would rather be together than with their current respective partners"

Where X and Y are not of the same sex and are the found names violating stability. The PicoLisp error message says "X likes Y1 better than Y2", which may well be the case, but does not point out how it violates the the stability criterion. Looking at the Python example, the check there could be better too, as it assumes that you know that the third name (dan) is the firsts partner. I'll fix it later. --Paddy3118 14:34, 20 August 2010 (UTC)

Hi Paddy, OK, I see. Half of the message is missing (though the code itself states it fully in the 'and' expression and the comments). Thanks! --Abu 12:34, 23 August 2010 (UTC)

J Stability Check

Again, it seems hard to work out that the stability criteria is violated using the results of the current J stability check. --Paddy3118 06:55, 3 September 2010 (UTC)

I do not understand this comment. Do you need another example to show what the stability check looks like when the result is stable? (There would be no output for that case). Do you need the result formatted in a different fashion? Do you need additional information (if so what additional information do you need)? For now, I am removing the comment on the main page because as near as I can tell the J implementation complies with the task description as is. --Rdm 12:37, 3 September 2010 (UTC)

Ok, never mind -- I had left a reference to what is now an undefined value for the stability check. I got rid of that now. --Rdm 12:42, 3 September 2010 (UTC)

Title

Since this specifies the Gale-Shapely algorithm, shouldn't that be the name of the task? Similar to how Lucas-Lehmer test finds Mersienne primes? --Michael Mol 16:30, 23 August 2010 (UTC)

Ah, your thinking logically. That's your problem! :-)

Stable marriage problem is more often quoted than the algorithm used to solve it, although it looks like that algorithm is the only one used to solve the problem (apart from exhaustive search). See this. --Paddy3118 21:58, 23 August 2010 (UTC)

Created Gale-Shapely algorithm as a redirect to this task. –Donal Fellows 14:34, 26 August 2010 (UTC)

An excellent solution I think! --Paddy3118 15:06, 26 August 2010 (UTC)

Incorrect statements of incorrectness

Currently the history for the main page looks like this:

(cur) (prev)  2010-09-08T14:48:58 Rdm (Talk | contribs) (45,168 bytes) (J: remove incorrect statement of incorrectness, again -- am adding to discussion page) (undo)
(cur) (prev)  2010-09-08T05:11:21 Paddy3118 (Talk | contribs) (45,259 bytes) (→J: Marked as incorrect as failures of the stability criterion are not clearly shown. (See talk).) (undo)

And, currently, the revision history of this page looks like this:

(cur) (prev)  2010-09-03T12:42:44 Rdm (Talk | contribs) (6,507 bytes) (→J Stability Check) (undo)
(cur) (prev)  2010-09-03T12:37:04 Rdm (Talk | contribs) (6,330 bytes) (→J Stability Check) (undo)
(cur) (prev)  2010-09-03T06:55:30 Paddy3118 (Talk | contribs) (5,812 bytes) (→J Stability Check: Can't work out that stability is violated with the results as given.) (undo)

In other words, a week ago Paddy marked the J solution as incorrect. I asked him what was incorrect about it, and then noticed a problem in the example usage, and fixed that. Now, a week later, he re-asserts that the solution is incorrect but with no statements about what is missing. So, I have removed his statement that it is incorrect and I am a little upset about this.

If we look at the main page's treatment of the stability criteria, we see in the task description:

1. Perturb this set of engagements to form an unstable set of engagements then check this new set for stability.

And we see in the J implementation:

Stability check:

<lang j> 1 2 A."_1 matchMake NB. perturbed matches

┌───┬────┬───┬───┬───┬────┬───┬────┬───┬───┐ │abe│bob │col│dan│ed │fred│gav│hal │jon│ian│ ├───┼────┼───┼───┼───┼────┼───┼────┼───┼───┤ │ivy│cath│dee│fay│jan│bea │gay│hope│eve│abi│ └───┴────┴───┴───┴───┴────┴───┴────┴───┴───┘

  checkStable 1 2 A."_1 matchMake 

Better matches: ┌───┬────┐ │jon│fay │ ├───┼────┤ │jon│gay │ ├───┼────┤ │jon│abi │ ├───┼────┤ │ian│hope│ └───┴────┘ |assertion failure: assert | assert-.bad</lang>

Now the task description defines a stable relationship as:

A stable set of engagements for marriage is one where no man prefers a women over the one he is engaged to, where that other woman also prefers that man over the one she is engaged to. I.e. with consulting marriages, there would be no reason for the engagements between the people to change.

So I would think that identifying a relationship where both parties prefer each other over their previous pairings would qualify as showing that the set was not stable.

And, for example, in the above example, jon and fay are listed as a pair where they both prefer each other over their previous pairs. And if we look at the perturbed data that was used, jon was paired with eve and fay was paired with dan. And if we look at the preference data we see:

  jon: abi, fay, jan, gay, eve, bea, dee, cath, ivy, hope
  fay: bob, abe, ed, ian, jon, dan, fred, gav, col, hal

So, clearly, the jon+fay paring by itself should be sufficient proof that the perturbed set of relationships was not stable.

So, in my opinion, Paddy has no basis for saying that the J solution is incorrect.

That said, if he wants to change the task description, adding new requirements for the stability check, I would be happy to satisfy those requirements. But I am not going to agree to fix some imaginary problem without a detailed explanation of what that problem is.

--Rdm 15:01, 8 September 2010 (UTC)