This creates an interesting added dimension. Now, we’ve got two layers In an iterated game, the optimal solution for players can be different than in the single iteration. The goal is to maximize your total utility at the end of a series of iterations. It’s OK if some iterations result in a loss of utility, so long as by the end of the series of iterations, the final <\/p>\n For example, look at the following game. (This example is copied Player 1 needs to choose either 1 or 2; player 2 needs to choose A or B. For simplicity, this is set up so that player 2 always pays player 1, so the utility values in the game grid are written as payoffs to player 1. (Originally, I didn’t include an explanation of the game grid payoffs. This confused a lot of readers. Sorry!)<\/em><\/p>\n There’s no saddle point here. The maximin for player 1 is 4 (at 2,B); the If the game is played once, then there’s no way to play optimally. It’s There is a successful grand strategy in this kind of iterated After all: if player 1 can figure out player 2’s grand strategy, So, let’s look at an example of a series of iterations, with player 1 selecting randomly, with a uniform probability distribution, and player It will continue like that. Player one will win 3 half the time, and 5 This is a pretty trivial game: for player 2, he’s guaranteed to If player 1 knows<\/em> that player 2 is always going to play A, then he As you can see from the example, the key to finding the optimal strategy is But is there always an optimal distribution? And how can you find it?<\/p>\n There is<\/em> always an optimum. John vonNeumann (who managed to have his Linear programming is a fascinating topic in itself. And it’s complicated The games that we’ve looked at so far are the simplest case of basic games. In these games, we’ve got a payoff matrix, and both players can see the whole matrix – the players have equal information, and nothing is secret. The players move simultaneously – so neither player can wait to see what his […]<\/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-637","post","type-post","status-publish","format-standard","hentry","category-game-theory"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-ah","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/637","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=637"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/637\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=637"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=637"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=637"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nof strategy: each iteration, each player selects a strategy; and then there’s an over-arching strategy that they use to select their strategy each iteration. That over-arching strategy is called a grand strategy<\/em><\/p>\n
\nsum of the utility of the series is maximal.<\/p>\n
\nfrom the textbook The Compleat Strategyst (Complete Strategist): Being A Primer On The Theory Of Games Of Strategy<\/a>![\"\"](\"http:\/\/www.assoc-amazon.com\/e\/ir?t=goodmathbadma-20&l=as2&o=1&a=0070703965\")
\n
\n <\/th>\n A<\/th>\n B<\/th>\n<\/tr>\n \n 1<\/th>\n 3<\/td>\n 6<\/td>\n<\/tr>\n \n 2<\/th>\n 5<\/td>\n 4<\/td>\n<\/tr>\n<\/table>\n
\nminimax for player 2 is 3 (at 1,A). So the simple solution formula from before
\ndoesn’t work. If we’re only playing the game once then there’s no way for
\neither player to create an idea outcome for themselves. Look at it from the
\nperspective of player 1. If player 2 picks strategy A, then the best thing for
\nplayer 2 to do is to pick strategy 2. But if player 2 picks B, then player 1
\nis better off picking A. Since the players move simultaneously, player
\n1 cannot pick the best strategy.<\/p>\n
\nbasically random. But if you repeat<\/em> the game multiple times – that
\nis, you play it as an iterated sequence of games – then you can find an
\noptimal strategy for selecting strategies. That’s called a grand
\nstrategy<\/em>: in a game where you make multiple moves, each move is a
\nstrategy, and the process of selecting strategies for each move is a
\ngrand strategy<\/em>. <\/p>\n
\nzero-sum game. What’s interesting about it is that our idea of
\nstrategy is not really what works as a successful grand strategy: the successful grand strategy is random<\/em>. <\/p>\n
\nthen he can easily pick an optimal strategy. So the best grand strategy
\nis one that the other player can’t<\/em> figure out. If you’re playing randomly, then there’s no way that the other player can predict
\nwhat strategy you choose. <\/p>\n
\n2 playing minimax:<\/p>\n\n
\nwins 5.<\/li>\n<\/ul>\n
\nthe other half – for an average of 4 – which is his maximin value. So
\nplaying this way is at least as good for player 1 as maximin. <\/p>\n
\nlose, and the only question is how quickly he’s going to lose. And
\nthere’s not any strategy that’s going to really improve things much for player 2. There’s not much that 2 can do: playing strategy B is pretty much a lose for
\nhim. So why would he ever do it?<\/p>\n
\ncould play strategy 2, and always win 5. So player two is motivated to
\nplay B just often enough to make player one try 1 once in a while. The
\nkey is, how often should he do that? What’s the best distribution for him,
\nto minimize his losses?<\/p>\n
\nprobability. You need to assign a probability distribution to the different
\nstrategies. Each iteration, you pick a strategy randomly, according to the
\ndistribution. If you can find the right probability distribution for your grand strategy, then you can optimize your winnings.<\/p>\n
\nfingers in an astonishing number of pies) proved that for every two player,
\nsimultaneous move zero-sum iterated game, there is an optimal grand strategy based
\non a probability distribution. And it’s computable. It took a while after
\nJvN to figure out the fast way of doing it – but it’s doable, and it’s doable
\nquickly, through a technique called linear programming.<\/p>\n
\nenough that it deserves a post of its own. (Or, more likely, several.)<\/p>\n","protected":false},"excerpt":{"rendered":"