Mathematik: Der Preis der Freiheit
Released by matroid on Sa. 06. Oktober 2018 09:22:28 [Statistics]
Written by AnnaKath - 892 x read [Outline] Printable version Printer-friendly version -  Choose language   
Vermischtes

\(\begingroup\)

Der Preis der Freiheit

- Selfish Routing -

Dieser Artikel beschäftigt sich in seinem (überschaubaren) mathematischen Kern mit einem kleinen Satz, der die Ineffizienz eines so genannten "selfish routing algorithm" beschränkt. Es ist aber auch ein Ziel, diese Aussage etwas weiter zu interpretieren und darzulegen, wie man von ganz anderen Fragestellungen motiviert, auf dieses Resultat stoßen kann. Dies ist eines der Dinge, die ich an der Mathematik so mag; durch die hohe Abstraktion und präzise Fassung von Begriffen tun sich gelegentlich ungeahnte Anwendungen auf. Auch dies soll der Artikel exemplarisch veranschaulichen. Natürlich mag auch die rein mathematische Aussage interessant sein und wer sich nur dafür interessiert möge die weiteren Ausführungen ignorieren. Um dies zu erleichtern sind die zu überschlagenden Textteile durch einen $\bigstar$ markiert und sogar durch $\bigstar\bigstar$, wenn es sich um eine rein persönliche Bemerkungen handelt. Zum Titel: Der übliche englische Begriff für das zu Behandelnde lautet "price of anarchy". Auch eine direkte Übersetzung gäbe durchaus wieder, worum es dabei geht, entspricht aber nicht der (persönlichen) Motivation. Und eine letzte Anmerkung vorweg: Ich schreibe diesen Artikel aus Sicht einer Volkswirtschaftlerin. Diese Disziplin nannte man früher "politische Ökonomie" und so lässt es sich nicht vermeiden, dass man die ein oder andere Aussage eben "politisch" deuten kann. Dies ist ausdrücklich nicht meine Absicht und wäre eine vorsätzliche Missinterpretation. Leser, die sich in Gefahr sehen, mögen bitte die mit $\bigstar$ markierten Passagen übergehen.

$\bigstar$ Hintergrund

In den Wirtschaftswissenschaften betrachtet man oft den rationalen Agenten als ein Modell für das Handeln von Menschen. Dieser Modell-Mensch wählt seine Handlungen so, dass er seinen individuellen Nutzen (der gewissen Annahmen genügt) maximiert. Ich möchte dieses Konzept - und seine Sinnhaftigkeit - nicht in diesem Artikel diskutieren. Unterstellen wir einer Gruppe von Menschen ein solches Verhalten und vergleichen dieses mit einem sozialen Optimum, so stellt sich die Frage, ob es Abweichung zwischen realer und theoretisch optimaler Wohlfahrt gibt und inwieweit sich eine solche Abweichung gegebenenfalls quantifizieren lässt. Diese Frage mag aus sich heraus interessant sein; sie hat aber auch naheliegende Implikationen dafür, wie wir unsere Gesellschaft organisieren wollen. Für ein Modellproblem, das heutzutage meist aus einer technischen und algorithmischen Perspektive betrachtet wird (etwa [rou02]), möchte ich diese Frage aus einer spieltheoretischen Sichtweise beantworten. Natürlich ist dies keine besonders neue oder gar meine eigene Erkenntnis. Aber sie mag trotzdem interessieren. $\bigstar\bigstar$ Kritiker nennen den rationalen Agenten (dann auch häufig abfällig homo oeconomicus genannt) egoistisch und für die Gesellschaft schädlich, da sie wohl einen bestimmten Schlag von realen Menschen dahinter vermuten. Dem entgegnen eher liberal gesinnte Menschen dann vielleicht mit dem primitiven "Wenn jeder an sich selbst denkt, ist an alle gedacht!" Für die Handelnden ("Agenten") in diesem Artikel stellt sich hoffentlich keine solche Grundlagenfrage, denn in der heute hauptsächlichlich betrachteten Anwendung handelt es sich um bloßes Blech ("Netzwerkinfrastruktur") oder Software. Diese darf man wohl ohne falsche Rücksichtnahme als "selfish" - im Sinne von nutzenmaximierend - bezeichnen. In einer Diskussion mit einem Bekannten über individuelle Freiheit und deren potentiellen Schaden an einer Gesellschaft habe ich einmal scherzhaft eine sechsspurige Autobahn nebst Rheinbrücke gefordert, die meinen Wohnort direkt mit der Düsseldorfer Innenstadt verbinden sollte. Worauf sich eine interessante Diskussion über die Verkehrplanung ergab und er Braess' Paradoxon erwähnte. Dies war mir nur am Rande bekannt; einer Auffrischung dieses Wissens und meine Interpretation sowie die folgende gemeinsame Erörterung war die Grundlage zu diesem Artikel.

Einführung

