#acl All:read Alamelu:read,write

= CMPE 248: Games in Design and Control =
 * Instructor: [http://www.soe.ucsc.edu/~luca Luca de Alfaro]
 * Place: Crown Classroom 203
 * Time: 5-6:45pm MW
 * Office Hours: Fridays, 11-12, or by appointment (email me).
== General Information ==
 * [:CMPE 248 Spring 2008/Synopsis:Synopsis].
 * Intended audience: CS/CE/EE/ISM graduate students, and interested (and sufficiently prepared) undergraduate students.
 * [:CMPE 248 Spring 2008/Prerequisites: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"]

== Reading Material ==
=== Lectures ===
 * [attachment:lecture1.pdf Lecture 1], on Nash equilibria and examples, including also the first problem, due April 7, 2008 (see notes below for the first problem).
 * [attachment:lecture2.pdf Lecture 2], on zero-sum games.
 * [attachment:lecture3.pdf Lecture 3], on Sperner's Lemma, Brower's fixpoint theorem, and Kakutani's fixpoint theorem.
 * [attachment:lecture4.pdf Lecture 4], on Mixed move equilibria, and existence of Nash equilibria.
 * [attachment:lecture5.pdf Lecture 5], on the value of 0-sum games, and on evolutionary stable equilibria.

 * [attachment:lecture7.pdf Lecture 7], on reachability, safety, Buchi, and coBuchi games.
 * [attachment:lecture8.pdf Lecture 8], introducing concurrent games, randomized strategies, and (lack of) optimal strategies.
 * [attachment:lecture9.pdf Lecture 9], on concurrent reachability games and value iteration.
 * [attachment:lecture10.pdf Lecture 10], on the proof of the solution formula for concurrent reachability games.
 * [attachment:lecture11.pdf Lecture 11], on the proof of the solution formula for concurrent safety games, and on reachability and safety in Markov decision processes. 
 * [attachment:lecture12.pdf Lecture 12], on mechanism design.
 * [attachment:lecture13.pdf Lecture 13], on CVG mechanism design.

=== Papers ===
 * [http://www.soe.ucsc.edu/~luca/papers/05/emsoft05.pdf Paper on games to manage resources (lock, mutexes) in embedded software]
 * [http://www.soe.ucsc.edu/~luca/papers/02/iccad02.pdf Paper on games to synthesize protocol converters]
 * [http://www.eecs.berkeley.edu/~tah/Publications/alternating-time_temporal_logic.html Paper on games as specification mechanism for systems]
 * [http://www.soe.ucsc.edu/~luca/papers/98/focs_98.pdf Concurrent Reachability Games].  I strongly advise you to read up to section 3.1 included. 
 * [http://www.soe.ucsc.edu/~luca/papers/04/jcss04.pdf Quantitative Omega-Regular Games].  I strongly advise you to read up to section 3 included.
 * [http://www.cs.ubc.ca/~condon/papers/random.pdf 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. 
 * [http://www.soe.ucsc.edu/~luca/papers/06/qest06-games.pdf 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. 

== Homeworks ==
 * [:CMPE 248 Spring 2008/Problem 1:/Problem 1], due April 7, 2008
 * [attachment:hw2.pdf Homework 2], due Monday May 5, 2008
 * Do the problems mentioned in Lecture 8.  Due: Monday May 12, 2008.