direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments


Paths to stable allocations
Zitatschlüssel CsehSkutella2014
Autor Cseh, Ágnes and Skutella, Martin
Jahr 2014
Journal Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT)
Zusammenfassung The stable allocation problem is one of the broadest extensions of the well-known stable marriage 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 blocking edges and reducing it on worse edges if needed. Do such myopic changes lead to a stable solution? In our present work, we analyze both better and best response dynamics from an algorithmic point of view. With the help of two deterministic algorithms we show that random procedures reach a stable solution with probability one for all rational input data in both cases. Surprisingly, while there is a polynomial path to stability when better response strategies are played (even for irrational input data), the more intuitive best response steps may require exponential time. We also study the special case of correlated markets. There, random best response strategies lead to a stable allocation in expected polynomial time.
Link zur Originalpublikation Download Bibtex Eintrag


Preprint 023-2012
Cseh, Ágnes and Matuschke, Jannik and Skutella, Martin.
Stable Flows over Time.

Preprint 04-2013
Cseh, Ágnes and Skutella, Martin.
Paths to stable allocations and flows.

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe

Diese Seite verwendet Matomo für anonymisierte Webanalysen. Mehr Informationen und Opt-Out-Möglichkeiten unter Datenschutz.