Lecturers Prof. Nicola Gatti (nicola.gatti at polimi dot it) Dr. Giuseppe De Nittis (giuseppe.denittis at polimi dot it) Dr. Stefano Paladino (stefano.paladino at polimi dot it)
Course description Economics and computer science have developed a remarkable number of points of contact over the past two decades. Some of these are directly motivated by applications such as large-scale digital auctions and markets, while others stem from fundamental questions such as the computational complexity of Nash equilibria, and complexity and approximation in mechanism design. Many computer scientists have realized that, in order to productively model and study the Internet and its novel computational phenomena, they need models and insights from disciplines such as game theory, economic theory and sociology, while many economists have found that a computational point of view is essential in order to understand a world in which markets are networked and the default platforms of economic transactions are algorithmic. During these past fifteen years much has been accomplished, both in achieving a remarkable degree of communication and collaboration between the fields, but also in making progress through interdisciplinary work on many central research questions, such as: studying the complexity of computing Nash and price equilibria; analyzing the efficiency of equilibria through the “price of anarchy”; and developing a computational theory of mechanism design which has informed the design of digital auctions. There is a consensus that the field is now ready for the next generation of problems and insights. This is precisely the objective of this program: to further the interaction between theoretical computer scientists and economists so as to identify, articulate and make progress on the new generation of research challenges at the intersection of the two fields.
Detailed program of the course and material Introduction 00. Presentation: Economics and computation(slides) Further readings: Machina economica (paper), Games and Internet (paper).
Basic game models 01. Theory: Extensive-form representation (notes) (questions). 02. Theory: Normal-form representation(notes) (questions). Further readings: Reduced normal form (paper), Reduced normal form and subgames (paper). Complementary: Agent-form representation (notes). 03. Theory: Sequence-form representation(notes) (questions). Further readings: Sequence form (paper). 04. Theory: Representation forms equivalence(notes) (questions). Complementary:Agent-form equivalence(notes).
Special classes of games and extensions 05. Theory: Special classes (notes) (questions). Further readings: Strictly-competitive games (paper), Strictly-competitive multi-player games (paper),Almost strictly-competitive games (paper), Almost strictly-competitive extensive-form games (paper),Zero-sum Polymatrix games (paper), Graphical games (paper), Unilaterally competitive games (papers). 06. Theory: Model extensions(notes) (questions). 07. Exercise: Game models (notes). Complementary: Solution concepts (notes).
Equilibrium finding algorithms and complexity 08. Presentation: Computational complexity (notes). Complementary: Primal, dual, complementary slackness (notes). 09. Theory: 2-player normal-form Maxmin/Minmax strategy (notes) (questions). 10. Theory: 2-player sequence-form Maxmin/Minmax strategy (notes) (questions). 11. Theory: n-player normal-form Maxmin/Minmax strategy (notes) (questions). Further readings: Team-maxmin complexity(paper), Computing a Team-maxmin equilibrium(paper). Complementary: Complexity of Maxmin/Minmax strategies (notes). 12. Laboratory: Maxmin/minmax strategy (notes) (solutions). 13. Theory: Sperner's Lemma and Scarf's algorithm (notes) (questions). 14. Theory: Fixed points and computational complexity (notes) (questions). 15. Theory: Mathematical programs for Nash equilibrium (notes) (questions). 16. Theory: Lemke-Howson algorithm (notes) (questions). Further readings: MIP methods(paper), Support enumeration algorithms (paper), Random restarts methods(paper). 17. Laboratory: Nash equilibrium (notes) (solutions). 18. Theory: Arrow-Debreu equilibrium (notes) (questions). Further readings:Arrow-Debreu equilibrium variations (paper),Arrow-Debreu equilibrium complexity (paper). 19. Theory: Leader-Follower equilibrium (notes) (questions). Further readings: Optimistic/pessimistic Leader-Follower equilibrium (paper), Finding an optimistic Leader-Follower equilibrium(paper). 20. Presentation: Security games (slides). 21. Laboratory: Leader-Follower equilibrium (notes) (solutions). 22. Theory: Potential games (notes) (questions). Complementary: Mathematical programming for potential games (notes) (solutions).
Notes about the exam The exam will be composed of two parts. * Part 1 includes a set of questions randomly drawn from the questions reported above with only numeric variations. These questions could include exercises (some examples of exercises can be found in the notes of the Laboratory Lectures and of the Exercise Lectures reported above). Part 1 gives at most 29 points. * Part 2 includes a set of 3 questions on advanced topics not reported in above questions (they are reported in the Theory and Exercise Lectures above), from which the student can choose one question. Part 2 gives at most 4 points.
Complementary notes, Presentations, and Further readings do not constitute topics of the exam. Their goal is to provide a support to a scientific researcher in the field.
Additional material Additionalexercises (by Nicola Gatti): some exercises.