thmod99.sch

Introduction to Game Theory
Course Fall 2008

dr. Peter van Emde Boas

hours:
Monday 11.-- -- 12.45 Zaal P 018

Thursday 13.-- -- 14.45 Zaal P 016

Beware ! as of Sep 01 2007 The UvA has adopted the policy that classes start at the full hour !

THE EXCERCISES PAGE HAS NOW BEEN OPENED.

Scheme of classes (with tentative subjects):

Week   Monday                                                                              Thursday

36        Sep 01 Introduction Game Models    Sep 04    Abstract Game models
37        Sep 08 Concrete Game Models       Sep 11     Strategic Games; problems with backward Induction
38        Sep 15 Motivating Example Games        Sep 18 No Class - Funeral
39        Sep 22   Probabilistic Moves in games   Sep 25     Analysis of games with probabilstic moves
40 Sep 29 Utility Theory    Oct 02 No Class - diploma ceremony MSE
41        Oct 06   Rationality principles and Utility Theory Oct 09     Dominated strategies; Kuhhandel
42        Oct 13   Nash Bargaining Theory   Oct 16    The Ultimatum Game
43        Oct 20 No Class (exam week)    Oct 23 No Class (exam week)

44        Oct 27   Von Neumann Min-Max Theorem       Oct 30 Von Neumann Min-Max Theorem
45        Nov 03 Election Special          Nov 06 No Class (phd. defence F. Terpstra)
46        Nov 10 On Equilibria          Nov 13      Correlated equilibria; Iterated games
47        Nov 17   Iterated Games; games played by Automata    Nov 20 Evolutionary models
48        Nov 24   Evolutionary Models          Nov 27 No Class ("oratie" P. Grunwald Leiden)
49 Dec 01 Cheating Husbands after Moses, Halpern ea.     Dec 04    Mechanisms on the Internet after Nissan & Ronen
50 Dec 08 No Class (Parallel worlds Congress)                 Dec 11 No Class (Symposium TH Koornwinder)
51        Dec 15 No Class (exam week)                                       Dec 18    No Class (exam week)

This course is offered in the master programs Logic, Grid Computing, Artificial Intelligence
in all cases as an elective course. The course is open as a choice subject for
students of other programs.

The course is a resurrection from a course from the old program: Intelligent Databases ,
both offered for the last time in the year 2002 - 2003. During the years 2003-06 this course was
incorporated into a course Game Theory for Information Sciences, but this merger has been undone.

During the year 2008 - 2009 a number of other game related courses will be offered in the Master of Logic Program:

Semester 2:

U. Endriss: Computational Social Choice

K.R. Apt: Cooperative games

Course Contents:

Game theory originates from Economical Sciences; it
treates theories about strategic interaction and
related rationality concepts. The subject is currently attracting researchers from
Computer Science and Technology, particularly involving
themes about controling behavior of unrelyable agents on the
Internet.

The course provides an introduction to some fundamental models and concepts
in Classical game theory: game models, probabilistic games, utility functions,
and equilibria.

Sheets available: (Updated or from the previous course Introduction Game Theory)

Part 1: Topics: Introduction, Games and Tilings:
Available in Powerpoint00 format and pdf format

Part 2: Topics: Introductionary Examples
Available in Powerpoint00 format and pdf format

Part 3: Topics: Games with chance moves
Available in Powerpoint00 format and pdf format

Part 4:      Topics: Utility Theory
                   with an extension into the axiomatic theory of Utility
                   based on material by Wakker and Meyerson listed below.
                Available in Powerpoint00 format and pdf format

Part 5: Topics: Domination of strategies, with an application to Kuhhandel
Available in Powerpoint00 format and pdf format

Part 6: Topics: Cooperative games: Nash Bargaining Theory
Available in Powerpoint00 format and pdf format

Extra: Topics: Chaotic Elections (after Donald G. Saari):
Available in Powerpoint00 format and pdf format

Part 7: Topics: Mixed Strategies and von Neuman Min-Max Theorem
Available in Powerpoint00 format and pdf format

Part 8: Topics: More on equilibria and correlated equilibria
Most recent version Available in Powerpoint00 format and pdf format

Part 9: Topics: Iterated games
Available in Powerpoint00 format and pdf format

Part 10: Topics: Adaptive strategies
Available in Powerpoint00 format and pdf format

Part 11: Topics: Mechanism Design after Nissan & Ronen
Available in Powerpoint00 format and pdf form

Part 12: Topics: Halpern, Moses & Dolev on the Cheating Husbands problem
Version Available in Powerpoint00 format and pdf form

