Time and the Prisoner's Dilemma

This paper examines the integration of computational complexity into game theoretic models. The example focused on is the Prisoner’s Dilemma, repeated for a finite length of time. We show that a minimal bound on the players’ computational ability is sufficient to enable cooperative behavior. In addition, a variant of the repeated Prisoner’s Dilemma game is suggested, in which players have the choice of opting out. This modification enriches the game and suggests dominance of cooperative strategies. Competitive analysis is suggested as a tool for investigating sub-optimal (but computationally tractable) strategies and game theoretic models in general. Using competitive analysis, it is shown that for bounded players, a sub-optimal strategy might be the optimal choice, given resource limitations.

• Publication year

  2007

• Venue

  International Conference on Multiagent Systems

• Publication date

  2007-01-22

• Fields of study

  Mathematics, Computer Science, Economics

• Identifiers
  arXiv cs/0701139
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Three-person non-zero-sum nonnegotiable games.

  2007cited by this paper
• Master’s thesis

  1996cited by this paper
• Clustering and Information Sharing in an Ecology of Cooperating Agents

  1995cited by this paper
• Network-Based Information Brokers

  1995cited by this paper
• Models of Bounded Rationality

  1995cited by this paper
• Optimality and domination in repeated games with bounded players

  1993cited by this paper
• A strategy of win-stay, lose-shift that outperforms tit-for-tat in the Prisoner's Dilemma game

  1993cited by this paper
• Better Than The Best: The Power of Cooperation

  1993cited by this paper
• On platers with a bounded number of states

  1992influential reference
• Rationality, Morality, and Exit

  1992cited by this paper
• Bounded Versus Unbounded Rationality: The Tyranny of the Weak

  1989cited by this paper
• Bounded Rationality and Strategic Complexity in Repeated Games

  1987cited by this paper
• On Play by Means of Computing Machines

  1986cited by this paper
• Amortized efficiency of list update rules

  1984cited by this paper
• Rational cooperation in the finitely repeated prisoners' dilemma

  1982cited by this paper
• The evolution of cooperation

  1981cited by this paper
• The Sciences of the Artificial

  1970cited by this paper
• [On play].

  1956cited by this paper
• A Strategy of Win-stay, Lose-shift That Outperforms Tit-for-tat in the Prisoner's Counting the Cost of Disease Resistance

  year unknowncited by this paper

• Picky losers and carefree winners prevail in collective risk dilemmas with partner selection

  2020cites this paper
• Outcome-based Partner Selection in Collective Risk Dilemmas

  2019cites this paper
• Agent-Based Computing

  2019cites this paper
• Computación Evolutiva y Teoría de Juegos: Un Híbrido Para La Automatización En Sistemas De Soporte A La Negociación

  2014cites this paper
• Trust and reputation for formation and evolution of multi-robot teams

  2013cites this paper
• Learn your opponent ’ s strategy ( in polynomial time ) ! Conference Item

  2012cites this paper
• Computer science and decision theory

  2008cites this paper
• The Tragedy of the Commons : Pricing Social Welfare in Multiagent Systems

  2007cites this paper
• Evolution of Cooperation in a Population of Selfish Adaptive Agents

  2007cites this paper
• Two Game Models for Cooperation with Implicit Noncooperation

  2006cites this paper
• Bounded Rationality in the Iterated Prisoner ’ s Dilemma

  2005influential citation
• Multi-Agent Cooperation using Trickle-Down Utility

  2003cites this paper
• Nash Equilibrium or Nash Bargaining ? Choosing a Solution Concept for Multi-Agent Learning

  2003cites this paper
• Learning To Cooperate in a Social Dilemma: A Satisficing Approach to Bargaining

  2003cites this paper
• An Introduction to Game Theory and Decision Theory

  2002cites this paper
• An Introduction to MultiAgent Systems

  2002cites this paper
• Multiagent Systems: A Survey from a Machine Learning Perspective

  2000cites this paper
• Game theoretic reasoning in multi-agent coordination by negotiation with a trusted third party

  1999cites this paper
• Making Rational Decisions in N-by-N Negotiation Games with a Trusted Third Party

  1999cites this paper
• Risk Control in Multi-agent Coordination by Negotiation with a Trusted Third Party

  1999cites this paper
• Escape from a prisoners' dilemma by communication with a trusted third party

  1998cites this paper
• Co-ordination in Artificial Agent Societies

  1998cites this paper
• A Fuzzy Game Theoretic Approach to Multi-Agent Coordination

  1998cites this paper
• A Game-Theoretic Solution of Conflicts among Competitive Agents

  1997cites this paper
• Layered Learning in Multiagent Systems

  1997cites this paper
• Cooperative Behavior in an Iterated Game with a Change of the Payoff Value

  1996cites this paper
• Learn Your Opponent's Strategy (in Polynominal Time)!

  1995cites this paper