Best-Reply Strategies in Repeated Games

The actions that players naturally and frequently choose to perform throughout a repeated game are the “best-reply strategy”. Making the determination that such strategies lead to an equilibrium point is a difficult and sensitive operation since, often, the behavior of a single cost-function when such best-reply techniques are used turns out to be non-monotonic. The convergence to a stable equilibrium is not always guaranteed, even in repeated games. In this chapter, we demonstrate that the best-reply actions surely lead to an equilibrium point for a type of finite controlled Markov Chains dynamic games. The Lyapunov Games concept, which is based on the design of a unique Lyapunov function (associated with a unique cost function) that monotonically reduces (non-increases) throughout the game, achieves this result. We provide a technique for creating a Lyapunov-like function that describes how players behave in a recurrent Markov chain game. The Lyapunov-like function replaces the components of the ergodic system, which simulate players’ anticipated behavior in one-shot games, for the recursive process. We first provide a non-converging state-value function that varies (increases and decreases) between states of the repeating Markov game in order to demonstrate our claim. Then, we demonstrate that using a one-step-ahead fixed-local-optimal approach, it is possible to describe that function in a recursive format. Thus, we show that the previous recursive expression for the repeated game can be used to construct a Lyapunov-like function; the resulting Lyapunov-like function is a monotonic function that can only decrease (or remain the same) over time, regardless of the initial distribution of probabilities. The best-reply methods examined in this study are connected to what are known as pure and stationary fixed-local-optimal actions, or, to put it another way, with one step ahead optimization algorithms that are extensively employed in the Artificial Intelligence theory. The Bank Marketing Campaigns Game and the Duel Game with Best-Reply Strategies Application serve as examples of the proposed strategy.