Insegnamento a.a. 2020-2021

20733 - ECONOMICS AND COMPUTATION

Cross-institutional study L. Bocconi - Politecnico Milano

Course taught in English
Go to class group/s: 31
CYBER (6 credits - II sem. - OP  |  ING-INF/05)
Course Director:
NICOLA GATTI

Classes: 31 (II sem.)
Instructors:
Class 31: NICOLA GATTI


Mission & Content Summary

MISSION

The goal of the course is to provide the groundings of algorithmic microeconomics. More precisely, the course explores mathematical models, computational complexity, and algorithms for adversarial and economic settings. Security applications will be discussed.

CONTENT SUMMARY

PRELIMINARIES OF GAME THEORY

  • Definition of non-cooperative game
  • Representations of a game

 

ALGORITHMIC GAME THEORY

  • Solving maxmin/minmax problems
  • Computational complexity of finding a Nash equilibrium
  • Algorithms for finding a Nash equilibrium
  • Arrow-Debreu market model and equilibrium
  • Algorithms for finding a Stackelberg equilibrium
  • Real-world application: security games
  • Congestion games
  • Price of Anarchy and Price of Stability

 

ECONOMIC MECHANISM DESIGN

  • Social choice function
  • Definition of economic mechanism
  • Gibbard-Satterthwaite theorem
  • Quasi-linear environment and linear environment
  • Implementation of a social choice function
  • Groves mechanisms
  • Green-Laffont characterization and Myerson characterization
  • Economic mechanisms for online advertising (real-world applications)

 

ALGORITHMIC MECHANISM DESIGN

  • Non-scalability of Groves mechanisms (real-world examples: combinatorial auctions)
  • Developing computationally efficient mechanisms
  • Economic mechanisms for combinatorial auctions (real-world applications)
  • Economic mechanisms for double auctions
  • Economic mechanisms for knapsack auctions
  • Automated mechanism design

Intended Learning Outcomes (ILO)

KNOWLEDGE AND UNDERSTANDING

At the end of the course student will be able to...
  • know what is a strategic situation,
  • know models for strategic situations,
  • know algorithms for strategic situaions.

APPLYING KNOWLEDGE AND UNDERSTANDING

At the end of the course student will be able to...
  •  model real-world applications by means of mathematical models from microeconomics,
  • identify the most suitable class of algorithms to solve a given adversarial problem,
  •  use the tools already available to solve a given adversarial problem in practice,
  • design an algorithm to solve a given problem whenever no algorithm is known.

Teaching methods

  • Face-to-face lectures
  • Online lectures
  • Exercises (exercises, database, software etc.)
  • Group assignments

DETAILS


Assessment methods

  Continuous assessment Partial exams General exam
  • Written individual exam (traditional/online)
   x x
  • Group assignment (report, exercise, presentation, project work etc.)
   x  

ATTENDING STUDENTS

There are three possible forms of exams that every student can choose:

  • a general written exam,
  • a general written exam in which a part of the questions is substituted with 3 group assignments (for 20% of the final grade),
  • 4 written midterms (for the 80% of the final grade) and 3 group assignments (for the 20% of the final grade).

 

The general written exam is composed of exercises and theoretical questions over the entire course.

 

The written midterms are composed of exercises and theoretical questions that are similar to those of the general written exam. Every midterm focuses on a specific part of the course.

 

The group assignments are scientific works in which the students are required to study a scientific problem not discussed during the course, develop an algorithm to solve it and present their solution.


NOT ATTENDING STUDENTS


Teaching materials


ATTENDING AND NOT ATTENDING STUDENTS

The material (video lectures, questions, quizzes) is entirely provided by the lecturer.

The following textbooks are suggestes:

  • Noam Nisan, Tim Roughgarden, Eva Tardos, V. Vazirani, Algorithmic Game Theory, Publisher: Cambridge University Press.
  • Kevin Leyton-Brown, Yoav Shoham, Essentials of Game Theory, Publisher: Cambridge University Press
Last change 14/07/2020 15:14