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)