Paths to Stable Allocations

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.