FOUNDATIONS OF COOPERATIVE AI

Tuesday and Thursday, 11AM - 12:20PM, DH 2105.
Course begins the week of January 13.

INSTRUCTOR: Vincent Conitzer.
TA: Emanuel Tewolde.
See also: Foundations of Cooperative AI Lab (FOCAL).

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 (free PDF of the book available at that link), 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 LIKELY TO BE COVERED:

  • Game theory: representations, solution concepts, algorithms
  • Cooperation in repeated games and stochastic games, folk theorems
  • Commitment
  • Program equilibrium
  • Correlated equilibrium, mediated equilibrium
  • Team games
  • Mechanism design
  • Automated mechanism design
  • Market design and algorithms for running such markets, e.g., kidney exchange
  • Learning in games, equilibrium selection
  • Evaluating agents, also in non-zero-sum games
  • Agent design: identities, preferences, beliefs
  • Imperfect recall, belief formation, variants of decision theory
  • Learning-based notions of rationality
  • Cooperative game theory

    TENTATIVE SCHEDULE:

    -
    Topic Instructor Date Materials
    Overview partVinceJan 14, 16, 21, 23Foundations of cooperative AI vision paper.
    Slides: pptx, pdf. Emanuel's project ideas: pptx, pdf.
    AI alignment and social choice Vince Jan 23, 28Social choice for AI alignment position paper.
    Slides: pptx, pdf.
    Normal-form games Vince Jan 28, Feb 4Chapters 3 and 4 of Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations (also review Appendices A and B as needed)
    Slides: ppt, pdf.
    Extensive-form games Vince Feb 11-13Chapter 5 of Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations
    Slides: ppt, pdf.
    Optional: Paper on finding optimal strategies to commit to.
    Program and mediated equilibrium Caspar Feb 6Slides: pdf.
    HW1.
    Repeated games, stochastic games, learning in games Vince Feb 13-Feb 25Chapters 6.1, 6.2, 7 of Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations.
    Slides: repeated games: ppt, pdf; learning in games: ppt, pdf.
    HW2.
    Bayesian games and auctionsVinceFeb 25-March 20SLB 6.3, 11.1.1-11.1.8. Optional: 11.1.9, 11.1.10.
    Slides: ppt, pdf.
    Mechanism design Vince March 20-27 Slides: ppt, pdf.
    SLB 10.1-10.4.
    Optional: rest of chapter 10.
    Article on the Swoopo auction.
    MIDTERM Vince March 13 (practice questions covered on March 11)Practice questions. Whiteboard screenshots from solution videos: q1, q2, q3, q4, q5.
    Combinatorial auctions and variantsVinceMarch 25Slides: ppt, pdf.
    SLB 11.3.1-11.3.4, 11.4.1.
    Optional: 11.2, 11.3.5, Conitzer chapter on auctions, Lehmann et al. chapter on winner determination, Sandholm chapter on optimal winner determination.
    Automated mechanism design Vince March 27-April 1 Slides: ppt, pdf.
    HW3.
    Optional: Chapter on automated mechanism design, read up to and including 6.6.
    Coalitional/cooperative game theory Vince April 1-8 Slides: ppt, pdf.
    SLB Chapter 12.
    Self-locating beliefs VinceApril 10Slides: 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).
    Decision theories Caspar April 15Slides: pdf.