There are many flavors of games in Game Theory which are interesting from Machine Learning perspectives, especially from multi-agent Reinforcement Learning applications. Here is the summary of multiple game types are if MinMax algorithm works and what type of strategy one needs to employ.
| Game ID | #Players | Outcome | Deterministic? | Information | #Round | Strategy |
| 1 | 2 | Zero-sum | Deterministic | Perfect Information | Single | MinMax works, Pure strategy |
| 2 | 2 | Zero-sum | Stochastic | Perfect | Single | MinMax works, Pure strategy |
| 3 | 2 | Zero-sum | Stochastic | Hidden | Single | MinMax does NOT work, Mixed Strategy |
| 4 | 2 | Non-zero sum | Stochastic | Hidden | outcome is same for every round | Solve for Nash Equilibrium, Pure or mixed |
| 5 | 2 | zero-sum | Stochastic | Hidden | defined by gamma | With finite states, it is a Markov Decision Process. Solve Minimax-Q algorithm |
| 6 | 2 or more | Non-zero sum | Stochastic | Not-hidden | Defined by gamma | Active Research! |
Comments on Strategy
Game ID#4: If strongly dominant strategy is present, then pure strategy might work or else might need a mixed strategy
Game ID#5: For small number of rounds (gamma~=0), betrayal might provide more reward, but for infinite number of rounds (gamm~=1), cooperation yields more reward
Interesting Facts from the Theory
- Tit-for-Tat is not subgame perfect when considering a longer future time horizon! It means it can give itself more rewards overall if it does not choose to retribute against the other player! So forgiveness is a better virtue! This forgiving strategy is called Pavlov state machine!