CS 244

Game-Theoretic Artificial Intelligence

Professor Amy Greenwald

CS 244
Mondays, 3-5:20 PM
CIT 345

Course Description

This course surveys recent developments in an emerging area known as game-theoretic artificial intelligence (AI), which incorporates fundamental principles of game theory into AI. Research in this area is motivated by game-theoretic applications, such as auction design and voting, as well as AI application areas, such as multiagent systems. Students will conduct theoretical, empirical, and experimental investigations, asking fundamental questions such as: can computational agents learn to play game-theoretic equilibria?

Course Goals

This course is intended to introduce students to an emerging area of artificial intelligence that stems from the intersection of game theory and computer science. The computer science student will develop a comfort level with basic game-theoretic concepts, and the economics student will be exposed to computational aspects of agent behavior. These goals will be achieved through a combination of lectures, student presentations, programming and written assignments, and a course project.

Prerequisites

This course draws on ideas from multiple disciplines, most notably AI and game theory. Basic knowledge of computer science is assumed, but basic knowledge of game theory is not (the course begins with an overview of game theory fundamentals). Parts of the course are mathematically rigorous, so although there are no formal prerequisites, a reasonable level of mathematical sophistication is necessary, particularly the ability to reason abstractly. Permission of the instructor is required.

Course Organization

Although this course initiates with a series of lectures given by the Instructor on game theory fundamentals, it is primarily a seminar. Students read papers, prepare presentations, and lead discussions. Grading is based in part on class participation (particularly, student presentations) and in part on the course project. Short written and programming exercises may also be assigned throughout.

Course Project

The course project presents the student with an opportunity to develop a deep understanding of any topic that interfaces game theory and AI. Projects can incorporate theoretical, experimental, or empirical studies. Ideally, students would tackle an open research problem. Students are welcome (even encouraged) to collaborate on projects, but the contribution of each individual participant must be easily identfiable.

Syllabus

	Speaker	Topic	References
		Matrix Games
1/28	Amy	Rationality Expected Utility Theory	Ellsberg Paradox Allais Paradox
2/04	Casey	Nash Equilibrium	J. Nash, Jr., Non-cooperative Games, Annals of Mathematics, 54: 286-295, 1951
2/11	Victor & Warren	Minimax Equilibrium	Victor's Slides: On Pure Strategy Equilibria in Zero-Sum Games Warren's Slides: A Proof of the Minimax Theorem
2/18	LONG WEEKEND
2/25	Victor & Warren	Simplex Method & Lemke-Howson Algorithm
3/03	Amy	Correlated Equilibrium	Correlated Equilibrium as an Expression of Bayesian Rationality Computing Correlated Equilibria in Multiplayer Games Andreas' Summary (Andreas' Slides) and Victor's Explanation
		Extensive-Form Games
3/03	Casey	Backward Induction & Subgame Perfect Equilibrium	Efficient Computation of Behavioral Strategies Extensive Form Correlated Equilibrium
		Markov Games
3/10	Long & Amy	Markov Chains (AM 120 Notes) & Markov Decision Processes (I, II)
3/17	Shay	Zero-Sum Markov Games	L. Shapley, "Stochastic Games," Proceedings of the National Academy of Sciences, 1953. Minimax Q-Learning and Friend-or-Foe Q-Learning
3/24	SPRING BREAK
3/31	Feng-Hao	General-Sum Markov Games	Nash Q-Learning and Correlated Q-Learning Cyclic Equilibrium
		Repeated Games
		Game-Theoretic (Convergence) Results	Blackwell's Approachability Theorem A General Class of No-Regret Learning Algorithms and Game-Theoretic Equilibria
		Computer Science (Bounding) Results	Bounds for Regret-Matching Algorithms No-Regret Learning in Convex Games
		Applications
4/14	Victor & Eric	Mechanism Design (I, II) Matching Mechanisms	Parkes' Classic Mechanism Design
4/14	Long & Amy	Combinatorial Auctions Trading Agents	Approximately Efficient Combinatorial Auctions
4/21	Justin, Suman & Yuri & Tim	Sponsored Search Social Networks Prediction Markets
4/28	Tim & Serdar & Arjun	Prediction Markets Reputation Systems Peer to Peer Systems	Robust Incentive Techniques for P2P Networks
5/05	Kembey & Dilyana, Teodor, & Adrian	Automated Portfolio Management State Aggregation in MDPs
		Course Projects
5/12	2-5 pm	Student Presentations

Related Courses

Etessami's class at Edinburgh: Algorithmic Game Theory and Applications
Shoham's course at Stanford: Multiagent Systems
Tardos' course at Cornell: Algorithmic Game Theory
Larson's course at Waterloo: Game-theoretic Methods for Computer Science
Papadimitriou's course at Berkeley: Topics on the border of CS, Game theory, and Economics
Parkes' course at Harvard: Topics at the Interface between Computer Science and Economics
Sandholm's course at CMU: Foundations of Electronic Marketplaces

Related Texts

N. Nisan, E. Tardos, T. Roughgarden, and V. Vazirani. Algorithmic Game Theory. Available for download here.
M. Osbourne and A. Rubinstein. A course in Game Theory, MIT Press 1994.
H. Peyton Young. Strategic Learning and its Limits. Oxford University Press, 2004.
D. Fudenberg and D. Levine. The Theory of Learning in Games, MIT Press 1998.