RL — Game Theory

There are lot of definitions of game theory, such as mathematics of conflict of interest. Decision making is about single agent taking decisions, however in real world, there is almost always other agent or agents who are taking rational, self-interested decisions along with you. Hence game theory is also about multiple agents making optimal decisions. It was and is used in lot of practical subjects such as economics, politics and biology. Game theory is increasing becoming part of AI/ML.

Minimax ≡ Maximin

Consider a game being played by two agents, where both the agents are trying to maximize their value. While first player tries to find maximum minimum for self, the other player will try to find minimum maximum for the first player. In a Two players zero sum finite deterministic game of perfect information Minimax ≡ Maximin. There always exists and optimal pure strategy for each player. Assumption here is both the players are rational, trying for optimal maximum benefit for the self.

Nash Equilibrium

Consider n players with strategies they can choose from S1, S2, …, Sn. Each of these strategies is a set, so S1 is a set, S2 is a set and so on. Now S1* ϵ S1, S2* ϵ S2, …, S3* ϵ S3, where * denotes a particular strategy. Now these S1* S2* …, SN* are in Nash equilibrium if and only if, for each one of those strategies chosen by n players, it is the strategy that maximizes the utility for that particular player, given all the other strategies that were chosen.

Given that you have set of strategies S1*, S2*, … . We know that these strategies are in Nash equilibrium, if and only if, a player is chosen randomly, and if this player is given a choice to switch their strategy, they would have no reason to do so.

This is the state where everything is balanced, and no one has reason to move away from their strategy. This works for both pure and mixed strategy.

Three fundamental theorems:

1. In the n-player pure strategy game, if elimination of strictly dominated strategies eliminates all but one combination, that combination is the unique Nash Equilibrium
2. Any Nash Equilibrium will survive elimination of strictly dominated strategies
3. If n is finite and for each of the set of strategies, that set of strategies is also finite then there exists at least one Nash Equilibrium which might involve mixed strategies.

Folk Theorem

In repeated games, the possibility of retaliation opens the door for cooperation. In mathematics — results known, at least to experts in the field, and considered to have established status, but not published in complete form. So there is no ‘original publication’, everyone knows about it. All folk theorem are provable, an oral tradition.

The Folk theorem in Game theory —describe the set of payoffs that can result from Nash strategies in repeated games.

Definition — Any feasible payoff profile that strictly dominates the minmax/security level profile can be realized as a Nash Equilibrium payoff profile, with sufficiently large discount factor.
Proof: If it strictly dominates the minmax profile, can use it as a threat, hence better off doing what is told.

Conclusion

We looked at Nash Equilibrium and Folk Theorem. Game theory has much more details — such as iterated prisoners dilemma, sub-game perfections and plausible threats, computational folk theorem, stochastic games, generalized MDPs and repeated games.

References — Heavily borrowed from my notes on CS7641, so thanks to Prof Charles Isbell and Prof Michael Littman. Errors are all mine.