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.
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.
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.
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.
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.
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?
It’s a straightforward linear programming problem. See here. There are fairly efficient algorithms for such things, and thus automated tools, though I don’t know of where to get one.
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.
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.
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.
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] = 0R + 6W + 2B, P[sub]W[/sub] = -2R + 4W + 3B, and P[sub]B[/sub] = 3R -3W -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.
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”.
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.
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.