01TYKPF

A.A. 2019/20

2019/20

Optimal control and game theory

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.

Optimal control and game theory

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.

Optimal control and game theory

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

Optimal control and game theory

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

Optimal control and game 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.

Optimal control and game 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.

Optimal control and game 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.

Optimal control and game 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.

Optimal control and game theory

Optimal control and game theory

Optimal control and game theory

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.

Optimal control and game theory

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.

Optimal control and game theory

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

Optimal control and game theory

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

Optimal control and game theory

**Modalità di esame:** Prova scritta (in aula);

Optimal control and game theory

Optimal control and game theory

**Exam:** Written test;

Optimal control and game theory

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.

© Politecnico di Torino

Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY

Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY