Speltheorie in de computerwetenschappen Patrick De Causmaecker Met dank aan Katja Verbeeck Katholieke Universiteit Leuven Campus Kortrijk
Mezelf • Licentiaat Wiskunde (Gent) • Doctor in de Fysica (Leuven) • Professor Informatica (Leuven-Kortrijk) Richtingen Wiskunde, Fysica, Informatica
Mijn Groep • ~20 onderzoekers • Artificiele intelligentie voor complexe combinatorische optimalisatie Optimalisatie in gedistribueerde systemen/Planning en Scheduling/Roosters voor personeel/bioinformatica/e-learning/digitale beeldverwerking/
Waarover gaat ‘speltheorie’? Speltheorie (Game Theory) = De theorie van rationele keuzes Onderwerp = Het gedrag van interagerende rationele beslissingsmakers
Rationeel? Het Monty-hall probleem
Wat is een spel? • Een spel beschrijft de STRATEGIEEN die de spelers kunnen kiezen • Een spel is geen relaas van keuzes en gebeurtenissen
1.e4 e5 2.Pf3 Pc6 3.Lb5 a6 4.La4 Pf6 5.d3 b5 6.Lb3 Lc5 7.Pc3 d6 8.Pd5 Pg4 9.00 Pa5 10.Lg5 f6 11.Ld2 Pb3 12.ab c6 13.La5
Een voorbeeld, we zullen verder niet over schaken spreken… •Bach/Stravinsky •2 spelers - 2 mogelijke acties
Bach
Strav.
Bach
2,1
0,0
Strav.
0,0
1,2
Een rationele keuze • De rijspeler is rationeel • …en weet dat de kolomspeler rationeel is L T
1,1
M
2,2
B
1,0
M
R
0,2
2,1
1,1 0,0
0,0 -1,1
Een beetje geschiedenis
• Gaat voor een deel terug tot de 18de eeuw. • Moderne grondleggers: • Emile Borel (1871~1956 • John Von Neumann (1903~1957)
Het eerste boek • Speltheorie wordt een onderzoeksdomein met het boek van John von Neumann en Oskar Morgenstern (1944)
John Nash (1928--)
Doctoraat Princeton 1950 (28 bladzijden!) Nash Equilibrium Theorie van het bieden
Toepassingen van speltheorie • • • • •
Economisce wet. Politieke wet. Psychologie Evolutieleer Computerwet.
• Prijszetting oligarchien,… • Drijgingen, koude oorlog • Probleem van de commons • Cooperatie in soorten • Netwerken, software
Nobelprijzen economie 1994
John C. Harsanyi
John F. Nash Jr.
Reinhard Selten
"for their pioneering analysis of equilibria in the theory of non-cooperative games"
Nobelprijzen economie 2005
Robert J. Aumann
Thomas C. Schelling
"for having enhanced our understanding of conflict and cooperation through game-theory analysis"
Kolom: Ik wil heel graag naar Bach gaan luisteren, ook wel naar Stravinsky Rij: Ik hoor liever Stravinsky, maar als het niet anders kan zit ik wel een Bachje uit Beiden: Alleen gaan is helemaal niets
Bach
Strav.
Bach
2,1
0,0
Strav.
0,0
1,2
Dit is een voorbeeld van een strategisch spel • Ook wel ‘matrix’ spel. • Beide spelers weten mekaars voorkeuren • Ze kunnen één voorstel doen, daarna ligt de beslissing vast • Hierbij weten ze (nog) niet waar de ander voor gaat
B S
Bach 2,1 0,0
Strav. 0,0 1,2
Stategische spelen • In het algemeen gaat het over n spelers • Het aantal spelers is hier 2 • In dit geval spreken we van rij (Stravinsky fan) en kolom (Bach liefhebber)
B S
Bach 2,1 0,0
Strav. 0,0 1,2
Acties • Elke speler beschikt over een verzameling acties • Een spel is eindig als het aantal acties voor elke speler eindig is
B S
Bach 2,1 0,0
Strav. 0,0 1,2
B
S
E
B
2,1
0,0
0,0
S
0,0
1,2
0,0
E
0,0
0,0
3,3
Acties • De spelers hebben voorkeuren • Deze voorkeuren zijn meestal voorgesteld door een getal (utility)
B S
Bach 2,1 0,0
Strav. 0,0 1,2
B
S
E
B
2,1
0,0
0,0
S
0,0
1,2
0,0
E
0,0
0,0
3,3
Een aantal klassieke voorbeelden: Het dilemma van de gevangenen • Prisoners dilemma
Ontken
Beken
Ontken
(1,1)
(4,0)
Beken
(0,4)
(3,3)
• De getallen stellen de te verwachten straf voor • De gevangenen verkiezen de lagere ‘waarden’
‘Battle of the sexes’
Bach
Strav.
Bach
2,1
0,0
Strav.
0,0
1,2
Een coördinatiespel
Mozart
Mahler
Mozart
2,2
0,0
Mahler
0,0
1,1
De havik en de duif Welk gedrag kiezen we? Duif
Havik
Duif
3,3
1,4
Havik
4,1
0,0
Chicken game
Chicken
Straight
Chicken
0,0
-1,1
Straight
1,-1
-10,-10
Kop of munt Zuiver competitief
Chemistry
Voor
Achter
Voor
1,-1
-1,1
Achter
-1,1
1,-1
Nash evenwichten • De verhandeling van John Nash in 1950 had als titel ‘Non-cooperative games’ • Hij toonde aan dat de oplossingen van spelen die tot dan toe bekend waren een kenmerk gemeen hadden: Nash Evenwicht
Informele definitie
Rationeel
• Een verzameling acties in een spel is in Nash Evenwicht als geen van de spelers een reden heeft om zijn gedrag te veranderen
• Prisoners dilemma
Ontken
?
? Beken
Ontken
(1,1)
(4,0)
Beken
(0,4)
(3,3)
‘Battle of the sexes’
Bach
Strav.
Bach
2,1
0,0
Strav.
0,0
1,2
De havik en de duif Welk gedrag kiezen we? Duif
Havik
Duif
3,3
1,4
Havik
4,1
0,0
Kop of munt Zuiver competitief
Chemistry
Voor
Achter
Voor
1,-1
-1,1
Achter
-1,1
1,-1
Een oneindig spel • Verkoop per opbod • Bieders 1,2,…,n • v1 > v2 > … > vn • Bod b1,b2,…,bn • Utility vi-bi voor de winnaar, 0 voor de anderen
Wat zijn de Nash Evenwichten voor dit spel?
Een oneindig spel • Verkoop per opbod • Bieders 1,2,…,n • v1 > v2 > … > vn • Bod b1,b2,…,bn • Utility vi-bi voor de winnaar, 0 voor de anderen
Elk bod van b1 met • v1 >= b1 >= v2 • b1 >= bj voor j <> 1 • b1 = bj, minstens één j > 1
Een oneindig spel • Onderstelling: – Alle vi zijn door iedereen gekend (iedereen weet wat het goed waard is voor elke andere)
• Andere technieken zijn nodig indien dit niet zo is
Elk bod van b1 met • v1 >= b1 >= v2 • b1 >= bj voor j <> 1 • b1 = bj, minstens één j > 1
Hoe komen we de echte waarde te weten?
• Alle spelers bieden, de hoogste bieder wint, maar betaalt de prijs van de tweede hoogste bieder • Vickery auction
Domante strategie: bj = vj, voor elke j
Nobelprijs economie 1996
William Vickery, vader van de theorie van veilingen
Dominante strategieën • Prisoners dilemma
Dominant voor de rijspeler
Dominant voor de kolomspeler
Ontken
Beken
Ontken
(1,1)
(4,0)
Beken
(0,4)
(3,3)
Pareto-optimale strategieën • Prisoners dilemma
Ontken
Beken
Ontken
(1,1)
(4,0)
Beken
(0,4)
(3,3)
• Er is geen andere strategie die – voor niemand slechter is – voor iemand beter is
Som nul spelen Steen Schaar Papier
• Voor elke strategie is de som van de utilities gelijk nul
Steen
0
1
-1
Schaar
-1
0
1
Papier
1
-1
0
Hoe speel je Schaar-Papier-Steen? 1/3
Rock
1/3
1/3
Scissor Paper
0.4
Rock Scissor
0 -1
1 0
-1 1
0.3
Paper
1
-1
0
0.3
• Geef de tegenspeler niets om zich aan vast te houden • Kies ALTIJD willeurig • Voorbeeld van een GEMENGDE strategie
STELLING
• Elk spel met n spelers en een eindig aantal zuivere strategieen heeft minstens één (misschien gemengd) Nash Evenwicht
Even proberen • The Da Vinci Code
• Mission Impossible III
1,0 1,0 0,1 0,1 2/3, 1/3 1/3, 2/3
DVC 2,1 0,0
DVC MI:3
MI:3 0,0 1,2
Speltheorie en Computerwetenschappen
• Berekenen van Nash evenwichten is een moeilijk en ingewikkeld probleem – Gebruik sterke rekencomputers – ‘Computational gametheory’
Speltheorie en Computerwetenschappen
• Bijvoorbeeld : – e-commerce – Beurs – Netwerken – Youtube – Productie –…
Speltheorie en Computerwetenschappen
• Het internet is een (grote) verzameling toestellen en programma’s die iets doen in opdracht van hun gebruikers (waarschijnlijk mensen) – Deze toestellen en programma’s gedragen zich rationeel en spelen eigenlijk een spel met heel veel spelers en heel veel acties
Morality • Rationaliteit is egocentrisch • Is dit realistisch • Misschien heb ik een beeld van mijn ‘tegenstrever’ • Wat brengt de toekomst • Kan dit echt gevat worden in speltheorie?
• We laten gehandicapten en ouderen zitten op de bus • Mijn tegenstrever is mijn tweelingbroer – Die doet wel net als ik
Wat brengt de toekomst? • Misschien ontmoeten we mekaar nog wel eens. • Als we het spel van de gevangenen herhaald spelen, wat doen we dan best?
• Spelen we oneindig lang of is er ooit een laatste keer?
• Als we het oneindig lang kunnen spelen is vertrouwen noodzakelijk
• De laatste keer kun je je tegenspeler niet meer vertrouwen… • De voorlaatste keer? • Prisoners dilemma
Ontken
Beken
Ontken
(1,1)
(4,0)
Beken
(0,4)
(3,3)
Gaat dit echt zo? • Axelrod 1984 – Laat ons dit uitproberen – We laten echte spelers het dilemmaspel spelen
• Een wedstrijd, diegene met de laagste straf of de hoogste opbrengst wint
And the winner is… • TIT-FOR-TAT – Begin met samen te werken (ontken) – Daarna doe je telkens wat er in de ronde ervoor werd gedaan
?
