Selfish Routing

Aus Wikiludia

Version vom 21. Januar 2009, 13:30 Uhr von Rauschecker (Diskussion | Beiträge)

(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

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.

Inhaltsverzeichnis

1 Beispiele
- 1.1 Pigou's Beispiel
- 1.2 Braess Paradoxon
2 Modell
- 2.1 Flüsse
- 2.2 Der Preis der Anarchie
3 Charakterisierung von optimalen Flüssen und Nash-Flüssen
4 Reduktion der Preis der Anarchie auf Pigou-ähnliche Instanzen
5 Quellen und Links

Beispiele

Pigou's Beispiel

Wir betrachte das Netzwerk in der folgenden Abbildung, das aus zwei parallelen Kanten besteht.

Jede Kante e ist mit einer Latenzfunktion $c_e \colon \mathbb{R}^+ \to \mathbb{R}^+$ 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 $p \in [0,1]$ Einheiten auf der unteren und $1 - p$ Einheiten auf der oberen Kante. Die durchschnittliche Latenz ist dann $(1 - p) + p 2$ ; diese Funktion wird für $p = \frac{1}{2}$ minimiert und beträgt somit $\frac{3}{4}$ .

Braess Paradoxon

Wir betrachten das linke Beispielnetzwerk in folgender Abbildung.

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 $\frac{3}{2}$ . 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.

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 $G = (V, E)$ mit Knotenmenge $V$ und Kantenmenge $E$ .
Für jede Kante $e \in E$ ist eine nicht-negative Latenzfunktion $c_e \colon \mathbb{R}^+ \to \mathbb{R}^+$ gegeben.
Wir haben k Knotenpaare $(s_i, t_i) \in V \times V, s_i \ne t_i$ , von Start- und Zielknoten, die wir hier als $c o m m o d i t i e s$ (Güter) bezeichnen. Für jede commodity $i \in [k]$ möchten wir $r i > 0$ Flusseinheiten von $s i$ nach $t i$ senden. Wir nennen $r i$ die $R a t e$ von commodity i.

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

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

Flüsse

Definition Ein Fluss f in einem Graphen $G$ ist ein Vektor $(f_P)_{P\in \mathcal P}$ , der jedem Pfad $P\in \mathcal P$ einen nicht-negativen Wert zuweist. Für einen Pfad $P\in \mathcal P_i$ ist $f P$ die Flusseinheit, die von $s i$ nach $t i$ entlang des Pfades $P$ geschickt wird.

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

$\forall i \in [k] : \sum_{P\in \mathcal P_i}f_p = r_i$

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

Definition Wir definiere den Fluss auf einer Kante $e \in E$ als $f_e:= \sum_{P\in \mathcal P:e\in P}f_p$

Jeder Pfadfluss $(f_P)_{P\in \mathcal P}$ induziert einen eindeutigen Kantenfluss $(f_e)_{e\in E}$ . 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 $c_e \colon \mathbb{R}^+ \to \mathbb{R}^+$ für jede Kante $e \in E$ nicht-negativ, differenzierbar und (schwach) monoton steigend ist. Diese Klasse von Kostenfunktionen reicht für viele Anwendungen aus.

Definition Wir definieren die Kosten eines Pfades $P$ bzgl. f als $c_P(f) := \sum_{e\in P}c_e(f_e)$ . Intuitiv ist $c P (f)$ die gesamte Latenz, die man auf dem Pfad $P$ erfährt.

Die gesamten Kosten (Netzbelastung) eines Flusses $f$ sind wie folgt definiert: $C(f) := \sum_{P\in \mathcal P}c_P(f)\cdot f_P$

Wir betrachten hier die gesamte im Netzwerk vorhandene Latenz anstatt der durchschnittlichen Latenz; diese beiden Werte unterscheiden sich lediglich um einen konstanten Faktor

\sum r i i

Durch Umformung erhalten wir die folgende alternative Definition:

$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$

Definition Ein zulässiger Fluss $f *$ ist optimal, wenn er die Kostenfunktion $C(\cdot)$ ü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 $C(\cdot)$ stetig ist (Satz von Weierstraß).

Intuitiv ist ein zulässiger Fluss f ein Nash-Fluss, wenn gilt: für jede commodity $i \in [k]$ gibt es keine $δ$ -Flusseinheit, die durch Wechseln von ihrem zugehörigen Pfad $P_1 \in \mathcal P_i$ auf einen Pfad $P_2 \in \mathcal P_i$ die Kosten verringern kann. Formal definieren wir dies wie folgt:

Definition Sei f ein zulässiger Fluss für $(G, r, c)$ . f ist ein Nash-Fluss (auch: Wardrop-Equilibrium), wenn für jede commodity $i \in [k]$ , für alle Pfade $P_1,P_2 \in \mathcal P_i$ mit $f_{P_1} > 0$ und für jedes $\delta \in (0, f_{P_1}]$ gilt: $c_{P_1}(f) \leq c_{P_2}(\tilde f)$ ,

wobei

$\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}$

