logo-polimi
Loading...
Risorse bibliografiche
Risorsa bibliografica obbligatoria
Risorsa bibliografica facoltativa
Scheda Riassuntiva
Anno Accademico 2018/2019
Scuola Scuola di Ingegneria Industriale e dell'Informazione
Insegnamento 097676 - ECONOMICS AND COMPUTATION
Docente Gatti Nicola
Cfu 6.00 Tipo insegnamento Monodisciplinare

Corso di Studi Codice Piano di Studio preventivamente approvato Da (compreso) A (escluso) Insegnamento
Ing Ind - Inf (Mag.)(ord. 270) - BV (479) MANAGEMENT ENGINEERING - INGEGNERIA GESTIONALE*AZZZZ097688 - ECONOMICS AND COMPUTATION
Ing Ind - Inf (Mag.)(ord. 270) - MI (474) TELECOMMUNICATION ENGINEERING - INGEGNERIA DELLE TELECOMUNICAZIONI*AZZZZ097688 - ECONOMICS AND COMPUTATION
Ing Ind - Inf (Mag.)(ord. 270) - MI (481) COMPUTER SCIENCE AND ENGINEERING - INGEGNERIA INFORMATICA*AZZZZ097688 - ECONOMICS AND COMPUTATION
Ing Ind - Inf (Mag.)(ord. 270) - MI (487) MATHEMATICAL ENGINEERING - INGEGNERIA MATEMATICA*AZZZZ097676 - ECONOMICS AND COMPUTATION

Obiettivi dell'insegnamento

This course is of 6 CFU and is associated with a version of 5 CFU named 097688 - ECONOMICS AND COMPUTATION (5 CFU). The current form specifies goals, program and expected learning results for both courses.

 

For both versions of the course (6 CFU and 5 CFU), 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 economic settings. The course focuses both on non-cooperative game theory, describing the models and the algorithms used in real-world applications in various settings (e.g., poker and security), and on mechanism design, describing economic mechanisms and algorithms used in auctioning settings (e.g., digital advertising and online auctions). The treatment of the topics will be both from a theoretical point of view, describing the models/algorithms and their properties, and from a practical point of view, discussing how the algorithms can be applied and applying them in practice during some laboratory sessions. Furthermore, the course aims at presenting some real-world applications of paramount importance. The difference between the two versions of the course (6 CFU and 5 CFU) is just in the depth with which some topics are discussed. 


Risultati di apprendimento attesi

For both versions of the course (6 CFU and 5 CFU), we expect that the students learn:

  • how to model real-world applications by means of mathematical models from microeconomics,
  • how to identify the most suitable class of algorithms to solve a given problem,
  • how to use the tools already available to solve a given problem in practice,
  • how to design an algorithm to solve a given problem whenever no algorithm is known

Argomenti trattati

We report the topics discussed in both versions of the course (6 CFU and 5 CFU). We use '(*)' for the topics that will not be discussed in the 5 CFU version.

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 (*)

Prerequisiti

For both versions of the course (6 CFU and 5 CFU), having attended:

  • a course on Game Theory is suggested, but not strictly necessary,
  • a course on Optimization is suggested, but not strictly necessary.

Modalità di valutazione

The exam is the same for both versions of the course (6 CFU and 5 CFU), except for the questions that, in the case of the 5 CFU version, may be different. More precisely, the exam can be of two forms:

  • standard: written exam (2.5 hours)
    • 3 exercises (the first exercise is on noncooperative game theory models and on the adoption of operations research tools to solve a game, the second exercise is on algorithmic game theory or economic mechanism design, the third exercise is on economic mechanism design or algorithmic mechanism design) (max 27 points), --- here the students are required to solve exercises similar to those studied during the course or to answer some theoretical questions about topics discussed during the course; the capabilities the students must show are: modeling real-world applications by means of mathematical models from microeconomics, indentifying the most suitable class of algorithms to solve a given problem, using the tools already available to solve a given problem in practice ---;
    • 1 question on advanced topics (on all the topics of the course) (max 5 points) --- here the students are required to answer a question that is beyond the topics discussed during the course; the capabilities the students must show are: generalizing the skills learned during the course to design an algorithm for a given problem that has not discussed during the course;
  • engaged: the course is divided into four parts (Part 1: noncooperative game theory models; Part 2: Maxmin and Nash equilibrium; Part 3: Stackelberg, Congestion games, social choice functions; Part 4: mechanism design and algorithm mechanism design), at the fourth week of each part of the course, students take part in a midterm exam (2.5 hours), composed as:
    • exercise/theory (1 exercise and 2 theory questions) (max 27 points) --- here the students are required to solve exercises similar to those studied during the course or to answer some theoretical questions about topics discussed during the course; the capabilities the students must show are: modeling real-world applications by means of mathematical models from microeconomics, identifying the most suitable class of algorithms to solve a given problem, using the tools already available to solve a given problem in practice ---;
    • challenge on scientific research problems (max 8 points); the challenge is carried on by teams, each of 2-3 students --- here the students are required to answer some questions that are beyond the topics discussed during the course; the capabilities the students must show are: generalizing the skills learned during the course to design an algorithm for a given problem that has not discussed during the course.

Each student can choose the form of the exam she/he prefers. If a student opts for the engaged form and she/he is not satisfied with the achieved grade, she/he can repeat the exam in the standard form.


Bibliografia
Risorsa bibliografica facoltativaNoam Nisan, Tim Roughgarden, Eva Tardos, V. Vazirani, Algorithmic Game Theory, Editore: Cambridge University Press
Risorsa bibliografica facoltativaKevin Leyton-Brown, Yoav Shoham, Essentials of Game Theory, Editore: Cambridge University Press

Forme didattiche
Tipo Forma Didattica Ore di attività svolte in aula
(hh:mm)
Ore di studio autonome
(hh:mm)
Lezione
39:00
58:30
Esercitazione
21:00
31:30
Laboratorio Informatico
0:00
0:00
Laboratorio Sperimentale
0:00
0:00
Laboratorio Di Progetto
0:00
0:00
Totale 60:00 90:00

Informazioni in lingua inglese a supporto dell'internazionalizzazione
Insegnamento erogato in lingua Inglese
Disponibilità di materiale didattico/slides in lingua inglese
Disponibilità di libri di testo/bibliografia in lingua inglese
Possibilità di sostenere l'esame in lingua inglese
Disponibilità di supporto didattico in lingua inglese
schedaincarico v. 1.6.1 / 1.6.1
Area Servizi ICT
08/12/2019