Game Theory 4 PDF

to compute, the equilibria of zero-sum game, and we do it by simply laying out a linear program that captures the game. And here it is. So, u1* is going to be the value of the game. That is the payoff to player 1 in equilibrium. And so, we're going to specify from player's two point of view. We coul...

to compute, the equilibria of zero-sum game, and we do it by simply laying out a linear program that captures the game. And here it is. So, u1* is going to be the value of the game. That is the payoff to player 1 in equilibrium. And so, we're going to specify from player's two point of view. We could have done it the other way around also. So what player two is saying, is simply, says for each of the actions of player one, each action that player one Might consider. I want to find a mixed strategy s2, so here's my mixed strategy s2. It will look at all my 2 strategies k and make sure that, that probability, this probability distribution over the sum, the sum to 1 and they're not negative. So what I'd like to do, is that the best response to my strategy by player one for any of these actions will never exceed this value of the game, because I am trying to minimize it. So I am going to find the lowest u that has a property that player 1 doesn't have a preferable deviation by any of his, of his of his pure strategies. So when I look at the payoff For player 2. When I play, A2K, and he plays A1J. That would, that J that I'm considering right now. And I multiply the probability of, in my mixed strategy playing, A2K. I don't want that player one, to have a profile deviation so its got to be that expected pay off will be no greater than the value you want to start so clearly this is a correct formulation of the game and it is a linear program as we know linear programs are efficiently solvable. In theory by a interior method that is provably polyomial in practice by procedures that are worst case exponential, but in practice work well.