#acl All:read

= CMPE 248: Games in Design and Control =

 * Instructor: [http://www.soe.ucsc.edu/~luca 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 ==

 * [:/Synopsis: Synopsis].
 * Intended audience: CS/CE/EE/ISM graduate students, and interested (and sufficiently prepared) undergraduate students. 
 * [:/Prerequisites: Prerequisites]
 * '''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.
 * [:/Homework Policy: Homework Policy]

== Reading Material ==

=== Lectures ===

 * [attachment:lnotes.pdf Lecture Notes] (draft!)
 * [attachment:lect1.pdf Lecture 1: Jan 4]
 * [attachment:lect2.pdf Lecture 2: Jan 9]
 * [attachment:lect3.pdf Lecture 3: Jan 11]
 * [attachment:lect4.pdf Lecture 4: Jan 13]
 * [attachment:lect5.pdf Lecture 5: Jan 18]
 * [attachment:lect6.pdf Lecture 6: Jan 23]
 * Lecture 7, Jan 25: on interface theories.  You can look at [http://www.soe.ucsc.edu/~luca/papers/03/GamesForOpenSystems.pdf Game Models for Open Systems] to get the gist of the discussion, as well as this [http://www.soe.ucsc.edu/~luca/papers/06/ticc-intro-techrep06.pdf introduction to the tool Ticc]. 
 * [attachment:lect8.pdf Lecture 8: Jan 30], with a [attachment:parityalgo1.pdf summary of the recursive algorithm for parity games]. 
 * [attachment:lect9.pdf Lecture 9: Feb 1], with a [attachment:concreach.pdf summary of concurrent reachability games]. 
 * [attachment:lect10-11.pdf Lectures 10 and 11: Feb 6 and 8] 
 * [attachment:lect12.pdf Lecture 12: Feb 13]
 * [attachment:lect13.pdf Lecture 13: Feb 15]
 * [attachment:lect14.pdf Lecture 14: Feb 20]
 * [attachment:lect15.pdf Lectures 15 and 16: Feb 22 and 27] [http://mtc.epfl.ch/~tah/Publications/games_with_secure_equilibria.html Games with Secure Equlibria], by Chatterjee, Henzinger, Majumdar. 
 * [attachment:lect17.pdf Lecture 17: Mar 1]
 * [attachment:lect18.pdf Lecture 18: Mar 5]

=== Other assigned readings ===

You are strongly encouraged to read these portions of papers: 

 * For the recursive algorithm for parity games, you can read [http://www.dcs.warwick.ac.uk/~mju/Papers/JPZ06-SODA.pdf A Deterministic Subexponential Algorithm for Solving Parity Games], up to section 3 included. 
 * For quantitative reachability and safety games, you can read [http://www.soe.ucsc.edu/~luca/papers/04/jcss04.pdf Quantitative solution of omega-regular games] up to page 11 included. 

=== Other readings ===

 * Here is an [http://www.soe.ucsc.edu/~luca/papers/06/qest06-games.pdf 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 1, due Thu Jan 18: [attachment:hw1.ps PS] [attachment:hw1.pdf PDF]
 * Homework 2, due Tue Feb 6:  [attachment:hw2.ps PS] [attachment:hw2.pdf PDF]
 * [attachment:hw3.pdf Homework 3], due Thu Feb 8
 * {*} ["/Maze navigation problem"].