direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments


Paths to stable allocations and flows
Zitatschlüssel Report-04-2013
Autor Cseh, Ágnes and Skutella, Martin
Seiten 11
Jahr 2013
Nummer 04
Zusammenfassung The stable allocation and the stable network flow problems are amongst the broadest extensions of the stable marriage problem. In this paper, we investigate the case of uncoordinated processes. 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 blocking edges. This can be seen as a generalization of the paths to stability problem in the matching case. Here we describe an algorithm that yields a stable allocation in finite time for all rational input data. With this we also show that random best response strategies terminate with a stable allocation with probability one. We also show that if the market is correlated, both the better and the best response strategies lead to a stable allocation in expected polynomial time. We prove similar results for stable flows: a deterministic algorithm guarantees that a random series of myopic changes terminates with a stable solution with probability one.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag