2023/12/15 by Xinxiang Guo, Guo, Xinxiang, Yifen Mu +1
Computer Science · Decision Sciences · Physics and Astronomy · #91A05 #91A20 #Artificial Intelligence in Games #FOS: Mathematics #Game Theory and Applications #Opinion Dynamics and Social Influence #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2312.09472
openalex publication_date 2023/12/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper aims to solve the optimal strategy against a well-known adaptive algorithm, the Hedge algorithm, in a finitely repeated 2× 2 zero-sum game. In the literature, related theoretical results are very rare. To this end, we make the evolution analysis for the resulting dynamical game system and build the action recurrence relation based on the Bellman optimality equation. First, we define the state and the State Transition Triangle Graph (STTG); then, we prove that the game system will behave in a periodic-like way when the opponent adopts the myopic best response. Further, based on the myopic path and the recurrence relation between the optimal actions at time-adjacent states, we can solve the optimal strategy of the opponent, which is proved to be periodic on the time interval truncated by a tiny segment and has the same period as the myopic path. Results in this paper are rigorous and inspiring, and the method might help solve the optimal strategy for general games and general algorithms.