CMPE 248: Games in Design and Control

General Information

Synopsis.
Intended audience: CS/CE/EE/ISM graduate students, and interested (and sufficiently prepared) undergraduate students.
Prerequisites
Textbook: Osborne and Rubinstein: A Course in Game Theory. The book should be available at the Bookstore. We will follow the book, and supplement it with notes that will be provided by the instructor.
Homework Policy

Lecture 1, on Nash equilibria and examples, including also the first problem, due April 7, 2008 (see notes below for the first problem).
Lecture 2, on zero-sum games.
Lecture 3, on Sperner's Lemma, Brower's fixpoint theorem, and Kakutani's fixpoint theorem.
Lecture 4, on Mixed move equilibria, and existence of Nash equilibria.
Lecture 5, on the value of 0-sum games, and on evolutionary stable equilibria.
Lecture 7, on reachability, safety, Buchi, and coBuchi games.
Lecture 8, introducing concurrent games, randomized strategies, and (lack of) optimal strategies.
Lecture 9, on concurrent reachability games and value iteration.
Lecture 10, on the proof of the solution formula for concurrent reachability games.
Lecture 11, on the proof of the solution formula for concurrent safety games, and on reachability and safety in Markov decision processes.
Lecture 12, on mechanism design.
Lecture 13, on CVG mechanism design.

Paper on games to manage resources (lock, mutexes) in embedded software
Paper on games to synthesize protocol converters
Paper on games as specification mechanism for systems
Concurrent Reachability Games. I strongly advise you to read up to section 3.1 included.
Quantitative Omega-Regular Games. I strongly advise you to read up to section 3 included.
Algorithms for Simple Stochastic Games, by A. Condon. Note that the reachability games are assumed to be such that all strategy pairs are proper, i.e., the union of the reachability set and the sink is reached with probability 1 under any policy. I advise to read all this paper.
Strategy Improvement for Concurrent Reachability games. Note that this paper lifts the assumption that all strategy pairs are proper. The paper is a recommended read.