Game Theory for Network Systems, January-March 2023

Teachers: Giacomo Como

Course description

While originally developed to model socio-economic phenomena, Game Theory has recently emerged as a powerful framework to efficiently solve optimisation and multi-agent decision problems in engineering and computer science. After presenting the basic concepts and notation from classical competitive game theory, the course will focus on network games and learning dynamics and their convergence properties. Particular emphasis will be on mechanism design. Starting from problems such as constraint satisfaction, resource allocation, Bayesian inference, the course will show how to design a game and a learning mechanism to solve them in an efficient and distributed fashion.

Pre-requirements

Good knowledge of basic math is assumed (calculus, linear algebra, graphs, elementary probability and Markov chains). All remaining concepts will be built within the course.

Course topics

1. Non-cooperative strategic games. Historical remarks. Basic examples. Fundamental concepts: Best Response, Dominated strategy, Nash equilibrium, Price of anarchy. Games with with continuous action sets: Cournot and Bertrand models. First results on existence and uniqueness of Nash equilibria.
2. Existence of Nash equilibria and potential games. Mixed strategies and the Nash’s existence theorem. Potential games. Finite improvement property. Congestion games.
3. Network games. Pairwise separable games. Graphical potential games. Examples: network coordination, anti-coordination, coloring, public good games.
4. Best response and noisy best response dynamics. Asymptotic behavior for potential games. Applications: graph coloring and other constraint satisfaction problems.
5. Quadratic games. Motivating examples. Characterization and stability of Nash equilibria. Positive and negative externalities. Strategic complements and substitutes. The role of network centrality and the concept of key player. Constraint quadratic games.
6. Supermodular games. Lattice structure of Nash equilibria set. Asymptotic behavior of the best response dynamics. Comparative statics.
7. Population games and evolutionary dynamics. Evolutionary stable strategies. Replicator dynamics and other imitation rules.
8. Learning in games. Fictitious play. Convergence properties.
9. Optimal targeting. Threshold models of cascades. Complexity results and submodularity.
10. Network intervention and mechanism design. Continuous congestion games. Optimal pricing

Exam

Oral presentation

PeriodP.D.1-1 - January

Additional information

10 3-hour lectures from the beginning of January to mid March, 2023

Course website