stochastic-games-tutorial-abstract

Stochastic Games: A TutorialMarcin Jurdzinski´Department of Computer ScienceUniversity of Warwick, UKGame theory [1]isaformalismforthestudyofcompetitiveinteractionintherich spectrum of relationships ranging between conflict and cooperation. Origi-nallyconceivedasamathematicalfoundationofeconomics, itproveditsrobust-ness by providing new techniques and insights in logic and set theory [15, 13],evolutionary and population biology [22], auction design and implementation,the design and study of the internet [19], analysis of cold war strategies, etc.Dynamic games are used to model competitive processes evolving over time.Stochastic transitionsareusedforabstractioninmodellingortoformalizeinher-entuncertainty,leadingtoquantitativestatisticalanalysis. Stochasticgames aredynamic games with stochastic transitions. They enjoy rich and mature math-ematical theory [11, 23] and a wide range of applications including economics,cell, populationandevolutionarybiology[26], queueingtheoryandperformanceevaluation, and quantitative temporal model checking [17, 8].In this tutorial we explore the spectrum of competitive dynamic behaviouralmodels ranging from Markov chains, to transition systems, to Markov deci-sion processes [20], to 2-player and multi-player perfect-information and generalstochastic games [11]. We also consider the spectrum of qualitative and quan-titative objectives for the players contained in the class of Borel-measurablefunctions [16], and we survey ...