Source-linked AI summary
Feedback autocratic strategies in stochastic games
Masahiko Ueda
TL;DR
The paper addresses how feedback strategies can control payoffs unilaterally in stochastic games, extending ideas from repeated games. It develops feedback strategies and conditions for autocratic control, and reports that examples show they can be implemented more easily than zero-determinant strategies.
Problem
How feedback control performs in stochastic games remains unclear, despite repeated-game strategies that control payoffs unilaterally.
Source: §1 · p. 2Method
The paper defines feedback strategies for a target quantity B and derives conditions for them to be autocratic under stated assumptions.
Source: §2.2 · p. 4, §3.1 · pp. 4–5Results
The authors report that feedback strategies can be implemented more easily than zero-determinant strategies and demonstrate their results in stochastic and periodic prisoner’s dilemma games.
Source: §1 · p. 2, §4 · p. 15Takeaways & Limitations
The findings connect payoff control in repeated games with feedback control in stochastic games.
Source: §4 · p. 15The analysis assumes deterministic transitions and another stated assumption; existence conditions for feedback autocratic strategies in general stochastic cases remain unresolved.
Source: §4 · p. 15
Abstract
from arXiv · showhide
A stochastic game is an optimal control problem for multiple agents in a stochastic environment. Stochastic games contain important practical problems, related to environmental issues or traffic flows. If the number of environmental states is one, such stochastic games are called repeated games. In repeated games, several strategies which unilaterally control payoffs have been proposed, and these strategies work in a mechanism similar to feedback control. In this paper, we generalize these strategies as feedback strategies in stochastic games, and investigate their properties. In particular, we provide a necessary and sufficient condition for such feedback strategies to work as controllers of payoffs under some assumptions. We demonstrate the performance of such feedback strategies in several examples related to social dilemmas. Our findings connect the theory of payoff control in repeated games to the theory of feedback control in stochastic games.
1. Introduction
The paper extends feedback control to stochastic games, where multiple agents optimize different objectives in a stochastic environment. It addresses how feedback strategies can control payoffs unilaterally, generalizing strategies previously studied in repeated games.
1. Introduction
- Classical feedback control adjusts output in the opposite direction of its change, with stability understood for linear dynamical systems and optimal regulation derived for linear-quadratic systems.The paper places this control concept in the context of nonlinear optimal-control problems.Source: §1 · p. 1
- Stochastic games combine multiple agents’ distinct objectives with a stochastic environment and cover practical problems such as environmental issues and traffic flows.They extend differential games and Markov decision processes in the optimal-control framework.Source: §1 · pp. 1–2
- In repeated games, zero-determinant strategies can unilaterally enforce linear payoff relationships, while other strategies target an opponent’s payoff, unbeatable play, or mutual cooperation.Repeated games are stochastic games with one environmental state, and zero-determinant strategies have been described as operating similarly to feedback control.Source: §1 · p. 2
- The performance of feedback control in stochastic games remains unclear, motivating a generalization of repeated-game strategies to this setting.The paper identifies strategies for directly controlling an opponent’s payoff and equalizing players’ payoffs as feedback-control examples.Source: §1 · p. 2
- The paper introduces feedback strategies for stochastic games and finds through examples that they can be implemented more easily than zero-determinant strategies.These strategies decrease or increase the output when it increases or decreases, respectively.Source: §1 · p. 2
2. Preliminaries
The preliminaries specify the stochastic-game setting and introduce feedback autocratic strategies for controlling a chosen quantity B. They define the strategy’s unilateral-control objective and the feedback principle that guides its actions.
2.1. Stochastic games
- Players choose actions based on full histories of actions and states, and payoffs are defined using expectations over strategies and transitions, with lim inf used if the limit does not exist.The framework also specifies players, environmental states, action sets, transition probabilities, and an initial-state distribution.Source: §2.1 · pp. 2–3
2.2. Feedback autocratic strategies
- The paper assumes deterministic transitions and a second assumption that permits defining unique actions.The transition probability is represented by a transition function under Assumption 1.Source: §2.2 · pp. 3–4
- A feedback strategy selects actions expected to increase total B when it is negative and decrease it when it is positive; it is autocratic if it controls B unilaterally.The definition requires control regardless of the other players’ strategies and for arbitrary initial conditions, with some constant Δ ≥ 0.Source: §2.2 · pp. 3–4
- The feedback-autocratic framework encompasses repeated-prisoner’s-dilemma strategies for controlling an opponent’s payoff or the difference between two players’ payoffs.The cited examples are equalizer strategies and cumulative reciprocity.Source: §2.2 · p. 4
3. Results
The section gives cycle-based conditions for feedback strategies to control payoffs autocratically, then applies them to stochastic and periodic prisoner’s dilemma games. The examples show broader existence of payoff-equalizing strategies in periodic games than memory-one zero-determinant strategies.
3.1. Existence condition
- A feedback strategy is autocratic if and only if the required inequalities hold for every possible cycle in both modes.The existence proof models the game as two finite automata and bounds the accumulated quantity using the finite number of states.Source: §3.1 · pp. 4–6
- A statewise inequality provides a sufficient condition for a feedback strategy to be autocratic.The theorem’s proof notes that this condition makes the cycle conditions hold for all possible cycles.Source: §3.1 · p. 6
3.2. Periodic games
- For periodic games, the autocracy test reduces to inequalities for the single state cycle, with conditions equivalent to those for zero-determinant strategies in multichannel games.A periodic game cycles through its states regardless of players’ actions.Source: §3.2 · p. 7
3.3. Stochastic prisoner’s dilemma
- In the stochastic prisoner’s dilemma, player 1’s feedback strategy controlling B = s1 − s2 is autocratic and essentially matches cumulative reciprocity.The example uses a fair feedback strategy and applies the general cycle condition.Source: §3.3 · pp. 8, 10
3.4. Periodic prisoner’s dilemma
- In the periodic prisoner’s dilemma, feedback autocratic strategies exist in the listed cases, while memory-one zero-determinant strategies exist only in cases 3, 4, 9, and 10.The paper concludes that feedback strategies can equalize the players’ payoffs in broader situations.Source: §3.4 · p. 14
4. Concluding remarks
The paper establishes conditions for feedback strategies to be autocratic, relates the periodic-game condition to autocratic-strategy existence in multichannel games, and demonstrates results in two prisoner’s dilemma settings. It also identifies computational, design, assumption, and comparison questions that remain open.
4. Concluding remarks
- The paper demonstrates its main results in the stochastic and periodic prisoner’s dilemma games.Source: §4 · p. 15
- Checking conditions (9) and (10) across all cycles can be computationally hard because cycle counts may grow exponentially with environmental-state count.The authors suggest finding equivalent alternative conditions.Source: §4 · p. 15
- Whether definitions (6) and (7) are best for general stochastic games remains unknown, although Theorem 3 establishes their optimality for periodic games.The authors identify finding the best definitions as an important future problem.Source: §4 · p. 15
- Without Assumptions 1 and 2, system dynamics become stochastic, and existence conditions for feedback autocratic strategies in general stochastic cases remain unresolved.The paper states that this analysis would be more complicated.Source: §4 · p. 15
- In stochastic games, defining zero-determinant strategies as memory-one strategies leaves a discrepancy with fair feedback autocratic strategies; an equivalent definition remains open.The paper notes that the environmental state changes over time, complicating the short-memory definition.Source: §4 · p. 16
Appendix A. Lemma
The lemma’s proof rewrites its assumption as S_T < 0 and uses a tie-breaking choice of t* with periodicity to select t0 = t*.
Appendix A. Lemma
- The proof begins from a negative sum of b_t and selects t0 in [1, T] appropriately so the sequence satisfies the stated condition.Source: Appendix A · p. 16
- The proof chooses the largest t* satisfying Eq. (A.3) when multiple choices exist.Source: Appendix A · p. 16
- Under the rewritten assumption S_T < 0, periodicity yields a choice t0 = t*.Source: Appendix A · p. 17