Stochastic multiplayer games [Elektronische Ressource] : theory and algorithms / Michael Ummels

Michael Ummels

Sujets

• Informatik

Informations

• Publié par: rheinisch-westfalischen_technischen_hochschule_-rwth-_aachen
• Publié le: 01 janvier 2011
• Nombre de lectures: 8
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

StochasticMultiplayerGames
TheoryandAlgorithmsA
Typesetbytheauthor inFedraSerifBusingLT X.
E
CoverdesignbySamRoss-Gower.
ISBN 978 90 85550402
NUR 918
D 82(Diss.RWTHAachenUniversity,2010)
©MichaelUmmels,2010.
PublishedbyPallasPublications,AmsterdamUniversityPress,Amsterdam.
cbnd
This work is licensed under the Creative Commons Attribution-NonCommercial-
NoDerivs 3.0 Unported License. To view a copy of this license, visit http://
creativecommons.org/licenses/by-nc-nd/3.0/,orsendalettertoCreativeCom-
mons, 1712ndStreet,Suite300,SanFrancisco,California, 94105,USA.StochasticMultiplayerGames:
TheoryandAlgorithms
Von der Fakultät für Mathematik, Informatik und
Naturwissenschaften der RWTH Aachen University
zurErlangungdesakademischenGradeseinesDoktors
der Naturwissenschaften genehmigte Dissertation
vorgelegtvon
Diplom-Informatiker
MichaelUmmels
ausKöln
Berichter: UniversitätsprofessorDr.ErichGrädel
UniversitätsprofessorDr.WolfgangThomas
AssistantProfessorDr.MarcinJurdziński
Tagder mündlichenPrüfung:27.Januar2010
DieseDissertation istaufdenInternetseitenderHochschulbibliothek onlineverfügbar.Preface
The lastdecades haveseenan immenseamount ofresearch onthealgo-
rithmic content of game theory. On the one hand, a new subject called
algorithmic gametheoryhasemergedthatisconcernedwiththestudyofthe
algorithmictheory of finite gameswith multipleplayers.Onthe other hand,
infiniteand, inparticular,stochastictwo-playerzero-sum games havebecome
an importanttool fortheverification of opensystems,which interactwith
theirenvironment.
Theaim ofthiswork istobringtogetheralgorithmic gametheorywith
the gamesthatareused inverificationbyextendingthealgorithmicthe-
oryofstochastictwo-playerzero-sumgamestoincorporatemultipleplay-
ers, whose objectives are not necessarily conflicting. In particular, this
workcontainsacomprehensivestudy ofthecomplexity ofthe mostpromi-
nentsolutionconceptsthatareapplicable inthissetting, namelyNashand
subgame-perfectequilibria.
ThisbookistheresultofmydoctoralstudiesatRWTHAachenUniver-
sity. Iam indebtedto myprimarysupervisorErichGrädel for giving methe
opportunitytopursuethesestudies,forintroducingmetothescientificcom-
munityandforgivingmeadvicejustwhenIneededit.Iamequallygrateful
to mysecondarysupervisorWolfgangThomas for hisconstantsupportand
encouragement.
MarcinJurdzińskidid not hesitatetoactasanexternalreviewer forthis
thesis.Ithank him not only for hiscarefulreadingand numerousremarks,
butalso for givingan inspiringtalk onbranchingvectoradditionsystems,
which indirectly ledtotheresolution ofaproblemthatwas left open inthe
originalversion ofthisthesis.
Asubstantialpart ofthisbook isbased on jointworkwithDominikWojt-
czak. I am indebted to him for our numerous illuminating discussions,
for his insightsand ideas,and—lastbut not least—for hosting me inEdin-
burgh,AmsterdamandOxford.
5Amongthevariousotherpeoplewhocontributedtothiswork,Iwould
liketothank inparticularŁukaszKaiser for manyenlighteningdiscussions
and fordiscoveringProposition3.18.Specialthanksalso gotoFlorianHorn
formanyinterestingdiscussions,toJánosFleschforpointingoutProposi-
tion3.13,andtoPeterBroMiltersenfordrawingmyattentiontoCorollary4.4.
Moreover,Iam gratefultoHugoGimbertandEilonSolan foranswering my
questionsandtoRohitChadha,TobiasGanzow,JörgOlschewskiandEdeline
Wong fortheircomments onpreliminarydrafts ofthiswork.
Finally,Iwould liketothankSamRoss-Gower fordesigningthecover of
A
thisbook,andDonaldKnuthandLeslieLamport forcreating(L)T X.
E
Paris,November2010
6Contents
1 Introduction • 15
1.1 Gamesandequilibria • 15
1.2 Thestochasticdiningphilosophersproblem • 21
1.3 Contributions • 25
1.4 Relatedwork • 27
1.5 Outline • 28
2 StochasticGames • 31
2.1 Arenasand objectives • 31
2.2 Strategiesandstrategyprofiles • 37
2.3 Subarenasandendcomponents • 41
2.4 Values,determinacyand optimalstrategies • 42
2.5 Algorithmicproblems • 47
2.6 Existence ofresidually optimalstrategies • 51
3 Equilibria • 55
3.1 Definitionsandbasicproperties • 55
3.2 Existence ofNashequilibria • 59
3.3 Existence ofsubgame-perfectequilibria • 64
3.4 Computingequilibria • 69
3.5 Decisionproblems • 73
4 Complexity ofEquilibria • 77
4.1 Positionalequilibria • 77
4.2 Stationaryequilibria • 82
4.3 Pureandrandomisedequilibria • 88
4.4 Finite-stateequilibria • 96
4.5 Summary ofresults • 98
7Contents
5 DecidableFragments • 99
5.1 Thestrictlyqualitative fragment • 99
5.2 Thepositive-one fragment • 113
5.3 Thequalitative fragment fordeterministic games • 122
5.4 Summary ofresults • 133
6 Conclusion • 135
6.1 Summaryand openproblems • 135
6.2 Perspectives • 138
A Preliminaries • 141
A.1 Probabilitytheory • 141
A.2 Computationalcomplexity • 144
B MarkovChainsandMarkovDecisionProcesses • 149
B.1 Markovchains • 149
B.2 Markovdecisionprocesses • 152
Bibliography • 157
Notation • 169
Index • 171
8List ofFigures
1.1 Matchingpenniesasa game inextensive form • 18
1.2 Diningphilosophers • 22
1.3 Processes forthestochasticdiningphilosophersproblem • 23
1.4 Thestochasticdiningphilosophers gamewithtwo
philosophers • 24
2.1 A hierarchy ofprefix-independent objectives • 36
2.2 Anexample ofatwo-playerSSMG • 38
2.3 AnMDPwith no optimalstrategy • 44
2.4 AnotherMDPwith no optimalstrategy • 44
3.1 Atwo-playerreachability gamewithan irrationalNash
equilibrium • 58
3.2 Atwo-player gamewithapair of optimalstrategiesthatcannot
beextendedtoaNashequilibrium • 62
3.3 AnSSMGwith nostationaryNashequilibrium • 63
3.4 Atwo-playerSSMGwith nopositionalNashequilibrium • 64
3.5 ABüchiSMGwith nosubgame-perfectequilibrium • 68
3.6 AnSSMGthat hasastationarysubgame-perfectequilibrium
whereplayer0winsalmostsurelybut nopureNashequilibrium
whereplayer0winswithpositiveprobability • 75
3.7 ThedifferentdecisionproblemsrelatedtoNashand
subgame-perfectequilibria • 76
4.1 ReducingSATtoPosNE,StatNE,PosSPEandStatSPE • 79
4.2 ReducingSqrtSumtoStatNEandStatSPE • 85
4.3 Simulatingatwo-counter machine • 90
4.4 Reducing fromthe haltingproblem • 97
9List ofFigures
5.1 ReducingSATtoStrQualNEforgameswithStreettobjectives • 104
5.2 ReducingSATtodecidingtheexistence ofaplaywinning forall
players inadeterministicRabin game • 108
5.3 A gamewith onlytwopurebut infinitely manyrandomisedNash
equilibria • 124
5.4 ReducingSATtoQualNE fordeterministicco-Büchi games • 129
A.1 A hierarchy ofcomplexityclasses • 147
10