Markov strategy

In game theory, a Markov strategy ^[1] is one that depends only on state variables that summarize the history of the game in one way or another. ^[2] For instance, a state variable can be the current play in a repeated game, or it can be any interpretation of a recent sequence of play.

A profile of Markov strategies ^[3] is a Markov perfect equilibrium if it is a Nash equilibrium in every state of the game. The Markov strategy was invented by Andrey Markov. ^[4]

Definition

To formally define Markov strategy, we need the definition of stochastic game and behavioral strategy. Intuitively speaking, a stochastic game is a collection of normal-form games; the agents repeatedly play games from this collection, and the particular game played at any given iteration depends probabilistically on the previous game played and on the actions taken by all agents in that game. ^[5]

(Stochastic game). A stochastic game (also known as a Markov game) is a

tuple ${\displaystyle (Q,N,A,P,R)}$, where:

• ${\displaystyle Q}$ is a finite set of states;
• ${\displaystyle N}$ is a finite set of n players;
• ${\displaystyle A=A_{1}\times \dots \times A_{n}}$, where ${\displaystyle A_{i}}$ is a finite set of actions available to player ${\displaystyle i}$;
• ${\displaystyle P:Q\times A\times Q\rightarrow [0,1]}$ is the transition probability function; ${\displaystyle P(q,a,{\hat {q}})}$ is the probability of transitioning from state ${\displaystyle s}$ to state ${\displaystyle {\hat {q}}}$ after action profile ${\displaystyle a}$; and
• ${\displaystyle R=r_{1},\dots ,r_{n}}$, where ${\displaystyle r_{i}:Q\times A\rightarrow R}$ is a real-valued payoff function for player ${\displaystyle i}$.

Now let us consider the strategy space for stochastic games. As in the other game forms, an agent's strategy can consist of any mixture over deterministic strategies.Actually there are several restricted classes of strategies that are of interest. The first restriction is that the mixing takes place at each history independently, which leads us to behavioral strategy.

(Behavioral strategy). A behavioral strategy ${\displaystyle s_{i}(h_{t},a_{i_{j}})}$ returns the probability of playing action ${\displaystyle a_{i_{j}}}$ for history ${\displaystyle h_{t}}$.

(Markov strategy). A Markov strategy ${\displaystyle s_{i}}$ is a behavioral strategy in which ${\displaystyle s_{i}(h_{t},a_{i_{j}})=s_{i}(h_{t}',a_{i_{j}})}$ if ${\displaystyle q_{t}=q_{t}'}$, where ${\displaystyle q_{t}}$ and ${\displaystyle q_{t}'}$ are the final states of ${\displaystyle h_{t}}$ and ${\displaystyle h_{t}'}$, respectively

A Markov strategy further restricts a behavioral strategy so that, for a given time t, the distribution over actions depends only on the current state. In other words, a Markov strategy will only consider the action from the last round to decide action in this round.

Example

Repeated Prisoner’s dilemma is a very special case of stochastic game where the ${\displaystyle |Q|=1}$. And it is easy to see that Tit-for-Tat is a Markov strategy while grim-trigger strategy is not a Markov strategy since the action in the current stage is not solely determined by the last move.

In more general case, consider a “real” stochastic game with two stages ${\displaystyle \{x,y\}}$, and we have the normal-form of ${\displaystyle x}$ is:

P2 P1	C	D
C	(2,2)	(0,3)
D	(3,0)	(1,1)

And we have the normal-form of ${\displaystyle y}$ is

P2 P1	C	D
C	(5,5)	(2,1)
D	(1,2)	(1,1)

The transition probability function for stage ${\displaystyle x}$ is

P2 P1	C	D
C	(0.5,0.5)	(1,0)
D	(1,0)	(1,0)

References

1. "First Links in the Markov Chain". American Scientist. 2017-02-06. Retrieved 2017-02-06.
2. Fudenberg, Drew (1995). Game Theory. Cambridge, MA: The MIT Press. pp. 501–40. ISBN   0-262-06141-4.
3. "Markov Strategy" . Retrieved 2017-11-17.
4. Sack, Harald (2022-06-14). "Andrey Markov and the Markov Chains". SciHi Blog. Retrieved 2017-11-23.
5. "Essentials of Game Theory: A Concise Multidisciplinary Introduction | Synthesis Lectures on Artificial Intelligence and Machine Learning". doi:10.2200/s00108ed1v01y200802aim003?casa_token=omxkyngxikcaaaaa:hgkme_qlkinn0ph7hddzcqnodzg53-vjmg0yek0rrynkfdzzrkdif0lkkw-txvjrqfwf7nln96g.