• CMPE 248 Topics

CMPE 248: Games in Design and Verification

Main Topics

1. Preliminaries.
2. Two-person zero-sum games and Markov decision processes.
3. Structural properties of MDPs: end components, maximal end-component decomposition.
4. The sure-winning case: guaranteed winning of games with respect to safety and reachability goals.
5. Quantitative solution of MDPs with respect to safety, reachability, and total reward goals.
6. Quantitative solution of safety and reachability games.
7. Omega-regular games via the mu-calculus.
8. Game relations.
9. The average reward case.

Optional Advanced Topics

• We will cover some of these topics time permitting.

• Partial information and team games.
• Real-time games.
• Non-zero sum games: Nash equilibria, Kakutani's theorem.
• Advanced optional topic: discounting.