Algorithmic Game Theory (2020/2021)

Course code
4S008905
Name of lecturer
Ferdinando Cicalese
Coordinator
Ferdinando Cicalese
Number of ECTS credits allocated
6
Academic sector
INF/01 - INFORMATICS
Language of instruction
Italian
Location
VERONA
Period
II semestre dal Mar 1, 2021 al Jun 11, 2021.

Lesson timetable

Go to lesson schedule

Learning outcomes

Many problems in computer science involve settings where multiple self-interested parties interact, e.g., resource allocation in large networks, online advertising, managing electronic marketplaces and networked computer systems. Computational (algorithmic) game theory complements economic models and solution concepts, to reason about how agents should act when the actions of other agents affect their utilities, with a focus to discuss computational complexity issues, and the use of approximation bounds for models where exact solutions are unrealistic. The course aims to give students an introduction to the main concepts in the field of computational game theory with representative models and (algorithmic) solution chosen to illustrate broader themes. Students will acquire the basic skills to design models and computer systems that performs optimally/well in some paradigmatic multiagent settings; and to reason about the design of mechanisms to incentivate self-interested users to behave in a desirable way.

Syllabus

1. Introduction to strategic games, costs, payoffs; basic solution concepts; equilibria and learning in games; Nash equilibrium; repeated games; cooperative games; markets and algorithmic issues. 2. Basic computational issues of finding equilibrium. 3. Repeatedly making decisions with uncertainty; learning, regret minimization and equilibrium. 3. Graphical games and connections to probabilistic inference in machine learning. 4. Elements of Mechanism Design; Auctions; distributed mechanism design.

Reference books
Author Title Publisher Year ISBN Note
Nisan, Roughgardner, Tardos, Vazirani Algorithmic Game Theory Cambridge University Press 2007 978-0-521-87282-9
Martin J. Osborne An introduction to Game Theory Oxford University Press 2004 0-19-512895-8

Assessment methods and criteria

The exam verifies that the students have acquired sufficient confidence and skill in the application of the basic game thoretic models and their solutions, and are able to contextualize them in simple novel multiagent scenarios.

The exam consists of a written test with open questions and multiple choice questions. The test includes some mandatory exercises and a set of exercises among which the student can choose what to work on. The mandatory exercises are meant to verify a straightforward application of the elements studied in class. The "free-choice" exercises test the ability of students to re-elaborate these notions in "new" scenarios.