- 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.