Viele Menschen machen sich heutzutage Gedanken über den Autoverkehr, sei es als an die Umwelt denkender Mensch, sei es durch die persönliche Verärgerung im Stau oder bei der Parkplatzsuche. Abstrakt kann man sich ein Straßensystem als gerichteten Graphen vorstellen; jede Kante dieses Graphen hat eine Kapazität und die Geschwindigkeit des Verkehrsflusses ist umgekehrt proportional zur Ausnutzung dieser Kapazität (oder einer Potenz davon - die Empirie legt hier $4$ nahe; natürlich außerdem durch $0$ und das Tempolimit beschränkt). Vermutlich ebenso viele Menschen - und wohl alle Nutzer des Matheplaneten - sind darüber hinaus im Internet unterwegs, dessen Geschwindigkeit gelegentlich zu Wünschen übriglässt. Ein mögliche Quelle dieser Langsamkeit kann ineffizientes Routing sein. Ein (Rechner-)Netzwerk kann man sich auch hier als gerichteten Graphen vorstellen, bei dem jede Kante eine gewisse Latenz hat und deren Übertragungsgeschwindigkeit insbesondere abnimmt, wenn mehr Daten über die Leitung übermittelt werden (sollen). Auf den ersten Blick ist die Ähnlichkeit der beiden Probleme ersichtlich. Im Übrigen ist das zweite Beispiel die heute dominierende Anwendung, was der Grund sein mag, dass die Literatur zum Thema mehr und mehr durch Informatiker beherrscht wird, die oft einen Fokus auf Algorithmen und effiziente Heuristiken legen. Zur Einführung wollen wir ein Beispiel betrachten, welches auch sogleich als Warnung dienen soll, inwiefern die Intuition bei derartigen Netzwerkproblemen in die Irre leiten kann. Beispiel 1. Das Braess-Paradoxon in seiner ursprünglichen Formulierung bezieht sich tatsächlich auf eine (hypothetische) Problemstellung der Verkehrsführung. Für unsere Zwecke wollen wir unter dieser Bezeichnung einen etwas vereinfachten Graphen betrachten.
\begin{tikzpicture}[->,>=latex,auto,place/.style={circle,draw}] \node[place] (top) at ( 0, 1) {$o$}; \node[place] (bottom) at ( 0,-1) {$u$}; \node[place] (left) at (-2, 0) {$s$}; \node[place] (right) at ( 2, 0) {$t$}; \path (left) edge node {$x$} (top) edge node[swap] {$1$} (bottom) (top) edge node {$1$} (right) (bottom) edge node[swap] {$x$} (right); \end{tikzpicture} \begin{tikzpicture}[->,>=latex,auto,place/.style={circle,draw}] \node[place] (top) at ( 0, 1) {$o$}; \node[place] (bottom) at ( 0,-1) {$u$}; \node[place] (left) at (-2, 0) {$s$}; \node[place] (right) at ( 2, 0) {$t$}; \path (left) edge node {$x$} (top) edge node[swap] {$1$} (bottom) (top) edge node {$0$} (bottom) (top) edge node {$1$} (right) (bottom) edge node[swap] {$x$} (right); \end{tikzpicture}
Man möge sich den Graphen links etwa als Straßensystem zwischen den Städten $s$ und $t$ mit den Dörfern $o$ und $u$ vorstellen. Morgens fahren Menschen von $s$ nach $t$ zur Arbeit. Die Straßen sind derart, dass ein Autofahrer für die Strecken $su$ und $ot$ jeweils eine Stunde brauchen und auf den Strecken $so$ und $ut$ aufgrund des geringeren Ausbaugrads den Bruchteil einer Stunde, der dem Anteil der Berufspendler entspricht, die diese Route benutzen. Wollen die Fahrer ohne Rücksicht auf andere lediglich ihre Fahrzeit minimieren, so wird sich rasch ein Gleichgewicht im Berufsverkehr einstellen und $50\%$ der Fahrer nehmen die Route $sot$ und ebenso viele die Route $sut$. Die Fahrzeit für jeden einzelnen Pendler beträgt dann $1.5$ Stunden. Betrachten wir nun den zweiten, rechten, Graphen. Es wurde eine weitere, besonders moderne "Straße" von $o$ nach $u$ gebaut, die Autofahrer unabhängig vom Verkehrsaufkommen in Nullzeit nutzen können (wie auch immer dies gehen mag; sehen wir die neue Verbindung als Wurmloch an). Was wird nun geschehen? Jeder - nur an sich denkende - Pendler wird die Route $sout$ nehmen (und vermutlich hoffen, seine Fahrzeit dadurch auf eine Stunde reduzieren zu können). Allerdings steigt die Auslastung durch den zusätzlichen Verkehr die Reisezeit für die Strecken $so$ und $ut$ auf jeweils eine Stunde. Trotzdem hat kein Pendler einen Grund von sich aus die Route zu wechseln, eine schnellere Route steht nicht zur Verfügung. Durch den Bau des "Wurmlochs" hat sich - entgegen der Intuition der meisten Menschen - die Leistungsfähigkeit des gesamten Netzwerkes dauerhaft reduziert. Die Reisezeit der Pendler stieg von $1.5$ auf $2$ Stunden. Den Quotienten $2/1.5=4/3$ nennt man Preis der Freiheit (die individuelle Wahlfreiheit bewirkt diesen Wohlfahrtsverlust. Ein altruistischer Diktator könnte den alten, besseren - und tatsächlich optimalen - Zustand erzwingen). Die Größe des Quotienten ist im Übrigen kein Zufall. Nach dieser Einführung sollte eine physikalische Konstruktion des Paradoxons nicht mehr so sehr verblüffen; es ist trotzdem sehenswert.

Grundlagen

