FOUNDATIONS OF COOPERATIVE AI

Tuesday and Thursday, 10:10AM - 11:30AM, WEH 5312
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:

  • 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 part 1 Vince Sep 6Foundations of cooperative AI vision paper.
    Slides: pptx, pdf.
    Overview part 2 Vince Sep 8(see above materials)
    Normal-form games Vince Sep 13Chapters 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 20Slides: 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 29Chapters 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 4Slides: pptx, pdf.
    Learning in extensive-form games Gabriele Farina guest lecture Oct 6Slides: pptx, pdf.
    Mediation in extensive-form games Brian Hu Zhang guest lecture Oct 11Slides: pptx, pdf.
    MIDTERM Caspar Oct 13Practice questions.
    Decision theories Caspar Oct 25Slides: pdf.
    Self-locating beliefs Caspar Oct 27Slides: 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 1Chapters 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+VinceNov 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 10Slides: pptx, pdf. Readings: paper 1. Optional: paper 2, paper 3. Also see Piazza post on outcomes of presentation slots auction.
    Kidney exchange continuedTuomas 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