When I last wrote about game theory, we were working up to how to find
\nthe general solution to an iterated two-player zero-sum game. Since it’s been
\na while, I’ll take a moment and refresh your memory a bit.<\/p>\n
A zero-sum game is described as a matrix. One player picks a row, and one player picks a column. Those selections are called strategies<\/em>. The intersection In an iterated game, you’re not going to just play once – you’re going to play it repeatedly. To maximize your winnings, you may want to change strategies. It turns out that the optimal strategy is probabilistic – you’ll assign probabilities to your Jon Von Neumann proved that for any two-player zero-sum game, there is an optimal grand strategy based on probability. In a game where both players know exactly what the payoffs\/penalties are, the best strategy is based on constrained randomness – because any deliberate system for choosing strategies can be cracked by your opponent, resulting in his countering you. The best outcome comes from assessing potential wins and losses, and developing a probabilistic scheme for optimizing the way that you play.<\/p>\n Once you make that fundamental leap, realizing that it’s a matter <\/p>\n The basic idea is: take the game matrix. Work out the expected payoff for each As usual, that sounds terribly confusing until you see an example.<\/p>\n Let’s get specific. Here’s a game. We’ll call the two players H (for the player who picks a strategy that’s a horizontal line across the graph), and V. The grid is set up from the viewpoint of player H: the entry in a position is what V needs to pay to H if that pair of strategies is selected: <\/p>\n Then the linear programming problem works out as follows:<\/p>\n Maximize: min(E(H1), E(H2), E(H3)), where Σpi<\/sub>=1, When we run that through our linear programming tool, we get the following probability assignment (rounded to two figures): p1<\/sub>=0.57, p2<\/sub>=0.17, p3<\/sub>=0.26.<\/p>\n If we transpose, and look at things from the perspective of V, we get that the That example is an unfair game, because V always pays H. But the There’s one more question about the game: what’s the expected payoff? In game theory terms, we call that the value<\/em> of the game: the value of the game to a player is the amount that the player will win\/lose if both they and their opponent play optimally. It’s very easy to figure: the probability assignments work out so that the expectation is the same for all three strategies. So to find the value for H, you pick one strategy for V, and work out the expectation for H given the probabilities in his grand strategy.<\/p>\n So, suppose that player V chose strategy 1. Then the expectation for H would be: When you see this, it’s pretty obvious that it works. In fact, most people see it, When I last wrote about game theory, we were working up to how to find the general solution to an iterated two-player zero-sum game. Since it’s been a while, I’ll take a moment and refresh your memory a bit. A zero-sum game is described as a matrix. One player picks a row, and one player […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[88],"tags":[],"class_list":["post-658","post","type-post","status-publish","format-standard","hentry","category-game-theory"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-aC","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/658","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=658"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/658\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=658"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=658"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=658"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nof the strategies in the game matrix describes what one player pays to the other. The
\nmatrix is generally written from the point of view of one player. So if we call
\nour two players A and B, and the matrix is written from the viewpoint of A, then
\nan entry of $50 means that B has to pay $50 to A; an entry of $-50 means that A has to pay $50 to B.<\/p>\n
\nstrategy choices, and use that probability assignment to randomly select your
\nstrategy each iteration. That probability assignment that dictates how you’ll
\nchoose a strategy each iteration is called a grand strategy<\/em>.<\/p>\n
\nof probability, it’s not particularly difficult to find the grand strategy: it’s just a simple optimization task, solveable via linear programming. The solution is very elegant: once you see it, once you see how to
\nformulate the game as a linear optimization process, it just seems completely obvious.<\/p>\n
\nstrategy for one player in terms of an unknown probability assignment. Then, using linear programming, optimize for the maximum value of the minimum expected payoff,
\nsubject to constraints that basically describe a probability assignment.<\/p>\n\n
\n <\/th>\n V1<\/th>\n V2<\/th>\n V3<\/th>\n<\/tr>\n \n H1<\/th>\n 3<\/td>\n 1<\/td>\n 3<\/td>\n<\/tr>\n \n H2<\/th>\n 2<\/td>\n 4<\/td>\n 5<\/td>\n<\/tr>\n \n H3<\/th>\n 3<\/td>\n 6<\/td>\n 1<\/td>\n<\/tr>\n<\/table>\n \n
\nand ∀i: 0≤pi<\/sub>≤1.<\/p>\n
\noptimal strategy is (0.70, 0.09, 0.22).<\/p>\n
\nsame basic construction of the solution will work. It’s implicit in the names of
\nthe basic strategies: maximin; maximize the minimum. It’s just that now, instead
\nof maximizing the minimum of a single strategy selection, we’re maximizing the minimum of the expected outcomes based on the probability assignments in the grand strategy.<\/p>\n
\n0.57*3 + 0.17*2 + 0.26*3 = 2.83. So the value of the game to player H is 2.83. If you work it out from the transpose matrix to get the value of the game to player V, it works out to -2.83.<\/p>\n
\nand react, roughly, “Of course! Maximize the minimum!” It seems so simple! The real fundamental achievement by Jon Von Neumann wasn’t figuring out how to describe the probabilistic grand strategies as an optimization problem – that’s actually easy. The real key was realizing that the optimal strategy was based on probability – that the whole key to optimizing a zero-sum game lies in randomness constrained by a probability distribution.<\/p>\n","protected":false},"excerpt":{"rendered":"