Abstract
The problem of computing optimal strategy to commit to in various games has attracted intense research interests and has important real-world applications such as security (attacker-defender) games. In this paper, we consider the problem of computing optimal leader's machine to commit to in two-person repeated game, where the follower also plays a machine strategy. Machine strategy is the generalized notion of automaton strategy, where the number of states in the automaton can be possibly infinite. We begin with the simple case where both players are confined to automata strategies, and then extend to general (possibly randomized) machine strategies. We first give a concise linear program to compute the optimal leader's strategy and give two efficient implementations of the linear program: one via enumeration of a convex hull and the other via randomization. We then investigate the case where two machines have different levels of intelligence in the sense that one machine is able to record more history information than the other. We show that an intellectually superior leader, sometimes considered being exploited by the follower, can figure out the follower's machine by brute-force and exploit the follower in return.
Introduction
In game theory, the Stackelberg model describes a scenario where a leader commits to a strategy first, and a follower responds optimally. While this has been extensively studied for one-shot games—particularly in AI security for tasks like patrolling—real-world interactions are often repeated. In infinitely repeated games, the strategy space becomes infinite, rendering standard one-shot algorithms inapplicable. This paper addresses the challenge of finding an optimal "machine strategy" for a leader to maximize long-term average payoffs against a rational follower.
Modeling Strategies as Machines
The authors generalize the concept of automata strategies into "machine strategies." A machine is defined by a set of states (representing memory), an action rule, and a transition function. This formalization allows for a compact, rule-based representation of complex behaviors in repeated interactions.
By using these machines, the leader's commitment becomes credible through repetition. The follower observes the leader's pattern over time and eventually recognizes that deviating from the best response to this pattern is suboptimal.
Computational Framework
The search for an optimal commitment strategy is reduced to a Linear Programming (LP) problem over the convex hull of the game's feasible payoffs. The objective is to maximize the leader's utility while ensuring the follower receives at least their "security level" (minmax value), consistent with the Folk Theorem for repeated games.
To solve this efficiently, the authors propose two algorithms:
- Deterministic Convex Hull Construction: Achieves $O(mn \log mn)$ complexity.
- Randomized Algorithm: Achieves a state-of-the-art linear time complexity of $O(mn)$ relative to the game matrix size.
The Advantage of Asymmetric Intelligence
A key contribution of this work is the analysis of "asymmetric intelligence," where players have different memory capacities. The paper demonstrates that intellectual superiority—defined as having more memory states—provides a significant strategic advantage.
If a leader can record more history than the follower, they can "brute-force" the follower's machine configuration. This allows the leader to predict moves and suppress the follower's security level to its absolute minimum (the "min-min" value), thereby expanding the set of achievable payoffs for the leader.
Key Results and Conclusion
The paper proves that an optimal automata strategy always exists for any two-person repeated game under limit-of-means utility. Furthermore, this strategy can be computed in linear time, making it practical for large-scale applications.
Future work may explore scenarios where the follower's machine class is unknown, or investigate "unpredictable" strategies that might negate a leader's memory advantage. Additionally, shifting the focus from memory capacity to asymmetric computational power (e.g., P-time vs. NP-time) remains a promising research direction.
Summary updated