Talk:Stable marriage problem: Difference between revisions

← Older edit

Talk:Stable marriage problem (view source)

Revision as of 16:55, 24 July 2016

8,583 bytes added , 7 years ago

The name (from wp and other sources), seems to be Shapley (which was probably auto-mis-corrected to Shapely)

Anonymous user

rosettacode>Paddy3118

Revision as of 12:42, 3 September 2010 (view source) Rdm (talk \| contribs) (→‎J Stability Check) ← Older edit		Latest revision as of 16:55, 24 July 2016 (view source) rosettacode>Paddy3118 (The name (from wp and other sources), seems to be Shapley (which was probably auto-mis-corrected to Shapely))
(16 intermediate revisions by 9 users not shown)
Line 61: == Title == Since this specifies the Gale-~~Shapely~~Shapley algorithm, shouldn't that be the name of the task? Similar to how [[Lucas-Lehmer test]] finds Mersienne primes? --[[User:Short Circuit\|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 [http://googlefight.com/index.php?lang=en_GB&word1=%22Gale+~~Shapely~~Shapley+algorithm%22&word2=%22Stable+marriage+problem%22 this]. --[[User:Paddy3118\|Paddy3118]] 21:58, 23 August 2010 (UTC) :: Created [[Gale-~~Shapely~~Shapley algorithm]] as a redirect to this task. –[[User:Dkf\|Donal Fellows]] 14:34, 26 August 2010 (UTC) ::: An excellent solution I think! --[[User:Paddy3118\|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) (→<nowiki>{{header\|J}}</nowiki>: 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: :# ... :# 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, <code>jon</code> and <code>fay</code> 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. --[[User:Rdm\|Rdm]] 15:01, 8 September 2010 (UTC) :Hi Rdm, First my apologies. I did not mean to upset, and I though the arguments for the other cases of where I thought the stability check was unclear might suffice. I should add that I too went and added to my original Python example to make it clear. :An issue I had with other checks was that they didn't show ''why'' stability was violated without having to compute the stability criterion in your head, i.e. pairing A and B was better ''because'' A likes B better than present partner C and B likes A better than present partner D. I thought that just showing a pairing wasn't enough. again, it is just an opinion, and I am sure the site can come to a consensus, especially if others chip in. Does the task description need expansion? Or should we accept that a check routine that prints a pairing that could be shown to violate stability is enough? --[[User:Paddy3118\|Paddy3118]] 15:38, 8 September 2010 (UTC) ::Thanks for giving your perspective. This does indeed help me. ::Personally, I am happy with showing pairings where both partners would prefer each other over their previously asserted partners. That said, if you want additional information to be reported, I would be happy to provide it -- I just want that to be a part of the task. --[[User:Rdm\|Rdm]] 18:09, 8 September 2010 (UTC) I have changed the example perturbation to be the same as the one used in other examples to facilitate easier comparison. I've also edited the introductory text for the list of better matches to explicitly state why they are better. Hopefully that will satisfy everyone. I note that apart from the J solution, currently only the PicoLisp solution enumerates all the better matches that would cause a set of engagements to be unstable. The J and PicoLisp solutions agree. --[[User:Tikkanz\|Tikkanz]] 21:44, 8 September 2010 (UTC) == Problem with the Tcl example? == The test output for the Tcl example finishes with: :Swapping two fiances to introduce an error : abi is now engaged to fred : ... :... and abi likes fred better than their current partner Huh? --[[User:PhilThornley\|PhilThornley]] 16:48, 12 September 2010 (UTC) : Hi Phil, the full text for the TCL check is: <pre>Swapping two fiances to introduce an error abi is now engaged to fred bea is now engaged to jon fred likes bea better than abi and abi likes fred better than their current partner Engagement stability check FAILED</pre> :Which is a much better statement of violation of stability than for the SPARK example. Could you possibly read the sections above on writing a checker that prints output that doesn't need too much mental gymnastics to work out how the stability ccriterion is violated? Thanks. --[[User:Paddy3118\|Paddy3118]] 17:10, 12 September 2010 (UTC) ::Hi Paddy - but if "abi is now engaged to fred" then "their current partner" for abi is fred, so: ::"abi likes fred better than their current partner" == abi likes fred better than fred ::I think that the output from the D code is correct, what's your opinion? ::--[[User:PhilThornley\|PhilThornley]] 19:13, 12 September 2010 (UTC) ::: Hey, you ''are'' right! There is a problem with the TCL examples checking routine! Sorry to doubt. --[[User:Paddy3118\|Paddy3118]] 21:05, 12 September 2010 (UTC) : The error message was the same as the one originally produced by the Python version, but hadn't been updated when that other code was changed. –[[User:Dkf\|Donal Fellows]] 08:58, 16 September 2010 (UTC) == Nobel Prize == The 2012 Nobel Prize in Economics was awarded to Roth and Shapley for work that began with this algorithm. It seems the algorithm was the start of a new field called "market design" that goes far beyond marriage design, and that even the original Gale/Shapley algorithm has more general applications. —[[User:Sonia\|Sonia]] 21:22, 16 October 2012 (UTC) : Thanks for this nugget. --[[User:Paddy3118\|Paddy3118]] 15:54, 17 October 2012 (UTC) == OOP? == After looking at some of the solutions here, I noticed that there are several that used a language with OOP capabilities, but did not come up with an object-oriented solution. I'm not saying that's good or bad necessarily; but it would be interesting to see more solutions that go beyond translations of straight procedural logic. --[[User:MikeLorenz\|Mike Lorenz]] 05:06, 3 November 2012 (UTC) == PHP == If you want you can add my PHP port of the Python version from: http://www.leaseweblabs.com/2013/04/stable-marriage-problem-in-php/ --[[User:Maurits\|Maurits]] ([[User talk:Maurits\|talk]]) 15:01, 24 April 2013 (UTC)