Multiagent decision-making and control

You find details regarding the course topics, teaching staff and grading in the Course information.pdf

Important dates:

1.  Mar 26: Quiz 1, 13:15-14:15, 20%
2. April 30: Quiz 2, 13:15-14:15, 20%
3. Apr 16: project update: 13:15-14:00, 10%
4. May 26: final project report,  20%, upload pdf by 21:00.
5. May 28: final project presentation: 13:15-16:00, 30%, upload pdf by 13:00.

Note: The quizzes are closed book. You are not allowed any electronic or notes. You can bring one page (one sheet one sided) of hand-written notes.

Reference books: While they are not required, they can help deepen the understanding of the topics we cover. Furthermore, I suggest additional readings from these references.

• Basar and Jan Olsder, Dynamic Noncooperative Game Theory, 1982, available online from EPFL library website
• Fudenberg and Tirole, Game Theory, 1991, available at EPFL library
• Nissan, Roughgarden, Tardos, and Vazirani, Algorithmic Game Theory, 2007
• Hespanha, Noncooperative Game Theory, 2015, available online from EPFL library website
• Karlin and Peres, Game Theory, Alive, 2016

We introduced game theory as a framework for multiagent decision-making. Defining a notion of rationality, we motivated and defined a Nash equilibrium as a solution concept for multi-agent decision-making. Additional reading: Chapters 1, 10 of Hespanha book. 

For background on convex sets and convex functions please read Chapters 2,3 of this book. Additional reading for zero-sum games: Chapters 5-6 of Hespanha book.

Additional reading: Chapters 12-13 of Hespanha book. The potential game paper by Monderer and Shapley. 

We continued discussion on potential game and proved convergence of best-reply dynamics to a Nash equilibrium in this class of games. We also introduced extensive form games. Additional reading: Chapters 2, 6 of Hespnha book.

We continue with discussion of feedback games and backward induction for feedback games. We proved that subgame perfect equilibria using backward induction are Nash equilibria for the game (but not vice versa). Additional reading: Example 6.1.6 (Centipede) in Game Theory Alive, and Chapter 7 in Hespanha's book.

In the first hour, we reviewed different equilibrium strategies in extensive form games. In the second hour, we introduced dynamic games, and the principle of optimality in single player dynamic games. We described how this principle leads to the dynamic programming approach to solve the finite horizon optimal control problem. Additional reading: Sections 14.1-14.2, 15.1-15.4 from Hespanha's book.

We showed how to use dynamic programming to compute the subgame perfect Nash equilibrium strategies in dynamic games. We looked at a specific class of dynamic games, namely, linear quadratic games and showed the subgame perfect equilibrium is linear state-feedback (if it exists). Additional reading: Chapter 17 in Hespanha book.

We had the project presentations, followed by a lecture on Markov games. A Markov game is an extension of our dynamical feedback games, which includes stochastic in the dynamics. The cost is formulated through an expectation operator and the dynamic programming approach can be used to find subgame perfect Nash equilibrium strategies for the players.

Note regarding practice quiz: You can skip problem 1 from Quiz 2 of last year, and Problem 3 from Preparation for Quiz 2 of last year. The topics were not covered this year yet. 

We had a quiz followed by a lecture on convex games. 

Students To Do: For next week's exercise hour, fill out the project deliverable document given to you in class.

We discussed existence and computation of equilibria in convex games. In particular, for computation, we motivated using a projected gradient descent approach and leveraging the contraction mapping theorem to prove its convergence under Lipschitz continuity and monotonicity of the pseudo-gradient. In the exercise hour, we answered questions regarding your projects, based on your project sheet.

In the first part of the lecture,  proved the convergence of playerwise gradient descent for monotone games with Lipschitz continuous pseudo-gradient, with suitable choice of stepsize. Next, we introduced auctions and provide a game theoretic view of first-price and second-price auction.