Ferguson T. S., Game Theory Text.pdf

GAME THEORY

Thomas S. Ferguson

University of California at Los Angeles

Contents

Introduction.

References.

Part I. Impartial Combinatorial Games.

1.1 Take-Away Games.

1.2 The Game of Nim.

1.3 Graph Games.

1.4 Sums of Combinatorial Games.

1.5 Coin Turning Games.

1.6 Green Hackenbush.

References.

Part II. Two-Person Zero-Sum Games.

2.1 The Strategic Form of a Game.

2.2 Matrix Games. Domination.

2.3 The Principle of Indiﬀerence.

2.4 Solving Finite Games.

2.5 The Extensive Form of a Game.

2.6 Recursive and Stochastic Games.

2.7 Continuous Poker Models.

Part III. Two-Person General-Sum Games.

3.1 Bimatrix Games — Safety Levels.

3.2 Noncooperative Games — Equilibria.

3.3 Models of Duopoly.

3.4 Cooperative Games.

Part IV. Games in Coalitional Form.

4.1 Many-Person TU Games.

4.2 Imputations and the Core.

4.3 The Shapley Value.

4.4 The Nucleolus.

Appendixes.

A.1 Utility Theory.

A.2 Contraction Maps and Fixed Points.

A.3 Existence of Equilibria in Finite Games.

INTRODUCTION.

Game theory is a fascinating subject. We all know many entertaining games, such

as chess, poker, tic-tac-toe, bridge, baseball, computer games — the list is quite varied

and almost endless. In addition, there is a vast area of economic games, discussed in

Myerson (1991) and Kreps (1990), and the related political games, Ordeshook (1986),

Shubik (1982), and Taylor (1995). The competition between ﬁrms, the conﬂict between

management and labor, the ﬁght to get bills through congress, the power of the judiciary,

war and peace negotiations between countries, and so on, all provide examples of games in

action. There are also psychological games played on a personal level, where the weapons

are words, and the payoﬀs are good or bad feelings, Berne (1964). There are biological

games, the competition between species, where natural selection can be modeled as a game

played between genes, Smith (1982). There is a connection between game theory and the

mathematical areas of logic and computer science. One may view theoretical statistics as

a two person game in which nature takes the role of one of the players, as in Blackwell and

Girshick (1954) and Ferguson (1968).

Games are characterized by a number of players or decision makers who interact,

possibly threaten each other and form coalitions, take actions under uncertain conditions,

and ﬁnally receive some beneﬁt or reward or possibly some punishment or monetary loss.

In this text, we study various models of games and create a theory or a structure of the

phenomena that arise. In some cases, we will be able to suggest what courses of action

should be taken by the players. In others, we hope to be able to understand what is

happening in order to make better predictions about the future.

As we outline the contents of this text, we introduce some of the key words and

terminology used in game theory. First there is the number of players which will be

denoted by n . Let us label the players with the integers 1 to n , and denote the set of

players by N = { 1 , 2 ,...,n} . We will study mostly two person games, n =2,wherethe

concepts are clearer and the conclusions are more deﬁnite. When specialized to one-player,

the theory is simply called decision theory. Games of solitaire and puzzles are examples

of one-person games as are various sequential optimization problems found in operations

research, and optimization, (see Papadimitriou and Steiglitz (1982) for example), or linear

programming, (see Chvatal (1983)), or gambling (see Dubins and Savage(1965)). There

are even things called “zero-person games”, such as the “game of life” of Conway (see

Berlekamp et al. (1982) Chap. 25); once an automaton gets set in motion, it keeps going

without any person making decisions. We will assume throughout that there are at least

two players, that is, n

There are three main mathematical models or forms used in the study of games, the

extensive form ,the strategic form and the coalitional form . These diﬀer in the

2. In macroeconomic models, the number of players can be very

large, ranging into the millions. In such models it is often preferable to assume that there

are an inﬁnite number of players. In fact it has been found useful in many situations to

assume there are a continuum of players, with each player having an inﬁnitesimal inﬂuence

on the outcome as in Aumann and Shapley (1974). In this course, we always take n to be

ﬁnite.

≥

amount of detail on the play of the game built into the model. The most detail is given

in the extensive form, where the structure closely follows the actual rules of the game. In

the extensive form of a game, we are able to speak of a position in the game, and of a

move of the game as moving from one position to another. The set of possible moves

from a position may depend on the player whose turn it is to move from that position.

In the extensive form of a game, some of the moves may be random moves , such as the

dealing of cards or the rolling of dice. The rules of the game specify the probabilities of

the outcomes of the random moves. One may also speak of the information players have

when they move. Do they know all past moves in the game by the other players? Do they

know the outcomes of the random moves?

When the players know all past moves by all the players and the outcomes of all past

random moves, the game is said to be of perfect information . Two-person games of

perfect information with win or lose outcome and no chance moves are known as combi-

natorial games . There is a beautiful and deep mathematical theory of such games. You

may ﬁnd an exposition of it in Conway (1976) and in Berlekamp et al. (1982). Such a

game is said to be impartial if the two players have the same set of legal moves from each

position, and it is said to be partizan otherwise. Part I of this text contains an introduc-

tion to the theory of impartial combinatorial games. For another elementary treatment of

impartial games see the book by Guy (1989).

We begin Part II by describing the strategic form or normal form of a game. In the

strategic form, many of the details of the game such as position and move are lost; the main

concepts are those of a strategy and a payoﬀ. In the strategic form, each player chooses a

strategy from a set of possible strategies. We denote the strategy set or action space

of player i by A i ,for i =1 , 2 ,...,n . Each player considers all the other players and their

possible strategies, and then chooses a speciﬁc strategy from his strategy set. All players

make such a choice simultaneously, the choices are revealed and the game ends with each

player receiving some payoﬀ. Each player’s choice may inﬂuence the ﬁnal outcome for all

the players.

We model the payoﬀs as taking on numerical values. In general the payoﬀs may

be quite complex entities, such as “you receive a ticket to a baseball game tomorrow

when there is a good chance of rain, and your raincoat is torn”. The mathematical and

philosophical justiﬁcation behind the assumption that each player can replace such payoﬀs

with numerical values is discussed in the Appendix under the title, Utility Theory .This

theory is treated in detail in the books of Savage (1954) and of Fishburn (1988). We

therefore assume that each player receives a numerical payoﬀ that depends on the actions

chosen by all the players. Suppose player 1 chooses a 1 ∈

A i ,player2chooses a 2 ∈

A 2 ,etc.

A n . Then we denote the payoﬀ to player j ,for j =1 , 2 ,...,n ,

by f j ( a 1 ,a 2 ,...,a n ), and call it the payoﬀ function for player j .

The strategic form of a game is deﬁned then by the three objects:

(1) the set, N = { 1 , 2 ,...,n} ,ofplayers,

(2) the sequence, A 1 ,...,A n , of strategy sets of the players, and

and player n chooses a n ∈

(3) the sequence, f 1 ( a 1 ,...,a n ) ,...,f n ( a 1 ,...,a n ), of real-valued payoﬀ functions of

the players.

A game in strategic form is said to be zero-sum if the sum of the payoﬀs to the

players is zero no matter what actions are chosen by the players. That is, the game is

zero-sum if

f i ( a 1 ,a 2 ,...,a n )=0

i =1

A n . In the ﬁrst four chapters of Part II, we restrict

attention to the strategic form of two-person, zero-sum games. Theoretically, such games

have clear-cut solutions, thanks to a fundamental mathematical result known as the mini-

max theorem . Each such game has a value , and both players have optimal strategies

that guarantee the value.

A 1 , a 2 ∈

A 2 , ... , a n ∈

In the last three chapters of Part II, we treat two-person zero-sum games in extensive

form, and show the connection between the strategic and extensive forms of games. In

particular, one of the methods of solving extensive form games is to solve the equivalent

strategic form. Here, we give an introduction to Recursive Games and Stochastic Games,

an area of intense contemporary development (see Filar and Vrieze (1997), Maitra and

Sudderth (1996) and Sorin (2002)).

In Part III, the theory is extended to two-person non-zero-sum games. Here the

situation is more nebulous. In general, such games do not have values and players do not

have optimal optimal strategies. The theory breaks naturally into two parts. There is the

noncooperative theory in which the players, if they may communicate, may not form

binding agreements. This is the area of most interest to economists, see Gibbons (1992),

and Bierman and Fernandez (1993), for example. In 1994, John Nash, John Harsanyi

and Reinhard Selten received the Nobel Prize in Economics for work in this area. Such

a theory is natural in negotiations between nations when there is no overseeing body

to enforce agreements, and in business dealings where companies are forbidden to enter

into agreements by laws concerning constraint of trade. The main concept, replacing

value and optimal strategy is the notion of a strategic equilibrium , also called a Nash

equilibrium . This theory is treated in the ﬁrst three chapters of Part III.

On the other hand, in the cooperativetheory the players are allowed to form binding

agreements, and so there is strong incentive to work together to receive the largest total

payoﬀ. The problem then is how to split the total payoﬀ between or among the players.

This theory also splits into two parts. If the players measure utility of the payoﬀ in the

same units and there is a means of exchange of utility such as side payments ,wesaythe

game has transferable utility ;otherwise non-transferable utility .Thelastchapter

of Part III treat these topics.

When the number of players grows large, even the strategic form of a game, though less

detailed than the extensive form, becomes too complex for analysis. In the coalitional

form of a game, the notion of a strategy disappears; the main features are those of a

coalition and the value or worth of the coalition. In many-player games, there is a

tendency for the players to form coalitions to favor common interests. It is assumed each

for all a 1 ∈

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: