A Matrix Representation of an n-Person 0-1 Game and Its 0-1 Tail Algorithm to Find (Strictly) Pure Nash Equilibria
Dianyu Jiang
Institution of Game Theory and Its Application, Huaihai Institute of Technology, Lianyungang, China
Email address:
To cite this article:
Dianyu Jiang. A Matrix Representation of an n-Person 0-1 Game and Its 0-1 Tail Algorithm to Find (Strictly) Pure Nash Equilibria. Mathematics and Computer Science. Vol. 1, No. 1, 2016, pp. 5-9. doi: 10.11648/j.mcs.20160101.12
Received: April 2, 2016; Accepted: April 11, 2016; Published: May 9, 2016
Abstract: An n-person double action game, i.e., an n-person strategy game, i.e., every player has and only has two actions, is a typical and useful game. It has been proved that in an n-person double game, every player’s two actions can be denoted by 0 and 1. An n-person double action game, i.e., every player’s action set is denoted as {0,1}, is said to be an n-person 0-1 game. In this paper, we first give a matrix representation of an n-person 0-1 game and then give a new and simpler algorithm to find all the (strictly) pure Nash equilibria for an n-person 0-1 game, called 0-1 tail algorithm. Specially, this algorithm can be simplified if the game is symmetrical. Some examples are given to show the algorithm.
Keywords: n-person Double Action Game, n-person 0-1 Game, Symmetry, Matrix Representation, 0-1 Tail Algorithm, Symmetrical 3-person PD, Symmetrical 3-person Game of Rational Pigs
1. Introduction
Some classical Examples such as prisoners’ dilemma, battle of the sexes, hawk-dove game, game of warriors, game of rational pigs, and game of patrolling by poor and rich men occur in many literatures. These games are all 2×2 bi-matrix games. They are the simplest and the most typical. There are only 2 players and each of them has only 2 pure actions in these games. If we extend number of players in a 2×2 bi-matrix game to any natural number to be greater than 1 and every player has exactly 2 actions, then we obtain other simple and typical games, n-person double action games. These games have many backgrounds. For example, the most important and the most typical one of them is famous n-person prisoner's dilemma (See [1-4]). It is obvious that n-person double action games have very strong character and so there are special solving methods not to be contained in that of general n-person strategy games.
Jiang (2015) [5] proved that every double action game can be denoted as a 0-1 game which is simpler and can be easily dealt with by binary numbers. That is, every player’s two actions can be denoted as 0 and 1, respectively.
It is an important topic to find all (strictly) pure Nash equilibria for an n-person double action game. Jiang (2015) [5] gives a sieve method, but the method is complex.
In this paper, we have two tasks. First one of them is to give a matrix representation of an n-person 0-1 game and the second one is to give a new algorithm, called 0-1 tail algorithm, to find all (strictly) pure Nash equilibria for an n-person 0-1 game. This paper is divided into four sections. Section 2 gives a matrix representation of n-person 0-1 games. Section 3 gives a 0-1 tail algorithm to find all (strictly) pure Nash equilibria. Finally, section 4 defines symmetrical 0-1 games and simplifies 0-1 tail algorithm.
2. A Matrix Representation of n-person 0-1 Games
An n-person 0-1 game can be written as the formal structure, where is the i-th player’s serial number, , 0 and 1 are the player i's two actions, is the player i's utility under the situation , , . More precisely, when every player i uses his or her action , , the player i’s profit is .
As everyone knows, Schelling (1980) [6] wrote a 2-person 0-1 game as
.
Based on Schelling (1980) [6], McCain (2004) [7] wrote a 3-person 0-1 game as two Schelling matrices as follows.
, and
.
The first matrix denotes the case that when the player 3 uses his or her action 0 and the second does that when the player 3 uses his or her action 1.
Jiang (2015) [5] uses the symbols
,.
to write an n-person 0-1 game, where n can be any natural number to be greater than 1.
Now let us give two matrix representations of an n-person 0-1 game as follows. The first one is
,
and second one is transposition of the first one, i.e.,
.
As an example, we only explain the first one because the second is similar. Row numbers of the matrix are denoted by binary numbers with the length n according to their size order. Thus the matrix has rows and their decimal numbers are from 0 to . The -th column denotes the player ,. A row number with binary number denotes a situation. For example, for a 3-person 0-1 game, 010 denotes that the player 1 and 3 use their actions 0 and that the 2 does 1. The element of the matrix denotes the player ’s utility under the situation , where , .
3. A 0-1 Tail Algorithm to Find (Strictly) Pure Nash Equilibria
For a number , we will write , i.e.,
For an n-person 0-1 game , if there exists a situation
, , ,
such that
, , (3-1)
then is called a pure Nash equilibrium. A set of all the pure Nash equilibria for the n-person 0-1 game is written as .
When every inequalities in (3-1) is strict, i.e.,
, , (3-2)
then is called a strictly pure Nash equilibrium. A set of all the strictly pure Nash equilibria for the n-person 0-1 game is written as .
The above concepts and marks can be found from Jiang (2015) [5].
As everyone known, Schelling (1980) [6] gave a streak method to find pure Nash equilibria for a bi-matrix game, or 2-person double action game. Jiang (2015) [5] gave a sieve method to find pure strictly Nash equilibria for an n-person 0-1 game. However, the sieve method is complex.
Based on our matrix representation, we can obtain a new algorithm to find (strictly) pure Nash equilibria, called 0-1 tail algorithm.
Theorem 3.1(0-1 Tail Algorithm to Find all Pure Nash Equilibria)
All pure Nash equilibria for an n-person 0-1 game can be found by the following algorihm.
First, write out the matrix of the given n-person 0-1 game. Then execute the following algorithm.
(1) Set .
(2) Set .
(3) If , then go to (4); else go to(7).
(4) Write 0(called a tail) after the matrix elements with the row number (called a head), and then let .
(5) If , then go to (3); else go to (6).
(6) Let tail of be 1.
(7) Let tail of be 0.
(8) Taking the top of binary numbers without tail and then go to (2) until every binary row number (i.e., head) gets its tail 0 or 1.
A situation is a pure Nash equilibrium if and only if its tail is marked 1.
If every strictly inequality in the step (3) is rewritten as the corresponding non-strict one , then a set of strictly pure Nash equilibria can be obtained by the algorithm as well.
Proof: For every situation, it needs be checked that from . They can be executed by the steps (2) and (3).
If the inequality holds, then the situation is not a pure Nash equilibrium and so its tail should be marked by 0. If does not, namely, , then the situation is not a pure Nash equilibrium and hence its tail should be marked by 0 as well as. This can be executed by the steps (3), first part of (4) and (7).
When the inequality is satisfied, we should check the next player i+1, i.e., we need let , which is the second part of the step (4). If this new meets the condition, then we need recheck the inequality . When the inequalitydoes not hold, i.e., , all the inequalities
,
have been checked. Thus the situation is a pure Nash equilibrium and so its tail should be marked by 1. Those can be executed by the steps (5) and (6).
The other parts of the algorithm are trivial and so they can be omitted. Q. D. E.
Example 3.1 By 0-1 tail algorithm, we can know that the 4-person 0-1 game has two pure Nash equilibria 1100 and 1111.
4. Symmetrical n-person 0-1 Games and Simplified 0-1 Tail Algorithm
Definition 4.1 We will say that a given n-person 0-1 game is symmetrical if
(1) for any situation , it can be obtained that ,, and
(2) for any permutation , the following relation can be obtained .
A 0-1 tail algorithm about a symmetrical 0-1 game can be simplified by the following theorem.
Theorem 4.1 If (1), (2) can be obtained by a permutation on , and (3) tail of has been obtained, then the tail of is the same as that of .
Example 4.1 (Game of collecting oysters, refer to Roger (2004)[7]).Three persons arecollecting oystersin Chesapeake Bay. They all know that there is an oyster bed on the northeast coast that has never been collected. If the oysters are not harvested before the next month, they will fetch more money on the market after growing to maturity. These three collectors are currently considering if they would go collecting (action 0) or wait for some days (action 1). (1) Whether is the following game symmetrical? (2) Find all the strictly pure Nash equilibria.
Solution: (1) Payoff matrix of this game can be written as
.
It is trivial that every row satisfies the condition (1) for Theorem 4.1.
Now let us verify the condition (2). Let , and . Then
.
.
It is similar for the rows 011, 101 and 110. Thus this game is symmetrical.
(2) We have
By this computation we can know that they would go collecting early. However, the stable situation about individual rationality is worse than that they wait for some days to collect.
In fact, the game is a symmetrical 3-person prisoner’s dilemma. Its general form is the follows.
Example 4.2 (a symmetrical 3-person prisoner's dilemma) Three people 1, 2 and 3, arrested with stolen property in their possession, are being interviewed separately by the police. They know that if they keep quiet there is not enough evidence for them to be convicted of theft, and so every one of them gets years jail sentence for being in possession of stolen property. If they confess to the theft, every one of them gets years in prison. If one confesses and both keep quiet, one who confesses will go free, while each of the other two will have years jail sentence. If one keeps quiet and the other two confess, then one who keeps quiet will have year jail sentence, while each of the other two will have year jail sentence. Where . If we use 1 to denote keeping quiet and 0 do confess. Then
Therefore their stable situation with individual rationality is that everyone confesses. However, the stable situation is worse than everyone chooses keeping quiet, non-stable.
Example 4.3(A symmetrical 3-person game of rational pigs) Three pigs with the same sizes are put in a Skinner box with a special panel at one end and a food dispenser at the other. It needs pay units of cost to press the panel. When the panel is pressed, 3 units of food are dispensed and every pig can eat some food. When the three pigs press the panel at the time, every pig can eat 1 unit of food. When two pigs press the panel, each of them can eat units of food and so the other one can eat units. When one presses the panel, it can eat units and so each one of the other two pigs can eat units. When none presses the panel, every pig cannot eat anything. Let us find set of strictly pure Nash equilibria.
Solution: We have known that when the panel is pressed, 3 units of food are dispensed and every pig can eat some food. Then when one pig presses or two pigs press the panel, there is at least one pig first to eat and can get more than 1 unit of food and so every pig who presses the panel can eat food which is smaller than 1 unit. Thusand (i.e., ). Since
,
we can obtain
Case 1. When , then
It can be obtained that the set of strictly pure Nash equilibria is . In words, when one pig who press the panel is profitable, the stable situation is that exact one of the three pigs would go to press the panel.
Case 2. When , then
Thus, should one pig pressing the panel lose more than gain, none would press the panel.
In any case, it is impossible for more than one pig to press the panel, or equivalently, at most one pig would go to press the panel.
Fabac, Radoševic and Magdalenic (2014) [8] created a rational pigs game extended (briefly, RPGE), in which the introduction of a third pig entails significant structural changes. In fact, this article is the first 3-rational pigs game. Jiang (2015b) [9] established L-system of axiomatic theory of boxed pigs and its deductive sub-systems were obtained from it, such as simple K-systems, instant K-systems and timing K-systems, K=0,1. Finally, the method to change a game among many pigs (can be infinitely many) into a game between a big pig and a small pig and applicable degree of the method are given. However, the game among many rational pigs is an approximate description that rational pigs must be sufficiently many. Jiang(2015c) [10] defines that each of two n-person strategy games is said to be a negative game of the other one if sum of their utilities is equal to zero. Since games based on traditional boxed pigs story, such as Jiang (2015b) [9], are called boxed pigs games or rational pigs games, it means that they should be positive, such as 3 means +3. Therefore negative game of a boxed pigs (or rational pigs) game should be called a negative boxed pigs (or rational pigs) game. Li, et al (2015) [11] gives a special rational pigs game. Jiang, et al (2016) [12] researches the negative game of the game given by Li, et al (2015) [11] and gives an application to website management.
References