In der Hoffnung, dass die meisten Leser schon einmal von der Spieltheorie gehört haben, beschränke ich mich hier auf wenige Grundbegriffe. Definition 2. Ein Tripel $(N,A,u)$ heißt Spiel (in Normalform), sofern $N$ eine endliche Menge (von Spielern), $A = A_1 \times \ldots \times A_{|N|}$ eine Menge (von möglichen Strategien der Spieler $1, \ldots, |N|$) und $u: A\to\mathbb{R}^{|N|}$ (die sogenannte Nutzenfunktion oder auch "pay-off"). Beispiel 3 ("Gefangenendilemma"). Betrachten wir ein klassisches Beispiel. Zwei Ganoven wurden glücklicherweise durch die Polizei gefasst. Sie haben zwar tatsächlich einen Raub begangen; dies kann die Polizei aber nicht ohne das Geständnis mindestens eines der Schurken nachweisen. Sollten also beide schweigen, werden sie nur wegen kleinerer Delikte zu jeweils $2$ Jahren Haft verurteilt. Sollte jedoch einer gestehen (und der andere schweigt), so wird der Geständige nur zu einem Jahr, der andere dagegen zu $10$ Jahren verurteilt. Gestehen beide, so wirkt sich das Geständnis zwar mildernd aus, aber beide werden zu jeweils $7$ Jahren verurteilt. Formalisieren wir das Beispiel indem wir $N=\{X,Y\}$, $A_X=A_Y=\{$schweigen,gestehen$\}$ setzen und $u$ beschrieben durch die folgende (Bi-)Matrix:
X gestehtX schweigt
Y gesteht(-7,-7)(-10,-1)
Y schweigt(-1,-10)(-2,-2)
Die Mengen $A_j$ der Definition eines Spieles heißen Strategiemengen. Sie fassen die Handlungsoptionen der Spieler zusammen. Betrachten wir diese etwas genauer. Definition 4. Sei $(N,A,u)$ ein Spiel. Eine (gemischte) Strategie $p=(p_1, \ldots, p_{|N|})$ ist ein Tupel, so dass $p_j$ eine Wahrscheinlichkeitsverteilung über $A_j$ für jeden Spieler $j\in N$. Eine Strategie heißt reine Strategie, wenn $p=(p_1, \ldots, p_{|N|})$ Dirac-verteilt ist. Eine Strategie $p$ heißt Nash-Gleichgewicht, wenn $u_j(p_1, ...p_{j-1},s,p_{j+1}, \ldots, p_{|N|}) \leq u_j(p_1, ...p_{j-1},p_j,p_{j+1}, \ldots, p_{|N|})$ für alle $j\in N$ und $s\in A_j$ gilt. Das Nash-Gleichgewicht ist ein Konzept, das sich völlig natürlich aus der Anwendung ergibt. Betrachten beispielsweise wieder das Gefangenendilemma aus Beispiel 3. Sollte einer der Kriminellen, sagen wir $X$, auf irgendeine Weise wissen, wie sich $Y$ verhält - also dasjenige $y\in A_Y$ (fast sicher) kennen, für das $p_Y(y)=1$ gilt - so wird er vermutlich seine eigene Handlungsweise danach ausrichten und versuchen, seine eigene Strafe zu minimieren. Ist $y=$schweigt, so könnte $X$ gestehen, und selber mit der mildest möglichen Strafe (und damit dem höchsten Nutzen für ihn) davon zu kommen. Gesteht dagegen $Y$, so sollte es auch $X$ tun. Genau diese Überlegung liegt der Definition eines Nash-Gleichgewichts zu Grunde. Kann ein Spieler (würde er die Strategiewahl aller anderen Spieler kennen) seinen Nutzen verbessern, so unterstellen wir, dass er dies tut. Ein Nash-Gleichgewicht ist gerade eine Strategie für die dies keinem Spieler möglich ist. Für das Gefangenendilemma bedeutet dies, dass die (reine) Strategie (gestehen, gestehen) ein - und zwar das einzige - Nash-Gleichgewicht ist. Bemerkungen 5. (1) Ist die Nutzenfunktion $u$ quasikonkav und stetig, und sind die Strategiemengen $A_j$ (i) endlich oder (ii) konvex und kompakt, so besitzt jedes Spiel (mindestens) ein Nash-Gleichgewicht. Im Falle (ii) besteht dieses Gleichgewicht sogar aus reinen Strategien. Diese Anforderungen sind ziemlich milde und im Folgenden stets erfüllt. (2) Es gibt noch andere Gleichgewichtsbegriffe in der Spieltheorie (vgl. etwa hier). Für das Folgende benötigen wir Spiele einer speziellen Struktur. Definition 6 Ein Auslastungsspiel ist ein Quadrupel $(N, R, A, c)$. Dabei sind $N$ und $R$ endliche und nichtleere Mengen, $A=A_1 \times \ldots \times A_{|N|}$ mit $A_j \subset 2^R \backslash \{\emptyset\}$ für $j\in N$ und $c=(c_1, \ldots, c_{|R|})$ mit $c_k:\mathbb{N}\to\mathbb{R}$ für $k\in R$. Dabei bezeichnet $N$ eine Menge an Spieler- oder Agententypen, jedes $A_j$ bezeichnet die Menge der Handlungsalternativen für Spieler $j$, $R$ ist eine Menge von Ressourcen und jedes $c_k$ ist eine sogenannte Kostenfunktion. Wir wollen ein solches Spiel veranschaulichen. Bei einem Empfang werden im Rahmen eines Buffets verschiedene Speisen, z.B. Salat, Fisch, Fleisch ..., angeboten. Jeder der $|N|$ Gäste wird sich aus einigen der $|R|$ Speisen sein persönliches Menü zusammenstellen, sagen wird Gast $1$ nimmt Fisch und Salat, Gast $2$ isst gar nichts, Gast $3$ versucht es mit dem Fleisch usf. Die Strategien dieser Gäste sich genau dann diese Zusammenstellungen, also etwa $a_1=\{$Salat,Fisch$\}$ und $a_2=\emptyset$. Der Partyservice ist natürlich vor Ort und wird nachlegen, sollte eine der Speisen rar werden. Allerdings dauert dies einige Zeit und die Gäste werden dadurch nicht zufriedener (Ist es schon einmal einem Leser gelungen, nicht doch auf die Mousse au Chocolat warten zu müssen, obwohl man sich bereits seit 'Ewigkeiten' durch die Buffetschlange vortrippelt?). Genau solche Situationen beschreiben Auslastungsspiele. Die Ressourcen sind zwar in ausreichender Menge vorhanden, von je mehr Spielern sie jedoch beansprucht werden, desto geringer ist ihr Nutzen (das Essen ist schon kalt, man muss lange darauf warten, ...). Bezeichnen wir mit $z:R\times A\to\mathbb{N}$ die Anzahl der Spieler, in deren Strategie $a_j$ für $a\in A$ die Ressource $r\in R$ genutzt wird. Dann heißt Abbildung $u_j:A\to\mathbb{R}$ mit $u_j(a)=\sum \limits_{r\in a_j} c_r(z(r,a))$ Kostenfunktion des Spielertyps $j$. Diese Art von Spielen sind geeignet, die in der Einführung aufgeworfene Fragestellung zu modellieren und im Rahmen der Spieltheorie zu untersuchen. Die Größe $c(a) = \sum \limits_{j\in N} u_j(a)$ heißt dann Gesamtkosten (oder auch soziale Kosten oder Wohlfahrtsverlust). Bemerkungen 7 (1) Jedes Auslastungsspiel besitzt ein Nash-Gleichgewicht aus reinen Strategien. (2) Alle Nash-Gleichgewichte eines Auslastungsspiels haben die gleichen Gesamtkosten.

Transportnetzwerke

Kehren wir zu den einführenden Beispielen - Verkehrs- und Rechner-Netzwerken - zurück und fassen wir die Gemeinsamkeit dieser Beispiele formal. Im Anschluss wollen wir diese Netzwerke in die Sprache der Spieltheorie übersetzen und untersuchen, inwieweit sich Gleichgewichtsflüsse von optimalen Lösungen unterscheiden. Definition 8. Ein Tupel $(G,M,s,t,\gamma,r)$ heißt Transportnetzwerk, wenn $G=(V,E)$ einen gerichteten, schlingenfreien, endlichen Graphen bezeichnet, $M$ eine nichtleere, endliche Menge ist, $s:M\to E$ und $t:M\to E$ injektive Funktionen sind mit $\mathrm{Im}\;s \cap \mathrm{Im}\;t = \emptyset$, $r:M\to\mathbb{R}^{+}$ und $\gamma: E \to \mathbb{R}^{\mathbb{R}}$ so, dass jedes $\gamma(e)$ stetig, monoton wachsend und nichtnegativ ist. Diese Definitionen wollen wir zur Veranschaulichung auf ein Servernetzwerk übertragen. Die Knotenmenge $\mathrm{Im}(s)$ bezeichnen wir als Quellen, das sind die Rechner, die Daten schicken wollen. Deren Ziele sind die Senken $\mathrm{Im}(t)$, wobei Rechner $s(i)$ gerade $r(i)$ Datenvolumen an $t(i)$ senden möchte. Die Kanten des Graphen sind Netzwerkverbindungen (Kabel, Satellitenverbindung etc.) und die Knoten aus $Z = V \backslash (\mathrm{Im}(s) \cup \mathrm{Im}(t))$ Router oder andere Verzweigungspunkte des Netzwerkes. Was bedeutet nun das $\gamma$? Dies ordnet jeder Kante $e$ eine so genannte Kostenfunktion $\gamma(e) = c_e: \mathbb{R}\to \mathbb{R}^{+}$ zu. Diese Funktion beschreibt den Zeitaufwand $c_e(x)$, den ein (infinitesimal kleines) Datenpaket benötigt, wenn über die Leitung $e$ bereits ein Datenvolumen von $x$ gesendet werden muss. Vereinfachung 9: Für das Folgende betrachten wir - der leichteren Verständlichkeit geschuldet - ein etwas einfacheres Modell. Wir nennen $\mathcal{N}=(G,M,s,t,\gamma,r)$ ein vereinfachtes Transportnetzwerk, wenn $G$ zusammenhängend ist, und $M=\{\star\}$ genau ein Element besitzt. Versuchen wir nun den Datentransport durch das Netzwerk zu formalisieren. Betrachten wir dazu zu einer Knotenmenge $W \subset V$ mit $\overleftarrow{E}(W)$ die Menge der Kanten in $E$, die in einem $w \in W$ enden, mit $\overrightarrow{E}(W)$ entsprechenden die Menge der Kanten $w$, die in einem $w \in W$ beginnen. Definition 10. Ein Fluss (durch ein vereinfachtes Transportnetzwerk) ist ein $f \in \mathbb{R}^{|E|}$ für das gilt: $\sum \limits_{e \in \overrightarrow{E}(\{t\})} f_e=r, \sum \limits_{e \in \overleftarrow{E}(\{s\})} f_e=r$ und $\sum \limits_{e \in \overrightarrow{E}(Z)} f_e + \sum \limits_{e \in \overleftarrow{E}(Z)} f_e=0$ für $Z=V\backslash \{s,t\}$ gilt. Die Größe $c(f)= \sum \limits_{e \in E} c_e(f_e)$ heißt (soziale) Gesamtkosten des Flusses. Ein Fluß ordnet also jeder Kante $e$ Gewichte $f_e$ so zu, dass die Kirchhoff'sche Knotenregel für alle Vertizes $v\in Z$ erfüllt ist, aus der Quelle genau das Volumen $r$ abfließt und in der Senke genau dieses Volumen einströmt. Eine äquivalente Beschreibung eines Flusses erreicht man, indem man alle Pfade des Graphen betrachtet und diese gewichtet. Ein Pfad $p(v,w)$ ist dabei ein geschlossener Kantenzug unter Beachtung der Kantenorientierung, der in $v\in V$ beginnt und in $w\in V$ endet und keinen Kreis enthält. Wir bezeichnen mit $\mathcal{P}(v,w)$ die Menge der Pfade von $v$ nach $w$. Ist $f$ ein Fluss, so gibt es reelle Zahlen $q_1, \ldots, q_l$ mit $l=|\mathcal{P}(s,t)|$, so dass $f_j=\sum \limits_{P\in \mathcal{P}(s,t)} q_P$ gilt. Wir nennen $q(f)=(q_1, ..., q_l)$ die Pfaddarstellung von $f$. Es gilt im Übrigen offensichtlich $\sum \limits_{j=1}^l q_j=r$. Definition 11. Ein Nash-Fluss ist ein Fluss $f$ mit Pfaddarstellung $q(f)$, für den gilt: Für jeden anderen Fluss $g$ mit $q(g)_j=g(f)_j+\epsilon$, $q(g_k)=g(f)_k-\epsilon$, $\epsilon \in [0,f_k)$ und für alle $j,k\in\mathcal{P}(s,t)$ gilt: $C(f)\leq C(g)$. Bei einem Nash-Fluss führt also eine (infinitesimale) Verlagerung des Stromes durch das Netzwerk zu einer Erhöhung der sozialen Kosten. Wir bemerken noch, dass die sozialen Kosten eines Netzwerkes für alle Nash-Gleichgewichte gleich sind (s. etwa [rou02] und die Referenzen dort). Dies widerspricht nicht der Tatsache, dass es andere Flüsse geben kann, die global geringere soziale Kosten als ein Nash-Fluss aufweisen. Diese sind nur nicht (Nash-)stabil, d.h. eigennütziges Verhalten der Agenten (Autofahrer, Router, ...) zerstört ein solches Optimum. Jedes Transportnetzwerk besitzt (mindestens) einen Nash-Fluss. Überführen wir das vereinfachte Transportnetzwerk in den Rahmen der Spieltheorie. Bemerkung 12. (1) Das graphentheoretisch formulierte Transportnetzwerk lässt sich als so genanntes nichtatomares Auslastungsspiel auffassen. (2) Ein Nash-Fluss ist gerade ein Nash-Gleichgewicht des Spiels. (3) Im Sinne der Spieltheorie wird ein Transportnetzwerk von unendlich vielen Spielern gespielt (die aber zu endlich vielen Typen gehören). Daher die Bezeichnung "nichtatomar". (4) Auf den ersten Blick ist ein solche nichtatomares Auslastungsspiel kein Spiel in Normalform. Es lässt sich aber in ein solches übersetzen. Wir nennen ein aus einem Transportnetzwerk entstandenes nichtatomares Auslastungsspiel auch "selfish routing system". Die Bezeichnung "selfish" rührt von der Tatsache her, dass die Nash-Flüsse im Netzwerk derart sind, dass jeder (Server-/Router-)Knoten im Netzwerk sich so verhält, dass er die jeweils minimalen Kosten für die Weiterleitung der Daten wählt. Ohne auch nur minimales Verständnis von dieser Technik zu habe, nenne ich hier für Spezialisten den Begriff "Hot Potatoe-Routing", was wohl das gleiche meint. Betrachten wir das charakteristische Beispiel für selfish routing system, den so genannten Pigou-Graphen.
\begin{tikzpicture}[->,>=latex,auto,place/.style={circle,draw}] \node[place] (left) at (-2, 0) {$s$}; \node[place] (right) at ( 2, 0) {$t$}; \path (left) edge[bend left=45] node {$x^d$} (right) edge[bend right=45] node[swap] {$1$} (right); \end{tikzpicture}
Beispiel 13. Der Pigou-Graph besteht nur aus zwei Knoten ($s$ und $t$) sowie zwei Kanten von $s$ nach $t$. Die obere Kante $o$ hat eine Kostenfunktion $c_o(x)=x^d$, $d\in\{0,1,2 \ldots \}$, die untere Kante $u$ eine konstante Kostenfunktion $c_u(x)=1$. Der Nash-Fluss $f$ lenkt den gesamten Strom über die Kante $o$ und seine Kosten betragen dann $C(f)=1$. Die Idee, den optimalen Fluss $g$ zu bestimmen ist offensichtlich. Ein (je größer $d$ ist umso größerer) Anteil des Verkehrs fließt über $o$, der Rest über $u$. Ein bisschen Rechnerei zeigt: $\wp = C(f)/C(g) = [d\cdot (d+1)^{(d+1)/d}]^{-1}$, für $d=0$ definieren wir $\wp=1$.

