TEL  Vol.8 No.10 , June 2018
An Alternative Interpretation of Mixed Strategies in n-Person Normal Form Games via Resource Allocation
ABSTRACT
In this paper, we give an interpretation of mixed strategies in normal form games via resource allocation games, where all players utilize the same resource. We define a game in normal form such that each player allocates to each of his pure strategies a fraction of the maximum resource he has available. However, he does not necessarily allocate all of the resource at his disposal. The payoff functions in the resource allocation games vary with how each player allocates his resource. We prove that a Nash equilibrium always exists in mixed strategies for n-person resource allocation games. On the other hand, we show that a mixed Berge equilibrium may not exist in such games.

1. Introduction

Game theory is the study of mathematical decision making among multiple players. Each player makes an individual choice according to his notion of rationality and to his expectations of the other players’ choices. Game theory can be non-cooperative as described in [1] or cooperative as described in [2] . In non-cooperative game theroy, the concept of the Nash equilibrium (NE) was introduced in [3] and [4] . The proof of the existence was based on the Kakutani and the Brouwer fixed point theorems [5] . Another solution concept, the Berge equilibrium, was introduced in [6] and formalized by [7] . A strategy is considered to be a Berge equilibrium if some or all players other than player i cannot increase the expected payoff for player i by changing strategies. The Berge equilibrium was extended to mixed strategies in [8] , where it was also shown that a mixed Berge equilibrium may not exist.

The computation of equilibria points is an essential component of game theory research and is well studied in the literature. For example, a nonlinear programming approach to find an NE for three player games was developed in [9] and for n-person games in [10] . The nonlinear programming approach for finding an NE was extended in [11] to find a generalized equilibrium that includes the case of an MBE.

Such equilibria have been widely in economics. However, game theory faces some challenges such as making it more useful in applications as noted in [12] . Thus there is a need for a behavior interpretation of a strategy. For example, [13] gives a behavioral interpretation of a dominant strategy, while belief hierarchies play a prominent role in game theory as described in [14] . Moreover, there has been a growing use of epistemic game theory. [15] gives a historical overview of the transition from classical game theory in the sense of Nash to epistemic game theory.

The purpose of this paper is to deal with the difficulties associated with mixed strategies. See [16] for an extensive literature review on the concept of mixed strategies, which require a randomizing process as described in [17] and [18] . According to [19] , randomization lacks behavioral support. [20] gives two interpretations for mixed strategies. The first is based on the purification theorem of [21] . Purification refers to how mixed strategies reflect the player’s lack of knowledge of other players’ information and decision-making process. The second interpretation is that a mixed strategy represents the fraction of a large population that adapts each of the pure strategies. In [22] mixed strategies are interpreted as the belief player i’s opponents have on what strategy player i will choose. Therefore, as argued in [16] , mixed strategies are used in games where a pure NE does not exist, but their use is principally to provide an elegant mathematical theory. In practice, they are problematic with no generally accepted interpretation. We offer here a simple, intuitive interpretation for a certain class of games.

In this paper, we construct resource allocation games (RAGs) such that the equilibria strategies represent the fraction of a resource each player allocates to each of his pure strategies. In particular, we consider the NE and the MBE. The purpose of RAGs is to give a physical interpretation of the concept of mixed strategies, as distinguished from other interpretations. Our interpretation is as follows. The probability that a player chooses a pure strategy equals the fraction of the resource the player allocates to that pure strategy over the total amount of the resource the player allocates to all his pure strategies. The underlying idea is as follows. Suppose there is a single resource used by all players. Suppose player 1 had 100 units of the resource to be used up in whole or in part. If he considered using 40 units on implementing strategy 1 and 60 units on implementing strategy 2, whatever they are, then his associated mixed game theoretic strategy would be (0.4, 0.6), Thus in a RAG, he would choose both strategies as opposed to one chosen by, say, randomization. In other words, in a resource allocation game, one pure strategy does not preclude another. This simple idea is generalized here. A related notion was studied in [23] for infinitely repeated non-cooperative games played at discrete instants called stages. The payoffs in [23] were linear in the frequency that they had been played previously. Our approach differs significantly. For example, here a mixed strategy may or may not maximize the payoff functions for each player.

The organization of this paper is as following. In Section 2, we present the notation used. In Section 3, we prove the existence of an NE for a RAG. In Section 4, we present a nonlinear program to find an NE analytically. In Section 5, we consider the case of the MBE and present a nonlinear program to find one if one exists. In Section 6, we give some numerical examples and show that an MBE may not exist. In Section 7, we state our conclusions.

2. Preliminaries

In this section we define the notation used. Let the RAG Γ = I , ( S i ) i I , ( f i ) i I be an n-person resource allocation game in normal form with exactly one resource. The set I = 1 , , n is the set of the n-players. Let R i be the resource available for player i, so the n-tuple R = ( R 1 , , R n ) represents the amount of the resource each player has available. Define R i min > 0 to be the minimum

amount of the resource R i player i needs to allocate and α i min = R i min R i . The set of the m i pure strategies for player i is S i = ( s i 1 , , s i m i ) .

Each player player i allocates from his resource R i the fraction α i j to his pure strategy s i j , j = 1 , , m i . The set of all possible allocations for each player i is

Δ i = { α i = ( α i 1 , , α i m i ) : α i j 0 , j = 1 , , m i , α i min j = 1 m i α i j 1 } . (1)

Note that Δ i is compact and convex for each player i I . Let Δ i = Δ 1 × × Δ i 1 × Δ i + 1 × × Δ n and Δ = Δ 1 × × Δ n . The probability the player i chooses strategy s i j is α i j j = 1 m i α i j . Hence a mixed strategy for player i is the mi-tuple

( α i 1 j = 1 m i α i j , , α i m i j = 1 m i α i j ) ,

where α i min j = 1 m i α i j 1 and α i j 0 , j = 1 , , m i . A pure strategy j is an allocation α i min α i j 1 where the player i allocates α i j to his pure strategy j and allocates 0 to the rest of his pure strategies. The payoff function for each player is f i j , k ( α ) , where α = ( α 1 , , α n ) and α i = ( α 1 , , α i 1 , α i + 1 , , α n ) . The payoff functions f i j , k ( α ) , j = 1 , , m i , k = 1 , , m i are assumed to be continuous in α i j [ 0 , 1 ] , j = 1 , , m i , i I .

The set of joint pure strategies of all players other than player i, is the Cartesian product of the sets of pure strategies of all players other than player i, S i = × j I { i } ( S j ) and is denoted by S i = { s i 1 , , s i m i } , where

m i = j I { i } m j .

The joint probability

α i k = p I { i } α p k j = 1 m p α p j , k = 1 , , m i

is the probability that all the players other than player i choose the joint pure strategy s i k . It is the product of the fraction that each player in I { i } = { 1 , , i 1 , i + 1 , , n } allocates to his corresponding strategy.

We apply the identities proved in [8] to Γ . The following identities represent the expected payoff for player i. If player i allocates α i min α i j 1 to his strategy j and he allocates 0 to his other pure strategies while the rest of players choose the allocation α i is

F i j ( α ) = k = 1 m i α i k f i j , k ( α ) . (2)

If player i chooses the mixed allocation α i and the rest of players choose the allocation α i , then the expected payoff for player i is

F i ( α ) = j = 1 m i k = 1 m i α i j j = 1 m i α i j α i k f i j , k ( α ) . (3)

Table 1 shows an example of a 2-person RAG.

In this paper, it is useful to consider the following two cases.

1) Case 1. Each player i allocates all of his resource R i . In other words, j = 1 m i α i j = 1 , i I . In this case, each player i chooses strategy j with the probability α i j .

2) Case 2. Each player i does not necessarily allocate all of his resource R i . Hence α i min j = 1 m i α i j 1 , i I . In this case, each player i chooses strategy j with the probability

α i j j = 1 m i α i j , j = 1 , , m i .

Table 1. Example of a RAG.

R i , i I is considered fixed in these two cases. However, in the second case each player i may not use all of his resource. Note that the first case is a special case of the second case. In particular if R i min = R i , then the second case becomes the first case. We formalize this previous statement as follows.

Lemma 1. i I let R i min = R i . Then Case 1 and Case 2 are equivalent.

Proof. Let R i min = R i , i I . Hence α i min = 1 and j = 1 m i α i j = 1 . It follows immediately that Case 2 reduces to Case 1.

3. Existence of an NE for a RAG

In this section we prove the existence of an NE in Case 1 and Case 2 above. Hence we seek to find a mixed strategy such that a player i chooses strategy j with a probability

α i j j = 1 m i α i j , j = 1 , , m i , i I .

We next restate the definition of an NE in terms of allocation.

Definition 1. A strategy α * is an NE if and only if

F i ( α * ) = max j = 1 , , m i F i j ( α * ) , α i Δ i , i I . (4)

Intuitively, in an NE for the game Γ , no player can improve his expected payoff with a unilateral change in strategy, i.e., a unilateral reallocation of his previously allocated resource level. We now prove the existence of an NE in a finite n-person Γ . It suffices to prove the existence for case 2 since it subsumes case 1 by Lemma 1 when R i min = R i . The proof of the next theorem is similar to the proof of the existence of an equilibrium in [4] . Let

Δ i = { α i : α i j 0 , j = 1 , , m i , α i min j = 1 m i α i j 1 } (5)

and Δ = Δ 1 × × Δ n . The set Δ is compact and convex since the number of player is finite and each player has a finite number of strategies. Define the function ϕ = ( ϕ 1 , , ϕ n ) : Δ Δ where ϕ i = ( ϕ i 1 , , ϕ i m i ) and