oder für $\delta \to 0$ :

Definition Seien die Latenzfunktionen $(c_e)_{e\in E}$ 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 $i \in [k]$ gilt: $\forall P_1,P_2 \in \mathcal P_i, f_{P_1} > 0 : c_{P_1}(f) \leq c_{P_2}(f)$

Wir nennen einen $s i, t i$ -Pfad P mit positivem Fluss $f P > 0$ einen flussführenden Pfad.

Letztere Definition sagt Folgendes aus: In einem Nash-Fluss sind die Kosten eines jeden flussführenden $s i, t i$ -Pfades minimal. Ferner sind die Kosten aller flussführenden $s i, t i$ -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 $r i$ 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.

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 $ρ$ (G, r,c) für die Instanz (G, r,c) ist definiert als

$\rho(G, r,c):=\frac{C(f)}{C(f^*)}$

Sei $\mathcal I$ eine Menge von Selfish Routing Instanzen. Der Preis der Anarchie von $\mathcal I$ ist definiert als

$\rho (\mathcal I) := sup_{(G,r,c)\in \mathcal I}\rho(G, r,c)$

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 $ρ$ (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):

$min \sum_{e\in E} h_{e} (f_{e})|$

u.d.N. $\sum_{P\in \mathcal P_{i}} f_{P} = r_{i}$ $\forall i \in [k]$

$f_{e} = \sum_{P\in \mathcal P: e \in P} f_{P}$ $\forall e \in E$

$f_{P} \geq 0$ $\forall P\in \mathcal P$

Die erste und letzte Nebenbedingung stellen sicher, dass der Fluss $f(P)_{P\in \mathcal P}$ ein zulässiger Fluss für $(G, r, c)$ 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.

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

Satz (Optimalitätsbedingung für $(N L P)$ )

Betrachte das Programm $(N L P)$ mit konvexen und differenzierbaren Funktionen $(h_{e})_{e \in E}$ .

Ein zulässiger Fluss $f$ ist eine optimale Lösung für $(N L P)$ genau dann, wenn für jede commodity $i \in [k]$ und für alle Pfade $P_{1},P_{2} \in \mathcal P$ mit $f_{P_{1}} > 0$ gilt:

$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)$

