Appendix F: Randomized Strategies

The game described in Appendix E was played under the assumption that it was to be played only once. Hence, once R and C have selected their strategies, the result of the game is determined. Suppose, however, that a sequence of games is to be played and that R and C are permitted to change their strategies from game to game. How should they proceed then? Since each contestant assumes that the other is just as intelligent as he is, they dare not develop a systematic pattern of choosing strategies for fear of this being discovered ; hence, it would be advisable for them to choose their successive strategies by means of some random scheme. This can be accomplished by having R select a sect of probabilities p ₁ , p ₂ , ..., p _m that will determine the relative frequencies with which he wishes his strategies R ₁ , R ₂ , ..., R _m to be played. Similarly, C is permitted to select a set of probabilities q ₁ , q ₂ , ..., q _n that will determine the relative frequencies with which he wishes his strategies C ₁ , C ₂ , ..., C _n to be played.

As an illustration, in the game of the preceding section R might choose

Each time the game is to be played, R will use a game of chance that yields p ₁ twice as frequently as p ₂ to choose one of those strategies. This could be done, for example, by drawing a card from a set of three cards that contains two aces and one deuce. Similarly, C could draw a card from a set of four cards that contains two aces, one deuce, and one three.

Strategies that are selected by chance according to a set of probabilities are called randomized strategies. They include the one-play strategies that were obtained in the preceding section because it is merely necessary to choose p ₁ = 1, p ₂ = 0, and q ₁ = 0, q ₂ = 1, q ₃ = 0 to arrive at the strategies R ₁ and C ₂ that were determined for that game. If a player uses a set of probabilities in which one of them is 1 and all the rest are 0, he is said to be using a pure strategy, otherwise he is using a mixed strategy.

Even though a game is to be played only once, and this is the natural situation in most business-type games, it may be that one of the competitors can do better than the other by employing randomization in choosing his strategy. Therefore, we take a fresh look at our earlier one-play games in studying randomized games to see if improvements are possible by using randomization.

Since the payoffs will vary from game to game because they will depend on chance, we look at the average payoff in a long sequence of games. This is equivalent to looking at the expected value of the payoff. Now the expected value of the payoff in the ith row and jth column of the payoff matrix A is merely a _ij P _i q _j because the row and column choices are made independently, and therefore the probability of R winning the amount a _ij is the product of the ith row and jth column probabilities.

As an illustration of a randomized payoff matrix, consider a matrix with the possibilities of p ₁ = , p ₂ = , q ₁ = , q ₂ = , and q ₃ = . Letting B denote this matrix we find that

The expected payoff to R is the sum of these individual expected payoff values. Their sum is found to be 2 1/4; therefore, R would do slightly better under these two sets of randomized strategies than under the original nonrandomized version of the game. It may well be, however, that C chose a poor set of probabilities here. The purpose of this example is to illustrate how expected payoffs are calculated; it is not intended to illustrate good randomized strategies.

After a set of probabilities has been selected by each of R and C and the corresponding expected payoff matrix is calculated, the game is completely determined and could be played by a machine that selects successive pairs of strategies according to the probabilities p ₁ ,...,p _m and q ₁ ,...,q _n .

The interesting question now is: How should R and C choose their probabilities? For example, is it possible for R to do better than C in the preceding illustrative game if his probabilities are chosen properly, regardless of what probabilities C chooses? In the preceding illustration, R did do better but perhaps C could have prevented this with a better set of probabilities. The answer to this question is as follows : Independent of what probabilities R selects, C can find a set of probabilities such that the expected value of the payoff to R will not exceed $2. In addition, regardless of what probabilities C may select, R can find a set of probabilities such that he can be assured of averaging at least $2. Thus neither R nor C can gain in this particular problem by using mixed strategies rather than pure strategies, provided that both R and C employ their best defensive randomized strategies.