ϕ i j = α i j + max { 0 , F i j ( α ) F i ( α ) } 1 + j = 1 m i max { 0 , F i j ( α ) F i ( α ) } , i = 1 , , n , j = 1 , , m i . (6)

The functions ϕ i j are continuous since we assume that the f i j , k ( α ) are continuous in α i j [ 0 , 1 ] , j = 1 , , m i , i I . Therefore by the Brouwer fixed point theorem there exists fixed points

α i j = α i j + max { 0 , F i j ( α ) F i ( α ) } 1 + j = 1 m i max { 0 , F i j ( α ) F i ( α ) } , i = 1 , , n , j = 1 , , m i . (7)

We now prove the following result.

Theorem 2. Every finite RAG Γ has an NE in mixed strategies.

Proof. Let α be an NE. Then no player has an incentive to change his strategy based on the allocation α . Note that the function max { 0, F i j ( α ) F i ( α ) } represent player’s i gain by choosing his pure strategy j given the previous allocation α . Hence max { 0 , F i j ( α ) F i ( α ) } = 0 , j = 1 , , m i , i I . Thus α is a fixed point.

Conversely, let α be a fixed point. Then for each i let l be a pure strategy such that α i l > 0 , and F i l ( α ) = min j = 1 , , m i F i j ( α ) . Therefore,

max { 0 , F i j ( α ) F i ( α ) } = 0 , since F i j ( α ) F i ( α ) . Note that from Equation (7),

the right hand side is α i j only when the denominator equals 1. Hence, j = 1 m i max { 0 , F i j ( α ) F i ( α ) } = 0 . Hence no player has an incentive to change his strategy, and so α is an NE allocation to complete the proof.

We next show how a standard n-person game in normal form with constant von Neumann-Morgenstern (VNM) utility functions is a special case of an allocation game as defined in this paper.

Theorem 3. The payoff matrix for a standard normal form game is a special case of the payoff matrix for a RAG.

Proof. Let u i ( s i j , s i k ) = c i j , k , j = 1 , , m i , k = 1 , , m i , i I be constant VNM utilities for a normal form game. It suffices to show that for any player i the VNM utilities can be written as the payoffs for player i in an allocation game Γ . To do so simply let f i j , k ( α ) = c i j , k × R i , R i = 1, i I . It follows that a standard normal form game with constant VNM utilities is a special case of the game Γ to complete the proof.

In other words, for R i = 1 , i I the payoff functions for each player i need not vary with the fraction each player allocates to each of his pure strategies. It follows that for any equilibrium, say an NE or an MBE, a normal form game with VNM utilities is a special case of an associated RAG. In the next section we consider the computation of an NE. The computation of an MBE will be considered in Section 5.

4. The Computation of an NE for a RAG

In this section we provide a nonlinear programming approach to compute an NE for an n-person game by extending the nonlinear program in [10] to find an NE for the game Γ . Therefore an allocation α is an NE if and only the maximum of the following nonlinear program is zero.

Theorem 4. α * is an NE for Γ if and only if the maximum of the following nonlinear program is 0.

Maximize g ( α , β ) = i = 1 n [ F i ( α ) β i ] subject to k = 1 m i α i k f i j , k ( α ) β i , j = 1 , , m i , i I , α i j 0, j = 1, , m i , i I , α i min j = 1 m i α i j 1 , i I . (8)

Proof. Let α * be an NE where each player i allocates j = 1 m i α i j * of his total resource R i . Then F i ( α * ) = max j F i j ( α * ) = β i * . Therefore g ( α * , β * ) = 0 . Furthermore, all constraints (8) are satisfied since from Definition 1 β i * = max j = 1 , , m i F i j ( α * ) .

Conversely, let α * , β * be a feasible point such that g ( α * , β * ) = 0 . It can easily be checked by the constraints (8) and Equation (3) that F i ( α * ) β i * . Hence it must be the case that F i ( α * ) = β i * . Otherwise g ( α * , β * ) 0 which yields a contradiction. Moreover, from the constraints 8 β i * = max j = 1 , , m i F i j ( α * ) . Therefore α * is a NE by Definition 1.

It is worth noting that the payoff functions at an NE may not be maximized. To maximize the payoff functions one needs to find an allocation such that the fraction each player i allocates to each strategy maximizes each of the player i’s payoff functions. However, we analyze only the case where the payoff functions are monotonically nondecreasing functions in the fraction of the resource α i j . In this case, each of the payoff functions is maximized when the total resource R i is allocated to that strategy. In other words, F i j ( α i j = 1 , α i ) F i j ( α i , α i ) , j = 1 , , m i , α i Δ i , i I .

Lemma 5. Let f i j , k ( α ) be monotonically increasing functions in α i j , j = 1 , , m i , i I . Then the optimal strategy for each player is an NE if and only if the maximum of the following nonlinear program is 0.

Maximize g ( α , β ) = i = 1 n [ F i ( α ) β i ] subject to F i j ( α i j = 1 , α i ) β i , j = 1 , , m i , i I , α i j 0 , i I , j = 1 , , m i , j = 1 m i α i j = 1 , i I . (9)

Proof. Let α * be an NE where the payoff is maximized. Then

β i * = max j = 1 , , m i F i j ( α i j * = 1 , α i ) .

However, α * is an NE. Hence from Theorem 4 the maximum of the nonlinear program is 0.

Conversely, let α * , β * be a feasible point such that the maximum of (9) is 0. The functions f i j are monotonically nondecreasing in α i j , i I , j = 1 , , m i . Therefore, there exists a solution that zero-maximizes the objective function and satisfies all the conditions of the nonlinear program in Theorem 4. Hence the solution is an NE. Furthermore, the solution maximizes the expected payoff for each player of over all payoff functions and the proof is complete.

5. The Computation of an MBE for a RAG

In this section, we consider the MBE. We present an approach similar to (8) for computing an MBE if one exists. However, the case of computing an MBE is different from the case of computing an NE since an MBE for n 3 may not exist as shown by the example of section 6. An MBE for a RAG is defined as follows.

Definition 2. A strategy α * is an MBE for Γ if and only if

F i ( α * ) = m a x k = 1, , m i j = 1 m i α i j * j = 1 m i α i j * f i j , k ( α * ) , α i Δ i , i I . (10)

In other words, a strategy is an MBE if for all i = 1 , , n , when player i does not change his strategy, no one or more other players can change strategies and increase player i’s expected payoff. Thus in an MBE for the game Γ , no player has an incentive for a unilateral change of his resource allocation if increasing the other players’ expected payoffs is his completely unselfish objective. We now extend the nonlinear program presented in [11] to the RAG Γ .

Theorem 6. α * is an MBE for Γ if and only if the maximum of the following nonlinear program is 0.

Maximize h ( α , β ) = i = 1 n [ F i ( α ) β i ] subject to j = 1 m i α i j j = 1 m i α i j f i j , k ( α ) β i , k = 1 , , m i , i I , α i j 0 , i I , j = 1 , , m i , α i min j = 1 m i α i j 1 , i I . (11)

Proof. Let α * be an MBE allocation. Then each player allocates to each strategy a fraction α i j * of his resource that equals to the probability that the player uses that strategy. From Definition 2 one can check that F i ( α * ) = β i * = max k = 1 , , m i F i k ( α * ) , i I . Hence all constraints are satisfied. Moreover, h ( β * , α * ) = 0 .

Conversely, let ( α * , β * ) be a feasible solution such that h ( α * , β * ) = 0 . From (11), it is easy to see that F i ( α * ) β i * , i I . But h ( α * , β * ) = 0 , so it must be that F i ( α * ) = β i * , i I and β i * = max k = 1 , , m i F i k ( α ) . Therefore, F i ( α * ) = max k = 1 , , m i F i k ( α * ) , and hence α * is an MBE by Definition 2.

6. Examples

In this section we present three examples. The first example is a 2-person RAG, while the second and third are 3-person RAGs.

Example 1.

In this 2-person RAG each player has 2 strategies. For some single resource, player 1 has R 1 = 30 units and player 2 has R 2 = 50 units. The payoff matrix for each player is shown in Table 2. For this game, we consider Case 1 and Case 2 from Section 2. In the first case, each player uses his maximum resource. The following NLP finds an NE for Γ for Case 1.

Table 2. Example 1.

( P 1 ) Maximize g ( α , β ) = α 1 1 α 1 1 + α 1 2 α 2 1 α 2 1 + α 2 2 ( 3 + α 1 1 × 30 + 5 + α 2 1 × 50 ) + α 1 1 α 1 1 + α 1 2 α 2 2 α 2 1 + α 2 2 ( 2 + α 1 1 × 30 + 8 + α 2 2 × 50 ) + α 1 2 α 1 1 + α 1 2 α 2 1 α 2 1 + α 2 2 ( 2 + α 1 2 × 30 , 6 + α 2 1 × 50 ) + α 1 2 α 1 1 + α 1 2 α 2 2 α 2 1 + α 2 2 ( 5 + α 1 2 × 30 , 4 + α 2 2 × 50 ) β 1 β 2

subject to α 2 1 α 2 1 + α 2 2 ( 3 + α 1 1 × 30 ) + α 2 2 α 2 1 + α 2 2 ( 2 + α 1 1 × 30 ) β 1 α 2 1 α 2 1 + α 2 2 ( 2 + α 1 2 × 30 ) + α 2 2 α 2 1 + α 2 2 ( 5 + α 1 2 × 30 ) β 1 α 1 1 α 1 1 + α 1 2 ( 5 + α 2 1 × 50 ) + α 1 2 α 1 1 + α 1 2 ( 6 + α 2 1 × 50 ) β 2

α 1 1 α 1 1 + α 1 2 ( 8 + α 2 2 × 50 ) + α 1 2 α 1 1 + α 1 2 ( 4 + α 2 2 × 50 ) β 2 α 1 1 + α 1 2 = 1 α 2 1 + α 2 2 = 1.

One solution to (P1) with g ( α * , β * ) = 0 and hence an NE is α 1 1 * = 0.52 , α 1 2 * = 0.48 , α 2 1 * = 0.51 , α 2 2 * = 0.49 , β 1 * = 17.99 , β 2 * = 30.77 .

In Case 2 when each player allocates at least 0.4 of his resource, the following NLP finds an NE strategy for this problem.

( P 2 ) Maximize g ( α , β ) = α 1 1 α 1 1 + α 1 2 α 2 1 α 2 1 + α 2 2 ( 3 + α 1 1 × 30 + 5 + α 2 1 × 50 ) + α 1 1 α 1 1 + α 1 2 α 2 2 α 2 1 + α 2 2 ( 2 + α 1 1 × 30 + 8 + α 2 2 × 50 ) + α 1 2 α 1 1 + α 1 2 α 2 1 α 2 1 + α 2 2 ( 2 + α 1 2 × 30 , 6 + α 2 1 × 50 ) + α 1 2 α 1 1 + α 1 2 α 2 2 α 2 1 + α 2 2 ( 5 + α 1 2 × 30 , 4 + α 2 2 × 50 ) β 1 β 2

subject to α 2 1 α 2 1 + α 2 2 ( 3 + α 1 1 × 30 ) + α 2 2 α 2 1 + α 2 2 ( 2 + α 1 1 × 30 ) β 1 α 2 1 α 2 1 + α 2 2 ( 2 + α 1 2 × 30 ) + α 2 2 α 2 1 + α 2 2 ( 5 + α 1 2 × 30 ) β 1

α 1 1 α 1 1 + α 1 2 ( 5 + α 2 1 × 50 ) + α 1 2 α 1 1 + α 1 2 ( 6 + α 2 1 × 50 ) β 2

α 1 1 α 1 1 + α 1 2 ( 8 + α 2 2 × 50 ) + α 1 2 α 1 1 + α 1 2 ( 4 + α 2 2 × 50 ) β 2 0.4 α 1 1 + α 1 2 1 0.4 α 2 1 + α 2 2 1.

One solution to (P2) with g ( α * , β * ) = 0 and hence an NE is α 1 1 * = 0.45 , α 1 2 * = 0 , α 2 1 * = 0.23 , α 2 2 * = 0.17 , β 1 * = 15.94 , β 2 * = 16.5 . Thus there is an MBE for this example. However, in general an MBE need not exist for n 3 as shown in [8] . In such cased, the interpretation is that there may not exist an allocation such that every player other than player i allocates to each strategy a fraction equals to the probability of using that strategy that maximizes player i’s payoff. In the next example, an MBE does not exist, However, an NE exists by Theorem 2.

Example 2.

In this 3-person RAG each player has 2 strategies with R 1 = R 2 = R 3 = 1 and needs to allocate at least 0.2 of his maximum resource. The payoff matrix for each player is shown in Table 3.

We now write the following NLP to find an MBE.

( P 3 ) Maximize h ( α , β ) = α 1 1 α 1 1 + α 1 2 α 2 1 α 2 1 + α 2 2 α 3 1 α 3 1 + α 3 2 ( 1 + α 2 1 + α 3 1 + 1 + α 1 1 + α 3 1 + 0 ) + α 1 1 α 1 1 + α 1 2 α 2 1 α 2 1 + α 2 2 α 3 2 α 3 1 + α 3 2 ( 1 + α 1 1 + α 2 1 ) + α 1 2 α 1 1 + α 1 2 α 2 2 α 2 1 + α 2 2 α 3 1 α 3 1 + α 3 2 ( 1 + α 1 2 + α 2 2 ) + α 1 2 α 1 1 + α 1 2 α 2 2 α 2 1 + α 2 2 α 3 2 α 3 1 + α 3 2 ( 1 + α 2 2 + α 3 2 + 1 + α 1 2 + α 3 2 ) β 1 β 2 β 3

subject to α 1 1 α 1 1 + α 1 2 ( 1 + α 2 1 + α 3 1 ) + α 1 2 α 1 1 + α 1 2 ( 0 ) β 1 α 1 1 α 1 1 + α 1 2 ( 0 ) + α 1 2 α 1 1 + α 1 2 ( 0 ) β 1

Table 3. Example 2.

α 1 1 α 1 1 + α 1 2 ( 0 ) + α 1 2 α 1 1 + α 1 2 ( 1 + α 2 2 + α 3 2 ) β 1 α 2 1 α 2 1 + α 2 2 ( 1 + α 1 1 + α 3 1 ) + α 2 2 α 2 1 + α 2 2 ( 0 ) β 2

