## ECONOMICS AND COMPUTATION

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).

Further readings:* 2-player Nash complexity** *(paper),* 3-player Nash complexity *(paper), *Nash approximation complexity *(paper), *Optimal Nash complexity* (paper).

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 restart 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).

**Mechanism design groundings**

23. Theory:* **Social choice functions** *(notes) (questions)

24. Theory: *Economic mechanisms** and implementation* (notes) (questions)

25. Theory: *Quasi-linear environment* (notes) (questions)

26. Theory: *Groves mechanisms, Clarke mechanism, and Vickrey auction* (notes) (questions)

27. Exercise: *Groves mechanisms* (notes)

28. Theory: *DSIC and strict budget balance* (notes) (questions)

29. Theory: *Single-parameter **linear environment** *(notes) (questions)

**Algorithmic mechanism design**

30. Theory: *Knapsack auction* (notes) (questions)

31. Exercise: *Knapsack auction - An exact algorithm* (notes)

32. Theory: *Combinatorial auction with single-minded players* (notes) (questions)

33. Exercise: *Combinatorial auction with single-minded players - An exact algorithm* (notes)

34. Exercise: *Truthful **approximation mechanisms* (notes)

35. Theory: *Analysis of non-truthful auctions* (notes) (questions)

36. Exercise: *Automated mechanism design* (notes)

37. Laboratory: *Automated mechanism design* (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

Additional exercises (by Nicola Gatti): some exercises.

Lab Instructions (by Stefano Paladino): instructions for installing the software used during the lab sessions

AMPL Cheat Sheet: AMPL syntax reference

Software download

(guide: How to determine if your OS is 32-bit or 64-bit)

AMPL Windows 32 bit

AMPL Windows 64 bit

AMPL Mac OS

AMPL Linux 32 bit

AMPL Linux 64 bit

Thesis topics

A number of thesis topics are available on all the themes discussed in the course.

Related courses

“Economics and computation” at Harvard University and MIT (website)

*Agent-form equivalence*

*Almost strictly-competitive games*

*Zero-sum Polymatrix games*

*Single-parameter*

*linear environment*