• Blended Learning & Flipped Classroom
• MOOC

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. 

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

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

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.

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.