α 2 1 α 2 1 + α 2 2 ( 0 ) + α 2 2 α 2 1 + α 2 2 ( 0 ) β 2 α 2 1 α 2 1 + α 2 2 ( 0 ) + α 2 2 α 2 1 + α 2 2 ( 1 + α 1 2 + α 3 2 ) β 2 α 3 1 α 3 1 + α 3 2 ( 1 + α 1 2 + α 2 2 ) + α 3 2 α 3 1 + α 3 2 ( 0 ) β 3 α 3 1 α 3 1 + α 3 2 ( 0 ) + α 3 2 α 3 1 + α 3 2 ( 0 ) β 3

α 3 1 α 3 1 + α 3 2 ( 0 ) + α 3 2 α 3 1 + α 3 2 ( 1 + α 1 1 + α 2 1 ) β 3 α i j 0 , i I , j = 1 , , m i 0.2 j = 1 m i α i j 1 , i I .

In this problem, an MBE does not exist. This fact follows from (P3) having the maximum objective function value not equal zero. Moreover, note that there is not any pure Berge equilibrium because whenever players 1 and 2 gets a positive payoff, player 3 gets a payoff 0 and vice versa. Furthermore, if any mixed strategy is used then for at least one player i, the players −i will choose with a positive probability a strategy where at least one player i gets a payoff 0. Hence the maximum of (P3) cannot be 0, and there is no MBE by Theorem 6. In contrast to the MBE, an NE always exists by Theorem 2. The following is the nonlinear program to find an NE for this game.

( P 4 ) Maximize g ( α , β ) = α 1 1 α 1 1 + α 1 2 α 2 1 α 2 1 + α 2 2 α 3 1 α 3 1 + α 3 2 ( 1 + α 2 1 + α 3 1 + 1 + α 1 1 + α 3 1 + 0 ) + α 1 1 α 1 1 + α 1 2 α 2 1 α 2 1 + α 2 2 α 3 2 α 3 1 + α 3 2 ( 1 + α 1 1 + α 2 1 ) + α 1 2 α 1 1 + α 1 2 α 2 2 α 2 1 + α 2 2 α 3 1 α 3 1 + α 3 2 ( 1 + α 1 2 + α 2 2 ) + α 1 2 α 1 1 + α 1 2 α 2 2 α 2 1 + α 2 2 α 3 2 α 3 1 + α 3 2 ( 1 + α 2 2 + α 3 2 + 1 + α 1 2 + α 3 2 ) β 1 β 2 β 3

subject to α 2 1 α 2 1 + α 2 2 α 3 1 α 3 1 + α 3 2 ( 1 + α 2 1 + α 3 1 ) β 1 α 2 2 α 2 1 + α 2 2 α 3 2 α 3 1 + α 3 2 ( 1 + α 2 2 + α 3 2 ) β 1 α 1 1 α 1 1 + α 1 2 α 3 1 α 3 1 + α 3 2 ( 1 + α 1 1 + α 3 1 ) β 2

α 1 2 α 1 1 + α 1 2 α 3 2 α 3 1 + α 3 2 ( 1 + α 1 2 + α 3 2 ) β 2 α 1 2 α 1 1 + α 1 2 α 2 2 α 2 1 + α 2 2 ( 1 + α 1 2 + α 2 2 ) β 3 α 1 1 α 1 1 + α 1 2 α 2 1 α 2 1 + α 2 2 ( 1 + α 1 1 + α 2 1 ) β 3

α 1 1 , α 1 2 , α 2 1 , α 2 2 , α 3 1 , α 3 2 0 , i I , j = 1 , , m i 0.2 α 1 1 + α 1 2 1 0.2 α 2 1 + α 2 2 1 0.2 α 3 1 + α 3 2 1.

One solution to (P4) with g ( α * , β * ) = 0 and hence an NE is α 1 1 * = α 1 2 * = α 2 1 * = α 2 2 * = α 3 1 * = α 3 2 * = 0.1 , β 1 * = β 2 * , β 3 * = 0.3 , β 1 * = β 2 * , β 3 * = 0.3 .

Example 3.

In this 3-person RAG each player has 2 pure strategies with R 1 = R 2 = R 3 = 1 , and each player needs to allocate at least 0.2 of his maximum resource. The payoff matrices are shown in Table 4.

This example has an MBE obtained from the following NLP.

( P 5 ) Maximize h ( α , β ) = α 1 1 α 1 1 + α 1 2 α 2 1 α 2 1 + α 2 2 α 3 1 α 3 1 + α 3 2 × ( 2 + α 2 1 + α 3 1 + 1 + α 1 1 + α 3 1 + 2 + α 1 1 + α 2 1 ) + α 1 1 α 1 1 + α 1 2 α 2 2 α 2 1 + α 2 2 α 3 1 α 3 1 + α 3 2 × ( 1 + α 2 2 + α 3 1 + 2 + α 1 1 + α 3 1 + 1 + α 1 1 + α 2 2 ) + α 1 2 α 1 1 + α 1 2 α 2 1 α 2 1 + α 2 2 α 3 1 α 3 1 + α 3 2

