ACM-EC 2008

The ACM EC'08 conference has now started; I am not there myself, but one of my papers is. And I am happy to say that it was selected as one of two "outstanding papers" at the conference; the papers that received the award are

• Self-Financed Wagering Mechanisms for Forecasting, by Nicolas Lambert, John Langford, Jennifer Wortman, Yiling Chen, Daniel Reeves, Yoav Shoham and David Pennock


• Uncoordinated Two-Sided Matching Markets, by Heiner Ackermann, myself, Vahab Mirrokni, Heiko Roeglin and Berthold Voecking

Our paper, Uncoordinated Two-Sided Matching Markets, considers the stable marriage problem, which as we know, is efficiently solved by the Gale-Shapley algorithm. We consider two simple randomised algorithms that have the advantage over GS that they are arguably less "centralised" (participants don't have to be told what to do a central controller), and which are guaranteed to terminate. We show that unfortunately, for carefully-chosen preference lists, these algorithms take (in expectation) exponential time. I can imagine that further work might involve identifying conditions (hopefully not too onerous) on the preference lists, that would imply fast convergence of these algorithms.