Selfish Routing und der Preis der Freiheit

Im Folgenden wollen wir nun untersuchen, inwiefern das nutzenmaximierende Verhalten jedes Agenten zu einem Zustand führen kann, der nicht wohlfahrtsoptimal ist und diesen Unterschied zu quantifizieren. Die Ausführungen dieses Kapitels beziehen sich nur auf Spiele, die sich aus vereinfachten Transportnetzwerken ergeben, gelten aber sinngemäß für alle (nichtatomaren) Auslastungsspiele. Die Beweisführungen sind technisch aufwendiger, beruhen aber auf den jeweils gleichen Grundideen. Definition 14. Für ein vereinfachtes Transportnetzwerk $\mathcal{N}$ mit minimalen sozialen Kosten $k_o$ und Gesamtkosten $k_g$ im Nash-Gleichgewicht heißt $\wp(\mathcal{G}) = \frac{k_g}{k_o}$ der Preis der Freiheit. Wie bereits in der Einführung gesagt, heißt das entsprechende Konzept in der Literatur üblicherweise "Preis der Anarchie" bzw. engl. "price of anarchy". Die Bedeutung sollte intuitiv sein; der Preis der Freiheit misst die relative Abweichung des Gleichgewichtszustands von einem theoretischen Optimum. Wirtschaftswissenschaftlich betrachtet gibt diese Größe die (relativen) sozialen Mehrkosten bzw. den Wohlstandsverlust an, die durch eigennütziges Verhalten entstehen im Vergleich zur zentralen Planung durch einen altruistischen und allwissenden Diktator. Satz 15. Der Preis der Freiheit ist im Allgemeinen unbeschränkt, d.h. für jedes $\epsilon>0$ existiert ein Transportnetzwerk $\mathcal{G}$, so dass $\wp(\mathcal{G})< \epsilon$. Beweis. Für die nichtlinearen Pigou-Graphen $\mathcal{P}_d$ aus Beispiel 13 gilt $\wp(\mathcal{P}_d) = [d\cdot (d+1)^{(d+1)/d}]^{-1}$. Für $d\to \infty$ geht die rechte Seite gegen $0$. $\square$ Wir wollen die Menge aller polynomialen Funktionen vom maximalen Grad $d$ mit nicht-negativen Koeffizienten Pigou-Klasse (vom Grad $d$) nennen. Für solche Kostenfunktionen (und viele andere Klassen) kann man die Kosten der Freiheit nach oben beschränken. Satz 16. Stammen die Kostenfunktionen eines Transportnetzwerkes $\mathcal{N}$ aus einer Pigou-Klasse $C$, so gilt für den Preis der Freiheit: $\wp(\mathcal{G}) \leq \alpha(C) = \sup \limits_{c\in C} \sup \limits_{x\in \mathbb{R}} \sup \limits_{r \in \mathbb{R}} \left (\frac{r\cdot c(r)}{x\cdot c(x)+(r-x)\cdot c(r)} \right )$. Dabei heißt $\alpha(C)$ Pigou-Schranke. Beweis. (1) Sei $f$ ein Nash-Fluss, sei $g$ der optimale Fluss, d.h. ein Fluss, dessen soziale Kosten das globale Minimum realisiert. Man überzeugt sich anhand der charakteristischen Gleichgewichtseigenschaft von $f$, dass gilt: $\sum \limits_{e\in E} (g_e-f_e)c_e(f_e) \geq 0$. (2) Spezialisierung in der Wahl der Pigou-Schranke ergibt: $\alpha(C) = \sup \limits_{c\in C} \sup \limits_{x\in \mathbb{R}} \sup \limits_{r \in \mathbb{R}} \left (\frac{r\cdot c(r)}{x\cdot c(x)+(r-x)\cdot c(r)} \right ) \geq \frac{f_e\cdot c(f_e)}{g_e\cdot c(g_e)+(f_e-g_e)\cdot c(f_e)} $. Und somit $g_e\cdot c(g_e) \geq \alpha(C)^{-1} f_e\cdot c(f_e) + (g_e-f_e)\cdot c(f_e)$. Durch Summation über alle Kanten $e\in E$ ergibt sich $C(g)\geq \alpha(C)^{-1} \cdot C(f) + \sum \limits_{e\in E} (g_e-f_e)c_e(f_e)$ und mit (1) folgt die Behauptung. $\square$ Bemerkung 17. Die Schranke ist für polynomiale Kostenfunktionen scharf, d. h. die Pigou-Graphen realisieren jeweils die Schranke. Um die Größenordnung von $\alpha(C)$ einschätzen zu können, wollen wir diese Größe hier für die Pigou-Klassen aufführen.
Maximaler Grad$\alpha(C)$
$0$$1.0$
$1$$1.3$
$2$$1.6$
$3$$1.9$
$4$$2.2$
......
$d$$\Theta(\frac{d}{\log d})$
Für die technische Anwendung ist es interessant, dass die Kosten der Freiheit nicht von der Netzwerktopologie abhängen, sondern lediglich von der Klasse (also der Nichtlinearität) der Kostenfunktionen.