× ( 1 + α 2 1 + α 3 1 + 2 + α 1 2 + α 3 1 + 1 + α 1 2 + α 2 1 ) + α 1 2 α 1 1 + α 1 2 α 2 2 α 2 1 + α 2 2 α 3 1 α 3 1 + α 3 2 × ( 2 + α 2 2 + α 3 1 + 1 + α 1 2 + α 3 1 + 2 + α 1 2 + α 2 2 ) + α 1 1 α 1 1 + α 1 2 α 2 1 α 2 1 + α 2 2 α 3 2 α 3 1 + α 3 2 × ( 1 + α 2 1 + α 3 2 + 2 + α 1 1 + α 3 2 + 1 + α 1 1 + α 2 1 )

Table 4. Example 3.

+ α 1 1 α 1 1 + α 1 2 α 2 2 α 2 1 + α 2 2 α 3 2 α 3 1 + α 3 2 × ( 2 + α 2 2 + α 3 2 + 1 + α 1 1 + α 3 2 + 2 + α 1 1 + α 2 2 ) + α 1 2 α 1 1 + α 1 2 α 2 1 α 2 1 + α 2 2 α 3 2 α 3 1 + α 3 2 × ( 2 + α 2 1 + α 3 2 + 1 + α 1 2 + α 3 2 + 2 + α 1 2 + α 2 1 )

+ α 1 2 α 1 1 + α 1 2 α 2 2 α 2 1 + α 2 2 α 3 2 α 3 1 + α 3 2 × ( 1 + α 2 2 + α 3 2 + 2 + α 1 2 + α 3 2 + 1 + α 1 2 + α 2 2 ) β 1 β 2 β 3

subject to α 1 1 α 1 1 + α 1 2 ( 2 + α 2 1 + α 3 1 ) + α 1 2 α 1 1 + α 1 2 ( 1 + α 2 1 + α 3 1 ) β 1 α 1 1 α 1 1 + α 1 2 ( 1 + α 2 2 + α 3 1 ) + α 1 2 α 1 1 + α 1 2 ( 2 + α 2 2 + α 3 1 ) β 1 α 1 1 α 1 1 + α 1 2 ( 1 + α 2 1 + α 3 2 ) + α 1 2 α 1 1 + α 1 2 ( 2 + α 2 1 + α 3 2 ) β 1 α 1 1 α 1 1 + α 1 2 ( 2 + α 2 2 + α 3 2 ) + α 1 2 α 1 1 + α 1 2 ( 1 + α 2 2 + α 3 2 ) β 1

α 2 1 α 2 1 + α 2 2 ( 1 + α 1 1 + α 3 1 ) + α 2 2 α 2 1 + α 2 2 ( 2 + α 1 1 + α 3 1 ) β 2 α 2 1 α 2 1 + α 2 2 ( 2 + α 1 2 + α 3 1 ) + α 2 2 α 2 1 + α 2 2 ( 1 + α 1 2 + α 3 1 ) β 2 α 2 1 α 2 1 + α 2 2 ( 2 + α 1 1 + α 3 2 ) + α 2 2 α 2 1 + α 2 2 ( 1 + α 1 1 + α 3 2 ) β 2 α 2 1 α 2 1 + α 2 2 ( 1 + α 1 2 + α 3 2 ) + α 2 2 α 2 1 + α 2 2 ( 2 + α 1 2 + α 3 2 ) β 2 α 3 1 α 3 1 + α 3 2 ( 2 + α 1 1 + α 2 1 ) + α 3 2 α 3 1 + α 3 2 ( 1 + α 1 1 + α 2 1 ) β 3

α 3 1 α 3 1 + α 3 2 ( 1 + α 1 1 + α 2 2 ) + α 3 2 α 3 1 + α 3 2 ( 2 + α 1 1 + α 2 2 ) β 3 α 3 1 α 3 1 + α 3 2 ( 1 + α 1 2 + α 2 1 ) + α 3 2 α 3 1 + α 3 2 ( 2 + α 1 2 + α 2 1 ) β 3 α 3 1 α 3 1 + α 3 2 ( 2 + α 1 2 + α 2 2 ) + α 3 2 α 3 1 + α 3 2 ( 1 + α 1 2 + α 2 2 ) β 3 α i j 0 , i I , j = 1 , , m i 0.2 j = 1 m i α i j 1 , i I .

One solution to (P5) with h ( α * , β * ) = 0 and hence an MBE is

α 1 1 * = α 1 2 * = α 2 1 * = α 2 2 * = α 3 1 * = α 3 2 * = 0.125 , β 1 * = β 2 * , β 3 * = 1.75 .

7. Conclusion

In this paper, we gave an interpretation for mixed strategies to n-person games in normal form via the notion of resource allocation. In these games, a mixed strategy is an allocation strategy, as distinguished from other interpretations of a mixed strategy. Each player chooses a pure strategy with a probability that equals to the fraction of the maximum available resource allocated to that pure strategy over the total fraction of the the resource the player allocates to all his pure strategies. We proved the existence of an NE in these games. Furthermore, we showed that an MBE may not exist in a resource allocation game unless there exists a strategy yielding zero for the associated nonlinear program.

Acknowledgements

This research is funded by the US Department of Education GAANN Fellowship, reward No. P200A130164.

NOTES

*Both authors contributed equally to this research.

Cite this paper
Nahhas, A. and Corley, H. (2018) An Alternative Interpretation of Mixed Strategies in n-Person Normal Form Games via Resource Allocation. Theoretical Economics Letters, 8, 1854-1868. doi: 10.4236/tel.2018.810122.
References
[1]   Maschler, M., Solan, E. and Zamir, S. (2013) Game Theory (Translated from the Hebrew by Ziv Hellman and edited by Mike Borns).

[2]   Chakravarty, S.R., Mitra, M. and Sarkar, P. (2015) A Course on Cooperative Game Theory. Cambridge University Press, Cambridge.

[3]   Nash, J. (1950) Equilibrium Points in n-Person Games. Proceedings of the National Academy of Sciences of the United States of America, 36, 48-49.
https://doi.org/10.1073/pnas.36.1.48

[4]   Nash, J. (1951) Non-Cooperative Games. Annals of Mathematics, 54, 286-295.
https://doi.org/10.2307/1969529

[5]   Border, K.C. (1989) Fixed Point Theorems with Applications to Economics and Game Theory. Cambridge University Press, Cambridge.

[6]   Berge, C. (1957) Theorie Generale des jeux an Personnes. Gauthier-Villars.

[7]   Zhukovskiy, V. (1985) Some Problems of Nonantagonistic Differential Games. In: Kenderov, P., Ed., Matematiceskie Metody v Issledovanii Operacij, 103-195.

[8]   Corley, H.W. (2015) A Mixed Cooperative Dual to the Nash Equilibrium. Game Theory, 2015, Article ID: 647246.

[9]   Batbileg, S. and Enkhbat, R. (2010) Global Optimization Approach to Game Theory. Mongolian Mathematical Society, 14, 2-11.

[10]   Batbileg, S. and Enkhbat, R. (2011) Global Optimization Approach to Nonzero Sum N Person Game. International Journal: Advanced Modeling and Optimization, 13, 59-66.

[11]   Nahhas, A. and Corley, H.W. (2017) A Nonlinear Programming Approach to Determine a Generalized Equilibrium for N-Person Normal Form Games. International Game Theory Review, 19, 1750011.

[12]   Samuelson, L. (2016) Game Theory in Economics and Beyond. Journal of Economic Perspectives, 30, 107-130.
https://doi.org/10.1257/jep.30.4.107

[13]   Li, S.W. (2017) Obviously Strategy-Proof Mechanisms. American Economic Review, 107, 3257-3287.
https://doi.org/10.1257/aer.20160425

[14]   Siniscalchi, M. (2016) Epistemic Game Theory: Beliefs and Types. The New Palgrave Dictionary of Economics, 19, 1-7.

[15]   Perea, A. (2014) From Classical to Epistemic Game Theory. International Game Theory Review, 16, 1440001.
https://doi.org/10.1142/S0219198914400015

[16]   Corley, H.W. (2017) Normative Utility Models for Pareto Scalar Equilibria in n-Person, Semi-Cooperative Games in Strategic Form. Theoretical Economics Letters, 7, 1667-1686.
https://doi.org/10.4236/tel.2017.76113

[17]   Von Neumann, J. and Morgenstern, O. (1944) Theory of Games and Economic Behavior. Princeton University Press, Princeton.

[18]   Nash, J. (1953) Two-Person Cooperative Games. Econometrica: Journal of the Econometric Society, 21, 128-140.
https://doi.org/10.2307/1906951

[19]   Aumann, R.J. (1987) What Is Game Theory Trying To Accomplish? In: Arrow, K. and Honkapohja, S., Eds., Frontiers of Economics, Basil Blackwell, Oxford, 5-46.

[20]   Rubinstein, A. (1991) Comments on the Interpretation of Game Theory. Econometrica: Journal of the Econometric Society, 59, 909-924.
https://doi.org/10.2307/2938166

[21]   Harsanyi, J.C. (1973) Games with Randomly Disturbed Payoffs: A New Rationale for Mixed-Strategy Equilibrium Points. International Journal of Game Theory, 2, 1-23.
https://doi.org/10.1007/BF01737554

[22]   Aumann, R. and Brandenburger, A. (1995) Epistemic Conditions for Nash Equilibrium. Econometrica: Journal of the Econometric Society, 63, 1161-1180.
https://doi.org/10.2307/2171725

[23]   Joosten, R., Brenner, T. and Witt, U. (2003) Games with Frequency-Dependent stage Payoffs. International Journal of Game Theory, 31, 609-620.
https://doi.org/10.1007/s001820300143

 
 
Top