ABSTRACT
This paper generalises the treatment of compositional game theory as introduced by Ghani et al. in 2018, where games are modelled as morphisms of a symmetric monoidal category. From an economic modelling perspective, the notion of a game in the work by Ghani et al. is not expressive enough for many applications. This includes stochastic environments, stochastic choices by players, as well as incomplete information regarding the game being played. The current paper addresses these three issues all at once.
► BibTeX data
► References
[1] George A. Akerlof. The market for `lemons': Quality uncertainty and the market mechanism. Quarterly Journal of Economics, 84 (3): 488–500, 1970. 10.2307/1879431.
https://doi.org/10.2307/1879431
[2] Jeremy Avigad and Solomon Feferman. Gödel's functional (``Dialectica'') interpretation. In Handbook of proof theory, volume 137 of Studies in logic and the foundations of mathematics, pages 337–405. Elsevier, 1998. 10.2307/420972.
https://doi.org/10.2307/420972
[3] Joe Bolt. Probability and nondeterminism in compositional game theory. PhD thesis, University of Oxford, 2019.
[4] Colin F Camerer. Behavioral game theory: Experiments in strategic interaction. Princeton University Press, 2011.
[5] Valeria de Paiva. The dialectica categories. Technical report, University of Cambridge, 1991.
[6] Martin Escardó and Paulo Oliva. Selection functions, bar recursion and backward induction. Mathematical Structures in Computer Science, 20 (2): 127–168, 2010. 10.1017/S0960129509990351.
https://doi.org/10.1017/S0960129509990351
[7] Brendan Fong. The algebra of open and interconnected systems. PhD thesis, University of Oxford, 2016.
[8] Brendan Fong, David Spivak, and Rémy Tuyéras. Backprop as functor: A compositional perspective on supervised learning. In Proceedings of Logic in Computer Science (LiCS) 2019. ACM, 2019. 10.1109/LICS.2019.8785665.
https://doi.org/10.1109/LICS.2019.8785665
[9] Nate Foster, Michael Greenwald, Jonathan Moore, Benjamin Pierce, and Alan Schmitt. Combinators for bi-directional tree transformations: A linguistic approach to the view update problem. ACM Transactions on Programming Languages and Systems, 29 (3), 2007. 10.1145/1232420.1232424.
https://doi.org/10.1145/1232420.1232424
[10] Tobias Fritz. A synthetic approach to Markov kernels, conditional independence and theorems on sufficient statistics. Advances in Mathematics, 370, 2020. 10.1016/j.aim.2020.107239.
https://doi.org/10.1016/j.aim.2020.107239
[11] Tobias Fritz and Paolo Perrone. A probability monad as the colimit of spaces of finite samples. Theory and Applications of Categories, 34 (7), 2019.
[12] Drew Fudenberg and Jean Tirole. Game theory. MIT Press, 1991.
[13] Neil Ghani, Jules Hedges, Viktor Winschel, and Philipp Zahn. Compositional game theory. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, pages 472–481. ACM, 2018a. 10.1145/3209108.3209165.
https://doi.org/10.1145/3209108.3209165
[14] Neil Ghani, Clemens Kupke, Alasdair Lambert, and Fredrik Nordvall Forsberg. A compositional treatment of iterated open games. Theoretical Computer Science, 741: 48 – 57, 2018b. ISSN 0304-3975. 10.1016/j.tcs.2018.05.026. An Observant Mind : Essays Dedicated to Don Sannella on the Occasion of his 60th Birthday.
https://doi.org/10.1016/j.tcs.2018.05.026
[15] Neil Ghani, Clemens Kupke, Alasdair Lambert, and Fredrik Nordvall Forsberg. Compositional game theory with mixed strategies: Probabilistic open games using a distributive law. In Proceedings of ACT 2019, volume 323 of Electronic Proceedings in Theoretical Computer Science, 2020. 10.4204/EPTCS.323.7.
https://doi.org/10.4204/EPTCS.323.7
[16] Michèlle Giry. A categorical approach to probability theory. Categorical aspects of topology and analysis, pages 68–85, 1982. 10.1007/BFb0092872.
https://doi.org/10.1007/BFb0092872
[17] John C Harsanyi. Games with incomplete information played by ``Bayesian'' players, I–III Part I. The basic model. Management Science, 14 (3): 159–182, 1967. 10.1287/mnsc.14.3.159.
https://doi.org/10.1287/mnsc.14.3.159
[18] John C Harsanyi. Games with incomplete information played by ``Bayesian'' players part II. Bayesian equilibrium points. Management Science, 14 (5): 320–334, 1968a. 10.1287/mnsc.14.5.320.
https://doi.org/10.1287/mnsc.14.5.320
[19] John C Harsanyi. Games with incomplete information played by ``Bayesian'' players, part III. The basic probability distribution of the game. Management Science, 14 (7): 486–502, 1968b. 10.1287/mnsc.14.7.486.
https://doi.org/10.1287/mnsc.14.7.486
[20] Jules Hedges. Towards compositional game theory. PhD thesis, Queen Mary University of London, 2016.
[21] Jules Hedges. Coherence for lenses and open games. arXiv:1704.02230, 2017. 10.48550/arXiv.1704.02230.
https://doi.org/10.48550/arXiv.1704.02230
arXiv:1704.02230
[22] Jules Hedges. Morphisms of open games. Electronic Notes in Theoretical Computer Science, 341: 151 – 177, 2018a. ISSN 1571-0661. 10.1016/j.entcs.2018.11.008. Proceedings of the Thirty-Fourth Conference on the Mathematical Foundations of Programming Semantics (MFPS XXXIV).
https://doi.org/10.1016/j.entcs.2018.11.008
[23] Jules Hedges, Paulo Oliva, Evguenia Shprits, Viktor Winschel, and Philipp Zahn. Higher-order decision theory. In International Conference on Algorithmic DecisionTheory, pages 241–254. Springer, 2017a. 10.1007/978-3-319-67504-6_17.
https://doi.org/10.1007/978-3-319-67504-6_17
[24] Jules Hedges, Paulo Oliva, Evguenia Shprits, Viktor Winschel, and Philipp Zahn. Selection equilibria of higher-order games. In International Symposium on Practical Aspects of Declarative Languages, pages 136–151. Springer, 2017b. 10.1007/978-3-319-51676-9_9.
https://doi.org/10.1007/978-3-319-51676-9_9
[25] Julian Hedges. Lenses for philosophers, 2018b. Available at https://julesh.com/2018/08/16/lenses-for-philosophers/.
https://julesh.com/2018/08/16/lenses-for-philosophers/
[26] Martin Hofmann and Benjamin Pierce. Positive subtyping. Information and Computation, 126: 11–33, 1996. 10.1006/inco.1996.0031.
https://doi.org/10.1006/inco.1996.0031
[27] F. Loregian. Coend Calculus, volume 468 of London Mathematical Society Lecture Note Series. Cambridge University Press, first edition, 07 2021. 10.1017/9781108778657.
https://doi.org/10.1017/9781108778657
[28] Andreu Mas-Colell, Michael D. Whinston, and Jerry Green. Microeconomic Theory. Oxford University Press, 1995. ISBN 0195102681.
[29] Michael Maschler, Eilon Solan, and Shmuel Zamir. Game Theory. Cambridge University Press, 2013. 10.1017/CBO9780511794216.
https://doi.org/10.1017/CBO9780511794216
[30] John Nash. Equilibrium points in $n$-person games. Proceedings of the national academy of sciences, 36 (1): 48–49, 1950. 10.1073/pnas.36.1.48.
https://doi.org/10.1073/pnas.36.1.48
[31] John Von Neumann and Oskar Morgenstern. Theory of games and economic behavior. Princeton university press, 1944.
[32] Frank Oles. A category-theoretic approach to the semantics of programming languages. PhD thesis, Syracuse University, 1982.
[33] Martin J Osborne and Ariel Rubinstein. A course in game theory. MIT press, 1994.
[34] Luke Palmer. Making Haskell nicer for game programming. Available at https://lukepalmer.wordpress.com/2007/07/26/making-haskell-nicer-for-game-programming/, 2007.
https://lukepalmer.wordpress.com/2007/07/26/making-haskell-nicer-for-game-programming/
[35] John Power and Edmund Robinson. Premonoidal categories and notions of computation. Mathematical Structures in Computer Science, 7 (5): 453–468, 1997. 10.1017/S0960129597002375.
https://doi.org/10.1017/S0960129597002375
[36] Mitchell Riley. Categories of optics. arXiv:1809.00738v2, 2018.
arXiv:1809.00738v2
[37] Mario Román. Open diagrams via coend calculus. In Proceedings of Applied Category Theory 2020, volume 333 of Electronic Proceedings in Theoretical Computer Science, 2021. 10.4204/EPTCS.333.5.
https://doi.org/10.4204/EPTCS.333.5
[38] T. Świrszcz. Monadic functors and convexity. Bulletin de l'Acaédemie Polonaise des Sciences, 22 (1), 1974.
[39] Category Theory Zulip. Change of domain for coends. Archived at https://mattecapu.github.io/ct-zulip-archive/stream/229199-learning:-questions/topic/topic_.22change.20of.20domain.22.20for.20coends.html, 2021.
https://mattecapu.github.io/ct-zulip-archive/stream/229199-learning:-questions/topic/topic_.22change.20of.20domain.22.20for.20coends.html
Cited by
Could not fetch Crossref cited-by data during last attempt 2024-11-20 22:25:01: Could not fetch cited-by data for 10.32408/compositionality-5-9 from Crossref. This is normal if the DOI was registered recently. On SAO/NASA ADS no data on citing works was found (last attempt 2024-11-20 22:32:39).
This Paper is published in Compositionality under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.