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.
|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!