1932
0
  1. Home
  2. A-Z Publications
  3. Annual Review of Control, Robotics, and Autonomous Systems
  4. Volume 1, 2018
  5. Article

Annual Review of Control, Robotics, and Autonomous Systems

Volume 1, 2018

Game Theory and Control

Abstract

Game theory is the study of decision problems in which there are multiple decision makers and the quality of a decision maker's choice depends on both that choice and the choices of others. While game theory has been studied predominantly as a modeling paradigm in the mathematical social sciences, there is a strong connection to control systems in that a controller can be viewed as a decision-making entity. Accordingly, game theory is relevant in settings with multiple interacting controllers. This article presents an introduction to game theory, followed by a sampling of results in three specific control theory topics where game theory has played a significant role: () zero-sum games, in which the two competing players are a controller and an adversarial environment; () team games, in which several controllers pursue a common goal but have access to different information; and () distributed control, in which both a game and online adaptive rules are designed to enable distributed interacting subsystems to achieve a collective objective.

Keyword(s): distributed control, game theory, learning in games, mechanism design, team games, zero-sum games
Loading

Article metrics loading...

/content/journals/10.1146/annurev-control-060117-105102
2018-05-28
2024-04-19
Loading full text...

Full text loading...

/deliver/fulltext/control/1/1/annurev-control-060117-105102.html?itemId=/content/journals/10.1146/annurev-control-060117-105102&mimeType=html&fmt=ahah

