An application of Linear Programming in Game Theory

http://alabidan.me/2012/12/23/an-application-of-linear-programming-in-game-theory/

by alabid • 14 years ago

41 7 14 years ago

zissou• 14 years ago

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.

traldan• 14 years ago

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.

spne• 14 years ago

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.

gweinberg• 14 years ago

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

tansey• 14 years ago

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

leoplct• 14 years ago

I'm fashinated by Combinatorial Optimisation (I'm followinf course, too). Do you have other article or interesting resource about that?

alabid• 14 years ago

This could serve as a starting point: http://homepages.cwi.nl/~lex/files/dict.pdf.

An application of Linear Programming in Game Theory

Related Stories