tailieunhanh - IE675 Game Theory - Lecture Note Set 2

TWO-PERSON GAMES Two-Person Zero-Sum Games Basic ideas Definition . A game (in extensive form) is said to be zero-sum if and only if, at each terminal vertex, the payoff vector (p1 , . . . , pn ) satisfies n pi = 0. i=1 Two-person zero sum games in normal form. Here’s an example. . . −1 −3 −3 −2 1 −2 −1 A= 0 2 −2 0 1 | IE675 Game Theory Lecture Note Set 2 Wayne F. Bialas1 Wednesday January 19 2005 2 TWO-PERSON GAMES Two-Person Zero-Sum Games Basic ideas Definition . A game in extensive form is said to be zero-sum if and only if at each terminal vertex the payoff vector p1 . pn satisfies Y 1 Pi 0- Two-person zero sum games in normal form. Here s an example. 1 3 3 2 A 0 1 2 1 2 2 0 1 The rows represent the strategies of Player 1. The columns represent the strategies of Player 2. The entries aij represent the payoff vector aij aij . That is if Player 1 chooses row i and Player 2 chooses column j then Player 1 wins aij and Player 2 loses aj. If aij 0 then Player 1 pays Player 2 aij . Note . We are using the term strategy rather than action to describe the player s options. The reasons for this will become evident in the next chapter when we use this formulation to analyze games in extensive form. Note . Some authors in particular those in the field of control theory prefer to represent the outcome of a game in terms of losses rather than profits. During the semester we will use both conventions. 1 Department of Industrial Engineering University at Buffalo 301 Bell Hall Buffalo NY 142602050 USA E-mail bialas@ Web http bialas. Copyright @ MMV Wayne F. Bialas. All Rights Reserved. Duplication of this work is prohibited without written permission. This document produced January 19 2005 at 3 33 pm. 2-1 How should each player behave Player 1 for example might want to place a bound on his profits. Player 1 could ask For each of my possible strategies what is the least desirable thing that Player 2 could do to minimize my profits For each of Player 1 s strategies i compute a min a j j and then choose that i which produces max a . Suppose this maximum is achieved for i i . In other words Player 1 is guaranteed to get at least V A min a j min a j i 1 . m The value V A is called the gain-floor for the game A. In this case V A 2 with i 2 2 3 . .