Auslastungspiele Smoothness DichteSpiele IntuitionundGrenzen Preis der Anarchie Algorithmische Spieltheorie Sommer 2017 MartinHoefer AlgorithmischeSpieltheorie2017 PreisderAnarchie Auslastungspiele Smoothness DichteSpiele IntuitionundGrenzen Erinnerung: Preis der Anarchie Preis der Anarchie fu¨r reine Nash-Gleichgewichte: ◮ Strategisches Spiel Γ, soziale Kosten cost(s) fu¨r Zustand s von Γ ◮ Betrachte ΣRNG als die Menge der reinen Nash-Gleichgewichte von Γ ◮ Preis der Anarchie ist das Verh¨altnis: PoA= maxs′∈ΣRNG cost(s′) mins∈Σcost(s) PoA quantifiziert die Verschlechterung des teuersten NG im Vergleich zum optimalen Zustand des Spiels. Annahme Wir betrachten hier nur cost(s)= i∈Nci(s). P Gibt es eine Technik, mit der sich der Preis der Anarchie in vielen Spielen bestimmen l¨aßt? MartinHoefer AlgorithmischeSpieltheorie2017 PreisderAnarchie Auslastungspiele Smoothness DichteSpiele IntuitionundGrenzen Auslastungsspiele mit linearen Verz¨ogerungsfunktionen PoA in Auslastungsspielen mit dr(x)=ar ·x, fu¨r ar ≥0: ImfolgendenSpielgibtes4Spieler.DieSpielerm¨ochtenvon(1)u nachw,(2) w nachv,(3)v nachw und(4)u nachv.ImPrinziphatjederSpielernureine direkte (direkte Kante) und eine indirekte (u¨ber dritten Knoten) Strategie: w x x 0 x x u v 0 MartinHoefer AlgorithmischeSpieltheorie2017 PreisderAnarchie Auslastungspiele Smoothness DichteSpiele IntuitionundGrenzen Auslastungsspiele mit linearen Verz¨ogerungsfunktionen Optimum s∗ Ein schlechtes NG s x x x x 0 x 0 x x x 0 0 cost(s∗) = 1 + 1 + 1 + 1 = 4 cost(s) = 3 + 2 + 2 + 3 = 10 Der PoA in in diesem Spiel ist mindestens 2.5. Geht es noch schlechter? MartinHoefer AlgorithmischeSpieltheorie2017 PreisderAnarchie Auslastungspiele Smoothness DichteSpiele IntuitionundGrenzen Auslastungsspiele mit linearen Verz¨ogerungsfunktionen Wir zeigen, dass der PoA in diesen Spielen h¨ochstens 2.5 ist: Sei s das schlechteste reine Nash-Gleichgewicht. Wenn Spieler i in s zu einer anderen Strategie abweicht, werden seine Kosten nicht kleiner. Sei s∗ ein optimaler Zustand. Es gilt insbesondere, dass ci(s)≤ci(si∗,s−i). Damit k¨onnen wir die sozialen Kosten beschr¨anken durch ∗ cost(s) = ci(s) ≤ ci(si ,s−i) . (1) i∈N i∈N X X Diesisteineverschr¨ankteSumme–jederSpielerbetrachtetdieKostenwenner alleine zur Strategie in s∗ abweichen wu¨rde. Wie k¨onnen wir diesen Term auf cost(s) und cost(s∗) zuru¨ckfu¨hren? MartinHoefer AlgorithmischeSpieltheorie2017 PreisderAnarchie Auslastungspiele Smoothness DichteSpiele IntuitionundGrenzen Auslastungsspiele mit linearen Verz¨ogerungsfunktionen Betrachten wir den Term genauer fu¨r die Auslastungsspiele. Wir schreiben nr =nr(s) fu¨r die Last von Ressource r in Zustand s und nr∗ =nr(s∗) fu¨r s∗. Wenn Spieler i nach si∗ abweicht, dann sieht er auf jeder Ressource r ∈si∗ eine Last von h¨ochstens nr +1 (evtl. nur nr wenn r ∈si ∩si∗) ∗ ci(si ,s−i)≤ dr(nr +1) . i∈N i∈Nr∈s∗ X XXi Da genau nr∗ Spieler auf Ressource r abweichen, gilt: ∗ ∗ dr(nr +1)= nrdr(nr +1)= nrar ·(nr +1) . i∈Nr∈s∗ r∈R r∈R XXi X X Wir nutzen nun folgendes Lemma ohne Beweis: Lemma (Christodoulou, Koutsoupias, 2005) F¨ur alle nicht-negativen ganzen Zahlen y,z ∈{0,1,2,3,...} gilt 5 1 y(z+1)≤ ·y2+ ·z2 . 3 3 MartinHoefer AlgorithmischeSpieltheorie2017 PreisderAnarchie Auslastungspiele Smoothness DichteSpiele IntuitionundGrenzen Auslastungsspiele mit linearen Verz¨ogerungsfunktionen Mit y =nr∗ und z =nr +1 gilt also: ∗ ∗ ci(si ,s−i)≤ arnr(nr +1) i∈N r∈R X X ≤ ar 5(nr∗)2+ 1nr2 3 3 r∈R (cid:18) (cid:19) X 5 ∗ ∗ 1 = nr(arnr)+ nr(arnr) 3 3 r∈R r∈R X X 5 ∗ 1 = cost(s )+ cost(s) 3 3 und somit ∗ 5 ∗ 1 ci(si ,s−i)≤ ·cost(s )+ ·cost(s) (2) 3 3 i∈N X MartinHoefer AlgorithmischeSpieltheorie2017 PreisderAnarchie Auslastungspiele Smoothness DichteSpiele IntuitionundGrenzen Auslastungsspiele mit linearen Verz¨ogerungsfunktionen Damit k¨onnen wir nun den Preis der Anarchie wir folgt beschr¨anken: 5 ∗ 1 cost(s) ≤ ·cost(s )+ ·cost(s) 3 3 cost(s) 5/3 ⇒ PoA= ≤ = 2.5 (3) cost(s∗) 1−1/3 Aus diesem Beweis leiten wir ein Schema ab: 1. Stelle Ungleichung (1) auf. Sie beruht nur auf der Annahme an cost(s) und darauf, dass s ein reines NG ist. 2. Leite Ungleichung (2) mit Zahlen (λ,µ) her. Die Zahlen (5/3,1/3) waren hier spezifisch fu¨r das Spiel. 3. Schließe die Rechnung durch Ungleichung (3) ab. Die Schranke auf den PoA beruht nur auf den Zahlen in Ungleichung (2). MartinHoefer AlgorithmischeSpieltheorie2017 PreisderAnarchie Auslastungspiele Smoothness DichteSpiele IntuitionundGrenzen Smoothness Die einzige Information u¨ber das Spiel sind die Zahlen in (2). Wenn fu¨r ein Spiel also eine Ungleichung dieser Form gilt, dann k¨onnen wir eine Schranke auf den PoA fu¨r reine NG mit dem Schema finden. Definition Ein Spiel heißt (λ,µ)-smooth fu¨r λ > 0 und µ ≤ 1 wenn fu¨r jedes Paar von Zust¨anden s,s′ gilt ′ ′ ci(si,s−i)≤λ·cost(s )+µ·cost(s) (4) i∈N X Daraus folgt mit dem Schema dann direkt: Satz WenneinSpiel(λ,µ)-smoothist,dannistderPreisderAnarchief¨urreineNash- Gleichgewichte h¨ochstens λ . 1−µ MartinHoefer AlgorithmischeSpieltheorie2017 PreisderAnarchie Auslastungspiele Smoothness DichteSpiele IntuitionundGrenzen Beispiel: Wardropspiele Unser Beweis fu¨r den PoA in Wardropspielen nutzte auch das Schema. Im ersten Schritt C(f) = fede(fe) ≤ gede(fe) e∈E e X X stellen wir quasi (1) auf. Der Term rechts ist im Prinzip eine “verschr¨ankte Summe”, wenn im Gleichgewicht f jeder infinitesimal kleine Spieler einzeln zur Strategie im Optimalfluss g abweicht. Mit dem Lemma und dem Bild-Beweis ergibt sich fu¨r jedes Paar f,g von Flu¨ssen 1 1 gede(fe) ≤ gede(fe)+ fede(fe)= 1·C(g)+ ·C(f) . 4 4 e e∈E e∈E X X X Also: Wardropspiele mit affinen Verz¨ogerungen sind (1,1/4)-smooth. Eine Herleitung wie in (3) liefert C(f)/C(g)≤1/(1−1/4)=4/3. MartinHoefer AlgorithmischeSpieltheorie2017 PreisderAnarchie