Daniel Moeller (Theory Seminar F13)

moeller.jpg"Jealousy Graphs: Structure and Complexity of Decentralized Stable Matching"
Daniel Moeller
Monday, November 4th, 2013, 2:00 pm
EBU3B, Room 4140

The stable matching problem has many applications to real world markets and efficient centralized algorithms are known. However, little is known about the decentralized case. Several natural randomized algorithmic models for this setting have been proposed but they have worst case exponential time in expectation. We present a novel structure associated with a stable matching on a matching market. Using this structure, we are able to provide a finer analysis.