Tata Institute of Fundamental Research
Paths to Stable Allocations
STCS Student Seminar
Speaker:
Agnes Cseh (Technische Universitat Berlin
StraBe des 17. Juni 136
10623 Berlin
Germany)
Organiser:
Swagato Sanyal
Date:
Thursday, 19 Feb 2015, 14:00 to 15:30
Venue:
D-405 (D-Block Seminar Room)
(Scan to add to calendar)
Abstract:
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?
Keywords: game theory, graph algorithms, matchings.
| Speaker: | Agnes Cseh (Technische Universitat Berlin StraBe des 17. Juni 136 10623 Berlin Germany) |
| Organiser: | Swagato Sanyal |
| Date: | Thursday, 19 Feb 2015, 14:00 to 15:30 |
| Venue: | D-405 (D-Block Seminar Room) |
(Scan to add to calendar)
Abstract:
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?
Keywords: game theory, graph algorithms, matchings.
Keywords: game theory, graph algorithms, matchings.