Netzwerk-Design-Spiele. Lokales und Globales Verbindungsspiel

Inhaltsverzeichnis

1 Einleitung

2 Lokales Verbindungsspiel
2.1 Modell und grundlegende Eigenschaften
2.2 Preis der Anarchie
2.3 Baumvermutung
2.4 Verwandte Modelle

3 Globales Verbindungsspiel
3.1 Modell und grundlegende Eigenschaften
3.2 Preis der Stabilität
3.3 Approximative Nash-Gleichgewichte

4 Faires Globales Verbindungsspiel und Potentialspiele
4.1 Shapley-Kostenteilung
4.2 Faires Globales Verbindungsspiel
4.3 Potentialspiele und Potentialfunktionsmethode

Literature

1 Einleitung

Um in der Informatik das Internet zu beschreiben oder in der BWL komplexe Märkte, erweisen sich Netzwerkmodelle als besonders hilfreich, die kein zentral gesteuertes Design voraussetzen, sondern eigenständige Spieler abbilden, die zu ihrem eigenen Nutzen Verbindungen zu anderen Spielern herstellen. Die Spieler versuchen dabei die Qualität und die Kosten ihrer eigenen Aktionen zu optimieren. Bei den entstehenden Netzwerken wird untersucht, wie sich Effizienz und Stabilität gegenseitig beeinflussen. Dabei gibt es zwei konkurrierende Ziele: die Spieler versuchen ihre Kosten bei der Bildung des Netzwerks zu minimieren - aber dennoch gleichzeitig die bestmögliche Qualität an Leistung des Netzwerks zu erhalten. Die Qualität des Netzwerks kann gemessen werden in der Distanz zu den anderen Spielern (Abschnitt 2) oder der Konnektivität (Abschnitt 3).(vgl. [Algorithmic Game Theory], 487f.)

Die eigennützigen Spieler und die daraus entstehenden Netzwerke können mit den Mit- teln der Spieltheorie beschrieben werden. Normalformspiele und Nash-Gleichgewichte bilden die grundlegenden spieltheoretischen Konzepte, auf denen die weitere Betrach- tung aufbaut:

Definition 1. Ein N ormalf ormspiel ist ein Modell einer interaktiven Entschei- dungsfindung, bei der jeder Entscheider seinen Handlungsplan ein für allemal fest- legt. Diese Entscheidung wird gleichzeitig getroffen. Das Modell ist ein Tripel Γ = (N, Σ, c), bestehend aus einer endlichen Menge N = {1, 2, . . . , n} von Spielern, ei- nem Strategieraum Σ = Σ1 × Σ2 × · · · × Σn mit der nicht leeren Strategiemenge Σi des Spielers i, aus der er seine Handlung wählen kann, und einer Kostenf unktion c : Σ → Rn. Dabei ist ci : Σ → R die Kostenfunktion des Spielers i. Abhängig von der eigenen Strategie Si ∈ Σi, die Spieler i aus seiner Strategiemenge gewählt hat, und den Strategien der anderen Spieler entsteht ein Strategieprof il S = (S1, . . . , Si, . . . , Sn) mit Kosten von ci (S1, . . . , Si, . . . , Sn) = ci (S) für den Spieler i. Eine analoge Definition ist für eine Auszahlungs- bzw. Nutzenfunktion ui möglich. (vgl. [Game Theory], 11-13)

In der folgenden Betrachtung der Netzwerk-Design-Spiele werden Nash-Gleichgewichte als Lösungskonzept benutzt und die Netzwerke in diesen Gleichgewichten werden als stabil angesehen.(vgl. [Algorithmic Game Theory], 488)

Definition 2. Ein N ash − Gleichgewicht eines Normalformspiels Γ = (N, Σ, u) ist

ein Strategieprofil S∗, sodass für jeden Spieler i ∈ N gilt:

Abbildung in dieser Leseprobe nicht enthalten

wobei S−i = (S1, . . . , Si−1, Si+1, . . . , Sn). Analog lautet die Bedingung für eine

