Unformatted text preview:

CS 684 Algorithmic Game Theory Scribe: Mauro SozioInstructor: Eva Tardos November 2, 20051 Two persons gameIn this lesson we will talk about the two persons game and in particular, about the zero-sum games.In a 2 persons game there are one or more matrices which describe the game.For example in the rock-paper-scissors game there are two players the row player and the columnplayer. A matrix A specifies the payoffs for the row player. So, if the row player chooses row i andcolumn player choose column j the former gives to the latter aij. In Table 1 we report the matrixwith the payoffs.Another example of a 2 persons game is the coop erate-defec t game. In this game we have twomatrices. One matrix A for the payoffs of the row player and another matrix B for the columnplayer. If the 2 players cooperate then they will pay a low payoff but if one of the player cooperatesand the other defec ts then the former will pay 0 and the latter will pay the maximum payoff.Finally, if both defect they will pay a medium payoff. In Table 2 we report the two matrices.We say that the rock-paper-scissors-game is a zero-sum games because A + B = 0. In generalevery game in which the looser pay the winner is a zero-sum game. The cooperate-defect game isan example of a non-zero sum game.2 Randomized NashA randomized Nash is a probability distribution p of rows and q of columns, where p is a row vectorand q is a column vector. For example the rock-paper-scissors game has a unique randomized Nashand it is a uniform distribution on rows and columns.Given the probability distribution p and q let us compute the exp ec ted benefits for the twoplayers. We have that:expected benefit for row player = pAqexpected benefit for column player = pBqThe probability distributions p and q are in a Nash equilibrium if and only if given q row playerdoes not want to change p and given p the column player does not to change q. That is, if pi> 0the ith entry of Aq is the entry with the maximum value and qj> 0 implies that jth entry of pBis the entry with maximum value.R P SR 0 1 -1P -1 0 1S 1 -1 0Table 1: The payoffs of the row player in the rock-paper-scissors game.C DC 1,1 5,0D 0,5 4,4Table 2: The payoffs of the two players in the cooperate-defect game.What does it mean for a zero-sum game to be in a Nash equilibrium? Remember that in this casewe have only a matrix A that contains the payoffs of the row player and the win of column player.So from the row perspective Aq is the expected loss on rows, and from the column p e rspective pAis the expected win on columns.Suppose row publishes his strategy, what is the minimum guaranteeable loss for row? Let vRthis value. Row player wants to make maximum entry in pA as small as possible, so he wants tominimize vRsuch that pA ≤ vRe e = (1, . . . , 1).And what about the maximum guaranteeable win for column player when he publishes hisstrategy? Let vCthis value. He wants to make the minimum entry of Aq as small as possible, sohe wants to maximize vCsuch that Aq ≥ vCe e = (1, . . . , 1) where e is a column vector.What is the relation betwe en vRand vC? In the next class we will prove that vR= vCon allzero-sum


View Full Document

CORNELL CS 684 - Study Guide

Download Study Guide
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Study Guide and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Study Guide 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?