(Ph.D. in Computer Science, University of Milan, 2021)

Lecturer: Prof. Nicola Basilico

This course provides an introduction to multiagent systems by concentrating on modeling agents interactions by means of competitive games. The main objectives of this course are: conveying basic notions of game theoretical models, discussing in detail some of the algorithms for their resolution, and presenting some recent real-world applications. The course has 20 hours of class lectures and is worth 3 credits (CFU).

The course was previously hosted on an ARIEL website, the now deprecated web platform provided by the University of Milan.

The official course details are available at this page

For the 2021 edition, lectures will be held remotely in this Zoom meeting:

https://us02web.zoom.us/j/88308636330?pwd=VVhJeEVWY3UwZzJaU0Vmcmo1YzhsZz09

Meeting ID: 883 0863 6330

Passcode: 864451

• June 18, 2021, 14:00-17:00 (3 hours)
• June 22, 2021, 9:00-12:00 (3 hours)
• June 25, 2021, 14:00-17:00 (3 hours)
• June 29, 2021, 14:00-17:00 (3 hours)
• July 2, 2021, 14:00-17:00 (3 hours)

Whiteboards

• Shoham, Yoav, and Kevin Leyton-Brown. Multiagent systems: Algorithmic, game-theoretic, and logical foundations. Cambridge University Press, 2008.
• Leyton-Brown, Kevin, and Yoav Shoham. “Essentials of game theory: A concise multidisciplinary introduction.” Synthesis lectures on artificial intelligence and machine learning 2.1 (2008): 1-88.
• Adler, Ilan, Constantinos Daskalakis, and Christos H. Papadimitriou. “A note on strictly competitive games.” International Workshop on Internet and Network Economics. Springer, Berlin, Heidelberg, 2009.
• Porter, Ryan, Eugene Nudelman, and Yoav Shoham. “Simple search methods for finding a Nash equilibrium.” Games and Economic Behavior 63.2 (2008): 642-662.
• Daskalakis, Constantinos, Paul W. Goldberg, and Christos H. Papadimitriou. “The complexity of computing a Nash equilibrium.” SIAM Journal on Computing 39.1 (2009): 195-259.
• Sandholm, Tuomas, Andrew Gilpin, and Vincent Conitzer. “Mixed-integer programming methods for finding Nash equilibria.” AAAI. 2005.
• Papadimitriou, Christos H., and Tim Roughgarden. “Computing correlated equilibria in multi-player games.” Journal of the ACM (JACM) 55.3 (2008): 1-29.
• von Stengel, Bernhard, and Daphne Koller. “Team-maxmin equilibria.” Games and Economic Behavior 21.1-2 (1997): 309-321.
• Blum, Avrim, et al. “Computing Stackelberg Equilibria of Large General-Sum Games.” International Symposium on Algorithmic Game Theory. Springer, Cham, 2019.
• Vazirani, Vijay V. Approximation algorithms. Springer Science & Business Media, 2013.

The required assignment aims at promoting research thinking within the scope of the addressed topics. The course will provide basic notions that students are encouraged to apply to any problem (preferably, but not necessarily, in their area of expertise) they find interesting or significant, the objective being that of identifying (and, optionally, pursuing) possible research challenges. These are some possible lines of work:

• find a problem you are interested in and try to model it as a game played by multiple agents; describe your formalization and discuss some benefits and research challenges that it would introduce;
• select one of the topics introduced in the course and briefly review the recent state of the art on it or on some of its applications envisioning possible future directions of development;
• develop one or more tools that can be useful for the understanding of the course topics or that can support some insights discussed in the previous lines.

The minimal deliverable for the course assignment is a short report of at least 3 pages (lncs LaTeX format). Cooperation and discussion between students is encouraged (especially if from different research backgrounds). Assignments can be carried out by parties of at most 3 students, the workload should be equally divided and the contribution of each one should be explicitly pointed out in the report.

Students that deliver the assignment will receive a grade on a scale from A (best) to E (worst). To successfully register the course, a grade of at least C must be obtained.