Theoretical Economics Letters
Vol.08 No.10(2018), Article ID:85376,15 pages
10.4236/tel.2018.810122
An Alternative Interpretation of Mixed Strategies in n-Person Normal Form Games via Resource Allocation
Ahmad Nahhas*, H. W. Corley*
Center on Stochastic Modeling, Optimization, and Statistics, The University of Texas at Arlington, Arlington, TX, USA
Copyright © 2018 by authors and Scientific Research Publishing Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
Received: March 19, 2018; Accepted: June 18, 2018; Published: June 21, 2018
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.
Keywords:
Game Theory, Mixed Strategy, Resource Allocation
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 be an n-person resource allocation game in normal form with exactly one resource. The set is the set of the n-players. Let be the resource available for player i, so the n-tuple represents the amount of the resource each player has available. Define to be the minimum
amount of the resource player i needs to allocate and . The set of the pure strategies for player i is .
Each player player i allocates from his resource the fraction to his pure strategy . The set of all possible allocations for each player i is
(1)
Note that is compact and convex for each player . Let and . The probability the player i chooses strategy is . Hence a mixed strategy for player i is the mi-tuple
,
where and . A pure strategy j is an allocation where the player i allocates to his pure strategy j and allocates 0 to the rest of his pure strategies. The payoff function for each player is , where and . The payoff functions are assumed to be continuous in .
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, and is denoted by , where
.
The joint probability
is the probability that all the players other than player i choose the joint pure strategy . It is the product of the fraction that each player in 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 to his strategy j and he allocates 0 to his other pure strategies while the rest of players choose the allocation is
(2)
If player i chooses the mixed allocation and the rest of players choose the allocation , then the expected payoff for player i is
(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 . In other words, . In this case, each player i chooses strategy j with the probability .
2) Case 2. Each player i does not necessarily allocate all of his resource . Hence . In this case, each player i chooses strategy j with the probability
.
Table 1. Example of a RAG.
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 , then the second case becomes the first case. We formalize this previous statement as follows.
Lemma 1. let . Then Case 1 and Case 2 are equivalent.
Proof. Let . Hence and . 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
.
We next restate the definition of an NE in terms of allocation.
Definition 1. A strategy is an NE if and only if
(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 . The proof of the next theorem is similar to the proof of the existence of an equilibrium in [4] . Let
(5)
and . 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 where and
(6)
The functions are continuous since we assume that the are continuous in . Therefore by the Brouwer fixed point theorem there exists fixed points
(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 represent player’s i gain by choosing his pure strategy j given the previous allocation . Hence . Thus is a fixed point.
Conversely, let be a fixed point. Then for each i let l be a pure strategy such that , and . Therefore,
, since . Note that from Equation (7),
the right hand side is only when the denominator equals 1. Hence, . 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 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 . 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 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.
(8)
Proof. Let be an NE where each player i allocates of his total resource . Then . Therefore . Furthermore, all constraints (8) are satisfied since from Definition 1 .
Conversely, let be a feasible point such that . It can easily be checked by the constraints (8) and Equation (3) that . Hence it must be the case that . Otherwise which yields a contradiction. Moreover, from the constraints 8 . 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 . In this case, each of the payoff functions is maximized when the total resource is allocated to that strategy. In other words, .
Lemma 5. Let be monotonically increasing functions in . Then the optimal strategy for each player is an NE if and only if the maximum of the following nonlinear program is 0.
(9)
Proof. Let be an NE where the payoff is maximized. Then
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 are monotonically nondecreasing in . 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 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
(10)
In other words, a strategy is an MBE if for all , 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.
(11)
Proof. Let be an MBE allocation. Then each player allocates to each strategy a fraction of his resource that equals to the probability that the player uses that strategy. From Definition 2 one can check that . Hence all constraints are satisfied. Moreover, .
Conversely, let be a feasible solution such that . From (11), it is easy to see that . But , so it must be that and . Therefore, , 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 units and player 2 has 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.
One solution to (P1) with and hence an NE is , , , , , .
In Case 2 when each player allocates at least 0.4 of his resource, the following NLP finds an NE strategy for this problem.
One solution to (P2) with and hence an NE is , , , , , . Thus there is an MBE for this example. However, in general an MBE need not exist for 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 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.
Table 3. Example 2.
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.
One solution to (P4) with and hence an NE is , , .
Example 3.
In this 3-person RAG each player has 2 pure strategies with , 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.
Table 4. Example 3.
One solution to (P5) with and hence an MBE is
, , .
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.
Cite this paper
Nahhas, A. and Corley, H.W. (2018) An Alternative Interpretation of Mixed Strategies in n-Person Normal Form Games via Resource Allocation. Theoretical Economics Letters, 8, 1854-1868. https://doi.org/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
NOTES
*Both authors contributed equally to this research.