Talk:Stable marriage problem: Difference between revisions
→Incorrect statements of incorrectness: new section
(→Incorrect statements of incorrectness: new section) |
|||
Line 67:
:: Created [[Gale-Shapely 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) (→{{header|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:
:# 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)
| |||