"Jealousy Graphs: Structure and Complexity of Decentralized Stable Matching"
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.