Sheets available: (from the previous course Game Theory for Information Sciences;

Part 1: Topics: Introduction, Games and Tilings:
Updated version Available in Powerpoint00 format and pdf format

Part 2: Topics: Endgame Analysis, PSPACE and Parallellism:
Updated version Available in Powerpoint00 format and pdf format

Part 3: Topics: PSPACE, Alternation, Games:
Updated version Available in Powerpoint00 format and pdf format

Part 4: Topics: Introductionary Examples
Updated version Available in Powerpoint00 format and pdf format

Part 5: Topics: Games with chance moves
Updated version Available in Powerpoint00 format and pdf format

Part 6:      Topics: Utility Theory
                   with an extension into the axiomatic theory of Utility
                   based on material by Wakker and Meyerson listed below.
                Updated version Available in Powerpoint00 format and pdf format

Extra: Topics: Chaotic Elections (after Donald G. Saari):
Available in Powerpoint00 format and pdf format

Part 7: Topics: Domination of strategies
Updated version Available in Powerpoint00 format and pdf format

Part 8: Topics: Cooperative games:
Most recent version Available in Powerpoint00 format and pdf format

Part 9: Topics: Mixed Strategies and von Neuman Min-Max Theorem
Most recent version Available in Powerpoint00 format and pdf format

Part 10: Topics: More on equilibria and correlated equilibria
Most recent version Available in Powerpoint00 format and pdf format

Part 11: Topics: Mechanism Design after Nissan & Ronen
Old version Available in Powerpoint00 format and pdf form

Part 12: Topics: the Pebble Game:
Last version Available in Powerpoint00 Format and pdf format

Part 13: Topics: Diagonalization and Compression:
Updated and Extended version Available in Powerpoint00 format and pdf format

Sheets available: (from the previous course Theoretical Models)

Part 1: Topics: Introduction, Games and Tilings:
Available in Powerpoint00 format and pdf format

Part 2: Topics: Endgame Analysis, PSPACE and Parallellism:
Available in Powerpoint00 format and pdf format

Part 3: Topics: PSPACE, Alternation, Games:
Available in Powerpoint00 format and pdf format

Part 4: Topics: the Pebble Game:
Available in Powerpoint00 Format and pdf format

Part 5: Topics: Diagonalization and Compression: (version 2000)
Available in Powerpoint00 format and pdf format

Part 6: Topics: Interactive Proof Systems:
Available in Powerpoint00 format and pdf format

Part 7: Controling Selfish Agents on the Internet:
Available in Powerpoint00 format and pdf format

Sheets available: (from the last course Intelligent Databases)

Chapter 0: Topics: Introduction.
Available in Powerpoint98 format and pdf format

Chapter 1: Topics: Basic Concepts
Available in Powerpoint98 format and pdf format:

Chapter 2: Topics: Games with chance moves
Available in Powerpoint98 format and pdf format

Chapter 3:      Topics: Utility Theory
                        with an extension into the axiomatic theory of Utility
                        based on material by Wakker and Meyerson listed below.
                Available in Powerpoint98 format and pdf format

Chapter 4: Topics: Domination of strategies
Available in Powerpoint98 format and pdf format

Chapter 5: Topics: Cooperative games:
Available in Powerpoint98 format and pdf format

Chapter 6: Topics: Mixed Strategies
Available in Powerpoint98 format and pdf format

Chapter 7: Topics: On Equilibria: cheap talk and correlated equilibria
Available in Powerpoint98 format and pdf format

Contents of previous courses are almost identical, but beware for obsolete URL references !

Aditional Material related to games available as slides.

Extra:     Topics: The Game of Chaos: Presentation at the 34 Dutch Mathematics Conference April 1999
               Nov 19-20 1999. Available in Powerpoint98 Format and pdf format
                 See also: P. van Emde Boas & E.H. van Emde Boas, The Game of Chaos, as included in the
                bibliography below.

Extra: Topics: Games in the Classroom:
Available in Powerpoint98 format and pdf format

Extra:      Topics: The connection between Games and Computer Science,
                Talks prepared for a trip to China, April 2000:
                Available in Powerpoint98 format and pdf format

Extra:      Topics: The Games of Computer Science,
                Talk at TU Delft, Feb 23 2001:
                Available in Powerpoint98 format and pdf format

Extra:      Topics: Playing Savage:
                Available in Powerpoint98 format and pdf format
           Manuscript available in Postscript

Extra:      Topics: Imperfect Information Games, looking for the right model.
                 Talk at Algemeen Wiskunde Colloquium, Feb 27 2002:
                  Available in Powerpoint2000 format

Extra:      Topics: Imperfect Information Games, what makes them hard to decide.
                 Talk at Amsterdam Aachen Exchange Feb 15, 2002:
                  Available in Powerpoint2000 format

Extra: Topics: IF Logic; slides of the presentation of Merlijn Sevenster on Nov 29 2004
Available in pdf format

Extra:      Topics: Games in Computation and Complexity Theory,
                Tutorials at the workshop Games and Logic Kazimierz Dolny (PL), Sep 25-26 2006
                Available in Powerpoint2000 format and pdf format

Literature: (This is a joint list for both my game related courses).

Game Theory.

Ken Binmore, Playing for Real, a text on game theory, Oxford University Press, 2007;
this is a textbook which is used for this course

Elwyn R. Berlekamp, John H. Conway & Richard K. Guy,
Winning Ways (Vol 1 and Vol. 2), Academic Press, 1982.

John H. Conway, On Numbers and Games, Academic Press 1976.

the above two references develop the mathematics of combinatorial games in great depth.

V.W. Gijlswijk, G.A.P. Kindervater, G.J. van Tubergen & J.J.O.O Wiegerinck,
Computer Analysis of E. de Bono's L-Game, Rep. Math, Inst. UvA 76-18
(an early computerized backward analysis of a non-trivial game; also an early
student project in our department...)

M.J. Osborne & A. Rubinstein, A Course in Game Theory, MIT Press 1994.

Roger B. Myerson, Game Theory; Analysis of Conflict, Harvard University Press 1991.
see chapter 1 for the axiomatic treatement of Utility Theory.

Alexander Mehlman, The Game's Afoot!, Game Theory in Mythand Paradox,
Amer. Math. Soc. Student Math. Library 5, 2000
Introduction, with many examples drawn from the literature and
mythology; however, in final sections rather difficult.

Steven J. Brams, Superior Beings, Springer Verlag 1983;
Game theory applied to Theology.

Boudewijn de Bruin, Explaining Games, On the Logic of Game Theoretic Explanations,
Ph.D. Thesis ILLC UvA 20041207, ILLC Dissertation Series DS-2004-03
An in depth study of the connections between Backward Induction, Elimination of dominated strategies,
and Common Knowledge of Rationality.

K.R. Apt, "Order Independence and Rationalizability'' ,
Proc. of the 10th Conference on Theoretical Aspects of Rationality and Knowledge (TARK X),
pp. 22-38, 2005.

K.R. Apt, "The Many Faces of Rationalizability''.
Manuscript, August 2006.

Yoram Moses, Danny Dolev and Joseph Y. Halpern,
Cheating Husbands and other stories; a case study on knowledge, action, and communication,
Distributed Computing (1986) vol. 1 167-176.
Preprint in procs PODC 4, 1985.
An in depth study explaining the importance of synchronization for solving the muddy children problem.

Computation Theory.

John E. Hopcroft & Jeffrey D. Ullman, Intorduction to Automata Theory,
Languages and Computation, Addison Wesley, 1979.

David Harel, Algorithmics; the Spirit of Computing, (second Edition),
Addison Wesley 1992.

Thomas A. Sudkamp, Languages and Machines; An Introduction to the
Theory of Computer Science, (second Edition), Addison Wesley 1997.
a formerly used textbook for the course Automata and Complexity Theory

Harry R. Lewis & Christos H. Papadimitriou,
Elements of the Theory of Computation, Prentice Hall 1981.

Christos H. Papadimitriou, Computational Complexity,
Addison Wesley 1995.
Chapter 19 covers many of the computation theory subjects dealt with in this course!

Cees Slot & Peter van Emde Boas, The Problem of Space Invariance for
Sequential Machines, Inf. and Comp. 77 (1988) 93--122.

Peter van Emde Boas, Space Measures for Storage Modification Machines,
Inf. Proc. Letters 30 (1989) 103--110.

Peter van Emde Boas, Machine Models and Simulations, in
J. van Leeuwen, Handbook of Theoretical Computer Science vol A,
Algorithms and Complexity, Elsevier, 1990, pp 3--66;
preprint: ITLC-CT-89-02.

The last three papers concern the Invariance Thesis.

The pebling game, used as a model both for register allocation
and in the context of machine model theory.

J.E. Hopcroft, W. Paul & L. Valiant, On Time versus Space,
J. Assoc. Comput. Mach., 24 (1977) 332--337.

A. Lingas, A PSPACE Complete Problem related to a Pebble Game,
G. Ausiello & C Böhm eds., Proc. ICALP'78,
Springer LNCS 62, 1978, pp. 300--321.

P. van Emde Boas & Jan Van Leeuwen, Move Rules and
Trade-Offs in the Pebble Game, in K. Weihrauch ed.,
Proc. 4th GI Theoretical Computer Science Conference,
Springer LNCS 67 1979, pp. 101--112.

John R. Gilbert, Thomas Lengauer & Robert E. Tarjan,
The Pebbling Problem is Complete in Polynomial Space,
SIAM J. Comput. 9 (1980) 513--524.

Hiroaki Tohyama & Akeo Adachi,
Complexity of path discovery game problems,
Theor. Comp. Sci.. 237, 2000, 381--406.
another PSPACE-hard solitaire game.

Tiling Game and its use in Reduction Theory

Bogdan S. Chlebus, Domino-Tiling Games, J. Comput. Syst. Sci. 32
(1986), 374--392.

Martin. P.W. Savelsberg & Peter van Emde Boas, BOUNDED TILING,
an alternative to SATISFIABILITY?, in G.Wechsung ed., proc. 2nd
Frege Memorial Conference, Schwerin, Sep 1984, Akademie Verlag,
Mathematische Forschung vol. 20, 1984, pp. 401--407.
preprint: rep. CWI-OS-R8405.

Peter van Emde Boas, The Convenience of Tilings, in: Andrea Sorbi, ed.,
Complexity, Logic and Recursion Theory, lecture notes in pure and
applied mathetaics vol 187, 1997, pp. 331--363. (for ps. version of preprint ).
The sheets of this lecture are available at sheets in postscript . However
beware: on behalf of its origin as a (by now obsolete MacWrite document)
the Postscript pages are sorted in reverse order.

Peter van Emde Boas, Is elf plus één twaalf?; over rekenen en puzzelen.
Explanation of the construction of the tiling puzzle demonstration
model for precollege students (in Dutch). Text available in Postscript .
The corresponding figures are available in Postscript also: pict1pict2pict3pict4 .

David Harel, Recurring Dominos: making the Highly Undecidable
Highly Understandable, Ann. Discrete Math. 24 (1985) 51--72.

David Harel, Dynamic Logic, in D. Gabbay & F. Guenthner (eds.)
Handbook of PhilosophicalLogic, Vol II, D. Reidel 1984, pp. 497--604.
Background information on Dynamic Logic for the reduction to
PDL-Satisfiability from the two person tiling game as invented by
Chlebus.

The Alternating Machine model and its connection to
logic description languages and games.

A.K. Chandra, D. Kozen & L.J. Stockmeyer, Alternation,
J.Assoc. Comput. Mach. 28 (1981) 114--133.

Christos H. Papadimitriou, Computational Complexity,
Addison Wesley 1995. See chapter 19 in particular.

L.J. Stockmeyer & A.R. Meyer, Word problems requiring exponential time,
Proc STOC 5 (1973), pp 1--9.
An important early paper and the source of the QBF problem.

T.J. Schäfer, Complexity of some two-person perfect-information games,
J.Comput. Syst. Science, 16 (1978) 185--225.
The first PSPACE complete game: Geography.

D. Lichtenstein & M. Sipser, GO is polynomial-space hard,
J. Assoc. Comput. Mach, 27 (1980) 393--401.

S. Even & R.E. Tarjan, A combinatorial game which is complete for polynomial
space, J. Assoc. Comput. Mach, 23 (1976) 710--719.

S. Reisch, HEX ist PSPACE-volständig, Acta Informatica 15 (1981) 167--191.

A.S. Fraenkel, M.R. Garey, D.S. Johnson, T. Schäfer & Y. Yesha,
The complexity of checkers on an N X N board - preliminary report,
Proc IEEE FOCS 19 (1978) pp. 55--64.

A.S. Fraenkel & D. Lichtenstein, Computing a perfect strategy for n x n chess
requires time exponential in n, J. Combin. Theory series A 31 (1981) 119--213.

G.W. Flake & E.B. Baum, Rush Hour is PSPACE-complete, or "Why you should generously tip
parking lot attendants", Theoretical Computer Science, 270 (2002) 895--911.
A very simple combinatorial solitaire game which is PSPACE-complete. For a yet simpler version
see this note by John Tromp.

Erik D. Demaine, Playing Games with Algorithms: Algorithmic Combinatorial Game Theory ,
MFCS 2001, Springel LNCS 2136, pp. 18-32 .
Much more information is available from his impressive website .

The above five papers involve games played by real people.

P. van Emde Boas, The Second Machine Class 2, an Encyclopedic View on the
Parallel Computation Thesis. in: H. Rasiowa ed., Mathematical Problems in
Computation Theory, Banach Center Publications, vol 20, PWN Warsaw 1988,
pp. 235--256.
An older version of sections 3 and 4 in my Handbook Chapter.
Slides about this subject are available in Postscript
(but again in reverse order...).

Robert A. Stegwee, Leen Torenvliet & Peter van Emde Boas,
The Power of your Editor, Rep. IBM RJ 4711 (50179) 5/21/85;
also: Report FVI-UvA-85-03.
Sheets have been placed on the Web; once more in reverse order Postscript

Interactive Proof systems and other models of interaction and/or randomized computation

Carsten Lund, Lance Fortnow & Howard Karloff, Algebraic Methods for Interactive Proof Systems,
J. ACM. 39 (1992) 859-868.

Adi Shamir, IP = PSPACE, J.ACM. 93 (1992) 869-877.

A. Shen, IP= PSPACE: Simplified Proof, J.ACM. 93 (1992) 878-880.

L. Babai, E-mail and the unexpected power of interaction, Proc. IEEE Symp. Structure in
Complexity Theory 5, Barcelona, July 08-11 1990, pp. 30--44.

Shafi Goldwasser, Silvio Micali & Charles Rackoff, The Knowledge Complexity of
Interactive Proof Systems, SIAM, J. Comput. 18 (1989), 186-208.

Christos H. Papadimitriou, Games against Nature, Proc. IEEE FOCS 1983, pp. 446-450

L. Babai &S. Moran, Arthur-Merlin Games: a Randomized Proof System and a Hierarchy
of Complexity Classes, J. Comput. Syst. Sci. 36 (1988) 254-276.

The design of mechanisms for tweaking agents on the internet to behave
in a truthful manner.

Noam Nissan & Amir Ronen, Algorithmic Mechanism Design,
proc. ACM STOC 31 (1999).

Noam Nisan, Algorithms for Selfish Agents,
in C. Meinel & S. Tison, eds., Proc. STACS'99,
Springer LNCS 1563, 1999, pp. 1--15.

Amir Ronen, Algorithms for Rational Agents,
proc. SOFSEM 2000, Springer LNCS 1963, 56--70.

Evasiveness problem ("twenty questions")

M.R. Best, P. van Emde Boas and H.W. Lenstra, jr.,
A Sharpened version of the Aandera-Rosenberg Conjecture,
rep. MC-ZW-30-74, October 1974.

Ronald L. Rivest & Jean Vuillemin,
On recognizing Graph properties from Adjacency Matrices,
Theor. Comp. Sci. 3 (1976) 371-384.

J.Kahn, M. Saks, D. Sturtevant, A topological Approach to Evasiveness,
Combinatorica 4 (1984) 297-306.

N. Illies, A counterexample to the Generalized Aanderaa-Rosenberg Conjecture,
Inf. Proc. Letters, 7 (1978) 154-155.

L. Lovasz, Lecture notes on Evasive Graph properties, notes taken by Neal Young around fall 1990
at Princeton University.

A. Chakrabarti, S. Khot & Y. Shi, Evasiveness of subgraph containment and related properties,
SIAM J. of Computing 31(3) (2002) 866-875.

V. Welker, Constructions preserving evaisiveness and collapsability,
Discrete Math. 207 (1999) 243-255.

A. Aggarwal, D. Coppersmith & D. Kleitman, A generalized model for understanding Evasiveness,
Inf. proc. letters 30 (1989) 205-208.

F.H. Lutz, Some results Related to the Evasiveness Conjecture,
J. Comb. theory B 81 (2001) 110-124.

Unrelated but still about Games and/or Computer Science.

Peter van Emde Boas, Games in the Classroom,
position paper at OOPSLA'99 Workshop #2, Quest for Effective Classroom Examples.
Postscript version Available .

H. Jaap van den Herik, Jos W.H.M. Uiterwijk & Jack van Rijswijck,
Games solved: Now and in the future,
Artificial Intelligence 134 (2002), 277-311.
A survey on the state of the art in real life game analysis by computers;
the entire issue of Artificial Intelligence is dedicated to this problem area in AI.

Donald G. Saari, Chaotic Elections! A mathematical Looks at Voting,
AMS 2001.
A thorough analysis on how voting systems fail to implement democracy.
Mandatory reading material for voters.

Course Evaluation:

Except for specific student contributions (with previous arrangements
with the teacher) the students will be graded on their solutions of
homework exercises which will be made public on the website gradually
during the course. Answers should be returned within the deadline as listed with
the exercise, only on paper. Even when the answers are prepared electronically
the solution must be submitted on paper.