Mandatory course for the Master in Physics of Complex Systems (national track), 2nd year, 1st term.
Optimal control deals with the mathematical formulation of optimal policies to control the evolution of deterministic/stochastic dynamical systems. In this regards, there is a deep connection to game theory, that is the study of strategic reasoning by rational agents. The knowledge of both disciplines have recently become a necessary tool for the analysis of complex phenomena emerging in biological, social and technological systems. The course aims to provide an introduction to fundamental concepts of game theory and optimal control: in particular, Nash equilibria and other solution concepts, repeated games and planning problems, the mathematical basis of dynamic programming and the theory and applications of Pontryagin’s Maximum Principle. Applications to the dynamics of complex systems in physics, biology and economics are also discussed.
Mandatory course for the Master in Physics of Complex Systems (national track), 2nd year, 1st term.
Optimal control deals with the mathematical formulation of optimal policies to control the evolution of deterministic/stochastic dynamical systems. In this regard, there is a deep connection to game theory, which is the study of strategic reasoning by rational agents. The knowledge of both disciplines has recently become a necessary tool for the analysis of complex phenomena emerging in biological, social, and technological systems. The course aims to provide an introduction to fundamental concepts of game theory and optimal control: in particular, Nash equilibria and other solution concepts, repeated games and planning problems, the mathematical basis of dynamic programming, and the theory and applications of Pontryagin’s Maximum Principle. Applications to real-world problems arising in different fields are also discussed.
The students will become familiar with:
- basic concepts of strategic reasoning and non-cooperative decision making in two-person games and multi-player setups (networks);
- optimal planning and dynamic programming techniques both in discrete and continuous systems;
- relation between repeated games and optimal control problems;
- Pontryagin’s maximum principle and its applications to control and dynamic games.
Students will learn how to mathematically model control problems and analyse strategic decision-making in the presence of selfish individuals, with particular attention to the type of problems arising in the study of complex systems (with examples from physics, biology and economics).
The students will become familiar with:
- basic concepts of strategic reasoning and non-cooperative decision making in two-person games and multi-player setups (possibly also in networks);
- optimal planning and dynamic programming techniques both in discrete and continuous systems;
- relation between repeated games and optimal control problems;
- Pontryagin’s maximum principle and its applications to control and dynamic games.
Students will learn how to mathematically model control problems and analyse strategic decision-making in the presence of selfish individuals, with particular attention to the type of problems arising in the study of complex systems.
Basics of calculus, linear algebra and probability theory. Basic properties of ordinary differential equations. Elements of functional analysis (operators and functionals on Banach spaces) are desirable but not mandatory. Basic concepts of graph theory.
Basics of calculus, linear algebra and probability theory. Basic properties of ordinary differential equations. Elements of functional analysis (operators and functionals on Banach spaces) are desirable but not mandatory. Basic concepts of graph theory.
1. Introduction to game theory (20 h)
Normal-form games: solution concepts for zero-sum games, pure and mixed Nash equilibria, refinements.
Extensive-form games: subgame-perfect equilibria, repeated games, backward induction.
Games of incomplete information: bayesian games, global games, correlated equilibria.
Algorithmic game theory: complexity of Nash equilibria, price of anarchy.
2. Multi-agent systems (15h)
Congestion games and minority game, networks and graphical games, incentives and control of network dynamics.
3. Dynamic programming and Stochastic Optimal Control (10h)
Constrained and unconstrained smooth optimization: Lagrangian multipliers, Karush-Kuhn-Tucker optimality conditions, existence of global minima; Bellman’s principle in deterministic and stochastic discrete-time systems; Hamilton-Jacobi-Bellman equation in continuous-time systems.
Applications: linear-quadratic control, dynamic asset allocation.
4. Maximum principle (15h)
Pontryagin’s maximum principle (PMP) in the Hamiltonian and Lagrangian forms.
PMP and calculus of variations.
PMP for linear systems, time-optimality of the “bang-bang” control.
Sufficient conditions of optimality, existence of global optima.
Infinite dynamic games, PMP as a necessary condition for an equilibrium strategy.
1. Optimal Control (20h)
- Elements of constrained and unconstrained smooth optimization: Lagrangian multipliers, Karush-Kuhn-Tucker optimality conditions, existence of global minima.
- Optimal control problem formulation for finite-dimensional continuous-time problems.
- Pontryagin’s maximum principle (PMP) in the Hamiltonian and Lagrangian forms.
- PMP and calculus of variations.
- PMP for linear systems, time-optimality of the “bang-bang” control.
- Sufficient conditions of optimality, existence of global optima.
- Dynamic programming.
- Bellman’s principle in deterministic discrete-time systems; Hamilton-Jacobi-Bellman equation in continuous-time systems.
- Dynamic programming for stochastic discrete systems, Markov Decision Processes.
2. Game theory (40 h)
- Elements of decision theory: preference relations, utility function, decision under risk and ignorance, sequential decision problems, relation to optimal control and reinforcement learning.
- Games in normal form: dominance, best-response, rationalizability, Nash equilibria, correlated eq., solution concepts for zero-sum games.
- Computational aspects of normal-form games: algorithms for finding equilibria in zero-sum and general sum two-player games, computational complexity, price of anarchy, relation to linear and integer programming.
- Extensive-form games with perfect information: subgame-perfect equilibria, backward induction, repeated games.
- Extensive-form games with imperfect and incomplete information: sequential equilibria, bayesian games.
- Multi-agent games: games with global interaction, coordination and congestion games, cooperation, networks games.
- Learning and dynamical equilibrium selection.
Frontal lectures using mainly blackboard and (rarely) computer presentations. Approximately 20% of the lecture time will be devoted to
discuss examples and applications and to solve exercises. Homework problems will be also proposed after completing each topic and solved after a few lectures, in order to provide the students a way to see practical applications of the theory and test their level of understanding of the exposed notions.
Frontal lectures, using mainly blackboard and computer presentations (in the case of online course, use of slides and tablet whiteboard). Approximately 25% of the lecture time will be devoted to discussing examples and applications and solving exercises. Homework problems will be also proposed after completing each topic and possibly solved after a few lectures, in order to provide the students a way to see practical applications of the theory and test their level of understanding of the exposed notions.
- K.Leyton-Brown and Y. Shoham, Essentials of Game Theory: A concise, multidisciplinary Introduction, Morgan&Calypool Pubs, 2008.
- M. Osborne, A course in Game Theory, The MIT Press, 1994.
- N. Nisan, T. Roughgarden, E. Tardos, V. Vazirani, Algorithmic Game Theory, Cambridge Univ. Press, 2007.
- D. Easley and J. Kleinberg, Networks, Crowds, and Markets, Cambridge Univ. Press, 2010.
- M.O. Jackson, Social and Economic Networks, Princeton Univ. Press 2008.
- D.P. Bertsekas, Dynamic Programming and Optimal Control, Vol. I, Athena Scientific, 1995.
- E.B. Lee, L. Markus, Foundations of Optimal Control Theory, John Wiley & Sons, 1967.
- T. Basar and G.J. Olsder, Dynamic Non-cooperative Game Theory, ser. “Classics in Applied Mathematics”, vol. 23, SIAM, 1999.
- Lecture notes and reading material provided by the teacher.
- K.Leyton-Brown and Y. Shoham, Essentials of Game Theory: A concise, multidisciplinary Introduction, Morgan&Calypool Pubs, 2008.
- M.J. Osborne and A. Rubinstein, A course in Game Theory, The MIT Press, 1994.
- N. Nisan, T. Roughgarden, E. Tardos, V. Vazirani, Algorithmic Game Theory, Cambridge Univ. Press, 2007.
- D. Easley and J. Kleinberg, Networks, Crowds, and Markets, Cambridge Univ. Press, 2010.
- M.O. Jackson, Social and Economic Networks, Princeton Univ. Press 2008.
- D.P. Bertsekas, Dynamic Programming and Optimal Control, Vol. I, Athena Scientific, 1995.
- D. Lieberzon, "Calculus of Variations and Optimal Control Theory", Princeton University Press, 2012.
- E.B. Lee, L. Markus, Foundations of Optimal Control Theory, John Wiley & Sons, 1967.
- T. Basar and G.J. Olsder, Dynamic Non-cooperative Game Theory, ser. “Classics in Applied Mathematics”, vol. 23, SIAM, 1999.
Slides; Dispense; Esercizi; Esercizi risolti;
Lecture slides; Lecture notes; Exercises; Exercise with solutions ;
E' possibile sostenere l’esame in anticipo rispetto all’acquisizione della frequenza
You can take this exam before attending the course
Modalità di esame: Prova scritta (in aula); Prova orale obbligatoria;
Exam: Written test; Compulsory oral exam;
...
Assessment is performed through two written exams: one on game theory (part 1-2) and one on optimal control (part 3-4).
Each exam is composed of multiple-choice questions, open questions on proofs derivations and problems to be solved with the learned ideas and techniques. More specific information will be provided by the teacher at the beginning of the course.
The results of the two exams will contribute equally to the final grade.
The objective of the final exams is two-fold: to evaluate the theoretical knowledge of the subjects covered in the lectures and to assess the ability of the students to apply these concepts in order to solve practical problems. Both elements will have equivalent weight on the final grade: the exact weight of each part (question/problems) of the written exam will be clearly specified beforehand.
Gli studenti e le studentesse con disabilità o con Disturbi Specifici di Apprendimento (DSA), oltre alla segnalazione tramite procedura informatizzata, sono invitati a comunicare anche direttamente al/la docente titolare dell'insegnamento, con un preavviso non inferiore ad una settimana dall'avvio della sessione d'esame, gli strumenti compensativi concordati con l'Unità Special Needs, al fine di permettere al/la docente la declinazione più idonea in riferimento alla specifica tipologia di esame.
Exam: Written test; Compulsory oral exam;
The assessment is performed through a written exam plus a mandatory oral exam. The written exam is composed of a fixed number (e.g. 6) of multiple-choice questions and a few open problems (e.g. 3), to be solved by applying the ideas and techniques learned in the course. More specific information and examples of past exams will be provided by the teachers during the course. Duration of the exam: 2.30h. Students can consult lecture notes/personal notes during the exam.
There will be also a short (20-25 min) oral exam for students achieving in the written exam a grade equal to or larger than 18/30. The oral exam will focus on parts of the material covered during the course and specified beforehand.
The objective of the final exams is two-fold: to evaluate the theoretical knowledge of the subjects covered in the lectures and to assess the ability of the students to apply these concepts in order to solve practical problems. Both elements will have equivalent weight on the final grade: the exact weight of each part (question/problems) of the written exam will be clearly specified beforehand.
In addition to the message sent by the online system, students with disabilities or Specific Learning Disorders (SLD) are invited to directly inform the professor in charge of the course about the special arrangements for the exam that have been agreed with the Special Needs Unit. The professor has to be informed at least one week before the beginning of the examination session in order to provide students with the most suitable arrangements for each specific type of exam.