Quelltext anzeigen

Selfish Routing (engl. etwa "egoistisches Vermitteln") bezeichnet die Strategie, bei der Nutzer in einem fest vorgegebenen Netzwerk eigennützig immer die schnellsten Routen wählen. Dies erscheint auf den ersten Blick die effektivste und vernünftigste Vorgehensweise zu sein, jedoch hält diese Annahme einer genaueren Untersuchung nicht stand.

==Beispiele==

===Pigou's Beispiel===
Wir betrachte das Netzwerk in der folgenden Abbildung, das
aus zwei parallelen Kanten besteht.

[[Bild:Pigou.jpg]]

Jede Kante ''e'' ist mit einer Latenzfunktion <math>c_e \colon \mathbb{R}^+ \to \mathbb{R}^+</math> beschriftet, die die (flussabhängige) Latenz (Fahrzeit, Verzögerung, engl. latency) auf dieser Kante angibt. So ist z.B. die Latenz auf der oberen Kante 1 (unabhängig vom Fluss), die der unteren Kante hat wächst linear mit dem Fluss auf der Kante. Wir möchten eine Flusseinheit von ''s'' nach ''t'' schicken (diese Flusseinheit entspricht einer Vielzahl von Nutzern, die von ''s'' nach ''t'' wollen).

Im Falle von Selfish Routing wird jeder Nutzer wie folgt argumentieren: 
die Latenz auf der unteren Kante ist 1, falls der gesamte Fluss diese benutzt und kleiner
als 1, falls jemand die obere Kante wählt. Folglich wird jeder Nutzer die untere
Kante wählen; wir nennen dies einen Nash-Fluss.
Die durchschnittliche Latenz des Nash-Flusses bei Selfish Routing ist also 1.
Betrachten wir nun einen optimalen Fluss, der die durchschnittliche Latenz minimiert.
Dieser Fluss sendet <math>p \in [0,1]</math> Einheiten auf der
unteren und <math>1- p</math> Einheiten auf der oberen Kante. Die durchschnittliche Latenz ist dann
<math>(1- p)+ p^2</math>; diese Funktion wird für <math>p = \frac{1}{2}</math> minimiert und beträgt somit <math>\frac{3}{4}</math>.

===Braess Paradoxon=== 
Wir betrachten das linke Beispielnetzwerk in folgender Abbildung.
[[Bild:Braess.jpg]]

Erneut soll eine Flusseinheit von ''s'' nach ''t'' geschickt werden. Bei egoistischer Routenplanung
verteilt sich der (Nash-)Fluss gleichmäßig auf den oberen und unteren Pfad mit durchschnittlicher Latenz <math>\frac{3}{2}</math>.
Um die Situation zu verbessern, fügen wir eine Kante mit Latenz 0 ein; siehe rechte Abbildung
. Paradoxerweise verschlechtert sich damit aber der Nash-Fluss: die
Flusseinheit fließt entlang der linken oberen Kante, über die 0-Kante und schließlich
über die rechte untere Kante mit durchschnittlicher Latenz 2.
Das Beispiel zeigt, dass eine Verbesserung der Netzwerkinfrastruktur bei egoistischer
Routenplanung eine Verschlechterung verursachen kann.

Natürliche Anwendungsgebiete, in denen die Auswirkungen egoistischer Routenwahl
relevant sind, finden sich zum Beispiel in der Verkehrsplanung und -optimierung oder in
Netzwerk-Routing Protokollen.