Auszahlungs- bzw. Nutzenfunktion:

Abbildung in dieser Leseprobe nicht enthalten

Die Bedingung für ein Nash-Gleichgewicht fordert also, dass kein Spieler i eine Strategie zur Verfügung hat, die seine Kosten (bzw. Auszahlung) gegenüber der Strategie S*i senkt(bzw.erhöht),währendjederandereSpielerjseineGleichgewichtsstrategie j wählt. Kurz gesagt: kein Spieler kann nutzbringend abweichen, bei gegebenen Strategien der anderen Spieler. (vgl. [Game Theory], 14f.)

Eine andere Formulierung der Definition benutzt die Beste-Antwort-Funktion.

Definition 3. Für alle S−i ∈ Σ−i sei Bi (S−i) die Menge der besten Antworten von Spieler i bei gegebenen S−i:

Abbildung in dieser Leseprobe nicht enthalten

Die Funktion Bi, die als Werte Mengen hat, heißt Beste − Antwort − F unktion von Spieler i. In dieser Formulierung ist ein Nash-Gleichgewicht ein Profil S∗, das folgende Bedingung erfüllt:

Abbildung in dieser Leseprobe nicht enthalten

Diese Formulierung führt auf eine Methode, um Nash-Gleichgewichte aufzufinden: Zu- erst berechne man die Beste-Antwort-Funktion für jeden Spieler und finde dann ein Strategieprofil s*, sodass S*i

Abbildung in dieser Leseprobe nicht enthalten

2 Lokales Verbindungsspiel

2.1 Modell und grundlegende Eigenschaften

Das von Fabrikant et al. 2003 vorgestellte Lokale Verbindungsspiel (vgl. [PODC’03]; [Algorithmic Game Theory], 489-494) bildet ein Normalformspiel Γ = Γ(n, α) = (V, Σ, c) und geht aus von Spielern V = {1, ..., n} (= N ), die ein zusammenhängendes

Netzwerk konstruieren müssen. Dazu baut ein Spieler i eine Menge von Kanten zu anderen Spielern, die im Anschluss in beide Richtungen genutzt werden können. Durch das Bauen von Kanten entstehen Kosten und jeder Spieler profitiert von möglichst kurzen Wegen zu allen anderen Spielern. Die Menge von Nachbarknoten Si ⊆ V \{i} bildet eine Strategie von Spieler i. Zu einem Strategieprofil S = (S1, ..., Sn) betrachtet man den ungerichteten Graphen

Abbildung in dieser Leseprobe nicht enthalten

Die Kostenfunktion ci von Spieler i besteht aus den Kosten α > 0 pro aufgebauter Kante und der Länge des kürzesten Weges zu jedem Spieler j, ∀j = i. Als zu minimierende Kosten für den Spieler i ergeben sich daraus

Abbildung in dieser Leseprobe nicht enthalten

wobei dG(i, j) den Abstand zwischen den Knoten i und j bezeichnet.(vgl. [Graphentheorie], 9) Wenn die Knoten i und j nicht verbunden sind, wird dG(i, j) = ∞.

- Folglich ist jeder Graph G(S) in einem Nash-Gleichgewicht S zusammenhängend. Für die sozialen Kosten des gesamten Netzwerks folgt

Abbildung in dieser Leseprobe nicht enthalten

Diese sozialen Kosten bilden die (utilitaristische) Zielfunktion in der Effizienzbetrach- tung der Netzwerke.(vgl. [Algorithmic Game Theory], 443f.) Ein Netzwerk ist optimal, wenn es die sozialen Kosten C(S) minimiert, und sei bezeichnet mit OP T . Da jedes Knotenpaar, das nicht durch eine Kante verbunden wird, mindestens mit Abstand dG(i, j) = 2 entfernt liegt, ergibt sich als untere Schranke für die sozialen Kosten[PODC’03]:

Abbildung in dieser Leseprobe nicht enthalten

