Ing Ind - Inf (Mag.)(ord. 270) - BV (479) MANAGEMENT ENGINEERING - INGEGNERIA GESTIONALE

*

A

ZZZZ

097688 - ECONOMICS AND COMPUTATION

Ing Ind - Inf (Mag.)(ord. 270) - MI (474) TELECOMMUNICATION ENGINEERING - INGEGNERIA DELLE TELECOMUNICAZIONI

*

A

ZZZZ

097688 - ECONOMICS AND COMPUTATION

Ing Ind - Inf (Mag.)(ord. 270) - MI (481) COMPUTER SCIENCE AND ENGINEERING - INGEGNERIA INFORMATICA

*

A

ZZZZ

097688 - ECONOMICS AND COMPUTATION

Ing Ind - Inf (Mag.)(ord. 270) - MI (487) MATHEMATICAL ENGINEERING - INGEGNERIA MATEMATICA

*

A

ZZZZ

097676 - 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

Noam Nisan, Tim Roughgarden, Eva Tardos, V. Vazirani, Algorithmic Game Theory, Editore: Cambridge University Press
Kevin 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