Timeability of extensive-form games

DOI10.1145/2840728.2840737MaRDI QIDQ2800565zbMATH OpenOpenAlexFDO

Authors Sune Kristian Jakobsen, Troels Bjerre Sørensen, Vincent Conitzer

Publication date 15 April 2016

Published in Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

equilibrium computationcomputational game theory

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Noncooperative games (91A10) (n)-person games, (n>2) (91A06) Games in extensive form (91A18) Games of timing (91A55)

Abstract: Extensive-form games constitute the standard representation scheme for games with a temporal component. But do all extensive-form games correspond to protocols that we can implement in the real world? We often rule out games with imperfect recall, which prescribe that an agent forget something that she knew before. In this paper, we show that even some games with perfect recall can be problematic to implement. Specifically, we show that if the agents have a sense of time passing (say, access to a clock), then some extensive-form games can no longer be implemented; no matter how we attempt to time the game, some information will leak to the agents that they are not supposed to have. We say such a game is not exactly timeable. We provide easy-to-check necessary and sufficient conditions for a game to be exactly timeable. Most of the technical depth of the paper concerns how to approximately time games, which we show can always be done, though it may require large amounts of time. Specifically, we show that for some games the time required to approximately implement the game grows as a power tower of height proportional to the number of players and with a parameter that measures the precision of the approximation at the top of the power tower. In practice, that makes the games untimeable. Besides the conceptual contribution to game theory, we believe our methodology can have applications to preventing information leakage in security protocols.

Recommendations

• On the dispensable role of time in games of perfect information
• A numbers-on-foreheads game
• Players' information in extensive games
• Continuous-time games of timing
• Repeated games in continuous time as extensive form games

Cited in

(6)

• Timed Parity Games: Complexity and Robustness
• A numbers-on-foreheads game
• Expected reachability-time games
• scientific article; zbMATH DE number 3968395 (Why is no real title available?)
• Value functions for depth-limited solving in zero-sum imperfect-information games
• Rethinking formal models of partially observable multiagent decision making

This page was built for publication: Timeability of extensive-form games

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