Title: Paths to Stable Allocations
Speaker: Agnes Cseh
Venue: Room LC 102, Lecture Hall Complex
Time: 2:30 pm, Friday, February 27, 2015
Abstract: In the stable marriage problem, men rank women and women rank men in a strict order of preference. The goal is to find a set of marriages that does not allow a blocking pair: an unmatched pair so that both the man and the woman in this pair prefer each other to their partners. The stable allocation problem is one of the broadest extensions of this well-known problem. In an allocation problem, edges of a bipartite graph have capacities and vertices have quotas to fill. Here we investigate the case of uncoordinated processes in stable allocation instances. In this setting, a feasible allocation is given and the aim is to reach a stable allocation by raising the value of the allocation along edges of blocking pairs and reducing it on worse edges if needed. Do such myopic changes lead to a stable solution?
About the Speaker: Agnes Cseh is a final-year Ph.D. student of Martin Skutella at TU Berlin, Germany. Until April 2015, she is visiting Kavitha Telikepalli at TIFR.