CMPE 248: Games in Design and Control
Instructor: Luca de Alfaro
- Place: Social Sciences 2, Room 171
- Time: 2-3:45pm Tuesdays and Thursdays.
- Office Hours: 11:13-12:30 Wednesdays
Discussion group: http://groups-beta.google.com/group/ucsc-cmpe-248-winter-2007 (request membership, and I will approve it).
General Information
- Intended audience: CS/CE/EE/ISM graduate students, and interested (and sufficiently prepared) undergraduate students.
Textbook: Notes and reading material will be distributed in class. You can also refer to the book Filar, Vrieze: Competitive Markov Decision Processes, Springer-Verlag, 1996.
Reading Material
Lectures
Lecture Notes (draft!)
Lecture 7, Jan 25: on interface theories. You can look at Game Models for Open Systems to get the gist of the discussion, as well as this introduction to the tool Ticc.
Lecture 8: Jan 30, with a summary of the recursive algorithm for parity games.
Lecture 9: Feb 1, with a summary of concurrent reachability games.
Lectures 15 and 16: Feb 22 and 27 Games with Secure Equlibria, by Chatterjee, Henzinger, Majumdar.
Other assigned readings
You are strongly encouraged to read these portions of papers:
For the recursive algorithm for parity games, you can read A Deterministic Subexponential Algorithm for Solving Parity Games, up to section 3 included.
For quantitative reachability and safety games, you can read Quantitative solution of omega-regular games up to page 11 included.
Other readings
Here is an existence proof of memoryless strategies for concurrent reachability games. The paper came out of my teaching this class last year! The proof is somewhat technical, and reading this paper is optional. I advise you however to read the introduction.
Homeworks
Homework 3, due Thu Feb 8
