Anonymous user
Talk:Stable marriage problem: Difference between revisions
The name (from wp and other sources), seems to be Shapley (which was probably auto-mis-corrected to Shapely)
(The name (from wp and other sources), seems to be Shapley (which was probably auto-mis-corrected to Shapely)) |
|||
| (12 intermediate revisions by 8 users not shown) | |||
Line 61:
== Title ==
Since this specifies the Gale-
: 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+
:: Created [[Gale-
::: An excellent solution I think! --[[User:Paddy3118|Paddy3118]] 15:06, 26 August 2010 (UTC)
Line 73:
(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:
Line 135:
::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)
| |||