01TYKPF

A.A. 2020/21

Course Language

Inglese

Course degree

Master of science-level of the Bologna process in Physics Of Complex Systems (Fisica Dei Sistemi Complessi) - Torino/Trieste/Parigi

Course structure

Teaching | Hours |
---|---|

Lezioni | 36 |

Esercitazioni in aula | 24 |

Teachers

Teacher | Status | SSD | h.Les | h.Ex | h.Lab | h.Tut | Years teaching |
---|---|---|---|---|---|---|---|

Dall'Asta Luca | Professore Associato | FIS/02 | 24 | 16 | 0 | 0 | 5 |

Teaching assistant

Context

SSD | CFU | Activities | Area context |
---|---|---|---|

ING-INF/04 | 6 | B - Caratterizzanti | Discipline ingegneristiche |

2020/21

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

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

- 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.
- Lecture notes and reading material provided by the teacher.
- 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.

Assessment is performed through one written exam composed of a series of problems to be solved applying the ideas and techniques learned in the course. The problems are similar to those proposed as homework during the course and will cover topics from both game theory and optimal control. More specific information will be provided by the teachers at the beginning of the course.
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.

Assessment is performed through one written exam composed of a series of problems to be solved applying the ideas and techniques learned in the course. The problems are similar to those proposed as homework during the course and will cover topics from both game theory and optimal control. More specific information will be provided by the teachers at the beginning of the course.
Duration of the exam: 2h-2.5h. Students can consult lecture notes/personal notes during the exam.
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.

Assessment is performed through one written exam composed of a series of problems to be solved applying the ideas and techniques learned in the course. The problems are similar to those proposed as homework during the course and will cover topics from both game theory and optimal control. More specific information will be provided by the teachers at the beginning of the course.
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.

Assessment is performed through one written exam composed of a series of problems to be solved applying the ideas and techniques learned in the course. The problems are similar to those proposed as homework during the course and will cover topics from both game theory and optimal control. More specific information will be provided by the teachers at the beginning of the course.
Duration of the exam: 2h-2.5h. Students can consult lecture notes/personal notes during the exam.
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.

© Politecnico di Torino

Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY

Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY