Filebestrijding middels Speltheorie Krzysztof R. Apt (dus niet Krzystof en zeker niet Krystof) CWI & Universiteit van Amsterdam
Speltheorie – p. 1/3
Voorbeeld 1: Kilometerheffing 2 bestuurders. Elke bestuurder kiest een route van BEGIN naar zijn eigen depot. Meer bestuurders kiezen dezelfde route ⇒ de kosten worden verdeeld. BEGIN 5
4 1
DEPOT1
8 1
DEPOT2
Speltheorie – p. 2/3
Een evolutie (1) BEGIN 5
4 1
DEPOT1
8 1
DEPOT2
Speltheorie – p. 3/3
Een evolutie (2) BEGIN 5
4 1
DEPOT1
8 1
DEPOT2
Speltheorie – p. 4/3
Een evolutie (3) BEGIN 5
4 1
DEPOT1
8 1
DEPOT2
Nu zijn beide bestuurders tevreden.
Speltheorie – p. 5/3
Beetje theorie (1) Strategisch spel voor 2 spelers: Elke speler heeft een aantal strategieën. Elke speler wil zijn kosten minimaliseren. Beide spelers kiezen hun strategieën simultaan. Daarna moet elke speler zijn gedeelte van de kosten betalen. In ons voorbeeld: tolweg spellen 2 spelers. Elke speler heeft 2 strategieën. Kosten voor elke speler: totaal van de gedeelde kosten van de gekozen weg.
Speltheorie – p. 6/3
Nash Evenwicht (1) Neem een spel met willekeurige strategieën voor spelers 1 en 2. Strategie A van speler 1 is een beste respons op een strategie B van speler 2 als het de kosten van speler 1 t.o.v. B minimaliseert. Combinatie (A, B) van strategieën van spelers 1 en 2 is een Nash evenwicht als A is een beste respons op B en B is een beste respons op A. Intuïtie: in een Nash evenwicht heeft geen speler spijt van zijn keuze.
Speltheorie – p. 7/3
John Nash Van Wikipedia: “John Forbes Nash Jr. (Bluefield (West Virginia), 14 juni 1928) is een wiskundige, die in zijn beste tijd geniaal genoemd werd. Hij kreeg vooral bekendheid door zijn werk op het gebied van de speltheorie. Hij ontving hiervoor samen met twee andere speltheoretici, Reinhard Selten en John Harsanyi, de Nobelprijs voor de Economie in 1994.”
Speltheorie – p. 8/3
Wat hebben wij eigenlijk gedaan? Beste Respons Dynamiek Kies een ‘beginsituatie’: elke speler kiest een strategie. Een ‘ontevreden’ speler mag een andere keuze maken via de beste respons. Herhaal deze procedure. Als het eindigt dan bereiken wij een Nash evenwicht. Stelling (Rosenthal, 1973) Voor de tolweg spellen bereikt de beste respons dynamiek altijd een Nash evenwicht.
Speltheorie – p. 9/3
Sociaal Optimum (1) Sociaal optimum: combinatie van strategieën van spelers 1 en 2 die tot minimale totale kosten leidt. In ons voorbeeld was het unieke Nash evenwicht ook een sociaal optimum. BEGIN 5
4 1
DEPOT1
8 1
DEPOT2
Speltheorie – p. 10/3
Meerdere Nash evenwichten Voorbeeld
BEGIN
2
3
DEPOT
Speltheorie – p. 11/3
Sociaal Optimum (2) Een ander voorbeeld BEGIN 5
3 1
DEPOT1
5 1
DEPOT2
Uniek Nash evenwicht, met de kosten 8. Kosten van sociaal optimum: 7.
Speltheorie – p. 12/3
Voorbeeld 2: Files 5 bestuurders. Elke bestuurder kiest een route van BEGIN naar EIND, Meer bestuurders kiezen dezelfde route ⇒ grotere vertragingen. BEGIN
1/2/3
1/4/5
EIND
1/5/6
Speltheorie – p. 13/3
Een mogelijke evolutie (1) BEGIN
1/2/3
1/4/5
1/5/6
EIND
Speltheorie – p. 14/3
Een mogelijke evolutie (2) BEGIN
1/2/3
1/4/5
1/5/6
EIND
Speltheorie – p. 15/3
Een mogelijke evolutie (3) BEGIN
1/2/3
1/4/5
1/5/6
EIND
Speltheorie – p. 16/3
Een mogelijke evolutie (4) BEGIN
1/2/3
1/4/5
1/5/6
EIND
Nu is elke bestuurder tevreden.
Speltheorie – p. 17/3
Beetje theorie (2) Strategisch spel voor n spelers: Elke speler heeft een aantal strategieën. Elke speler wil zijn kosten minimaliseren. Alle spelers kiezen hun strategieën simultaan. Daarna moet elke speler zijn kosten betalen. In ons voorbeeld: 5 spelers. Elke speler heeft 3 strategieën. Kosten voor elke speler: de totale rijtijd.
Speltheorie – p. 18/3
Nash Evenwicht (2) Neem een spel. Stel elke speler heeft een strategie gekozen. Een strategie van een speler is een beste respons (t.o.v. de strategieën van de andere spelers) als het tenminste zo goed is als elke andere strategie van hem. Nash evenwicht: combinatie van strategieën van de spelers z.d.d. elke strategie een beste respons is (t.o.v. de andere strategieën). Wij hebben een Nash evenwicht bereikt middels de beste respons dynamiek. Stelling (Rosenthal, 1973) Voor de netwerkspellen bereikt de beste respons dynamiek altijd een Nash evenwicht.
Speltheorie – p. 19/3
Ander Voorbeeld Aannames: 4000 spelers rijden van A naar B. Elke bestuurder heeft 2 mogelijkheden (strategieën).
U T/100
45
45
B T/100
A R
Vraag: Wat is hier het Nash evenwicht? (T = aantal rijders, T/100 = vertraging.)
Speltheorie – p. 20/3
Nash evenwicht U T/100
45
45
B T/100
A R Antwoord: 2000/2000.
Totale rijtijd: 2000/100 + 45 = 45 + 2000/100 = 65.
Speltheorie – p. 21/3
Braess Paradox Voeg een snelle route van U naar R toe. Elke bestuurder heeft nu 3 mogelijkheden (strategieën): A - U - B, A - R - B, A - U - R - B.
U T/100
45 0
A 45
B T/100
R Vraag: Wat is hier het Nash evenwicht?
Speltheorie – p. 22/3
Nash evenwicht U T/100
45 0
A 45
B T/100
R Antwoord: Iedereen kiest de route A - U - R - B. Waarom?: De route A - U - R - B is altijd een beste respons.
Speltheorie – p. 23/3
Een probleem U T/100
45 0
A 45
B T/100
R Totale rijtijd: 4000/100 + 4000/100 = 80!
Speltheorie – p. 24/3
Gebeurt het eigenlijk? Van Wikipedia (‘Braess Paradox’): In Seoul, South Korea, a speeding-up in traffic around the city was seen when a motorway was removed as part of the Cheonggyecheon restoration project. In Stuttgart, Germany after investments into the road network in 1969, the traffic situation did not improve until a section of newly-built road was closed for traffic again. In 1990 the closing of 42nd street in New York City reduced the amount of congestion in the area. In 2008 Youn, Gastner and Jeong demonstrated specific routes in Boston, New York City and London where this might actually occur and pointed out roads that could be closed to reduce predicted travel times.
Speltheorie – p. 25/3
Prijs van Stabiliteit Definitie PvS: sociale kosten van het beste Nash evenwicht sociaal optimum Vraag: Wat is de PvS van de tolweg en de netwerkspellen?
Speltheorie – p. 26/3
Voorbeeld n
A
B
x
n - (even) aantal spelers en de vertraging op de bovenste route. x - aantal rijders en de vertraging op de onderste route.
Speltheorie – p. 27/3
Voorbeeld n
A
B
x
n - (even) aantal spelers en de vertraging op de bovenste route. x - aantal rijders en de vertraging op de onderste route.
Beste Nash evenwicht Twee Nash evenwichten: 1/(n − 1), met de kost n + (n − 1)2 . 0/n, met de kost n2 .
Speltheorie – p. 28/3
Voorbeeld n
A
B
x
n - (even) aantal spelers en de vertraging op de bovenste route. x - aantal rijders en de vertraging op de onderste route.
Beste Nash evenwicht Twee Nash evenwichten: 1/(n − 1), met de kost n + (n − 1)2 . 0/n, met de kost n2 . Sociaal optimum Neem f (x) = (n − x) · n + x · x = x2 − n · x + n2 . Wij willen f minimaliseren. f ′ (x) = 2x − n, dus f ′ (x) = 0 als x = n2 .
Speltheorie – p. 29/3
Voorbeeld n
A
B
x
Beste Nash evenwicht 1/(n − 1), met de kost n + (n − 1)2 . Sociaal optimum f (x) = x2 − n · x + n2 . Sociaal optimum = f ( n2 ) = 43 n2 . PoS = (n + (n − 1)2 )/ 34 n2 limn→∞ PoS = 43 .
=
2
4 n+(n−1) 3 n2
.
Speltheorie – p. 30/3
Harmonische Getallen H(n) = 1 + 1/2 + . . . + 1/n.
Stelling (Oresme, circa 1350) H(n) divergeert. Stelling (Euler, 1734) limn→∞ H(n) − ln(n) = γ . Probleem: Je stapelt veilig boeken:
Vraag: Met hoeveel boeken kun je de dubbele afstand bereiken? Antwoord: kleinste n z.d.d. 12 H(n) ≥ 2. 1 1 H(30) = 1.99749 , 2 2 H(31) = 2.01362.
Speltheorie – p. 31/3
Bewijs van Nicolas Oresme 1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + . . . = 1 + 1/2 + (1/3 + 1/4) + (1/5 + 1/6 + 1/7 + 1/8) + . . . > 1 + 1/2 + (1/4 + 1/4) + (1/8 + 1/8 + 1/8 + 1/8) + . . . = 1 + 1/2 + 1/2 + 1/2 + ...
Speltheorie – p. 32/3
PvS Stelling (Anshelevich et al, 2004) De PvS van een tolweg spel voor n spelers is ≤ H(n). Stelling (Roughgarden en Tárdos, 2002) Stel dat alle vertragingsfuncties (b.v. T /100) altijd lineair zijn. Dan is de PvS van een netwerkspel ≤ 34 . Het ‘goede’ Nash evenwicht wordt middels de beste respons dynamiek bereikt. Helaas: het kan exponentieel lang duren totdat het evenwicht bereikt wordt.
Speltheorie – p. 33/3
Open Problemen Voorbeeld Stel dat alle vertragingsfuncties polynomiaal zijn (b.v. T 2 + T /100). Wat is dan de PvS van een netwerkspel?
Speltheorie – p. 34/3
Referenties Algorithm Design, Jon Kleinberg and Éva Tardos, Addison-Wesley, 2006, pp. 690-700. Networks, Crowds, and Markets, David Easley and Jon Kleinberg, Cambridge University Press, 2010, pp. 239-253 (beschikbaar online).
Speltheorie – p. 35/3
Meer weten over de speltheorie?
Spelen en delen: speltheorie, de wiskunde van conflictmodellen, Frank Thuijsman, 55 pagina’s, Epsilon Uitgaven, 2005. Zie presentatie 13 in http://www.personeel.unimaas.nl/F-Thuijsman/ FT-presentations.htm Mijn college Strategic games: http://www.cwi.nl/~apt/stra. Deze presentatie: http://www.cwi.nl/~apt/slides/uva10-sli.pdf.
Speltheorie – p. 36/3
Bedankt
Speltheorie – p. 37/3
Vragen svp aan Minister Eurlings
Speltheorie – p. 38/3