wobei $h^{'}_{e}(x)$ die Ableitung $\frac {d}{dx} h_{e}(x)$ bezeichnet.

Optimale Flüsse

Definition

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

sei nun $h e (x): = x * c e (x)$

(die Menge aller optimalen Lösungen zu $(N L P)$ entspricht genau der Menge aller optimalen Flüsse)

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

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

Die Latenzfunktionen $(c_{e})_{e \in E}$ einer Selfish Routing Instanz $(G, r, c)$ 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 $h e (x)$ differenzierbar und konvex, und mit der Optimalitätsbedingung für $(N L P)$ gilt nun:

Sei $(G, r, c)$ eine gutmütige Selfish Routing Instanz.

Dann ist $f *$ genau dann ein optimaler Fluss, wenn für jede commodity $i \in [k]$ und für alle Pfade $P_{1},P_{2} \in \mathcal P_{i}$ mit $f^{*}_{P_{1}} > 0$ gilt:

$\sum_{e\in P_{1}} h^{'}_{e}(f^{*}_{e}) \leq \sum_{e\in P_{2}} h^{'}_{e}(f^{*}_{e})$ (marginale Kostenfunktion)

mit $h^{'}_{e}(x):= c_{e}(x) + x * c^{'}_{e}(x)$

Definition:Marginale Kostenfunktion

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

$c^{*}_{e}(x):= \frac {d}{dx} c_{e}(x)*x = c_{e}(x) + x * c^{'}_{e}(x)$

$\Rightarrow$

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

$\Rightarrow$

Sei nun $(G, r, c)$ eine gutmütige Selfish Routing Instanz.

Ein zulässiger Fluss $f *$ ist genau dann optimal für $(G, r, c)$ , wenn $f *$ ein Nash-Fluss für die Instanz $(G, r, c *)$ ist.

Existenz und Eindeutigkeit von Nash-Flüssen

Existenz eines Nash-Flusses:

Betrachte das nichtlineare Programm $(N L P)$ , wobei die Funktionen $(h_e)_{e \in E}$ wie folgt definiert sind:

$h_e (x) := \int_0^x c_e(t)\,dt$

Behauptung: Die optimalen Lösungen zu $(N L P)$ mit diesen Funktionen entsprechen gerade den Nash-Flüssen

Satz

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

(Beweis. Die Ableitung der Funktion $h e$ ist $c e$ , eine nicht-negative, differenzierbare und schwach monoton steigende Funktion. Somit ist die Funktion he für jede Kante $e \in E$ konvex. Ferner ist $h e$ differenzierbar. $(N L P)$ 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 $(N L P)$ , wenn für jede commodity $i \in [k]$ und für alle Pfade $P_1,P_2 \in \mathcal P_i$ mit $f_{P_1} > 0$ gilt:

$h^'_{P_1}(f) = c_{P_1}(f) \leq c_{P_2}(f) = h^'_{P_2}(f)$ .

Eine optimale Lösung $f$ von $(N L P)$ entspricht somit genau einem Nash-Fluss $f$ für $(G, r, c)$ . q.e.d.)

Korollar:

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

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

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

Es gilt: $C(f)= C(\tilde f)$ .

(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

Man betrachte nun diese Abbildung:

Ein Nash-Fluss $f$ hat die Eigenschaft, dass alle flussführenden $s, t - P f a d e$ 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 $c *$ . Die marginalen Kosten auf der untern Kante ist $2 x$ , die der oberen ist 1. Möchten wir die Kosten auf allen flussführenden Pfaden bzgl. $c *$ ausbalancieren, so geschieht dies, wenn wir $x = 1 / 2$ wählen; also je eine halbe Flusseinheit über die untere und obere Kante schicken.

Das ist ein optimaler Fluss.

Braess Paradoxon

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 $s, t - P f a d e$ . Wir senden daher eine Flusseinheit über die Kanten links oben, mitte, rechts unten. Der optimale Fluss balanciert die Kosten der flussführenden $s, t - P f a d e$ bzgl $c *$ . Wir schicken daher jeweils eine halbe Einheit entlangdes oberen und unteren Pfades.

Selfish Routing

Inhaltsverzeichnis

Beispiele

Pigou's Beispiel

Braess Paradoxon

Modell

Flüsse

Der Preis der Anarchie

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

Optimale Flüsse

Existenz und Eindeutigkeit von Nash-Flüssen

Beispiele

Pigou's Beispiel

Braess Paradoxon

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

Ansichten

Meine Werkzeuge

Navigation

Suche

Werkzeuge

∑	r_i
i