Wikipedia · einfach zusammengefasst · Stand
Preis der Anarchie
Der Preis der Anarchie ist ein Begriff der Wirtschaftswissenschaft und Spieltheorie, der die Auswirkung von eigennützigem Verhalten auf die Effizienz eines …
Grundidee
Der Preis der Anarchie ist ein Begriff aus Wirtschaftswissenschaft und Spieltheorie. Er misst, wie stark eigennütziges Verhalten einzelner Spieler die Effizienz eines gesamten Systems verschlechtern kann. Dazu wird das System als Spiel modelliert. Die Effizienz ist dabei eine Funktion, die jeder möglichen Strategiekombination eine Zahl zuordnet.
Der Begriff wurde von Koutsoupias und Papadimitriou genannt; die zugrunde liegende Idee ist aber älter. Verwandte Konzepte sind die Güte von Approximationsalgorithmen und die Kompetitivität von Online-Algorithmen.
Definition
Der Preis der Anarchie, englisch "Price of Anarchy", bezeichnet das Verhältnis zwischen dem Gewinn im gesamten System bei eigennützigem Verhalten der Spieler und dem optimalen Gewinn.
Eigennütziges Verhalten bedeutet dabei meist, dass die Spieler Strategien wählen, die einem Nash-Gleichgewicht entsprechen. Ein Nash-Gleichgewicht liegt vor, wenn jeder Spieler für sich selbst die beste Strategie wählt unter der Annahme, dass alle anderen Spieler bei ihrer aktuellen Strategie bleiben.
Der optimale Gewinn entsteht dagegen durch eine sozial optimale Wahl der Strategien. Das bedeutet: Die Strategien werden so gewählt, dass der Gewinn des gesamten Systems maximiert wird, nicht unbedingt der Vorteil jedes einzelnen Spielers.
Beispiel Straßenverkehr
Bei der Routenplanung zeigt sich der Unterschied zwischen sozial optimaler Planung und eigennützigem Verhalten besonders deutlich. Im Allgemeinen wählen einzelne Personen ihre Route so, dass sie für sich selbst unter Kenntnis der aktuellen Verkehrslage möglichst gut ist. Das entspricht einem Nash-Gleichgewicht.
Ein wichtiges Paradox ist, dass der Bau zusätzlicher Schnellstraßen nicht immer die gesamte Stauzeit im System verkürzt. Im Jahr 1990 wurde als Umweltaktion von New Yorks Commissioner die besonders stark gestaute 42nd Street für einen Tag gesperrt. Überraschenderweise gab es bei gleichem Verkehrsaufkommen insgesamt weniger Stau in der Stadt, obwohl eine der meistgenutzten Straßen nicht zur Verfügung stand. Dieses Phänomen ist als Braess-Paradox bekannt.
Die Erklärung lautet: Durch das Hinzufügen neuer Straßen kann die sozial optimale Stauzeit im System nur sinken. Bei eigennützigem Verhalten können sich die Nash-Gleichgewichte aber verschlechtern, etwa wenn alle Fahrer die neue große Straße nutzen und dort starke Staus entstehen.
Grenze bei affinem Stau
Wenn der Stau auf einer Straße affin von der Verkehrsmenge auf dieser Straße abhängt, lässt sich der Preis der Anarchie begrenzen. Affin bedeutet hier, dass der Zusammenhang durch eine lineare Funktion mit möglichem konstantem Anteil beschrieben wird.
In einem solchen System beträgt das Verhältnis zwischen dem schlechtesten Ergebnis eines Nash-Gleichgewichts und der sozial optimalen Reisezeit höchstens 4/3.