[http://www.sueddeutsche.de/wissen/454/326318/text/ Braess Paradoxon in der Presse]


Diesen beiden Beispiele werfen nun einige Fragen auf, wie z.B. wie groß kann die Abweichung des Nash-Flusses vom optimalen Fluss werden, wie hängt diese Abweichung vom zugrundeliegenden Netzwerk und von den Latenzfunktionen ab usw.


==Modell==

Vor der Untersuchung dieser Fragen definieren wir zunächst das
Modell und führen Notationen ein.

Eine Instanz des Selfish Routing Problems ist wie folgt spezifiziert. Gegeben sind:
*Ein gerichteter Graph <math>G = (V,E)</math> mit Knotenmenge <math>V</math> und Kantenmenge <math>E</math>.
*Für jede Kante <math>e \in E</math> ist eine nicht-negative Latenzfunktion <math>c_e \colon \mathbb{R}^+ \to \mathbb{R}^+</math> gegeben.
*Wir haben ''k'' Knotenpaare <math>(s_i, t_i) \in V \times V, s_i \ne t_i</math>, von Start- und Zielknoten, die wir hier als <math>commodities</math> (Güter) bezeichnen. Für jede commodity <math>i \in [k]</math> möchten wir <math>r_i > 0</math> Flusseinheiten von <math>s_i</math> nach <math>t_i</math> senden. Wir nennen <math>r_i</math> die <math>Rate</math> von commodity ''i''.

Wir schreiben <math>(G, r,c)</math>, um eine Instanz des Selfish Routing
Problems zu bezeichnen (hierbei ist <math>r := (r_i)_{i\in [k]}</math> und <math>c := (c_e)_{e\in E})</math>.
Sei <math>\mathcal P_i</math> die Menge aller (einfachen) Pfade von <math>s_i</math> nach <math>t_i</math> in <math>G</math> und definiere
<math>\mathcal P := \bigcup _{i\in [k]}\mathcal P_i</math>

als die Menge aller relevanten Pfade.Wir senden den Fluss entlang der Pfade <math>P</math> in <math>\mathcal P</math>.
Die Mengen <math>\mathcal P_i</math> sind paarweise disjunkt; ansonsten müssen
die Start-/Zielknoten von commodities ''i'' und ''j''gleich sein und wir können diese zu einer commodity der Rate <math>r_i+r_j</math> zusammenfassen.


===Flüsse===

{|
|width="5%" style="vertical-align:top" |
|width="90%" style="vertical-align:top" bgcolor="#DDFFFF"|
'''Definition'''
Ein ''Fluss'' f in einem Graphen <math>G</math> ist ein Vektor <math>(f_P)_{P\in \mathcal P}</math>, der jedem Pfad
<math>P\in \mathcal P</math> einen nicht-negativen Wert zuweist. Für einen Pfad <math>P\in \mathcal P_i</math> ist <math>f_P</math> die Flusseinheit,
die von <math>s_i</math> nach <math>t_i</math> entlang des Pfades <math>P</math> geschickt wird. 

Ein Fluss f heißt ''zulässig'', wenn
gilt:

<math>\forall i \in [k] : \sum_{P\in \mathcal P_i}f_p = r_i</math>
|
|}


In unserem Modell repräsentiert ein positiver Fluss <math>f_P > 0</math> auf einem Pfad <math>P\in \mathcal P_i</math>
eine Route <math>P</math> entlang welcher ein Bruchteil <math>\frac{f_P}{r_i}</math> des gesamten Flusses <math>r_i</math> von <math>s_i</math> nach <math>t_i</math>
gelangt. Insbesondere gehen wir davon aus, dass der Fluss bzgl. jeder commodity <math>i \in [k]</math>
zykelfrei ist. (Dies gilt o.B.d.A., wenn es keine gerichteten Kreise mit Latenz
0 gibt.)

{|
|width="5%" style="vertical-align:top" |
|width="90%" style="vertical-align:top" bgcolor="#DDFFFF"|
'''Definition'''
Wir definiere den ''Fluss auf einer Kante'' <math>e \in E</math> als
<math>f_e:= \sum_{P\in \mathcal P:e\in P}f_p</math>
|
|}

Jeder Pfadfluss <math>(f_P)_{P\in \mathcal P}</math> induziert einen eindeutigen Kantenfluss <math>(f_e)_{e\in E}</math>. Zu einem Kantenfluss kann es jedoch mehrere Pfadflüsse geben. Wir können mittels des Dekompositionssatzes
von Flüssen immer einen Pfadfluss aus einem Kantenfluss bestimmen.

Wir gehen im weiteren Verlauf davon aus, dass die Latenzfunktion <math>c_e \colon \mathbb{R}^+ \to \mathbb{R}^+</math> für
jede Kante <math>e \in  E</math> nicht-negativ, differenzierbar und (schwach) monoton steigend ist. Diese
Klasse von Kostenfunktionen reicht für viele Anwendungen aus.

{|
|width="5%" style="vertical-align:top" |
|width="90%" style="vertical-align:top" bgcolor="#DDFFFF"|
'''Definition'''
Wir definieren die ''Kosten eines Pfades'' <math>P</math> ''bzgl. f'' als
<math>c_P(f) := \sum_{e\in P}c_e(f_e)</math>.
Intuitiv ist <math>c_P(f)</math> die gesamte Latenz, die man auf dem Pfad <math>P</math> erfährt. 

Die ''gesamten Kosten'' (Netzbelastung) eines Flusses <math>f</math> sind wie folgt definiert:
<math>C(f) := \sum_{P\in \mathcal P}c_P(f)\cdot f_P</math>
|
|}

Wir betrachten hier die gesamte im Netzwerk vorhandene Latenz anstatt der durchschnittlichen Latenz; diese beiden Werte unterscheiden sich lediglich um einen konstanten Faktor<math>\sum_i r_i</math>Durch Umformung erhalten wir die folgende alternative Definition:
<math>C(f) = \sum_{P\in \mathcal P}c_P(f)\cdot f_P=\sum_{P\in \mathcal P}(\sum_{e\in P}c_e(f_e))\cdot f_P = \sum_{e\in E}c_e(f_e)\cdot \sum_{P\in \mathcal P:e\in P}f_P = \sum_{e\in E}c_e(f_e)\cdot f_e</math>


{|
|width="5%" style="vertical-align:top" |
|width="90%" style="vertical-align:top" bgcolor="#DDFFFF"|
'''Definition'''
Ein zulässiger Fluss <math>f^*</math> ist ''optimal'', wenn er die Kostenfunktion <math>C(\cdot)</math> über die Menge aller zulässigen Flüsse minimiert.
|
|}

Ein optimaler Fluss existiert, da die Menge aller zulässigen Flüsse kompakt ist und
die Funktion <math>C(\cdot)</math> stetig ist (Satz von Weierstraß).



Intuitiv ist ein zulässiger Fluss f ein ''Nash-Fluss'', wenn gilt: für jede commodity <math>i \in [k]</math>
gibt es keine <math>\delta</math>-Flusseinheit, die durch Wechseln von ihrem zugehörigen Pfad <math>P_1 \in \mathcal P_i</math> auf einen Pfad <math>P_2 \in \mathcal P_i</math> die Kosten verringern kann. Formal definieren wir dies wie folgt:
{|
|width="5%" style="vertical-align:top" |
|width="90%" style="vertical-align:top" bgcolor="#DDFFFF"|
'''Definition'''
Sei ''f'' ein zulässiger Fluss für <math>(G, r,c)</math>. ''f'' ist ein ''Nash-Fluss'' (auch: Wardrop-Equilibrium), wenn für jede commodity <math>i \in [k]</math>, für alle Pfade <math>P_1,P_2 \in \mathcal P_i</math> mit <math>f_{P_1} > 0</math> und für jedes <math>\delta \in (0, f_{P_1}]</math> gilt:
<math>c_{P_1}(f) \leq  c_{P_2}(\tilde f)</math>,

wobei

<math>\tilde f_P := \begin{cases}
f_p-\delta \ \mbox{falls} P=P_1 \\
f_p+\delta \ \mbox{falls} P=P_2 \\
f_p        \ \mbox{sonst} 
\end{cases}</math>
|
|}

oder für <math>\delta \to 0</math>:
{|
|width="5%" style="vertical-align:top" |
|width="90%" style="vertical-align:top" bgcolor="#DDFFFF"|
'''Definition'''
Seien die Latenzfunktionen <math>(c_e)_{e\in E}</math> differenzierbar und schwach monoton
steigend. Ein zulässiger Fluss ''f'' für die Instanz ''(G,r,c)'' ist genau dann ein Nash-Fluss,
wenn für jede commodity <math>i \in [k]</math> gilt:
<math>\forall P_1,P_2 \in \mathcal P_i, f_{P_1} > 0 : c_{P_1}(f) \leq c_{P_2}(f)</math>

Wir nennen einen <math>s_i, t_i</math>-Pfad ''P'' mit positivem Fluss <math>f_P > 0</math> einen ''flussführenden Pfad''.
|
|}

Letztere Definition sagt Folgendes aus: 
In einem Nash-Fluss sind die Kosten eines jeden flussführenden <math>s_i, t_i</math>-Pfades minimal. Ferner sind die Kosten aller flussführenden <math>s_i, t_i</math>-Pfade gleich.



'''Bemerkung'''

Wir haben es hier mit einem strategischen [[Spiel]] zu tun, in dem jeder
Spieler (= Nutzer) einer commodity einen infinitesimalen Bruchteil des Gesamtflusses <math>r_i</math> kontrolliert. Man spricht daher auch von einem nicht-atomaren, nicht-kooperativen Strategiespiel.





===Der Preis der Anarchie===

Durch den Vergleicht der Kosten
eines Nash-Flusses mit denen eines Systemoptimums kann man die Auswirkungen von Selfish Routing charakterisieren.

{|
|width="5%" style="vertical-align:top" |
|width="90%" style="vertical-align:top" bgcolor="#DDFFFF"|
'''Definition'''
Gegeben sei eine Instanz (G, r,c) des Selfish Routing Problems. Sei ''f'' ein Nash-Fluss und ''f*'' ein optimaler Fluss für ''(G, r,c)''. Der ''Preis der Anarchie'' <math>\rho</math>''(G, r,c)'' für die Instanz ''(G, r,c)'' ist definiert als

<math>\rho(G, r,c):=\frac{C(f)}{C(f^*)}</math>

Sei <math>\mathcal I</math> eine Menge von Selfish Routing Instanzen. Der ''Preis der Anarchie von'' <math>\mathcal I</math> ist definiert als

<math>\rho (\mathcal I) := sup_{(G,r,c)\in \mathcal I}\rho(G, r,c)</math>
|
|}


Der Preis der Anarchie ist wohldefiniert; im Folgenden wird gezeigt werden, dass es für Selfish Routing Probleme immer einen Nash-Fluss mit eindeutigen Kosten geben muss . Somit ist auch der Wert
<math>\rho</math>''(G, r,c)'' eindeutig.

Im Allgemeinen versteht man unter dem Preis der Anarchie das
Verhältnis eines schlechtesten Nash-Gleichgewichts zu einem optimal Fluss.



==Charakterisierung von optimalen Flüssen und Nash-Flüssen==

Bevor nun optimale Flüsse und optimale Nash-Flüsse charakterisiert und beschrieben werden, ist es noch notwendig, diesen Abschnitt um ein Merkmal aus der nicht-linearen Programmierung zu ergänzen:

Gegeben sei eine Selfish-Routing-Instanz (G, r,c). Betrachten das folgende nichtlineare Programm (NLP):

<center>
<math>  min \sum_{e\in E} h_{e} (f_{e})| </math>

u.d.N.  <math> \sum_{P\in \mathcal P_{i}} f_{P} = r_{i} </math> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <math> \forall i \in [k] </math>

<math> f_{e} = \sum_{P\in \mathcal P: e \in P} f_{P} </math> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <math> \forall e \in E </math>

<math> f_{P} \geq 0 </math> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <math>\forall P\in \mathcal P </math>
</center>

Die erste und letzte Nebenbedingung stellen sicher, dass der Fluss <math>f(P)_{P\in \mathcal P} </math> ein zulässiger Fluss für <math> (G,r,c) </math> ist.

Die zweite Nebenbedingung weist jeder Kante den entsprechenden Kantenfluss zu; dies wird benötigt, da die Zielfunktion auf der Grundlage eines Kantenflusses definiert ist.

Da wir es hier mit einem Programm mit exponentiell vielen Variablen zu tun haben, wandeln man dies nun (relativ leicht) in ein kompakteres Programm (Kantenformulierung) mit |E| vielen Variablen um.

<math>(NLP)</math> ist ein Lineares Programm, wenn die Funktionen <math>(h_{e})_{e \in E} </math> linear sind. Sind
die Funktionen <math>(h_{e})_{e \in E} </math> hingegen konvex und differenzierbar, gibt uns einer der wichtigsten
Optimalitätsbedingungen der nichtlineare Optimierung (first order, Kuhn–Tucker) den folgenden Satz:

{|
|width="5%" style="vertical-align:top" |
|width="90%" style="vertical-align:top" bgcolor="#DDFFFF"|
'''Satz (Optimalitätsbedingung für <math>(NLP)</math>)'''

Betrachte das Programm <math>(NLP)</math> mit konvexen und differenzierbaren Funktionen <math>(h_{e})_{e \in E} </math>.

Ein zulässiger Fluss <math>f</math> ist eine optimale Lösung für <math>(NLP)</math> genau dann, wenn für jede commodity <math> i \in [k] </math> und für alle Pfade <math> P_{1},P_{2} \in \mathcal P </math> mit <math> f_{P_{1}} > 0 </math> gilt:
<center>
<math> h^{'}_{P_{1}}(f) := \sum_{e\in P_{1}} h^{'}_{e}(f_{e}) \leq \sum_{e\in P_{2}} h^{'}_{e}(f_{e}) =: h^{'}_{P_{2}}(f)</math>

wobei <math> h^{'}_{e}(x)</math> die Ableitung <math> \frac {d}{dx} h_{e}(x) </math> bezeichnet.
</center>
|
|}


===Optimale Flüsse===

{|
|width="5%" style="vertical-align:top" |
|width="90%" style="vertical-align:top" bgcolor="#DDFFFF"|
'''Definition'''

Ein optimaler Fluss <math>f^{*}</math> ist ein zulässiger Fluss, der die Funktion <math> C( f ) = \sum_{e\in E} c_{e}(f_{e})* f_{e} </math> minimiert.
|
|}


sei nun
<math> h_{e}(x):= x * c_{e}(x) </math>

(die Menge aller optimalen Lösungen zu <math>(NLP)</math> entspricht genau der Menge aller optimalen Flüsse)

Die Funktion <math> c: \mathbb{R}^{+} \to \mathbb{R}^{+}</math> heisst ''semi-konvex'', wenn <math> x*c(x)</math> konvex ist.


Um die Charakterisierung eines optimalen Flusses abzuschliessen, treffen wir folgende Annahme:

Die Latenzfunktionen <math>(c_{e})_{e \in E}</math> einer Selfish Routing Instanz <math>(G,r,c)</math> sind
nicht-negativ, schwach monoton steigend, differenzierbar und semi-konvex.

Instanzen, die diese Bedingungen erfüllen, nennen wir ''gutmütig''.


Unter dieser Annahme sind die Funktionen <math>h_{e}(x)</math> differenzierbar und konvex, und mit der Optimalitätsbedingung für <math>(NLP)</math> gilt nun:

Sei <math>(G,r,c)</math> eine gutmütige Selfish Routing Instanz.

Dann ist <math>f{*}</math> genau dann ein optimaler Fluss, wenn für jede commodity <math>i \in [k]</math> und für alle Pfade <math>P_{1},P_{2} \in \mathcal P_{i}</math> mit
<math>f^{*}_{P_{1}} > 0 </math> gilt:
<center>
<math> \sum_{e\in P_{1}} h^{'}_{e}(f^{*}_{e}) \leq \sum_{e\in P_{2}} h^{'}_{e}(f^{*}_{e})</math> (marginale Kostenfunktion)
</center>

mit <math> h^{'}_{e}(x):= c_{e}(x) + x * c^{'}_{e}(x) </math>


{|
|width="5%" style="vertical-align:top" |
|width="90%" style="vertical-align:top" bgcolor="#DDFFFF"|
'''Definition''':Marginale Kostenfunktion

Sei <math>(G,r,c)</math> eine gutmütige Selfish Routing Instanz. 
Wir definieren die marginale Kostenfunktionen <math> c^{*} := (c^{*}_{e})_{e \in E} </math> als

<center>
<math> c^{*}_{e}(x):= \frac {d}{dx} c_{e}(x)*x = c_{e}(x) + x * c^{'}_{e}(x)</math>
</center>
|
|}


<math> \Rightarrow </math>

Ein zulässiger Fluss <math>f^{*}</math> ist somit genau dann optimal, wenn für jeden Pfad <math>P</math> mit <math>f^{*}_{P} > 0 </math> die marginalen Kosten <math> c^{*}_{P}(f)</math> minimal sind. 


<math> \Rightarrow </math>

Sei nun <math>(G,r,c)</math> eine gutmütige Selfish Routing Instanz.

Ein zulässiger Fluss <math>f^{*}</math> ist genau dann optimal für <math>(G,r,c)</math>, wenn <math>f^{*}</math> ein Nash-Fluss für die Instanz <math>(G,r,c^{*})</math> ist.


===Existenz und Eindeutigkeit von Nash-Flüssen===

Existenz eines Nash-Flusses:

Betrachte das nichtlineare Programm <math>(NLP)</math>, wobei die Funktionen <math>(h_e)_{e \in E} </math> wie folgt definiert sind:

<center>
<math> h_e (x) := \int_0^x c_e(t)\,dt </math> 
</center>


Behauptung: Die optimalen Lösungen zu <math>(NLP)</math> mit diesen Funktionen entsprechen gerade den Nash-Flüssen

'''''Satz'''''

Sei <math>(G,r,c)</math> eine Instanz des Selfish Routing Problems mit nicht-negativen, differenzierbaren und schwach monoton steigenden Latenzfunktionen <math>(c_e)_{e \in E}</math>. Dann ist die Menge aller Nash-Flüsse von <math>(G,r,c)</math> gerade die Menge aller optimalen Lösungen zu <math>(NLP)</math> mit den Kostenfunktionen <math> h_e (x)</math>.


(Beweis. Die Ableitung der Funktion <math> h_e</math> ist <math>c_e</math>, eine nicht-negative, differenzierbare und schwach monoton steigende Funktion. Somit ist die Funktion he für jede Kante <math>e \in E </math> konvex. Ferner ist <math>h_e</math> differenzierbar.
<math>(NLP)</math> ist also ein konvexes Programm und wir können den Satz über die Optimalitätsbedingungen anwenden.

Es folgt: f ist genau dann eine optimale Lösung für <math>(NLP)</math>, wenn für jede commodity <math>i \in [k]</math> und für alle Pfade <math>P_1,P_2 \in \mathcal P_i</math> mit <math>f_{P_1} > 0 </math> gilt:

<math>h^'_{P_1}(f) = c_{P_1}(f) \leq c_{P_2}(f) = h^'_{P_2}(f)</math>.

Eine optimale Lösung <math>f</math> von <math>(NLP)</math> entspricht somit genau einem Nash-Fluss <math>f</math> für <math>(G,r,c)</math>. q.e.d.)




'''''Korollar:'''''

Sei <math>(G,r,c)</math> eine Selfish Routing Instanz mit nicht-negativen, differenzierbaren und schwach monoton steigenden Latenzfunktionen <math>(c_e)_{e \in E}</math>. Dann existiert ein Nash-Fluss.

(Beweis. Die Zielfunktion des Programms <math>(NLP)</math> mit <math> h_e (x) := \int_0^x c_e(t)\,dt </math> ist stetig. 
Ferner ist die Menge aller zulässigen Flüsse kompakt. Somit existiert eine optimale Lösung zu <math>(NLP)</math> . Mit obigem Satz folgt die Aussage. q.e.d.)


Sei <math>(G,r,c)</math> eine Selfish Routing Instanz mit nicht-negativen, differenzierbaren und schwach monoton steigenden Latenzfunktionen <math>(c_e)_{e \in E}</math>. Seien <math>f</math> und <math>\tilde f</math> Nash-Flüsse für <math>(G,r,c)</math>.

Es gilt: <math>C(f)= C(\tilde f)</math>.

(Beweis: folgt aus obigem Satz.)

===Beispiele===

Um das, was eben erarbeitet wurde, an Beispielen zu illustrieren, greifen wir nun auf obige Beispiele (Pigou's Beispiel,Braess Paradoxon) zurück.

====Pigou's Beispiel====

[[Bild:Pigou.jpg]]

Man betrachte nun diese Abbildung:

Ein Nash-Fluss <math>f</math> hat die Eigenschaft, dass alle flussführenden <math>s,t-Pfade</math> die gleichen Kosten haben.

Der Fluss, der eine Flusseinheit entlang der unteren Kante schickt, hat diese Eigenschaft und ist somit ein Nash-Fluss.

Betrachten wir nun einen optimalen Fluss. Dieser ist ein Nash-Fluss bzgl. der marginalen Kostenfunktionen <math>c^*</math>.
Die marginalen Kosten auf der untern Kante ist <math>2x</math>, die der
oberen ist 1.
Möchten wir die Kosten auf allen flussführenden Pfaden bzgl. <math>c^*</math> ausbalancieren, so geschieht dies, wenn wir <math>x = 1/2</math> wählen; also je eine halbe Flusseinheit über die untere und obere Kante schicken.

Das ist ein optimaler Fluss.


====Braess Paradoxon====

[[Bild:Braess.jpg]]


Wenn wir jetzt wieder die Abbildung von oben betrachten, konzentrieren wir uns auf die rechte Abbildung:

Ein Nash-Fluss balanciert alle Kosten der flussführenden <math>s,t-Pfade</math>. Wir senden daher eine Flusseinheit über die Kanten links oben, mitte, rechts unten. Der optimale Fluss balanciert die Kosten der flussführenden <math>s,t-Pfade</math> bzgl <math>c^*</math>.
Wir schicken daher jeweils eine halbe Einheit entlangdes oberen und unteren Pfades.

==Reduktion der Preis der Anarchie auf Pigou-ähnliche Instanzen==


===Konstante Latenzfunktionen===

===Lineare und konstante Latenzfunktionen===

===Affin lineare Latenzfunktionen===

===Polynomielle Latenzfuntionen mit Grad p===


==Quellen und Links==

* Artikel über ''"Selfish Routing and the Price of Anarchy"'' in der MIT Press:
http://mitpress.mit.edu/catalog/item/default.asp?tid=10339&ttype=2

* Dissertation über ''"Selfish routing with incomplete information"'':
http://ubdok.uni-paderborn.de/servlets/DocumentServlet?id=5369