<p>In this paper, we consider an <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$n \times n$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>×</mo> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation> two-player zero-sum repeated game in which the row player (player X) employs the popular Hedge (also called Multiplicative Weights Update) learning algorithm, while the column player (player Y) adopts a myopic best response. We investigate the dynamics in the Hedge-myopic system by defining a metric <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$Q({\textbf {x}}_t)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>Q</mi> <mo stretchy="false">(</mo> <msub> <mi mathvariant="bold">x</mi> <mi>t</mi> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, which is related to the Kullback-Leibler divergence and measures the distance between the stage strategy <InlineEquation ID="IEq3"> <EquationSource Format="TEX">${\textbf {x}}_t$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="bold">x</mi> <mi>t</mi> </msub> </math></EquationSource> </InlineEquation> and the Nash Equilibrium (NE) strategy of player X. We analyze the trend of <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$Q({\textbf {x}}_t)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>Q</mi> <mo stretchy="false">(</mo> <msub> <mi mathvariant="bold">x</mi> <mi>t</mi> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and prove that it is bounded and can only take a finite number of values on the evolutionary path when the payoffs are rational numbers and the game has an interior NE. Based on this, we prove that the stage strategy sequence of both players is periodic after a finite number of stages, and the time-averaged strategy of player Y within one period is an exact NE strategy. Accordingly, we propose an asymmetric paradigm for solving a class of two-player zero-sum games. In the case of games with rational payoffs and a unique interior equilibrium, the paradigm can output the precise NE strategy; for any general zero-sum game, the time-averaged strategy converges to an approximate NE. Through simulation experiments, we show that, compared with other NE-solving methods, including Hedge self-play, Fictitious Play self-play, and regret matching self-play, this HBR paradigm exhibits a faster convergence rate and better stability.</p>

Periodicity in Hedge-Myopic System and an Asymmetric NE-Solving Paradigm for Two-Player Zero-Sum Games

期刊论文
发表日期：

2025年5月30日

查看全文

Xinxiang Guo,
Yifen Mu,
Xiaoguang Yang

摘要

In this paper, we consider an $n \times n$ $n \times n$ two-player zero-sum repeated game in which the row player (player X) employs the popular Hedge (also called Multiplicative Weights Update) learning algorithm, while the column player (player Y) adopts a myopic best response. We investigate the dynamics in the Hedge-myopic system by defining a metric $Q({\textbf {x}}_t)$ $Q (x_{t})$ , which is related to the Kullback-Leibler divergence and measures the distance between the stage strategy ${\textbf {x}}_t$ $x_{t}$ and the Nash Equilibrium (NE) strategy of player X. We analyze the trend of $Q({\textbf {x}}_t)$ $Q (x_{t})$ and prove that it is bounded and can only take a finite number of values on the evolutionary path when the payoffs are rational numbers and the game has an interior NE. Based on this, we prove that the stage strategy sequence of both players is periodic after a finite number of stages, and the time-averaged strategy of player Y within one period is an exact NE strategy. Accordingly, we propose an asymmetric paradigm for solving a class of two-player zero-sum games. In the case of games with rational payoffs and a unique interior equilibrium, the paradigm can output the precise NE strategy; for any general zero-sum game, the time-averaged strategy converges to an approximate NE. Through simulation experiments, we show that, compared with other NE-solving methods, including Hedge self-play, Fictitious Play self-play, and regret matching self-play, this HBR paradigm exhibits a faster convergence rate and better stability.