# Game Theory **URL:** \ **Category:** Factual Questions\ **Created:** [October 21, 2008, 10:57pm UTC](https://boards.straightdope.com/t/game-theory/468962 "2008-10-21T22:57:17Z")\ **Posts on this page:** 15\ **Page:** 1
**Author:** ![Santo\_Rugger](https://avatars.discourse-cdn.com/v4/letter/s/e95f7d/32.png) [@Santo\_Rugger](https://boards.straightdope.com/u/Santo_Rugger)\ **Post date:** [October 21, 2008, 10:57pm UTC](https://boards.straightdope.com/t/game-theory/468962/1 "2008-10-21T22:57:17Z")
I’m looking for a resource to solve a game theory problem. It is quite similar to the prisoner’s dilemma, except there are three chips that can be played (instead of a choice between two decisions). There is a payout table that is dependent on what the other player does (making a 3x3 matrix, instead of 2x2). I need to figure out the optimal strategy and the value of the game. I can’t find anything on Wikipedia and I’m not sure what to search for on Google. I can use Excel or MatLab, if necessary. Thanks in advance for any help. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [October 22, 2008, 12:19am UTC](https://boards.straightdope.com/t/game-theory/468962/2 "2008-10-22T00:19:04Z")
If it’s only a 3 x 3 matrix, you can do it by hand. For each move of the first player, consider the optimal move of the second player. If the first player has a better move to address the second player’s move, it’s not the optimum. ---
**Author:** ![Santo\_Rugger](https://avatars.discourse-cdn.com/v4/letter/s/e95f7d/32.png) [@Santo\_Rugger](https://boards.straightdope.com/u/Santo_Rugger)\ **Post date:** [October 22, 2008, 12:28am UTC](https://boards.straightdope.com/t/game-theory/468962/3 "2008-10-22T00:28:48Z")
Hmm, for this particular example, I’ve got: ```auto Red White Blue Red 0 -2 3 White 6 4 -3 Blue 2 3 -4 ``` The payouts are listed for the player choosing rows. So, if the row chooser picks red, the column chooser will pick white. When the column chooser picks white, the row chooser will pick white. However, when the row chooser picks white, the column player will pick blue. Since the column chooser is picking blue, the row chooser will pick red, and we’re back to where we started. ---
**Author:** ![Pasta](https://avatars.discourse-cdn.com/v4/letter/p/ecccb3/32.png) [@Pasta](https://boards.straightdope.com/u/Pasta)\ **Post date:** [October 22, 2008, 12:40am UTC](https://boards.straightdope.com/t/game-theory/468962/4 "2008-10-22T00:40:02Z")
I don’t see enough information here. Are these the payouts to both players? If so, there is no conflict: The top guy will always pick red and the left guy will always pick white. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [October 22, 2008, 12:41am UTC](https://boards.straightdope.com/t/game-theory/468962/5 "2008-10-22T00:41:42Z")
**Pasta** : No, this is a zero-sum game; the row player earns what the matrix says and the column player earns the negative of what the matrix says. **OP** : You want to look for the optimal in mixed strategies (i.e., players select independent probability distributions of choices, rather than single choices). You want to look for a solution where, holding any one player’s probability distribution constant, the best expected payoff for the other player is the one given by his selection. ---
**Author:** ![Pasta](https://avatars.discourse-cdn.com/v4/letter/p/ecccb3/32.png) [@Pasta](https://boards.straightdope.com/u/Pasta)\ **Post date:** [October 22, 2008, 12:45am UTC](https://boards.straightdope.com/t/game-theory/468962/6 "2008-10-22T00:45:20Z")
Ah, thanks. Should’ve guessed that. ---
**Author:** ![Santo\_Rugger](https://avatars.discourse-cdn.com/v4/letter/s/e95f7d/32.png) [@Santo\_Rugger](https://boards.straightdope.com/u/Santo_Rugger)\ **Post date:** [October 22, 2008, 12:47am UTC](https://boards.straightdope.com/t/game-theory/468962/7 "2008-10-22T00:47:16Z")
> [@Indistinguishable](#): > > **OP** : You want to look for the optimal in mixed strategies (i.e., players select independent probability distributions of choices, rather than single choices). I understand that part. For example, in rock paper scissor, if I were to just pick rock every time, you would pick paper every time, and I’d never win. So the optimum solution would be to pick each 1/3 of the time. But I don’t know how to do the math, I was hoping there was some sort of example problem online? Or would it be as simple as finding the expected payout of each color, and then selecting that color as often as the weighted average of that color’s payout is? ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [October 22, 2008, 12:50am UTC](https://boards.straightdope.com/t/game-theory/468962/8 "2008-10-22T00:50:17Z")
It’s a straightforward linear programming problem. See [here](http://en.wikipedia.org/wiki/Zero-sum#Solving). There are fairly efficient algorithms for such things, and thus automated tools, though I don’t know of where to get one. ---
**Author:** ![Grumman](https://avatars.discourse-cdn.com/v4/letter/g/43a26b/32.png) [@Grumman](https://boards.straightdope.com/u/Grumman)\ **Post date:** [October 22, 2008, 12:56am UTC](https://boards.straightdope.com/t/game-theory/468962/9 "2008-10-22T00:56:03Z")
> [@Santo\_Rugger](#): > > Hmm, for this particular example, I’ve got: > > ```auto > > Red White Blue > Red 0 -2 3 > White 6 4 -3 > Blue 2 3 -4 > > ``` Right from the start, I think you can ignore the blue row and red column - white is superior to blue for the rows for player 1, and for player 2 red is only marginally better than white in one case (which is unlikely to come up), and inferior in all other cases. ```auto White Blue Red -2 3 White 4 -3 ``` If player 2 picked both columns in equal numbers, player 1 would win 1/2 a point per game, for either the red or white rows. If player 1 picked both rows in equal numbers, player 2 would win 1 point per game if they pick white, or 0 points if they picked blue. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [October 22, 2008, 12:59am UTC](https://boards.straightdope.com/t/game-theory/468962/10 "2008-10-22T00:59:31Z")
> [@Grumman](#): > > Right from the start, I think you can ignore the blue row and red column - white is superior to blue for the rows for player 1, and for player 2 red is only marginally better than white in one case **(which is unlikely to come up)**, and inferior in all other cases. Not only unlikely, but actually will never happen in optimal play, given the realization that the white strategy dominates the blue one for the row player. ---
**Author:** ![Santo\_Rugger](https://avatars.discourse-cdn.com/v4/letter/s/e95f7d/32.png) [@Santo\_Rugger](https://boards.straightdope.com/u/Santo_Rugger)\ **Post date:** [October 22, 2008, 1:08am UTC](https://boards.straightdope.com/t/game-theory/468962/11 "2008-10-22T01:08:12Z")
Awesome, thanks for the link, **Indistinguishable** , and for the great start on the problem, **Grumman**. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [October 22, 2008, 1:15am UTC](https://boards.straightdope.com/t/game-theory/468962/12 "2008-10-22T01:15:26Z")
Presumably, both players make their move without knowledge of the other player’s move, like in Paper Rock Scissors. In this case, a strategy isn’t just “Pick red” or the like; it’s a set of probabilities for each (such as “Red 70%, White 10%, Blue 20%”). If there were a single optimum color for you, then your opponent could figure out what it is, and always pick the color that has a negative expectation for you, but if you’re picking somewhat randomly, your opponent wouldn’t be able to do that. The trick for finding the optimum set of probabilities is that usually, when you use the optimum set of probabilities, your expected payoff is the same no matter what your opponent does. Otherwise, your opponent’s optimal strategy would be to always pick the one that was best for him, and you would adjust your strategy to take advantage of his simple optimum. For this particular case, let R, W, and B be the probabilities of you picking each of the choices, in your optimal strategy. In that case, R + W + B = 1, since those are all the choices, and the payoff for each of your opponent’s choices are the same: P[sub]R[/sub] = 0_R + 6_W + 2_B, P[sub]W[/sub] = -2_R + 4_W + 3_B, and P[sub]B[/sub] = 3_R -3_W -4\*B, and P[sub]R[/sub] = P[sub]W[/sub] = P[sub]B[/sub] . We now have a system of four equations in four unknowns (the three probabilities and the payoff), which can be solved by any of the standard algebraic methods. ---
**Author:** ![Santo\_Rugger](https://avatars.discourse-cdn.com/v4/letter/s/e95f7d/32.png) [@Santo\_Rugger](https://boards.straightdope.com/u/Santo_Rugger)\ **Post date:** [October 22, 2008, 1:50am UTC](https://boards.straightdope.com/t/game-theory/468962/13 "2008-10-22T01:50:58Z")
Perhaps I’m doing something wrong, but I’m getting a negative value for W. When I try to force it to be 0 or positive, I’m getting “false” or “no feasible solution”. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [October 22, 2008, 3:24am UTC](https://boards.straightdope.com/t/game-theory/468962/14 "2008-10-22T03:24:41Z")
> [@](#): > > Right from the start, I think you can ignore the blue row and red column - white is superior to blue for the rows for player 1, and for player 2 red is only marginally better than white in one case (which is unlikely to come up), and inferior in all other cases. I should have noticed this… You’re right, that when one choice dominates over another, you can just eliminate the dominated choice. That simplifies the problem considerably. Come to think of it, the existence of dominating strategies in the payoff matrix might be what’s causing the weird behaviour **Santo** is seeing. Try it again, with **Grumman** ’s simplified matrix. ---
**Author:** ![Santo\_Rugger](https://avatars.discourse-cdn.com/v4/letter/s/e95f7d/32.png) [@Santo\_Rugger](https://boards.straightdope.com/u/Santo_Rugger)\ **Post date:** [October 22, 2008, 5:09am UTC](https://boards.straightdope.com/t/game-theory/468962/15 "2008-10-22T05:09:43Z")
Thanks, **Chronos** , I was able to solve the simplified matrix with the method you posted, and verified it with an online algorithm. I wonder if it’s similar to linear independence, and the dominated choice is trying to “force” itself into the solution when it’s really just extraneous data? Or if it’s because the P[sub]dominated[/sub] is not actually equal to the P[sub]dominating[/sub], and is instead equal to zero. That would give three equations and three unknowns; I think the method you posted is actually three equations with three unknowns, too. I’ll have to check it out in the morning.