An application of Linear Programming in Game Theory(alabidan.me)
alabidan.me
An application of Linear Programming in Game Theory
http://alabidan.me/2012/12/23/an-application-of-linear-programming-in-game-theory/
4 comments
For me it's less intuitive than a tree, but you can use a matrix to express all possible strategies of a two-player sequential game. This can help you visualize credible vs. noncredible threats from the second player. Ultimately I think the tree is more helpful in solving it visually, though.
This book provides a great introduction to game theory. What I like best about it is the way that it introduces simple examples in the first chapter, and then expands upon these examples in the following chapters, adding new complications each time.
I'll take a small issue with the end of the article that claims linear programming is used for game theory work in poker. With the exception of Andrew Gilpin's work using the "Excessive Gap Technique"[1], almost no poker game theory work relies on linear programming. Instead, the majority of work is on iterative game tree solutions like "Counterfactual Regret Minimization" [2].
In general, real-world games with imperfect information and stochastic outcomes (like poker) are just too large to represent in normal form.
[1] http://www.aaai.org/Papers/AAAI/2007/AAAI07-008.pdf
[2] https://www.cs.ualberta.ca/system/files/tech_report/2007/TR0...
In general, real-world games with imperfect information and stochastic outcomes (like poker) are just too large to represent in normal form.
[1] http://www.aaai.org/Papers/AAAI/2007/AAAI07-008.pdf
[2] https://www.cs.ualberta.ca/system/files/tech_report/2007/TR0...
"Note that this doesn’t mean that Daniel will always lose the game but that he can lose by at most 1/12 the value of the game. If Nick doesn’t play optimally (Nick doesn’t use his optimal mixed strategy), Daniel will most likely win!"
I don't think this is correct. I think if Daniel plays his optimum strategy, Nick will get the same payoff no matter what he plays.
I think this is a fairly general result, if one player is playing the optimal strategy, once the other player has eliminated options he should never play, it doesn't matter how his choices are distributed among the remaining options.
I don't think this is correct. I think if Daniel plays his optimum strategy, Nick will get the same payoff no matter what he plays.
I think this is a fairly general result, if one player is playing the optimal strategy, once the other player has eliminated options he should never play, it doesn't matter how his choices are distributed among the remaining options.
I'm fashinated by Combinatorial Optimisation (I'm followinf course, too). Do you have other article or interesting resource about that?
This could serve as a starting point: http://homepages.cwi.nl/~lex/files/dict.pdf.
1. Static Games of Complete Information
2. Dynamic Games of Complete Information
3. Static Games of Incomplete Information
4. Dynamic Games of Incomplete Information
This segmentation covers all possible types of games. It's great because then you only have to decide if the game is static vs. dynamic and whether it's a game of complete vs. incomplete information (remember, perfect/imperfect information is not the same as complete/incomplete information). If you can answer those 2 questions, then you know what kind of equilibrium is relevant. For example, if it's a game of incomplete information (meaning that there is a move of nature, or equally, that the players don't necessarily know the types/payoffs of the other players) then you know that you are playing a Bayesian game, and hence the equilibrium (it if exists) will be some kind of a Bayesian Nash equilibrium.
You can always express a game of incomplete information as a game of imperfect information (see: Harsanyi transformation). However, here's something to think about: What do you lose when you transform a game from extensive form (a tree) to strategic form (a matrix)? The answer: Timing.