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-SLB 6.3, 11.1.1-11.1.8. Optional: 11.1.9, 11.1.10.
    Slides: ppt, pdf.
    Mechanism design Vince Slides: ppt, pdf.
    SLB 10.1-10.4.
    Optional: rest of chapter 10.
    MIDTERM Vince March 13Practice questions.