Literature Cited

  1. 1.  Myerson R 1997. Game Theory Cambridge, MA: Harvard Univ. Press
  2. 2.  Zhou K, Doyle J 1998. Essentials of Robust Control Upper Saddle River, NJ: Prentice Hall
  3. 3.  Marden JR, Shamma JS 2015. Game theory and distributed control. Handbook of Game Theory with Economic Applications 4 H Young, S Zamir 861–99 Amsterdam, Neth.: Elsevier
     [Google Scholar]
  4. 4.  Marden JR, Shamma JS 2018. Game-theoretic learning in distributed control. Handbook of Dynamic Game Theory T Başar, G Zaccour. Cham Switz.: Springer. In press
     [Google Scholar]
  5. 5.  Fudenberg D, Tirole J 1991. Game Theory Cambridge, MA: MIT Press
  6. 6.  Osborne M, Rubinstein A 1994. A Course in Game Theory Cambridge, MA: MIT Press
  7. 7.  Cesa-Bianchi N, Lugosi G 2006. Prediction, Learning, and Games Cambridge, UK: Cambridge Univ. Press
  8. 8.  Leyton-Brown K, Shoham Y 2008. Essentials of Game Theory: A Concise, Multidisciplinary Introduction San Rafael, CA: Morgan & Claypool
  9. 9.  Nisan N, Roughgarden T, Tardos E, Vazirani VV 2007. Algorithmic Game Theory Cambridge, UK: Cambridge Univ. Press
  10. 10.  Başar T, Olsder G 1999. Dynamic Noncooperative Game Theory Philadelphia, PA: Soc. Ind. Appl. Math.
  11. 11.  Bauso D 2016. Game Theory with Engineering Applications Philadelphia, PA: Soc. Ind. Appl. Math.
  12. 12.  Hespanha J 2017. Noncooperative Game Theory: An Introduction for Engineers and Computer Scientists Princeton, NJ: Princeton Univ. Press
  13. 13.  Roughgarden T 2005. Selfish Routing and the Price of Anarchy Cambridge, MA: MIT Press
  14. 14.  Camerer C 2003. Behavioral Game Theory: Experiments in Strategic Interaction Princeton, NJ: Princeton Univ. Press
  15. 15.  Rubinstein A 1998. Modeling Bounded Rationality Cambridge, MA: MIT Press
  16. 16.  Ho Y, Bryson A, Baron S 1965. Differential games and optimal pursuit-evasion strategies. IEEE Trans. Automat. Control 10:385–89
     [Google Scholar]
  17. 17.  Isaacs R 1965. Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization New York: Wiley
  18. 18.  Liberzon D 2012. Calculus of Variations and Optimal Control Theory: A Concise Introduction Princeton, NJ: Princeton Univ. Press
  19. 19.  Blanchini F, Miani S 2007. Set-Theoretic Methods in Control Basel, Switz.: Birkhäuser
  20. 20.  Aubin J 1991. Viability Theory Basel, Switz.: Birkhäuser
  21. 21.  Mitchell IM, Bayen AM, Tomlin CJ 2005. A time-dependent Hamilton-Jacobi formulation of reachable sets for continuous dynamic games. IEEE Trans. Automat. Control 50:947–57
     [Google Scholar]
  22. 22.  Zhou Z, Zhang W, Ding J, Huang H, Stipanović DM, Tomlin CJ 2016. Cooperative pursuit with Voronoi partitions. Automatica 72:64–72
     [Google Scholar]
  23. 23.  Karaman S, Frazzoli E 2011. Incremental sampling-based algorithms for a class of pursuit-evasion games. In Algorithmic Foundations of Robotics IX: Selected Contributions of the Ninth International Workshop on the Algorithmic Foundations of Robotics D Hsu, V Isler, JC Latombe, MC Lin 71–87 Berlin: Springer
     [Google Scholar]
  24. 24.  Isler V, Kannan S, Khanna S 2005. Randomized pursuit-evasion in a polygonal environment. IEEE Trans. Robot. 21:875–84
     [Google Scholar]
  25. 25.  Zames G 1981. Feedback and optimal sensitivity: model reference transformations, multiplicative seminorms, and approximate inverses. IEEE Trans. Automat. Control 26:301–20
     [Google Scholar]
  26. 26.  Başar T, Bernhard P 1991. H-Infinity-Optimal Control and Related Minimax Design Problems Basel, Switz.: Birkhäuser
  27. 27.  Doyle J, Francis B, Tannenbaum A 2009. Feedback Control Theory Mineola, NY: Dover
  28. 28.  Banavar RN, Speyer JL 1991. A linear-quadratic game approach to estimation and smoothing. 1991 American Control Conference (ACC)2818–22 New York: IEEE
     [Google Scholar]
  29. 29.  Limebeer DJN, Anderson BDO, Khargonekar PP, Green M 1992. A game theoretic approach to control for time-varying systems. SIAM J. Control Optim. 30:262–83
     [Google Scholar]
  30. 30.  Engwerda J 2005. LQ Dynamic Optimization and Differential Games Hoboken, NJ: Wiley
  31. 31.  Bertsekas D, Rhodes I 1971. On the minimax reachability of target sets and target tubes. Automatica 7:233–47
     [Google Scholar]
  32. 32.  Bertsekas D 1972. Infinite time reachability of state-space regions by using feedback control. IEEE Trans. Automat. Control 17:604–13
     [Google Scholar]
  33. 33.  Bertsekas D 2005. Dynamic Programming and Optimal Control Belmont, MA: Athena Sci.
  34. 34.  Dahleh M, Diaz-Bobillo I 1995. Control of Uncertain Systems: A Linear Programming Approach Upper Saddle River, NJ: Prentice Hall
  35. 35.  Shamma JS 1993. Nonlinear state feedback for ℓ1 optimal control. Syst. Control Lett. 21:265–70
     [Google Scholar]
  36. 36.  Shamma JS 1996. Optimization of the ℓ∞-induced norm under full state feedback. IEEE Trans. Automat. Control 41:533–44
     [Google Scholar]
  37. 37.  Shamma JS 2012. An overview of LPV systems. Control of Linear Parameter Varying Systems with Applications J Mohammadpour, CW Scherer 3–26 Boston: Springer
     [Google Scholar]
  38. 38.  Shamma JS, Xiong D 1999. Set-valued methods for linear parameter varying systems. Automatica 35:1081–89
     [Google Scholar]
  39. 39.  Aumann RJ, Maschler M, Stearns RE 1995. Repeated Games with Incomplete Information Cambridge, MA: MIT Press
  40. 40.  Mertens J, Sorin S, Zamir S 2015. Repeated Games Cambridge, UK: Cambridge Univ. Press
  41. 41.  Smith JC, Prince M, Geunes J 2013. Modern network interdiction problems and algorithms. Handbook of Combinatorial Optimization PM Pardalos, DZ Du, RL Graham 1949–87 New York: Springer
     [Google Scholar]
  42. 42.  Zheng J, Castañón DA 2012. Stochastic dynamic network interdiction games. 2012 American Control Conference (ACC)1838–44 New York: IEEE
     [Google Scholar]
  43. 43.  Zheng J, Castañón DA 2012. Dynamic network interdiction games with imperfect information and deception. 2012 51st Annual IEEE Conference on Decision and Control (CDC)7758–63 New York: IEEE
     [Google Scholar]
  44. 44.  Alpcan T, Başar T 2010. Network Security: A Decision and Game-Theoretic Approach Cambridge, UK: Cambridge Univ. Press
  45. 45.  Li L, Shamma JS 2015. Efficient computation of discounted asymmetric information zero-sum stochastic games. 2015 54th Annual IEEE Conference on Decision and Control (CDC)4531–36 New York: IEEE
     [Google Scholar]
  46. 46.  Li L, Langbort C, Shamma J 2017. Computing security strategies in finite horizon repeated bayesian games. 2017 American Control Conference (ACC)3664–69 New York: IEEE
     [Google Scholar]
  47. 47.  Ho YC 1980. Team decision theory and information structures. Proc. IEEE 68:644–54
     [Google Scholar]
  48. 48.  Lewis FL, Zhang H, Hengster-Movric K, Das A 2013. Cooperative Control of Multi-Agent Systems: Optimal and Adaptive Design Approaches New York: Springer
  49. 49.  Shamma JS 2008. Cooperative Control of Distributed Multi-Agent Systems Hoboken, NJ: Wiley
  50. 50.  van Schuppen J, Villa T 2014. Coordination Control of Distributed Systems Cham, Switz.: Springer
  51. 51.  Wang Y, Zhang F 2017. Cooperative Control of Multi-Agent Systems: Theory and Applications Hoboken, NJ: Wiley
  52. 52.  Radner R 1962. Team decision problems. Ann. Math. Stat. 33:857–81
     [Google Scholar]
  53. 53.  Witsenhausen HS 1968. A counterexample in stochastic optimum control. SIAM J. Control 6:131–47
     [Google Scholar]
  54. 54.  Başar T 2008. Variations on the theme of the Witsenhausen counterexample. 2008 47th IEEE Conference on Decision and Control1614–19 New York: IEEE
     [Google Scholar]
  55. 55.  Ho YC, Chu K 1974. Information structure in dynamic multi-person control problems. Automatica 10:341–51
     [Google Scholar]
  56. 56.  Nayyar A, Mahajan A, Teneketzis D 2013. Decentralized stochastic control with partial history sharing: a common information approach. IEEE Trans. Autom. Control 58:1644–58
     [Google Scholar]
  57. 57.  Nayyar A, Mahajan A, Teneketzis D 2014. The common-information approach to decentralized stochastic control. Information and Control in Networks G Como, B Bernhardsson, A Rantzer 123–56 Cham, Switz.: Springer
     [Google Scholar]
  58. 58.  Kurtaran BZ, Sivan R 1974. Linear-quadratic-Gaussian control with one-step-delay sharing pattern. IEEE Trans. Autom. Control 19:571–74
     [Google Scholar]
  59. 59.  Sandell N, Athans M 1974. Solution of some nonclassical LQG stochastic decision problems. IEEE Trans. Autom. Control 19:108–16
     [Google Scholar]
  60. 60.  Nayyar N, Kalathil D, Jain R 2018. Optimal decentralized control with asymmetric one-step delayed information sharing. IEEE Trans. Control Netw. Syst. 5:653–63
     [Google Scholar]
  61. 61.  Bamieh B, Voulgaris PG 2005. A convex characterization of distributed control problems in spatially invariant systems with communication constraints. Syst. Control Lett. 54:575–83
     [Google Scholar]
  62. 62.  Rotkowitz M, Lall S 2006. A characterization of convex problems in decentralized control. IEEE Trans. Autom. Control 51:274–86
     [Google Scholar]
  63. 63.  Roughgarden T 2005. Selfish Routing and the Price of Anarchy Cambridge, MA: MIT Press
  64. 64.  Brown PN, Marden JR 2017. Studies on robust social influence mechanisms, incentives for efficient network routing in uncertain settings. IEEE Control Syst. Mag. 37:98–115
     [Google Scholar]
  65. 65.  Lasaulce S, Jimenez T, Solan E 2017. Network Games, Control, and Optimization: Proceedings of NETGCOOP 2016, Avignon, France Basel, Switz.: Birkhaüser
  66. 66.  Ozdaglar A, Menache I 2011. Network Games: Theory, Models, and Dynamics San Rafael, CA: Morgan & Claypool
  67. 67.  Marden JR, Ruben S, Pao L 2013. A model-free approach to wind farm control using game theoretic methods. IEEE Trans. Control Syst. Technol. 21:1207–14
     [Google Scholar]
  68. 68.  Johnson KE, Thomas N 2009. Wind farm control: addressing the aerodynamic interaction among wind turbines. 2009 American Control Conference2104–9 New York: IEEE
     [Google Scholar]
  69. 69.  Steinbuch M, de Boer WW, Bosgra OH, Peters S, Ploeg J 1998. Optimal control of wind power plants. J. Wind Eng. Ind. Aerodyn. 27:237–46
     [Google Scholar]
  70. 70.  Pao L, Johnson KE 2009. A tutorial on the dynamics and control of wind turbines and wind farms. 2009 American Control Conference35–36 New York: IEEE
     [Google Scholar]
  71. 71.  Cortes J, Martinez S, Karatas T, Bullo F 2004. Coverage control for mobile sensing networks. IEEE Trans. Robot. Autom. 20:243–55
     [Google Scholar]
  72. 72.  Marden JR, Arslan G, Shamma JS 2009. Cooperative control and potential games. IEEE Trans. Syst. Man Cybernet. B 39:1393–407
     [Google Scholar]
  73. 73.  Yazicioglu AY, Egerstedt M, Shamma JS 2016. Communication-free distributed coverage for networked systems. IEEE Trans. Control Netw. Syst. 4:499–510
     [Google Scholar]
  74. 74.  Fudenberg D, Levine D 1998. The Theory of Learning in Games Cambridge, MA: MIT Press
  75. 75.  Hart S, Mas-Colell A 2003. Uncoupled dynamics do not lead to Nash equilibrium. Am. Econ. Rev. 93:1830–36
     [Google Scholar]
  76. 76.  Marden JR, Young HP, Arslan G, Shamma JS 2009. Payoff based dynamics for multi-player weakly acyclic games. SIAM J. Control Optim. 48:373–96
     [Google Scholar]
  77. 77.  Babichenko Y 2010. Completely uncoupled dynamics and Nash equilibria Discuss. Pap., Cent. Study Ration., Hebrew Univ Jerusalem:
  78. 78.  Hart S 2005. Adaptive heuristics. Econometrica 73:1401–30
     [Google Scholar]
  79. 79.  Young HP 2005. Strategic Learning and Its Limits Oxford, UK: Oxford Univ. Press
  80. 80.  Shamma JS, Arslan G 2005. Dynamic fictitious play, dynamic gradient play, and distributed convergence to Nash equilibria. IEEE Trans. Autom. Control 50:312–27
     [Google Scholar]
  81. 81.  Fox MJ, Shamma JS 2013. Population games, stable games, and passivity. Games 4:561–83
     [Google Scholar]
  82. 82.  Frihauf P, Krstic M, Başar T 2012. Nash equilibrium seeking in noncooperative games. IEEE Trans. Autom. Control 57:1192–207
     [Google Scholar]
  83. 83.  Monderer D, Shapley L 1996. Potential games. Games Econ. Behav. 14:124–43
     [Google Scholar]
  84. 84.  Blume L 1993. The statistical mechanics of strategic interaction. Games Econ. Behav. 5:387–424
     [Google Scholar]
  85. 85.  Blume L 1997. Population games. The Economy as an Evolving Complex System II B Arthur, S Durlauf, D Lane 425–60 Reading, MA: Addison-Wesley
     [Google Scholar]
  86. 86.  Marden JR, Shamma JS 2012. Revisiting log-linear learning: asynchrony, completeness and a payoff-based implementation. Games Econ. Behav. 75:788–808
     [Google Scholar]
  87. 87.  Alos-Ferrer C, Netzer N 2010. The logit-response dynamics. Games Econ. Behav. 68:413–27
     [Google Scholar]
  88. 88.  Koutsoupias E, Papadimitriou C 1999. Worst-case equilibria. STACS 99: 16th Annual Symposium on Theoretical Aspects of Computer Science, Trier, Germany, March 4–6, 1999: Proceedings C Meinel, S Tison 404–13 Berlin: Springer
     [Google Scholar]
  89. 89.  Wolpert D 2004. Theory of collective intelligence. Collectives and the Design of Complex Systems K Tumer, D Wolpert 43–106 New York: Springer
     [Google Scholar]
  90. 90.  Arslan G, Marden JR, Shamma JS 2007. Autonomous vehicle-target assignment: a game theoretical formulation. ASME J. Dyn. Syst. Meas. Control 129:584–96
     [Google Scholar]
  91. 91.  Marden JR, Wierman A 2013. Distributed welfare games. Oper. Res. 61:155–68
     [Google Scholar]
  92. 92.  Gopalakrishnan R, Marden JR, Wierman A 2011. An architectural view of game theoretic control. ACM SIGMETRICS Perf. Eval. Rev. 38:31–36
     [Google Scholar]
  93. 93.  Phillips M, Shalaby Y, Marden JR 2016. The importance of budget in efficient utility design. 2016 55th Annual IEEE Conference on Decision and Control (CDC)6117–22 New York: IEEE
     [Google Scholar]
  94. 94.  Marden J, Phillips M 2016. Optimizing the price of anarchy in concave cost sharing games. 2017 American Control Conference (ACC)5237–42 New York: IEEE
     [Google Scholar]
  95. 95.  Marden J, Roughgarden T 2014. Generalized efficiency bounds in distributed resource allocation. IEEE Trans. Autom. Control 59:571–84
     [Google Scholar]
  96. 96.  Vetta A 2002. Nash equilibria in competitive societies with applications to facility location, traffic routing, and auctions. 43rd Annual IEEE Symposium on Foundations of Computer Science416–25 New York: IEEE
     [Google Scholar]
  97. 97.  Marden JR, Effros M 2012. The price of selfishness in network coding. IEEE Trans. Inform. Theory 58:2349–61
     [Google Scholar]
  98. 98.  Gairing M 2009. Covering games: approximation through noncooperation. Internet and Network Economics: 5th International Workshop, WINE 2009, Rome, Italy, December 14–18, 2009: Proceedings S Leonardi 184–95 Berlin: Springer
     [Google Scholar]
  99. 99.  Brown PN, Marden JR 2016. Optimal mechanisms for robust coordination in congestion games. 2015 54th Annual IEEE Conference on Decision and Control (CDC)2283–88 New York: IEEE
     [Google Scholar]
  100. 100.  Chen HL, Roughgarden T, Valiant G 2008. Designing networks with good equilibria. Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '08)854–63 New York: IEEE
     [Google Scholar]
  101. 101.  Gkatzelis V, Kollias K, Roughgarden T 2016. Optimal cost-sharing in general resource selection games. Oper. Res. 64:1230–38
     [Google Scholar]
  102. 102.  Dobzinski S, Mehta A, Roughgarden T, Sundararajan M 2017. Is Shapley cost sharing optimal?. Games Econ. Behav. In press
  103. 103.  Gopalakrishnan R, Marden JR, Wierman A 2014. Potential games are necessary to ensure pure Nash equilibria in cost sharing games. Math. Oper. Res. 39:1252–96
     [Google Scholar]
  104. 104.  Marden JR 2012. State based potential games. Automatica 48:3075–88
     [Google Scholar]
  105. 105.  Li N, Marden JR 2013. Designing games for distributed optimization. IEEE J. Sel. Top. Signal Process. 7:230–42
     [Google Scholar]
  106. 106.  Li N, Marden JR 2010. Designing games to handle coupled constraints. 2010 49th Annual IEEE Conference on Decision and Control (CDC)250–55 New York: IEEE
     [Google Scholar]
  107. 107.  Solan E, Vieille N 2015. Stochastic games. PNAS 112:13743–46
     [Google Scholar]
  108. 108.  Dudebout N, Shamma JS 2012. Empirical evidence equilibria in stochastic games. 2012 51st Annual IEEE Conference on Decision and Control (CDC)5780–85 New York: IEEE
     [Google Scholar]
  109. 109.  Dudebout N, Shamma JS 2014. Exogenous empirical-evidence equilibria in perfect-monitoring repeated games yield correlated equilibria. 2014 53rd Annual IEEE Conference on Decision and Control (CDC)1167–72 New York: IEEE
     [Google Scholar]
  110. 110.  Arslan G, Yksel S 2017. Decentralized Q-learning for stochastic teams and games. IEEE Trans. Autom. Control 62:1545–58
     [Google Scholar]
  111. 111.  Yu CK, van der Schaar M, Sayed AH 2017. Distributed learning for stochastic generalized Nash equilibrium problems. IEEE Trans. Signal Process. 65:3893–908
     [Google Scholar]
  112. 112.  Sandholm W 2010. Population Games and Evolutionary Dynamics Cambridge, MA: MIT Press
  113. 113.  Quijano N, Ocampo-Martinez C, Barreiro-Gomez J, Obando G, Pantoja A, Mojica-Nava E 2017. The role of population games and evolutionary dynamics in distributed control systems: the advantages of evolutionary game theory. IEEE Control Syst 37:70–97
     [Google Scholar]
  114. 114.  Caines PE 2013. Mean field games. Encyclopedia of Systems and Control J Baillieul, T Samad 1–6 London: Springer
     [Google Scholar]
  115. 115.  Hamza D, Shamma JS 2017. BLMA: a blind matching algorithm with application to cognitive radio networks. IEEE J. Sel. Areas Commun. 35:302–16
     [Google Scholar]
  116. 116.  Saad W, Han Z, Debbah M, Hjorungnes A, Basar T 2009. Coalitional game theory for communication networks. IEEE Signal Process. Mag. 26:77–97
     [Google Scholar]
  117. 117.  Saad W, Han Z, Poor HV 2011. Coalitional game theory for cooperative micro-grid distribution networks. 2011 IEEE International Conference on Communications Workshops (ICC) New York: IEEE https://doi.org/10.1109/iccw.2011.5963577
    [Crossref] [Google Scholar]
  118. 118.  Fele F, Maestre JM, Camacho EF 2017. Coalitional control: cooperative game theory and control. IEEE Control Syst 37:53–69
     [Google Scholar]
/content/journals/10.1146/annurev-control-060117-105102
Loading
Game Theory and Control
Annual Review of Control, Robotics, and Autonomous Systems 1, 105 (2018); https://doi.org/10.1146/annurev-control-060117-105102
/content/journals/10.1146/annurev-control-060117-105102
/content/journals/10.1146/annurev-control-060117-105102
Loading

Data & Media loading...

  • Article Type: Review Article

Most Cited Most Cited RSS feed

This is a required field
Please enter a valid email address
Approval was a Success
Invalid data
An Error Occurred
Approval was partially successful, following selected items could not be processed due to error