Tuesday and Thursday, 10:10AM - 11:30AM,

Course begins the week of September 6

INSTRUCTOR: Vincent Conitzer, Caspar Oesterheld, Tuomas Sandholm

See also: Foundations of Cooperative AI Lab (FOCAL), Electronic Marketplaces Lab (EM).

UNIVERSITY UNITS: 12

DESCRIPTION:

In AI and beyond, systems of multiple agents are naturally modeled using game theory. From game theory, we know that sometimes, when each agent pursues its own objectives, the outcome may be one that is bad for all agents (e.g., the Prisoner's Dilemma). Learning algorithms can indeed converge to such bad equilibria. What can be done to prevent such bad outcomes, and how should we think about designing agents in such contexts? In this course, we will approach this question from a variety of angles, ranging from traditional approaches in game theory to novel ones that fit AI better than humans.

PREREQUISITES:

There is no formal prerequisite for the course, but we do expect students to be mathematically well prepared and ready to undertake a significant course project. For students just looking to gain general background in AI, 15-780 is better suited.

TEXT:

Materials will be made available on the course website. A text that provides general background in game theory is Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations by Shoham and Leyton-Brown, but this text covers only some of the topics of the course.

METHOD OF EVALUATION:

Grading will be based on class participation (10%), homework assignments (20%), a midterm exam (20%), and a class project (50%).

TOPICS TO BE COVERED:

TENTATIVE SCHEDULE:

Topic |
Instructor |
Date |
Materials |

Overview part 1 | Vince | Sep 6 | Foundations of cooperative AI
vision paper. Slides: pptx, pdf. |

Overview part 2 | Vince | Sep 8 | (see above materials) |

Normal-form games | Vince | Sep 13 | Chapters 3 and 4 of Multiagent Systems:
Algorithmic, Game-Theoretic,
and Logical Foundations (also review Appendices A and B as needed) Slides: ppt, pdf. |

Normal-form games | Vince | Sep 15 | (see above materials) |

Program and mediated equilibrium | Caspar | Sep 20 | Slides: pdf. HW1. |

Intro extensive-form games (info sets, refinements) | Tuomas | Sep 22 (by this point we had gradually fallen behind to Sep 27) | Chapters 5 of Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. Slides: pptx, pdf. |

Various: repeated games, stochastic games, learning in games | Vince | Sep 29 | Chapters 6.1, 6.2, 7 of Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. Slides: repeated games: ppt, pdf; learning in games (skipped for now): ppt, pdf. |

Solving (imperfect info) extensive-form games | Tuomas | Oct 4 | Slides: pptx, pdf. |

Learning in extensive-form games | Gabriele Farina guest lecture | Oct 6 | Slides: pptx, pdf. |

Mediation in extensive-form games | Brian Hu Zhang guest lecture | Oct 11 | Slides: pptx, pdf. |

MIDTERM | Caspar | Oct 13 | Practice questions. |

Decision theories | Caspar | Oct 25 | Slides: pdf. |

Self-locating beliefs | Caspar | Oct 27 | Slides: pptx, pdf. Another resource/perspective on the material of these last two lectures is this tutorial, especially the second half / parts 3 and 4 (slides and link to YouTube videos are at that link). |

Mechanism design | Tuomas | Nov 1 | Chapters 10 and 11 (and 6.3 for background on Bayesian games) of Multiagent Systems:
Algorithmic, Game-Theoretic,
and Logical Foundations. Slides: pptx, pdf. HW2. |

Automated mechanism design, VCG, presentation slots auction | Tuomas+Vince | Nov 3 | (see above materials, Piazza post on presentation slots auction) |

Automated mechanism design continued | Tuomas | Nov 8 | (see above materials) |

Kidney exchange, presentation slots outcome | Tuomas+Vince | Nov 10 | Slides: pptx, pdf. Readings: paper 1. Optional: paper 2, paper 3. Also see Piazza post on outcomes of presentation slots auction. |

Kidney exchange continued | Tuomas | Nov 15 | (see above materials) |

Course presentations; moral AI in kidney exchange | all; Vince | Nov 17 | (For Vince's part) slides: pptx, pdf. Paper. |

Course presentations; safe Pareto improvements | all; Caspar | Nov 22 | (For Caspar's part) slides: pdf. Paper. |

Course presentations | all | Nov 29 | |

Course presentations | all | Dec 1 | |

Course presentations | all | Dec 6 | |

Course presentations | all | Dec 8 |