Coalgebraic analysis of subgame-perfect equilibria in infinite games without discounting

DOI10.1017/S0960129515000365zbMATH Open1364.91026DBLPjournals/mscs/AbramskyW17arXiv1210.4537WikidataQ57006399 ScholiaQ57006399MaRDI QIDQ5269005FDOQ5269005

Authors: Samson Abramsky, Viktor Winschel 

Publication date: 14 June 2017

Published in: Mathematical Structures in Computer Science (Search for Journal in Brave)

Abstract: We present a novel coalgebraic formulation of infinite extensive games. We define both the game trees and the strategy profiles by possibly infinite systems of corecursive equations. Certain strategy profiles are proved to be subgame perfect equilibria using a novel proof principle of predicate coinduction. We characterize all subgame perfect equilibria for the dollar auction game. The economically interesting feature is that in order to prove these results we do not need to rely on continuity assumptions on the payoffs which amount to discounting the future. In particular, we prove a form of one-deviation principle without any such assumptions. This suggests that coalgebra supports a more adequate treatment of infinite-horizon models in game theory and economics.

Full work available at URL: https://arxiv.org/abs/1210.4537

Recommendations

• ``Backward coinduction, Nash equilibrium and the rationality of escalation
• Subgame-perfect equilibria of finite- and infinite-horizon games
• On the existence of subgame-perfect equilibrium in infinite-action games of perfect information
• Subgame perfect equilibria in discounted stochastic games
• Non-existence of subgame-perfect \(\varepsilon \)-equilibrium in perfect information games with infinite horizon

Mathematics Subject Classification ID

Auctions, bargaining, bidding and selling, and other market models (91B26) Games in extensive form (91A18)

Cites Work

• Game theory
• Universal coalgebra: A theory of systems
• A lattice-theoretical fixpoint theorem and its applications
• Games with Incomplete Information Played by “Bayesian” Players, I–III Part I. The Basic Model
• Applications of Metric Coinduction
• Subgame-perfect equilibria of finite- and infinite-horizon games
• Coalgebraic logic
• A fixpoint theorem for complete categories
• Title not available (Why is that?)
• Title not available (Why is that?)
• ``Backward coinduction, Nash equilibrium and the rationality of escalation
• Harsanyi type spaces and final coalgebras constructed from satisfied theories
• Categories of coalgebraic games
• Conway games, algebraically and coalgebraically

Cited In (15)

• Coinductive predicates and final sequences in a fibration
• From Lawvere to Brandenburger-Keisler: interactive forms of diagonalization and self-reference
• ``Backward coinduction, Nash equilibrium and the rationality of escalation
• Infinite Horizon Extensive Form Games, Coalgebraically
• A compositional treatment of iterated open games
• Duality, intensionality, and contextuality: philosophy of category theory and the categorical unity of science in Samson Abramsky
• The game semantics of game theory
• Structure in machine learning
• Multigames and strategies, coalgebraically
• A simple case of rationality of escalation
• Long-term values in Markov decision processes, (co)algebraically
• Coinductive predicates and final sequences in a fibration
• Testing randomness by Matching Pennies
• Whither semantics?
• The category of node-and-choice forms, with subcategories for choice-sequence forms and choice-set forms

This page was built for publication: Coalgebraic analysis of subgame-perfect equilibria in infinite games without discounting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5269005)