Unformatted text preview:

7. Infinite Games.In this Chapter, we treat infinite two-person, zero-sum games. These are games(X, Y, A), in which at least one of the strategy sets, X and Y , is an infinite set. Thefamous example of Exercise 4.7.3, he-who-chooses-the-larger-integer-wins, shows that aninfinite game may not have a value. Even worse, the example of Exercise 4.7.5 showsthat the notion of a value may not even make sense in infinite games without furtherrestrictions. This latter problem can be avoided if we assume that the function A(x, y)iseither bounded above or bounded below.7.1 The Minimax Theorem for Semi-Finite Games. The minimax theorem forfinite games states that every finite game has a value and both players have optimal mixedstrategies. The first theorem below generalizes this result to the case where only one ofthe players has a finite number of pure strategies. The conclusion is that the value existsand the player with a finite number of pure strategies has an optimal mixed strategy. Butfirst we must discuss mixed strategies and near optimal strategies for infinite games.Mixed Strategies f or Infinite Games: First note that for infinite games, the notionof a mixed strategy is somewhat open to choice. Suppose the strategy set, Y ,ofPlayerII is infinite. The simplest choice of a mixed strategy is a finite distribution over Y .This is a distribution that gives all its probability to a finite number of points. Such adistribution is described by a finite number of points of Y ,sayy1,y2,...,yn,andasetofprobabilities, q1,q2,...,qnsumming to one with the understanding that point yjis chosenwith probability qj. We will denote the set of finite distributions on Y by Y∗F.When Y is an interval of the real line, we may allow as a mixed strategy any distribu-tion over Y given by its distribution function, F (z). Here, F (z) represents the probabiitythat the randomly chosen pure strategy, y,islessthanorequaltoz. The advantage ofenlarging the set of mixed strategies is that it then becomes more likely that an optimalmixed strategy will exist. The payoff for using such a strategy is denoted by A(x, F )forx ∈ X.Near Optimal Strategies for Infinite Games: When a game has a finite value andan optimal strategy for a player does not exist, that player must be content to choosinga strategy that comes within  of achieving the value of the game for some small >0.Such a strategy is called an -optimal strategy and was discussed in Chapter 6.In infinite games, we allow the value to be +∞ or −∞. For example, the value is +∞if for every number B, however large, there exists a mixed strategy p for Player I suchthat A(p,y) ≥ B for all y ∈ Y . A simple example would be: X =[0, ∞), Y arbitrary, andA(x, y)=x independent of y.Thevalueis+∞,sinceforanyB, Player I can guaranteewinning at least B by choosing any x ≥ B. Such a strategy might be called B-optimal.We will refer to both -optimal and B-optimal strategies as near optimal strategies.The Semi-Finite Minimax Theorem.For finite X = {x1,...,xm},wedenotethesetof mixed strategies of Player I as usual by X∗.IfPlayerIusesp ∈ X∗and Player II usesII – 1q ∈ Y∗F, then the average payoff is denoted byA(p, q)=ijpiA(xi,yj)qj. (1)We denote the set of mixed strategies of Player II by Y∗, but we shall always assume thatY∗F⊂ Y∗.Consider the semi-finite two-person zero-sum game, (X, Y, A), in which X is a finiteset, Y is an arbitrary set, and A(x, y) is the payoff function — the winnings of Player Iif he chooses x ∈ X and Player II chooses y ∈ Y . To avoid the the possibility that theaverage payoff does not exist or that the value might be −∞, we assume that the payofffunction, A(x, y), is bounded below. By bounded below, we mean that there is a numberM such that A(x, y) >M for all x ∈ X and all y ∈ Y . This assumption is weak fromthe point of view of utility theory because, as mentioned in Appendix 1, it is customaryto assume that utility is bounded.It is remarkable that the minimax theorem still holds in this situation. Specificallythe value exists and Player I has a minimax strategy. In addition, for every >0, PlayerII has an -minimax strategy within Y∗F.Theorem 7.1. If X is finite and A is bounded below, then the game (X, Y, A) has a finitevalue and Player I h as an optimal mixed strategy. In addition, if X has m elements, thenPlayer II has near optimal strategies that give weight to at m os t m points of Y .This theorem is valid without the asumption that A is bounded below provided PlayerII is restricted to finite strategies, i.e. Y∗= Y∗F. See Exercise 1. However, the value maybe −∞, and the notion of near optimal strategies must be extended to this case.By symmetry, if Y is finite and A is bounded above, then the game (X, Y, A)hasavalue and Player II has an optimal mixed strategy.Solving Semi-Finite Games. Here are two methods that may be used to solve semi-finite games. We take X to be the finite set, X = {x1,...,xm}.METHOD 1. The first method is similar to the method used to solve 2 × n gamespresented in Section 2.2. For each fixed y ∈ Y , the payoff, A(p,y), is a linear function of pon the set X∗= {p =(p1,...,pm):pi≥ 0,pi=1}. The optimal strategy for Player I isthat value of p that maximizes the lower envelope, f(p) ≡ infy∈YA(p,y). Note that f(p),being the infimum of a collection of concave continuous (here linear) functions, is concaveand continuous on X∗.SinceX∗is compact, there exists a p at which the maximum of f(p)is attained. General methods for solving concave maximization problems are available.Example 1. Player I chooses x ∈{x1,x2},PlayerIIchoosesy ∈ [0, 1], and the payoffisA(x, y)= y if x = x1(1 −y)2if x = x2II – 201.55301y=0y=1/4y=.382y=1/2y=2/3y=1Figure 7.1Let p denote the probability that Player I chooses x1. For a given choice of y ∈ Y byPlayer II, the expected payoff to Player I is A(p, y)=py +(1− p)(1 − y)2. The minimumof A(p, y)overy occurs at p − (1 −p)2(1 − y) = 0, or y =(2− 3p)/(2 − 2p); except thatfor p>2/3, the minimum occurs at y =0. So,f(p)=minyA(p, y)= p4−5p4−4pif p ≤ 2/31 − p if p ≥ 2/3The maximum of this function occurs for p ≤ 2/3, and is easily found to be p =1−(1/√5) = .553 .... The optimal strategy for Player II occurs at that value of y for whichthe slope of A(p, y) (as a function of p) is zero. This occurs when y =(1− y)2. We findy =(3−√5)/2=.382


View Full Document

UCLA STATS 596 - Infinite Games

Documents in this Course
Kelly

Kelly

8 pages

Load more
Download Infinite Games
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 Infinite Games 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 Infinite Games 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?