An application of Linear Programming in Game Theory

Always happy to see some game theory on HN. If you're looking for a good book that focuses more on how game theory is actually used in practice versus the more computational exposition here, then I'd recommend a very readable and cheap book called "Game Theory for Applied Economists" by Robert Gibbons (Google Preview: http://books.google.com/books/p/princeton?id=8ygxf2WunAIC). The book has only 4 chapters which cover the 4 different types of games:

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.

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

"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'm fashinated by Combinatorial Optimisation (I'm followinf course, too). Do you have other article or interesting resource about that?