From: Robert Irving Sent: 21 August 2013 15:14 To: Patrick Prosser Subject: FW: roommates algorithm Hi Patrick, Thought you might be interested in this recent exchange of messages involving Stephan Mertens. You might want to check out whether your implementation handles correctly the four instances of size 10 that he provided. Rob. From: David Manlove Sent: 29 May 2013 17:10 To: Stephan Mertens Cc: Robert Irving Subject: RE: roommates algorithm Dear Stephan, Thanks for your remarks. I have a vague recollection that Colin did try to reuse the tail where possible, but I would need to check in more depth to be sure. By the way, a couple of weeks ago I bought your book as well, having been alerted to it when Rob mentioned that you had contacted him. Regards, David From: Stephan Mertens [mailto:mertens@ovgu.de] Sent: 29 May 2013 17:03 To: David Manlove Cc: Robert Irving Subject: Re: roommates algorithm Dear David, maybe your PhD student has done the same as Rob in his later implementation. i.e., *never* reuse the "tail" from the previous call to "seek_cycle" and start the search from scratch. This fixes the error, but it is also sort of inefficient. It is more efficient to check whether the previous tail is still OK (which in most cases is true) and then reuse it. I just got a copy of your new book on matching :-) Best, Stephan Stephan Mertens Professor, Theoretical Physics Otto-von-Guericke University and the Santa Fe Institute The Nature of Computation Cristopher Moore and Stephan Mertens Available now at all good bookstores, or through Oxford University Press http://www.nature-of-computation.org/ Am 29.05.2013 um 10:06 schrieb David Manlove: Dear Stephan, Many thanks for sending these four instances. I tried them all out against the Java implementation of the stable roommates algorithm as developed by Colin Sng, my former PhD student. In each case his program found the same stable matching as yours. Regards, David From: Stephan Mertens [mailto:mertens@ovgu.de] Sent: 28 May 2013 21:21 To: David Manlove Cc: Robert Irving Subject: Re: roommates algorithm Dear David, here are 4 instances of size 10 that all have a stable matching (also shown), but which are flagged "unsolvable" by the defective implementation from Rob's paper. Note that the error shows up only rarely for small instances. I generated 10000 random samples of size 10 to fins these 4 instances. For larger instances, the error occurs frequently. Best, Stephan example 1429 0: 9 2 6 5 1 4 7 8 3 0 1: 3 6 5 8 7 2 4 9 0 1 2: 9 3 4 6 0 5 8 1 7 2 3: 0 6 5 8 9 4 2 1 7 3 4: 2 1 6 9 8 5 3 7 0 4 5: 4 7 0 9 6 2 1 8 3 5 6: 9 8 4 3 7 5 1 0 2 6 7: 1 2 0 8 5 3 6 4 9 7 8: 5 1 4 9 3 7 0 2 6 8 9: 5 0 7 4 1 3 2 8 6 9 stable matching: 0: 9 1: 8 2: 4 3: 6 4: 2 5: 7 6: 3 7: 5 8: 1 9: 0 example 3084 0: 1 4 2 3 8 6 7 9 5 0 1: 3 7 6 2 8 4 9 5 0 1 2: 3 5 7 1 0 8 4 9 6 2 3: 9 2 6 1 8 7 5 4 0 3 4: 6 1 2 8 0 7 3 9 5 4 5: 2 4 9 7 0 1 6 3 8 5 6: 8 1 2 7 0 9 4 5 3 6 7: 9 5 8 0 3 1 6 4 2 7 8: 3 4 1 9 6 5 7 0 2 8 9: 5 4 2 0 3 7 1 8 6 9 stable matching: 0: 7 1: 6 2: 5 3: 9 4: 8 5: 2 6: 1 7: 0 8: 4 9: 3 example 9045 0: 6 3 5 2 4 8 7 1 9 0 1: 9 2 3 4 6 5 0 7 8 1 2: 3 9 4 6 0 1 7 5 8 2 3: 9 5 1 2 8 7 0 6 4 3 4: 0 8 3 7 9 6 1 2 5 4 5: 0 7 9 6 2 3 1 4 8 5 6: 9 8 7 1 0 3 5 4 2 6 7: 9 8 5 1 2 4 0 6 3 7 8: 7 3 9 4 1 0 2 5 6 8 9: 4 7 8 3 6 1 0 5 2 9 stable matching: 0: 6 1: 2 2: 1 3: 5 4: 9 5: 3 6: 0 7: 8 8: 7 9: 4 example 9774 0: 5 1 3 8 2 4 9 6 7 0 1: 5 3 6 7 0 9 2 8 4 1 2: 3 6 8 9 1 7 0 4 5 2 3: 6 4 0 2 9 8 7 5 1 3 4: 9 7 0 2 1 5 3 6 8 4 5: 7 9 0 6 3 4 8 2 1 5 6: 2 8 1 4 7 3 0 9 5 6 7: 3 8 0 5 2 6 9 1 4 7 8: 5 4 9 7 3 1 0 6 2 8 9: 2 3 7 5 8 4 6 0 1 9 stable matching: 0: 1 1: 0 2: 6 3: 4 4: 3 5: 9 6: 2 7: 8 8: 7 9: 5 Am 28.05.2013 um 21:23 schrieb David Manlove: Dear Stephan, Further to Rob's email, I was wondering if you might be able to send me your instance of size 10 that you mentioned highlighted an issue in the case of the seek_cycle procedure? The reason for asking is that a former PhD student of mine implemented Rob's algorithm in Java several years ago, and it might be worth using this instance as a quick test to see whether it suffers from the same problem. With thanks and regards, David From: Robert Irving Sent: 28 May 2013 13:41 To: Stephan Mertens Cc: David Manlove Subject: RE: roommates algorithm Dear Stephan, Sorry for the delay in replying once again. I’m just back in the office today, with some time to think and to look at my records. I agree with your observation regarding the error in the seek-cycle procedure. It’s good that you spotted this. Somewhat to my surprise (in view of a large clearout of archived material that I undertook when I retired a couple of years ago), I did manage to find the code that I used for the simulations reported in the paper with Boris Pittel. The program is written in Pascal, and is almost identical to the version published in my Journal of Algorithms paper. The one significant difference is in the seek-cycle procedure, where the tail is discarded and the search for a cycle is started from scratch each time. This would explain why the results reported in the paper with Boris are correct. However, I really do not recall why this change was made. I don’t remember being consciously aware of the error, but memory can play tricks over a twenty year period. I must have had some reason for making that change. Thanks once again for alerting me to this problem, and please keep me informed of any further progress that you make with the Roommates problem. With best wishes, Rob. From: Stephan Mertens [mailto:mertens@ovgu.de] Sent: Saturday, May 18, 2013 4:32 PM To: Robert Irving Subject: Re: roommates algorithm Dear Rob, I've attached a copy of your '85 to this email. The error is in the subroutine "seek_cycle" on page 592. This subroutine always starts the search for a new cycle at the last person in the "tail" of the previous search (provided that search has left a tail). This is a good thing to do because it speeds things up, but it can fail! In the previous search, the tail has been populated by people with more than one active entries in their preference lists, i.e. "leftmost < rightmost", but in the reduction followed after the previous search, people in the tail can and up with a single partner (a matching). In these cases, the search for a new cycle must not be started from the previous tail but from scratch. Adding a line of code that checks not only for "first_in_cycle > 1" but also for "leftmost[first_in_cycle-1] < rightmost[first_in_cycle-1]" fixes the error. I can send you s simple example of size n=10 where this case occurs. Best, Stephan Am 18.05.2013 um 16:55 schrieb Robert Irving: Dear Stephan, Thanks for your email. Sorry for the delay in replying - I've been travelling, and now that I'm retired from my academic post, I check my email a little less regularly. I'm interested (and a little embarrassed) to know of the error in the Pascal version of the algorithm. I don't have a copy of the paper accessible here at home, but will retrieve a copy next time I call in to the office. I'd be grateful if you could pinpoint the error for me. I'll also check - if the evidence is still available - which implementation was used in my work with Boris Pittel. I've read your work with interest in the past, and have been impressed how you have been able to work with very large instances. Your conjecture as to the asymptotic behaviour of P(n) is certainly very convincing. But it's frustrating not to be able to make progress with the theoretical stidy of this function - even showing that it's a strictly decreasing function of n would be something! Best wishes, Rob. PS You may be interested to know that my colleague David Manlove has just published a new book on stable matching problems. See http://www.worldscientific.com/worldscibooks/10.1142/8591 andhttp://www.amazon.co.uk/ALGORITH MICS-MATCHING-UNDER-PREFERENCES-ebook/dp/B00CFG09DA From: Stephan Mertens [mertens@ovgu.de] Sent: 14 May 2013 21:45 To: Robert Irving; gusfield@cs.ucdavis.edu Subject: roommates algorithm Dear Rob, dear Dan, I found a subtle error in the algorithm for the stable roommates problem in Rob's seminal paper from 1985. More precise: the error is in the Pascal implementation, not in the algorithm itself. The error causes the algorithm to flag some instances as unsolvable which in fact have a solution. It seems that you've used the faulty implementation to compute the data for figure 1 in your book "The Stable Marriage Problem". I've attached a figure that presents the same data, computed with the original implementation of Rob's '85 paper and with a correct implementation. As you can see, the faulty implementation underestimates the probability $P_n$ , that a random instance of the stable roommates problem of size $n$ has a solution. In a later paper (Pittel, Irving, Random Structures and Algorithms 5 (1994), 465) the numerical data for $P_n$ is correct. Hence I wonder whether you have noticed the error from the '85 paper. Best, Stephan Stephan Mertens Professor, Theoretical Physics Otto-von-Guericke University and the Santa Fe Institute The Nature of Computation Cristopher Moore and Stephan Mertens Available now at all good bookstores, or through Oxford University Press http://www.nature-of-computation.org/ Stephan Mertens Professor, Theoretical Physics Otto-von-Guericke University and the Santa Fe Institute The Nature of Computation Cristopher Moore and Stephan Mertens Available now at all good bookstores, or through Oxford University Press http://www.nature-of-computation.org/ Stephan Mertens Professor, Theoretical Physics Otto-von-Guericke University and the Santa Fe Institute The Nature of Computation Cristopher Moore and Stephan Mertens Available now at all good bookstores, or through Oxford University Press http://www.nature-of-computation.org/