Algorithmic rationality: game theory with costly computation
From MaRDI portal
Abstract: We develop a general game-theoretic framework for reasoning about strategic agents performing possibly costly computation. In this framework, many traditional game-theoretic results (such as the existence of a Nash equilibrium) no longer hold. Nevertheless, we can use the framework to provide psychologically appealing explanations of observed behavior in well-studied games (such as finitely repeated prisoner's dilemma and rock-paper-scissors). Furthermore, we provide natural conditions on games sufficient to guarantee that equilibria exist.
The article introduces a novel direction in game theory, that of considering computations with a certain cost for the involved players. They also have the option of playing safe and free, but without the possibility of achieving the highest reward. The concepts are nicely introduced through examples, are well explained, but are also accompanied by thoroughly presented, theoretical descriptions. Throughout the article, the reader is often intrigued and challenged by the well-known examples that are adapted to include specific circumstances that help in understanding the presented concepts. Although the article represents a pleasant reading for every researcher in computer science or a connected area, it is more appealing for game theory enthusiasts.
Recommendations
Cites work
- A Memory-Based Model of Bounded Rationality
- A Pseudorandom Generator from any One-way Function
- An Approach to Communication Equilibria
- Bargaining with limited computation: Deliberation equilibrium
- Bounded complexity justifies cooperation in the finitely repeated prisoners' dilemma
- Bounded memory and biases in information processing
- Computationally restricted unmediated talk under incomplete information
- Computing equilibria in multi-player games
- Correlated Equilibrium as an Expression of Bayesian Rationality
- Distributed computing meets game theory
- Extensive games with possibly unaware players
- Finite automata play the repeated prisoner's dilemma
- Foundations of Cryptography
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- scientific article; zbMATH DE number 4202070 (Why is no real title available?)
- scientific article; zbMATH DE number 1759774 (Why is no real title available?)
- scientific article; zbMATH DE number 4197469 (Why is no real title available?)
- scientific article; zbMATH DE number 3068536 (Why is no real title available?)
- scientific article; zbMATH DE number 3078991 (Why is no real title available?)
- Incentive Compatibility and the Bargaining Problem
- LATIN 2004: Theoretical Informatics
- Non-cooperative games
- On complexity as bounded rationality (extended abstract)
- On computable beliefs of rational machines
- PRIMES is in P
- Principles and applications of continual computation
- Rational cooperation in the finitely repeated prisoners' dilemma
- The framing of decisions and the psychology of choice
Cited in
(31)- A computer scientist looks at game theory.
- Bidirectional constraint satisfaction in rational strategic decision making
- Observation, measurement, and computation in finite games
- The weirdness theorem and the origin of quantum paradoxes
- Minting mechanism for proof of stake blockchains
- Introduction to computer science and economic theory
- Game theory on the blockchain: a model for games with smart contracts
- An evidential game theory framework in multi-criteria decision making process
- Universal Computation in the Prisoner’s Dilemma Game
- Beyond Nash equilibrium: solution concepts for the 21st century
- Reflective Oracles: A Foundation for Game Theory in Artificial Intelligence
- Inverse game theory: learning utilities in succinct games
- Rationality authority for provable rational behavior
- Extending the Notion of Rationality of Selfish Agents: Second Order Nash Equilibria
- Bounded rationality, strategy simplification, and equilibrium
- Algorithmic Game Theory: A Snapshot
- Rationality, Computability, and Nash Equilibrium
- scientific article; zbMATH DE number 592681 (Why is no real title available?)
- scientific article; zbMATH DE number 2079853 (Why is no real title available?)
- scientific article; zbMATH DE number 1512638 (Why is no real title available?)
- The Gödelian foundations of self-reference, the liar and incompleteness: arms race in complex strategic innovation
- Probabilistic analysis of simulation-based games
- Translucent players: explaining cooperative behavior in social dilemmas
- A NOTE ON THE EXISTENCE OF RATIFIABLE ACTS
- Rigorous Computer Analysis of the Chow–Robbins Game
- Budget-constrained coalition strategies with discounting
- A probabilistic approach to the game of guessing in a random environment
- Winning without observing payoffs: exploiting behavioral biases to win nearly every round
- Playing repeated games with sublinear randomness
- Program equilibrium
- Outsourcing computation: the minimal refereed mechanism
This page was built for publication: Algorithmic rationality: game theory with costly computation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2253839)
