Source-linked AI summary
Performance of Zero-determinant Strategies in Repeated Games without Discounting
Masahiko Ueda
TL;DR
Earlier accounts of ZD strategies in undiscounted repeated games relied on the existence of a Cesàro-average limit, leaving their performance without that assumption unresolved. This paper analyzes ZD strategies without that limit and shows their payoff control is captured by a stronger inequality. The result permits discussion of ZD performance even when P* does not exist.
Problem
For undiscounted repeated games, the performance of ZD strategies was not known without assuming that the Cesàro average of action-profile probabilities has a limit.
Source: §1 · p. 1Method
Results
Even when P* does not exist, a ZD strategy unilaterally enforces an inequality that yields a linear relation different from the earlier limit-dependent result.
Source: §3.1 · p. 2, §4 · p. 3Takeaways & Limitations
The inequality allows the performance of ZD strategies to be discussed in undiscounted repeated games even when P* does not exist.
Source: §4 · p. 3The problem addressed is specific to repeated games without discounting; with δ ∈ [0, 1), P* is modified.
Source: §4 · p. 4
Abstract
from arXiv · showhide
Zero-determinant (ZD) strategies are a class of strategies in repeated games, which unilaterally control payoffs. It has been shown that several ZD strategies promote cooperation in social dilemma games. It has been widely believed that the performance of ZD strategies is expressed as ``unilaterally enforce linear relations between payoffs''. However, in order to interpret properties of ZD strategies in repeated games without discounting, previous studies assumed that the limit of the Cesaro average of the probability distribution of the action profile exists. Here, we explain the performance of ZD strategies without this assumption, which leads to a stronger result than previous ones.
1. Introduction
The introduction situates zero-determinant (ZD) strategies as a way to promote cooperation through repeated interaction and opponent learning. It identifies an unresolved case—undiscounted games without a Cesàro-limit assumption—and states that ZD performance can be described by an inequality stronger than the familiar linear-relation account.
1. Introduction
- In the prisoner’s dilemma, defection is individually rational, whereas mutual cooperation improves both players’ payoffs.1)Source: §1 · p. 1
- ZD strategies promote cooperation through opponents’ learning rather than rationality, while direct reciprocity explains cooperation through repeated interaction among agents.The introduction describes positively correlated ZD strategies as increasing both players’ payoffs when the opponent learns.Source: §1 · p. 1
- Earlier work established ZD payoff control under a Cesàro-average limit, leaving undiscounted games without that limit unresolved.The introduction also notes that the assumption is unnecessary when future payoffs are discounted.Source: §1 · p. 1
- Without a Cesàro-limit assumption, the paper shows ZD strategies control payoffs more strongly than the familiar unilateral linear-relation account, describing performance by an inequality.The unresolved setting is repeated games without discounting.Source: §1 · p. 1
2. Preliminaries
The preliminaries define the repeated-game strategy setting, distinguish memory-one strategies, and introduce ZD strategies through a controlled quantity B. They contrast payoff control based on a linear combination of payoffs, which assumes a Cesàro-average limit exists.
2. Preliminaries
- A repeated-game strategy specifies actions based on previous action profiles, while a memory-one strategy uses only information from the last round.Source: §2 · p. 1
- A ZD strategy is a special class of memory-one strategy that controls a quantity B; when B is related to one-shot payoffs, it can control payoffs.Source: §2 · pp. 1–2
- The familiar payoff-control formulation takes B as a linear combination of players’ one-shot payoffs, but its argument assumes that P* exists.Source: §2 · p. 2
3. Results
The paper establishes payoff-control results for ZD strategies without assuming that the Cesaro-average distribution has a limit, then extends Akin’s lemma and checks the theory numerically in a prisoner’s dilemma.
3.1 Performance of ZD strategies
- Even when P* does not exist, a ZD strategy controlling B unilaterally enforces inequality (14), which bounds total expected B by a constant independent of T.When P* exists, Eq. (16) coincides with Eq. (3); without that limit, Eq. (16) still applies.Source: §3.1 · p. 2
3.2 Akin’s lemma
- The authors extend Akin’s lemma without assuming P*, obtaining a modified result for arbitrary a_j that coincides with Eq. (17) when P* exists.The usual derivation of ZD properties from Akin’s lemma requires P*.Source: §3.2 · pp. 2–3
3.3 Numerical simulation
- For the numerical verification, Fig. 1 plots T horizontally and P_T vertically.The figure is identified as a numerical verification of theoretical result (26).Source: Figure 1 · p. 3, §3.3 · p. 3
- The numerical simulation uses a two-player prisoner’s dilemma with parameters (R, S, T, P) = (3, 0, 5, 1) and equalizer target r = 2.Player 1 uses the equalizer strategy, player 2 acts randomly from t ≥ 2, and the result is reported as consistent with theory (26).Source: §3.3 · p. 3, Figure 1 · p. 3
4. Concluding remarks
Without assuming that P* exists, the paper shows that ZD strategies enforce an inequality that also yields a linear relation. This framework interprets ZD strategy properties even when P* does not exist, and the results complete the characterization across discount factors.
4. Concluding remarks
- A ZD strategy controlling B unilaterally enforces inequality (14), which leads to linear relation (16), even when P* does not exist.Relation (16) differs from Eq. (3), which assumes P* exists.Source: §4 · p. 3
- The framework interprets Tit-for-Tat’s payoff-equalizing property when P* does not exist, where that property otherwise cannot be interpreted.For this case, the paper applies Eqs. (14) and (16) with B = s1 − s2.Source: §4 · pp. 3–4
- The results extend an inequality previously obtained for unbeatable imitation strategies to arbitrary ZD strategies.The paper notes that unbeatable Tit-for-Tat was proved to be a ZD strategy that unilaterally equalizes payoffs.Source: §4 · p. 4
- The problem treated here is specific to repeated games without discounting; for δ < 1, P* is modified and always exists, completing the characterization for all δ.The modified P* is given by a discounted average of the action-profile distributions.Source: §4 · p. 4
- The bound in inequality (14) depends on the coefficients c_aj, and strategies with smaller Δ := max_aj c_aj − min_aj c_aj are more powerful.How to obtain ZD strategies with small Δ remains for future investigation.Source: §4 · p. 4