dr. Peter van Emde Boas
hours:
Monday 13.15 -- 15.--
Zaal P017
Thursday 13.15 -- 15.--
Zaal A303
THE EXCERCISES
PAGE NOW HAS BEEN OPENED !
Scheme of classes:
Week Monday Thursday
37
Sep 09 General Introduction
Sep 12 Games and Computation
38
Sep 16 Tiling Game reduction
Sep 19 Endgame analysis in PSPACE
39
Sep 23 Characterization of PSPACE Sep 26
PSPACE, Games and Parallellism
40
Sep 30 Alternation Model
Oct 03 Direct reductions PSPACE to games
41
Oct 07 The pebbling Game
Oct 10 Lowerbound Pebbling Game - Hopcroft Paul Valiant
42
Oct 14 No Class: Schoolweek OZSL
Oct 17 No Class: Schoolweek OZSL
43
Oct 21 (No class: midterm exams) Oct
24 (No class: midterm exams)
44
Oct 28 Hopcroft Paul Valiant
Oct 31 Gilbert Tarjan & Lengauer
45
Nov 04 (No class: OOPSLA, Seattle) Nov 07 (No class: OOPSLA,
Seattle)
46
Nov 11 (No class: OOPSLA, Seattle)
Nov 14 Interactive models
47
Nov 18 Shamir Theorem IP = PSPACE Nov 21
Nisan & Ronen: Agents on the Internet
48
Nov 25 (Exam weeks)
Nov 28 (Exam weeks)
49
Dec 02 (Exam weeks)
Dec 05 (Exam weeks)
50
Dec 09 (Exam weeks)
Dec 12 (Exam weeks)
This course belongs to the by
now obsolete 4 year curriculum of the computer scxience program.
It is presented this year for
the last time as a service to remaining students from this program and
other interested students who
can select this course as a choice item in their program.
The course must be completed
before the end of this academic year, I.E. no later than August 31 2003.
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.
Fact is that concepts from game
theory have been used in
Computer Science already much
longer. Several of the models
used in theoretical Computer
Science for analysing problems with regards to
effectivity and efficiency can
be quite reasonably be described and analysed
in terms of games.
This link will be illustrated
in this course on the basis of a number
of models which originally date
from the 70-ies and 80-ies.
The main target is to illustrate
that games represent a computational
model in the same way nondeterministic
computations do.
Interesting in this regards is
to investigate which computational
models seem to be unrelated
to games and which game models
seem not to relate well with
computational models.
Examples of models connecting games and computation theory are:
The theory of Traub and Wozniakowski
on the solution of numerical
problems.
Deciding Graph properties from
Adjacency Matrices ("Twenty Questions");
theory of Evasiveness.
The pebling game, used as a model
both for register allocation
and in the context of machine
model theory.
The Tiling game and its use in Reduction Theory
The Alternating Machine model
and its connection to
logic description languages
and games.
Interactive protocols for convincing
opponents about the presence of
information, without leaking
more information than
necessary: (Interactive proofs,
Arthur Merlin games, Zero Knowledge
proofs, ...)
The design of mechanisms for
tweaking agents on the internet to behave
in a truthful manner.
Except for the latter problem
the game theory involved deals combinatorial
games rather than the more stochasitic
real valued games studied in
Econmical Sciences. The game
theory involved therefore is rather
elementary.
Sheets available: (for the larger part unchanged from the previous edition of this course)
Part 1:
Topics: Introduction, Games and Tilings:
Available in Powerpoint98
format and pdf
format
Part 2:
Topics: Endgame Analysis, PSPACE and Parallellism:
Available in Powerpoint98
format and pdf format
Part 3:
Topics: PSPACE, Alternation, Games:
Available in Powerpoint98
format and pdf
format
Part 4:
Topics: the Pebble Game:
Available in Powerpoint98 Formatand
pdf
format
Part 5:
Topics: Diagonalization and Compression: (version 2000)
Available in Powerpoint98
format and pdf
format
Part 6:
Topics: Interactive Proof Systems:
Available in Powerpoint98 formatand
pdf
format
Part 7: Controling
Selfish Agents on the Internet:
Available in Powerpoint00 format and pdf
format
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
Literature: (will be extended during the course).
Game Theory.
Ken Binmore, Fun and Games,
Houghton Mifflin Company, 1992;
this is the textbook used in
the course Intelligent
Database - Game Theory
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.
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.
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 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., Mathe,atical 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.
Unrelated but still about Games and 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
.
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.
Related courses:
prof. dr. J.F.A.K. van Benthem: Caput Logic and Languages: Logic and Games
dr. Peter van Emde Boas: Intelligent Databases (3rd trimester): game theory
dr. Peter van Emde Boas: Complexity and Computation Theory (2nd trimester): complexity theory