Diese Schranke wird von jedem Graphen erreicht, dessen Durchmesser (vgl. [Graphentheorie], 9) diamG ≤ 2 ist.

Analog entsteht eine zu maximierende Gewinnfunktion mit ui (S) = −ci (S).

Für ein Nash-Gleichgewicht gilt:

Abbildung in dieser Leseprobe nicht enthalten

Der Versuch Nash-Gleichgewichte zu finden, indem man mit einer Strategie startet und wiederholt die Strategien der einzelnen Spieler durch die beste Antwort ersetzt (vgl. “Best-Response-Dynamics” in [Algorithmic Game Theory], 30f.), erweist sich als schwierig:

Satz 1. Es ist NP-schwer bei gegebenem S = (S1, ..., Sn) und i ∈ V die beste Antwort von Spieler i zu berechnen.[PODC’03]

Beweis. Reduktion auf das Dominanzproblem.

Spieler i erhält die Konfiguration S−i des ganzen restlichen Graphen, einschließlich der eingehenden Kanten, und muss eine Teilmenge von Knoten auswählen, sodass seine Kosten ci minimiert werden, wenn die Kanten zu dieser Teilmenge gebaut werden. Wenn für 1 < α < 2 keine eingehenden Kanten existieren, ist die Strategie eine dominierende Menge für den restlichen Graphen, da der Durchmesser des Graphen G(S) höchstens 2 sein kann, und zur minimalen Anzahl an Kanten zusätzliche Verbindungen nur die Distanz in ci um 1 senken. Deshalb werden die Kosten minimiert, wenn die Größe der Teilmenge minimiert wird.[PODC’03]

Das Lokale Verbindungsspiel Γ(n, α) wird durch folgende grundlegende Eigenschaften gekennzeichnet:

1. In allen Nash-Gleichgewichten gibt es keine Verbindung, die von beiden End- punkten bezahlt wird.
2. Für α ≥ 2 ist jede Lösung S, dessen zugehöriger Graph G(S) einen Stern(vgl. [Graphentheorie], 18) bildet, eine optimale Lösung, für α ≤ 2 ist jede Lösung, des- sen zugehöriger Graph einen vollständigen Graphen bildet, eine optimale Lösung.
3. Für α ≥ 1 ist jede Lösung S, bei der G(S) einen Stern bildet, ein Nash-
Gleichgewicht, für α ≤ 1 ist jede Lösung S, bei der G(S) einen vollständigen Graphen bildet, ein Nash-Gleichgewicht.
4. Für α < 1 bilden die Strategieprofile S zum vollständigen Graphen G(S) die einzigen Nash-Gleichgewichte.

Eigenschaft 1: Würde eine Kante von beiden Endknoten bezahlt, hätte einer der beiden Spieler einen Anreiz seine Strategie dahingehend zu ändern, die Kante nicht mehr zu bezahlen, und dadurch seine Ausgaben zu senken, während er denselben Abstand zu allen anderen Spielern behält. Ein Strategieprofil, in dem Kanten von beiden Endknoten bezahlt werden, kann deshalb kein Nash-Gleichgewicht sein.

Eigenschaft 2: Angenommen S sei eine optimale Lösung mit m Kanten in G(S). Damit ist m ≥ n − 1, denn sonst wäre der Graph nicht zusammenhängend. Alle geordneten Knotenpaare, die nicht direkt verbunden sind, haben einen Abstand von mindestens 2 und es gibt n(n − 1) − 2m solche Paare. Zusammen mit den 2m Paaren mit Distanz 1 ergibt sich αm + 2n(n − 1) − 4m + 2m = (α − 2)m + 2n(n − 1) ≤ C(S) als untere Schranke für die sozialen Kosten. Sowohl der Stern als auch der vollständige Graph stimmen mit dieser Schranke überein. Die sozialen Kosten werden minimiert durch ein möglichst kleines m für α > 2 - also einen Stern - und ein möglichst großes m für α < 2 - einen vollständigen Graphen. (vgl. [Algorithmic Game Theory], 490)