$\bigstar$ Das (vorläufige) Ende der Debatte

Bedeutet dieses Ergebnis nun also, dass ein den individuellen Nutzen maximierendes Verhalten zu Abweichungen vom sozialen Optimum führt? Müssen wir diesen Preis für individuelle Freiheit zahlen? Ist eine zentrale Steuerung also überlegen? Ja und auch Nein. Einerseits zeigt bereits diese recht spezielle Klasse von Problemen, dass die "unsichtbare Hand" keineswegs stets ein soziales Optimum schafft. Wäre es dann also nicht erstrebenswert, eine zentrale Steuerung für derartige Konstellationen vorzunehmen, also den Agenten des Spiels vorzuschreiben, wie sie sich zu verhalten haben? Oder kann "man" nicht zumindest versuchen, den Rahmen so zu setzen, dass Phänomene wie das Braess'sche Paradoxon nicht auftreten? Gegen Letzteres spricht wohl nichts außer der Komplexität. Bereits für ein selfish routing Problem ist festzustellen, dass die Untersuchung, ob die Entfernung einer oder mehrerer Kanten des Graphen (der Rückbau/Sperrung von Straßen...) zu einer Absenkung der sozialen Kosten führt, ein NP-vollständiges Problem ist und dürfte damit zumindest derzeit nicht in Echtzeit durchführbar sein. Das systemtheoretische Argument gegen zentrale Planung und Steuerung - Anfälligkeit gegen äußere Manipulation oder zufällige Störungen mit potentiell katastrophalen Auswirkungen - will ich nicht weiter ausführen. Aber es gibt Möglichkeiten, das Problem praktisch zu lösen, ohne gleich zu einer (vollständigen) zentralen Steuerung (bis hin zu Verboten, überhaupt mit dem Auto zu fahren) überzugehen. Eine Möglichkeit ist etwa das Stackelberg routing ([rou02]), welches nur für wenige Agenten (Autofahrer) eine zentrale Steuerung erforderlich macht. Eine andere Möglichkeit wäre das Erheben gezielter Steuern für bestimmte Straßen ("marginal cost pricing" oder Pigou-Steuer), welches die individuelle Wahlfreiheit nicht grundsätzlich aufhebt, sondern nur beeinflusst. Und es gibt eine weitere Möglichkeit: Es gilt der Satz 18. Für ein selfish routing Problem $\mathcal{S}$ mit optimalen sozialen Kosten $q$ exitiert ein in allen sonstigen Belangen identisches Problem $\mathcal{S'}$, bei dem die Kosten einer Kanten $e$ gegeben sind durch $c'_e(x)=c_e(x/2)/2$ so, dass für jedes Nash-Gleichgewicht von $\mathcal{S'}$ gilt, dass dessen soziale Kosten geringer sind als die optimalen Kosten für $\mathcal{S}$, d.h. also $C(\mathcal{S'}) < q$. Beweis. Vgl. [slb09]. $\square$ $\bigstar\bigstar$ Es hilft also doch, mir die sechsspurige Autobahn zu bauen.

Abschluss

Wir haben anhand einer sehr einfachen Klasse von Problemen gesehen, dass (Markt-)Ineffizienzen auftreten können, wenn man den Agenten eines Spieles Freiheiten zu strategischem Verhalten lässt. Dies ist zwar keineswegs eine neue Erkenntnis, doch mag es überraschend sein, dass diese Tatsache nicht nur auf das menschliche Verhalten zurückzuführen ist. Eine Betrachtung eines Zusammenspiels autonomer Algorithmen führt zu ähnlichen Phänomenen. Ein Punkt fasziniert mich besonders: Es ist nicht die beliebig komplexe Netzwerktopologie, die die Kosten der Freiheit treibt; es ist die Nichtlinearität (ggf. einer einzelnen) Kante. Der denkbare einfache Pigou-Graph enthält somit bereits alles Wesentliche. Was dies konkret bedeutet, mag jeder selbst beurteilen. Ein paar Punkte in diesem Artikel sind - mit einer gewissen Absicht - nicht ausgeführt. Wem diese störend auffallen, der möge dies gerne im Kommentarbereich diskutieren. Einige dieser weiterführenden Themen oder ergänzenden Details werde ich vielleicht auch an anderer Stelle gerne aufnehmen. Einen speziellen Punkt möchte ich allerdings doch anführen: Die Übersetzung des graphentheoretischen Problems in die Sprache der Spieltheorie scheint für das mathematisch Behandelte unnötig. Um den Artikel nicht zu lang werden zu lassen, habe ich nur Weniges und am Rande erwähnt, was aus dieser Übersetzung folgt. Tatsächlich liegt mein persönliches Interesse auch mehr in der Umkehrung - der Übertragung des price of anarchy in das spieltheoretische und wirtschaftswissenschaftliche Setting. Ansonsten gilt das zuvor Bemerkte. Eure Anna-Katharina.

Literatur

Ich habe mich bemüht, Internet-Quellen als Belege aufzuführen. Einige Anregungen habe ich anderen Werken entnommen, die ich hier nur aufführe. [die00] R. Diestel, Graphentheorie (2. Auflage), 2000, Springer. [pig20] A. C. Pigou, The Economics of Welfare, 1920, Macmillan. [rou02] T. Roughgarden, Selfish Routing, 2002, Ph.D. Thesis. [slb09] Y. Shoham, K. Leyton-Brown, Multiagent Systems, 2009, herunterladbar hier.

!

Die letzten Worte dieses Artikels sollen denen gehören, die sie am meisten verdienen: E. für ihre Geduld; R. für das interessante Gesprächsthema. Und natürlich den eifrigen Korrekturlesern: Kuestenkind, ligning, mire2, Quantum-007 und tactac. Mein besonderer Dank an Quantum-007 gilt auch für die Erstellung der Abbildungen. Herzlichen Dank!
\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist nicht im Verzeichnis der Arbeitsgruppe Alexandria eingetragen.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 892
 
Aufrufstatistik des Artikels
Insgesamt 22 externe Seitenaufrufe zwischen 2020.05 und 2022.10 [Anzeigen]
DomainAnzahlProz
https://google.com1463.6%63.6 %
https://google.de836.4%36.4 %

Häufige Aufrufer in früheren Monaten
Insgesamt 22 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2020-2022 (14x)https://google.com/
2021-2022 (8x)https://google.de/

[Top of page]

"Mathematik: Der Preis der Freiheit" | 6 Comments
The authors of the comments are responsible for the content.

Re: Der Preis der Freiheit
von: Ex_Mitglied_39392 am: Do. 11. Oktober 2018 19:57:08
\(\begingroup\)Hallo, der Artikel fasziniert mich. Danke dafür. Allerdings muss ich gestehen, dass ich nur bis zu den Grundlagen folgen kann. Dann fehlen mir die mathematischen Fähigkeiten. Eigentlich reicht es nur bis zum Braess-Paradoxon. Auf der einen Seite ist mir mathematisch klar, dass sich mit einer zusätzlichen Straße die Fahrzeit für alle Fahrer verlängern kann, jedoch sträubt sich in mir der "gesunde Menschenverstand". Irgendwie möchte ich nicht, da es so ist. 😛 Dabei gibt es sogar ein reales Beispiel. Die nach langem politischen Gezänk (und dem Verlust des UNESCO-Welterbetitels für das Dresdner Elbtal) in Dresden gebaute Waldschlößchenbrücke brachte zwar Entlastung für andere Brücken. Im Ergebnis verringerten sich die Fahrtzeiten i.A. nicht. siehe: Wie sich die Waldschlößchenbrücke auswirkt Im Artikel ist vor allem der Routenvergleich interessant. Vor einiger Zeit habe ich mal ein kleines Programm geschrieben, bei dem man für die einfachste Version des Braess-Paradoxons für die Straßenabschnitte Zeitfunktionen testen kann. siehe https://mathematikalpha.de/braess-paradoxon Ich finde es erstaunlich, wie bei unterschiedlicher Anzahl der Fahrer die Auswahl der Fahrstrecken mit unterschiedlichen Fahrtzeiten eintreten. LG Steffen \(\endgroup\)
 

Re: Der Preis der Freiheit
von: AnnaKath am: Fr. 12. Oktober 2018 16:18:12
\(\begingroup\)Huhu Steffen, danke für die freundlichen Worte. Der price of anarchy ("POC") ist ein Konzept, das auch in vielen anderen Situationen auftreten kann. Einige sind vielleicht noch verblüffender und der Intuition "mehr" widersprechend als in den im Artikel genannten Beispielen. Ich freue mich aber auch über Deine Anmerkungen zur Waldschlößchenbrücke, die beweist, das es sich hierbei keineswegs um ein rein "hypothetisches" Problem handelt. Ein anderes konkretes Beispiel ist die "Nachwahl" im Wahlkreis Dresden I zur Bundestagswahl von 2005. Hier die Beschreibung der absurden Situation aus Wikipedia "Aufgrund des negativen Stimmgewichtes im Bundestagswahlrecht – das in der Prüfung der Wahl mittlerweile für verfassungswidrig erklärt wurde – wäre es möglich gewesen, dass zusätzliche Stimmen für eine Partei diese einen Sitz gegenüber dem ersten vorläufigen Ergebnis gekostet hätten. So hätte die CDU einen Sitz im Bundestag weniger erhalten, wenn sie in Dresden etwa 3000 Zweitstimmen mehr erhalten hätte. Das Wahlergebnis (CDU: −6,1 %, FDP: +9,6 % etc.) lässt vermuten, dass dies von einer großen Zahl von CDU-nahen Wählern verhindert wurde, indem sie mit der Zweitstimme FDP gewählt haben. Vorausgegangen war dem eine FDP-Zweitstimmenkampagne unter dem Motto 'Dresden wählt schlau: Erststimme CDU, Zweitstimme FDP'." Solche realen Beispiele mögen verstören. Auch hier gibt es eine gute Nachricht: Die Disziplin des Mechanismus-Design beschäftigt sich gerade mit der Frage, wie man Systeme so entwerfen kann, dass sie auch theoretisch immun gegen strategisches Verhalten ("Egoismus") sein können. Für eine gewisse Klasse von Problemen existiert mit dem VCG-Mechanismus eine solche Möglichkeit. Und kein Licht ohne Schatten: vgl. hier. Ein schönes Wochenende, AK.\(\endgroup\)
 

Re: Der Preis der Freiheit
von: Gerhardus am: So. 14. Oktober 2018 13:33:47
\(\begingroup\)Ein Beispiel für Definition 4 ist das Spiel "Schere, Stein, Papier". Eigentlich ist j darin kein Spieler, sondern eine Zahl zwischen 1 und |N|. Seit 4 Jahren liegt in meiner Schublade eine 6-seitige Einführung in die Spieltheorie, geeignet für Schüler, etwas, das auf dem Markt noch fehlt. Die reicht allerdings auch nicht, um den Artikel zu verstehen, der für mich auch zu schwierig ist. \(\endgroup\)
 

Re: Der Preis der Freiheit
von: AnnaKath am: So. 14. Oktober 2018 16:40:33
\(\begingroup\)Huhu Gerhardus, herzlichen Dank für Deine Anmerkung. Allerdings kann ich Dir in inhaltlicher Hinsicht nicht folgen - die Zahl $|N|=2$ für das Spiel "Schere-Stein-Papier" (und auch in der Erweiterung "-Lizard-Spock"!) gibt aus meinem Verständnis tatsächlich die Anzahl der Spieler an. Inwiefern siehst Du das anders? Einen schicken Sonntag wünscht Anna-Katharina.\(\endgroup\)
 

Re: Der Preis der Freiheit
von: Gerhardus am: So. 14. Oktober 2018 22:09:30
\(\begingroup\)Anna, ein Missverständnis. Mit "darin" meinte ich nicht das Spiel, sondern deine Definition 4. Erst sagst du, j ist ein Spieler aus N und dann taucht j-1 auf. Eigentlich ist j die Nummer (der Index) des Spielers. Wenn du mit jemand anders spielst, ist der/die andere Spieler(in) auch nicht Annakath ± 1. Abgesehen von dieser Feinheit, finde ich deine Definition klar.\(\endgroup\)
 

Re: Der Preis der Freiheit
von: AnnaKath am: Mo. 15. Oktober 2018 00:19:48
\(\begingroup\)OK, das stimmt natürlich. Für die Definition des Nash-Gleichgewichts müsste man $j$ aus einer Abzählung von $N$ wählen. Ich bitte, die Definition so zu lesen.\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]