ABSTRACT
We introduce open games as a compositional foundation of economic game theory. A compositional approach potentially allows methods of game theory and theoretical computer science to be applied to large-scale economic models for which standard economic tools are not practical. An open game represents a game played relative to an arbitrary environment and to this end we introduce the concept of coutility, which is the utility generated by an open game and returned to its environment. Open games are the morphisms of a symmetric monoidal category and can therefore be composed by categorical composition into sequential move games and by monoidal products into simultaneous move games. Open games can be represented by string diagrams which provide an intuitive but formal visualisation of the information flows. We show that a variety of games can be faithfully represented as open games in the sense of having the same Nash equilibria and off-equilibrium best responses.
- Samson Abramsky. 2005. Abstract scalars, loops, and free traced and strongly compact closed categories. In Proceedings of CALCO'05 (Lectures notes in computer science), Vol. 3629. 1--29. Google ScholarDigital Library
- Achim Blumensath and Viktor Winschel. 2013. A Compositional Coalgebraic Semantics of Strategic Games. (2013). arXiv:1712.08381.Google Scholar
- Bob Coecke and Aleks Kissinger. 2017. Picturing quantum processes. Cambridge University Press.Google Scholar
- Martin Escardó and Paulo Oliva. 2011. Sequential games and optimal strategies. Proceedings of the Royal Society A 467 (2011), 1519--1545.Google ScholarCross Ref
- Martin Escardó and Paulo Oliva. 2012. Computing Nash equilibria of unbounded games. Proceedings of the Turing centenary conference (2012).Google Scholar
- Brendan Fong. 2016. The algebra of open and interconnected systems. Ph.D. Dissertation. University of Oxford.Google Scholar
- Brendan Fong, David Spivak, and Rémy Tuyéras. 2017. Backprop as functor: A compositional perspective on supervised learning. (2017). arXiv:1711.10455.Google Scholar
- Neil Ghani, Clemens Kupke, Alasdair Lambert, and Fredrik Nordvall Forsberg. 2018. A compositional treatment of iterated open games. (2018). To appear in Sannellabration!, special issue of Theoretical computer science.Google Scholar
- Jules Hedges. 2016. Towards compositional game theory. Ph.D. Dissertation. Queen Mary University of London.Google Scholar
- Jules Hedges. 2017. Coherence for lenses and open games. (2017). arXiv:1704.02230.Google Scholar
- Jules Hedges. 2017. Morphisms of open games. (2017). arXiv:1711.07059.Google Scholar
- Jules Hedges, Paulo Oliva, Evguenia Shprits, Viktor Winschel, and Philipp Zahn. 2017. Higher-order decision theory. In Algorithmic Decision Theory (Lecture Notes in Artificial Intelligence), Jörg Rothe (Ed.), Vol. 10576. Springer, 241--254.Google Scholar
- Jules Hedges, Paulo Oliva, Evguenia Shprits, Viktor Winschel, and Philipp Zahn. 2017. Selection equilibria of higher-order games. In Practical aspects of declaritive languages (Lecture Notes in Computer Science), Yuliya Lierler and Walid Taha (Eds.), Vol. 10137. Springer, 136--151.Google Scholar
- Kevin Leyton-Brown and Yoav Shoham. 2008. Essentials of game theory: a concice, multidisciplinary introduction. Morgan and Claypool. Google ScholarDigital Library
- Lawrence S. Moss and Ignacio D. Viglizzo. 2004. Harsanyi Type Spaces and Final Coalgebras Constructed from Satisfied Theories. Electronic Notes in Theoretical Computer Science 106 (2004), 279--295. Proceedings of the Workshop on Coalgebraic Methods in Computer Science (CMCS).Google ScholarDigital Library
- Roger B. Myerson. 1991. Game theory: analysis of conflict. Cambridge: Harvard University Press USA.Google Scholar
- Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V Vazirani. 2007. Algorithmic Game Theory. Cambridge University Press, New York, NY, USA. Google ScholarDigital Library
- Dusko Pavlovic. 2009. A semantical approach to equilibria and rationality. In Algebra and coalgebra in computer science (Lectures notes in computer science), Vol. 5728. Springer, 317--334. Google ScholarDigital Library
- Matthew Pickering, Jeremy Gibbons, and Nicolas Wu. 2017. Profunctor optics: Modular data accessors. The art, science and engineering of programming 1, 2 (2017).Google Scholar
- Peter Selinger. 2011. A survey of graphical languages for monoidal categories. In New structures for physics, Bob Coecke (Ed.). Springer, 289--355.Google Scholar
- Michael Shulman. 2010. Constructing symmetric monoidal bicategories. (2010). arXiv:1004.0993.Google Scholar
- Jan Willems. 2007. The behavioural approach to open and interconnected systems. IEEE Control Systems 27, 6 (2007), 46--99.Google ScholarCross Ref
- Viktor Winschel and Markus Krätzig. 2010. Solving, Estimating, and Selecting Nonlinear Dynamic Models Without the Curse of Dimensionality. Econometrica 78, 2 (2010), 803--821.Google ScholarCross Ref
Recommendations
Discovering theorems in game theory: Two-person games with unique pure Nash equilibrium payoffs
In this paper we provide a logical framework for two-person finite games in strategic form, and use it to design a computer program for discovering some classes of games that have unique pure Nash equilibrium payoffs. The classes of games that we ...
Discovering theorems in game theory: two-person games with unique pure nash equilibrium payoffs
IJCAI'09: Proceedings of the 21st International Joint Conference on Artificial IntelligenceIn this paper we provide a logical framework for using computers to discover theorems in two-person finite games in strategic form, and apply it to discover classes of games that have unique pure Nash equilibrium payoffs. We consider all possible ...
Comments