Eigenschaft 3: Angenommen α ≥ 1 und G(S) sei ein Stern. Jede Zuordnung von Kanten zu inzidenten Spielern ergibt ein Nash-Gleichgewicht. Die folgende Zuordnung zeigt, dass es zu jedem Graph G(S), der einen Stern bildet, eine entsprechende Lösung S gibt, die ein Nash-Gleichgewicht bildet. Das Strategieprofil besteht darin, dass Spieler 1 (das Zentrum des Sterns) alle Kanten zu anderen Spielern kauft, während die ver- bleibenden n − 1 Spieler keine Kante kaufen. Spieler 1 hat keinen Anreiz abzuweichen, denn dann wäre der Graph nicht mehr zusammenhängend und dadurch die Kosten un- endlich. Die anderen n − 1 Spieler können nur abweichen, indem sie Kanten zusätzlich kaufen. Jeder solche Spieler spart durch k hinzugefügt Kanten k an der Distanz, muss aber αk hinzubezahlen, sodass es insgesamt keinen Nutzen bringt. Deshalb ist dieses Strategieprofil ein Nash-Gleichgewicht. Angenommen α ≤ 1 und G(S) sei ein vollständiger Graph, dessen Kanten zu inzi- denten Spielern zugeordnet sind. Weicht ein Spieler ab, in dem er k Kanten weniger kauft, spart er αk an Kosten, aber erhöht die Distanz um k, sodass er sich nicht verbessern kann. Jedes Strategieprofil S zum vollständigen Graphen G(S) ist deshalb ein Nash-Gleichgewicht. (vgl. [Algorithmic Game Theory], 491)

Eigenschaft 4: Laut Eigenschaft 2 wird das soziale Optimum erreicht durch alle Strategieprofile S, die einem vollständigen Graphen G(S) zugeordnet werden können. Für ein Strategieprofil, das keinen vollständigen Graphen G(S) bildet, gibt es einen Spieler, der die Distanz zu einem anderen Knoten um 1 senken kann, während die zusätzliche Kante nur α < 1 kostet. Folglich sind die dem vollständigen Graphen zugehörigen Strategieprofile die einzigen Nash-Gleichgewichte.

2.2 Preis der Anarchie

Das Konzept des Preises der Anarchie (Price of Anarchy) stammt von Koutsoupias und Papadimitriou mit Ihrem 1999 erschienen Artikel “Worst-case equilibria”.⁶ Der Begriff selbst wurde geprägt von Papadimitriou 2001⁸ ; er beschreibt, um welchen Faktor sich die Kosten des Netzwerks verschlechtern können gegenüber einem optima- len zentral konstruierten Netzwerk, wenn es von Spielern mit eigenem Interesse aufge- baut wird. Die Ineffizienz der Nash-Gleichgewichte wird mit einem worst-case Ansatz beschrieben: Es handelt sich um das Verhältnis der Kosten des schlechtesten Nash- Gleichgewichts max S Nash-Gleichgewicht bei zentralem Design:

Abbildung in dieser Leseprobe nicht enthalten

Satz 2. Für α < 1 ist der Preis der Anarchie 1. Für 1 ≤ α < 2 ist der Preis der Anarchie höchstens^{4 3}.

Beweis. Aus Eigenschaft 4 folgt direkt, dass der Preis der Anarchie 1 ist für α < 1.

Für 1 ≤ α < 2 wird das soziale Optimum weiterhin durch den vollständigen Graphen erreicht, obwohl die zugehörigen Lösungen S für α > 1 kein Nash-Gleichgewicht bilden. Jeder Graph zu einem Nash-Gleichgewicht hat einen Durchmesser von höchstens 2, sodass die sozialen Kosten genau Gleichung (1) entsprechen. Der Wert wird maximal, wenn |E| minimal wird, also für einen zusammenhängenden Graphen |E| = n − 1.

[...]