The aim of this study is to construct an epistemic model in which each rational choice under common belief in rationality is supplemented by a type which expresses such a belief. In practice, the finding of type depends on manual solution approach with some mathematical operations in scope of the theory. This approach becomes less convenient with the growth of the size of the game. To solve this difficulty, a linear programming model is constructed for two-player, static and non-cooperative games to find the type that is supporting that player’s rational choice is optimal under common belief in rationality and maximizing the utility of the game. Since the optimal choice would only be made from rational choices, it is first necessary to eliminate all strictly dominated choices. In real life, the games are usually large sized. Therefore, the elimination process should be performed in a computer environment. Since software related to game theory was mostly prepared with a result-oriented approach for some types of games, it was necessary to develop software to execute the iterated elimination method. With this regard, a program has been developed that determines the choices that are strictly dominated by pure and randomized choices in two-player games. Two functions named “esdc” and “type” are created by using R statistical programming language for the operations performed in both parts, and these functions are added to the content of an R package after its creation with the name EpistemicGameTheory.
In order to evaluate the possible results of the decision, it is very important to constitute a belief about opponents’ feasible preferences which can affect their choices. In addition to this, the precondition of making a good choice requires having a reasonable belief about opponents’ choices. However, in general each belief of players may not be reasonable according to their opponents. The player should determine the opponent’s possible idea about his opponent with putting himself into his opponent’s shoes, to decide which choice is reasonable for his opponent or which choice would not be preferred by him. In other words, before surmising an idea about opponents’ choices, it is compulsory to reason their system of thought. Indeed, Oskar Morgenstern who is one of the earliest founders of game theory, has highlighted this subject in his article “Perfect Foresight and Economic Equilibrium” which was published in 1935. In his article, Morgenstern has explained the significance of having idea about beliefs of the opponents, analyzing the opponents’ systems of thought properly and establishing a reasonable relation to make a good decision (Morgenstern 1935). However, the importance of this concept frequently has been underestimated in the studies on game theory, which have been published in last sixty years. Morgenstern’s bold idea of using the tools of formal logic to talk about how members of a social system think, about how they think about what other members think, and so on, was far ahead of its time. However now, in the form of epistemic game theory, it has found a home (Brandenburger 2010).
The discipline that studies these patterns of reasoning, and how they influence the eventual choices of the players, is called epistemic game theory (Perea 2012).1
Approximately twenty-five years ago, conceptual changes have emerged with the introduction of epistemic game theory. This new branch of science has brought game theory back to its fundamental concepts, its background. In other words, it has brought game theory back to reasonable modeling of players’ beliefs about their opponents. At the core of epistemic game theory, there is the fact that people have different tendencies to reason under same circumstances in a game. Therefore, it is not true reasoning in a unique way and claiming that it is the best option. Under such conditions, it can be said that there are only different reasoning ways, and it should be avoided that claiming on which one is better. In epistemic approach, the aim is to define the methods of reasoning, which can be used in the game, and to examine how the method affects the result of the game.
The belief of a player about choices of his opponents is a probability distribution which is defined over the set \(C_{-i}= C_1\times \ldots \times C_{i-1} \times C_{i+1} \times \ldots \times C_n\) where \(C_i\) is the set of player i’s choices. The probability value which is assigned by player i for his opponents’ each choice combination, is obtained by \(b_i (c_1,\ldots,c_{i-1},c_{i+1},\ldots,c_n )\).
Let us symbolize the utility function of player i with \(u_i\) and the belief about the choices of his opponents with \(b_i\). Accordingly, expected utility of player \(i\) from choosing the choice \(c_i\) is calculated by the equation below.
\[u_i (c_i,b_i ) = \sum_{(c_1,\ldots,c_{i-1},c_{i+1},\ldots,c_n )\in C_{-i}}b_i(c_1,\ldots,c_{i-1},c_{i+1},\ldots,c_n) \times u_i (c_1,\ldots,c_{i-1},c_i,c_{i+1},\ldots,c_n )\]
The concept of belief hierarchies is the basic element of epistemic approach. In an \(n\)-player game, the belief hierarchies for player \(i\) is as follows:
The belief that player \(i\) has about his opponents’ choice-combinations,
The belief that player \(i\) has about the beliefs that his opponents have about their opponents’ choice-combinations,
The belief that player \(i\) has about the beliefs that his opponents have about the beliefs that their opponents have about the other players’ choice-combinations,
and so on, ad infinitum. The first belief for player \(i\) is his first-order belief, the second belief is his second-order belief, and so on.
The belief hierarchies have some disadvantages both theoretically and practically. In theory, it is difficult to make a mathematical description of the hierarchy. In practice, it is often impossible to write and express each stage of the infinite hierarchy (first-order belief, second-order belief, etc.). For this reason, an approach that can express the hierarchy in a shorter and more formal way is needed.
The concept of infinite belief hierarchy has brought to game theory by John Harsanyi. He has worked on incomplete information games, also called Bayesian games, where players have incomplete information about the parameters of the game. It is aimed to model the beliefs of each player about the unknown parameters of the game, each player’s beliefs about the other players’ beliefs about these parameters, and so on ad infinitum. This may be called the explicit approach and is in fact feasible. However, the explicit approach is mathematically rather cumbersome and hardly manageable. Indeed, this was a major obstacle to the development of the theory of games with incomplete information at its early stages. The breakthrough was provided by John Harsanyi in a seminal work (Harsanyi 1982) that awarded him the Nobel Prize in 1994 after thirty years. While Harsanyi actually formulated the problem verbally, in an explicit way, he suggested a solution that ‘avoided’ the difficulty of having to deal with infinite hierarchies of beliefs, by providing a much more workable implicit, encapsulated model (Zamir 2013).
The concept of a type is the basis of the Harsanyi model. As a concept, type can be considered as a precise definition of players’ belief hierarchies about unknown parameters of the game. It is a special representation of the player’s beliefs about the actual parameters involved and the answers to the types of other players. This characteristic of the types gives the player the ability to self-reference inevitably that is, the ability to decide the types of other players through their own types in an interactive decision-making environment.
The construction that Harsanyi proposed in the context of a game with incomplete information on the preferences of the players was very simple: For every player, define a set of types, and for every type define a utility function, together with a probabilistic belief about the opponents’ types (Harsanyi 1982).
The content of the type in epistemic game theory differs from that of Harsanyi. While Harsanyi forms belief hierarchies for parameters of the game, epistemic game theory deals with the choices of the players. In the studies (Armbruster and Boge 1979) and (Boge and Eisele 1979), belief hierarchies have been used to describe the beliefs of players about their opponents’ choices.
Let us denote the belief hierarchy with \(t_i^c\) which supports player \(i\)’s any choice \(c\). In the literature, belief hierarchy is also used as epistemic type (or briefly type). Therefore, \(t_i\) represents an epistemic type of the player \(i\).
Let us consider an \(n\)-player game. The epistemic model, firstly, indicates possible types for each player. Let us symbolize the set of all possible types for every player \(i\) with \(T_i\). Each type \(t_i\) stores information about the beliefs on the choices of player \(i\)’s opponents and their types. The problem that arises here is how this belief can be expressed mathematically.
As it is known, every player \(i\)’s belief about choices of his opponents is a probability distribution \(b_i\) which has been defined on the set \(C_{-i}=C_1 \times \ldots \times C_{i-1} \times C_{i+1} \times \ldots \times C_n. t_i\) should have information about not only the belief about choices of his opponents but also information about his opponents’ types. Thus, \(t_i\) represents the choice-type combinations of player \(i\)’s opponents.
The set that contains all possible choice-type combinations of any opponent \(j\) of player \(i\) is \(C_j \times T_j\). In parallel with this definition, the set of all choice-type combinations of player \(i\)’s opponents’ becomes \((C_1 \times T_1) \times \ldots \times (C_{i-1} \times T_{i-1} )\times(C_{i+1}\times T_{i+1} )\times \ldots \times (C_n \times T_n)\). This set includes all possible combinations \(((c_1,t_1),\ldots,(c_{i-1},t_{i-1} ),(c_{i+1},t_{i+1} ),\ldots,(c_n,t_n))\).
An epistemic model specifies probability distribution \(b_i (t_i )\) defined on the set of all possible choice-type combinations \((C_1\times T_1)\times \ldots \times (C_{i-1} \times T_{i-1} ) \times (C_{i+1}\times T_{i+1} )\times \ldots \times (C_n \times T_n)\) for every player \(i\) and each type \(t_i\in T_i\). The probability distribution of \(b_i (t_i)\) represents the belief that type \(t_i\) has about the opponents’ choices and types.
Consider a type \(t_i\) for player i within an epistemic model. The choice \(c_i\) is rational for type \(t_i\) if it maximizes the expected utility for the belief that \(t_i\) holds about the opponents’ choice-type combinations.
The entire belief hierarchy can be expressed with an epistemic model. Constructing an epistemic model is easier than establishing a belief hierarchy. This is an important advantage of epistemic model. Another advantage of the epistemic model is that it can be defined by a mathematical expression conveniently.
Type \(t_i\) is said to believe in the opponents’ rationality if for every opponent \(j\), and every choice-type pair \((c_j,t_j)\in C_j \times T_j\) to which \(t_i\) assigns positive probability, the choice \(c_j\) is rational for type \(t_j\).
In order to define common belief in rationality, firstly, the definition of k-fold belief in rationality is needed and explained as follows.
Consider an epistemic model.
Type \(t_i\) expresses 1-fold belief in rationality if \(t_i\) believes in the opponents’ rationality.
Type \(t_i\) expresses 2-fold belief in rationality if \(t_i\) only assigns positive probability to the opponents’ types that express 1-fold belief in rationality.
Type \(t_i\) expresses 3-fold belief in rationality if \(t_i\) only assigns positive probability to the opponents’ types that express 2-fold belief in rationality.
And so on. Thus, \(k\)-fold belief in rationality can be recursively defined for every number \(k\).
The choice \(c_1^*\) is the optimal choice for player \(i\), if the expected utility of the choice \(c_i^*\) is maximum \((u_i (c_i^*,b_i) \geq u_i (c_i,b_i))\).
If the choice \(c_i^*\) is optimal with reference to player \(i\)’s belief about the opponents’ behavior patterns, then \(c_i^*\) is called as a rational choice.
Player \(i\) believes that his opponents are rational if he assigns positive probability for only his opponent’s rational choices.
If the choice \(c_i\) of player \(i\) is optimal for some belief \(b_i\) about the choices of his opponents’ while believing in the opponents’ rationality, then the choice \(c_i\) is a rational choice for player \(i\) under belief in the opponents’ rationality.
The concept of rational choice in game theory sometimes causes confusion. In the context of this study, the word “rational” is used as follows: If a player has built a belief about his opponent’s choices, and has made the optimal choice for himself under this belief, he has made a rational choice. However, this player may have had an unreasonable belief about the opponent, and making rational choice does not guarantee making the reasonable choice. Reasonability carries a subjective meaning and depends on the mindset of the person. Something that is reasonable for one may not be reasonable for another. Therefore, it is impossible to make a single definition of reasonable choice.
The reasonable choice should not only be rational under the belief in the opponents’ rationality, but at the same time, it should be optimal according to a reasonable belief about the opponents’ choices. What is open to debate is when does a belief about the opponent be reasonable? Epistemic game theory examines the answer to this question.
In an epistemic model, if the type \(t_i\) expresses \(k\)-fold belief in rationality for every \(k\), it can be said that \(t_i\) expresses common belief in rationality. If \(t_i\) expresses common belief in rationality and the choice \(c_i\) is optimal for the type \(t_i\), then \(c_i\) is a rational choice under common belief in rationality.
Common belief in rationality does not only mean that you believe that your opponents choose rationally, but you also believe that your opponents believe that their opponents will choose rationally, and that your opponents believe that their opponents believe that the other players will choose rationally, and so on.
Consider an epistemic model, which contains type sets \(T_1,\ldots,T_n\). If the player \(i\)’s choice \(c_i\) is not supported to express common belief in rationality by any type in \(T_i\), this does not mean that the choice \(c_i\) cannot be chosen under common belief in rationality. There may be another epistemic model that has a type supporting the choice \(c_i\) to express common belief in rationality. The purpose of this work is to seek an answer to the question that how this epistemic model can be detected.
Algorithm 1 (Choices that can be rationally chosen under common belief in rationality):
An algorithm has been required to use in order to find the choices that can be rationally chosen under common belief in rationality. Algorithm 1 is based on the following theorem.
Theorem 1: A choice \(c_i\) is irrational if and only if it is strictly dominated by another pure or randomized choice. In other words, a choice \(c_i\) is rational if and only if it cannot be strictly dominated by another pure or randomized choice 2 (Pearce 1984).
By Theorem 1, the algorithm is explained as follows.
1) Eliminate all strictly dominated choices in the original game.
2) Eliminate all strictly dominated choices in the reduced game obtained after the step (1).
3) Eliminate all strictly dominated choices in the reduced game obtained after the step (2).
⋮
Repeat this process until no strategy can be eliminated.
This algorithm ends with a finite number of steps and gives a set of choices that are not empty for each player if the game is finite. The order of elimination and speed do not affect the result.
Theorem 2: (Brandenburger and Dekel 1987) and (Tan and Werlang 1988) proved that, if the choices can be rationally made under \(k\)-fold belief in rationality for each \(k\geq1\), then these choices are also survived \((k+1)\)-fold elimination. This can be generalized as; the rational choices under common belief in rationality are the choices that survive the iterated elimination of strictly dominated choices.
In practice, the finding of type depends on non-computer based approach with some mathematical operations in scope of the theory. This approach becomes less convenient with the growth of the size of the game. For this reason, we construct a linear programming model for two-player, static and non-cooperative games to find the type that is supporting that player \(i\)’s rational choice \(c_i\) is optimal under common belief in rationality and maximizing the utility of the game. Since the optimal choice would only be made from rational choices, it is first necessary to eliminate all strictly dominated choices. By the reason of software related to game theory was mostly prepared with a result-oriented approach for some solution methods and some types of games, it was necessary to develop software to execute the iterated elimination method. With this regard, we developed a computer program that determines the choices that are strictly dominated by pure and randomized choices in two-player games. Başer transformed the operations performed in both parts to software by using R Statistical Programming Language and created a package with the name EpistemicGameTheory (Baser 2017a).
The EpistemicGameTheory R package containing functions named
esdc and type for both purposes explained above. The package
roxygen2 was used
to prepare the documentation when the R package was created (Wickham and et al 2015).
esdc functionAs it is known, since the optimal choice is made only from rational choices, it is first necessary to make iterated elimination of strictly dominated choices. For this purpose, the steps given in Algorithm 1 for two-player games need to be coded into software. We developed Algorithm 2 to make the steps of this algorithm suitable for programming architecture.
Let \(n\) be the number of choices of the first player; and \(m\) be the number of choices of the second player; the utility matrix of the first player would be;
\[A = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1m}\\ a_{21} & a_{22} & \cdots & a_{2m}\\ \vdots & \vdots & \ddots & \vdots\\ a_{n1} & a_{n2} & \cdots & a_{nm} \end{bmatrix}\]
the utility matrix of the second player would be;
\[B = \begin{bmatrix} b_{11} & b_{12} & \cdots & b_{1m}\\ b_{21} & b_{22} & \cdots & b_{2m}\\ \vdots & \vdots & \ddots & \vdots\\ b_{n1} & b_{n2} & \cdots & b_{nm} \end{bmatrix}\]
Each entry of matrix A represents a utility level of the first player while each entry of matrix B represents a utility level of the second player. The two subscripts of these entries indicate the strategies chosen by the two players where the first subscript refers to the strategy chosen by the first player and the second subscript refers to the strategy chosen by the second player.
Algorithm 2 (Creating the Algorithm to be Used in Comparing the Choices of the First Player):
1) A combination matrix \((C_A)\) is generated that contains all combinations of \((n,(n-t))\) with \(t=1\) at the initial point. Each row of \(C_A\) shows how to compare the choices.
It is aimed to obtain a randomized choice for each row by using its elements and then compare with the utility level of the choice which does not exist in that row. For instance, let \(c_1^{*}\) be the randomized choice that is obtained by randomization of the choices \((c_{11}, c_{12}, \ldots, c_{1(n-t) })\) . Then the utility level of \(c_1^{*}\) is compared with the utility level of the choice that does not exist in the first row. The randomization process is made with the procedures in the following steps.
\[C_A = \begin{bmatrix} c_{11} & c_{12} & \cdots & c_{1(n-t)}\\ c_{21} & c_{22} & \cdots & c_{2(n-t)}\\ \vdots & \vdots & \ddots & \vdots\\ c_{n1} & c_{n2} & \cdots & c_{n(n-t)} \end{bmatrix}\]
2) An index matrix \((N)\) with rows equal to the number of rows of the matrix \(C_A\) is generated. Each row of the index matrix is equal and consists of a number sequence of 1 to \(n\).
\[N = \begin{bmatrix} 1 & 2 & \cdots & n\\ 1 & 2 & \cdots & n\\ \vdots & \vdots & \ddots & \vdots\\ 1 & 2 & \cdots & n \end{bmatrix}\]
3) A comparison is made between the rows of \(C_A\) and N matrices. The elements existed in \(N\) and not in \(C_A\) are assigned to the corresponding row of the difference matrix. The purpose of this step is identifying the choice for each row which is compared with the randomized choice that is obtained in step 1.
\[D = \begin{bmatrix} d_{11} & d_{12} & \cdots & d_{1(n-(n-t))}\\ d_{21} & d_{22} & \cdots & d_{2(n-(n-t))}\\ \vdots & \vdots & \ddots & \vdots\\ d_{n1} & d_{n2} & \cdots & d_{n(n-(n-t))} \end{bmatrix}\]
4) For every row of \(C_A\), a probability vector \(P\) is generated from a uniform distribution on the \((n-t-1)-\) dimensional simplex.
\[P=(p_1,p_2,\ldots,p_{(n-t) }), \qquad p_1+p_2+\ldots+p_{(n-t) }=1\]
According to this probability vector, the first player chooses the first choice with the probability \(p_1\), the second choice with the probability \(p_2, ..., (n-t)\)th choice with the probability \(p_{(n-t)}\).
5) Using the obtained probability values, the expected utility for the first player as a result of choosing the randomized choice is calculated and compared with the utility provided by the choice not existed in the related row of the combination matrix.
If the first player believes that second player will choose his first strategy, the expected utility for the first player would be;
\[p_1 \times a_{11}+p_2\times a_{21}+\ldots+ p_{(n-t)} a_{(n-t)1}=E_1,\]
If the first player believes that second player will choose his second strategy, the expected utility for the first player is calculated as;
\[p_1\times a_{12}+p_2\times a_{22}+\ldots+ p_{(n-t)} a_{(n-t)2}=E_2,\]
\[\vdots\]
If the first player believes that second player will choose his last strategy, the expected utility for the first player is as below;
\[p_1\times a_{1m}+p_2\times a_{2m}+\ldots+ p_{(n-t)} a_{(n-t)m}=E_m,\]
If all expected utilities \((E_1,E_2,…,E_m)\) obtained are greater than the expected utility of the choice pointed by the element in the corresponding row of matrix \(D\), then the strategy is strictly dominated by that randomized choice. This process is made for every row of \(C_A\).
Two situations can arise here:
Elimination occurs: In this case, the reduced utility matrix is obtained. The new \(C (n^*,(n^*-t))\) combination matrix is created (where \(n^*\) is the number of rows of the reduced utility matrix) and the above steps are repeated.
Elimination does not occur: In this case, a new probability vector is generated, and the above steps are repeated. Here it is very important to decide the number of iterations that determine how many times the probability vector will be generated and it depends on the dimension of the game. Therefore, the number of iterations must be sufficiently large to be able to determine the strictly dominated choices (iteration \(\longrightarrow\) \(\infty\)). If there is no strictly dominated choice according to the utility matrix, the value of t is increased by “1” to form a new combination matrix \(C (n,(n-t))\) and the above steps are repeated.
6) When \((n^*-t) < 1\) the algorithm ends and the last reduced utility matrix is obtained.
The last reduced utility matrix determined by the above algorithm consists of the rational choices of the first player. The same steps are performed for the second player. The specified steps are written in the R statistical programming language, and a function named “esdc” is created. This function gives the reduced game after the iterated elimination of all strictly dominated choices. The properties of the function are shown in Figure 1.
esdc |
Eliminating strictly dominated choices |
|---|---|
| Description | |
| This function eliminates strictly dominated choices. | |
| Usage | |
esdc(n, m, A, choices.A, B, choices.B, iteration) |
|
| Arguments | |
n |
an integer representing the number of choices of player 1 |
m |
an integer representing the number of choices of player 2 |
A |
an nxm matrix representing the payoff matrix of player 1 |
choices.A |
a vector of length n representing the names of player 1’s choices |
B |
an nxm matrix representing the payoff matrix of player 2 |
choices.B |
a vector of length m representing the names of player 2’s choices |
iteration |
an integer representing the iteration number of algorithm |
| Details | |
| This function works for the games with two players. | |
| Value | |
| This function works for the games with two players. |
Figure 1: esdc Function
The esdc function uses seven arguments. These are; the choice number
of the first player (n), the choice number of the second player (m), the
utility matrix of the first player (A), the vector consisting of the
choice names of the first player (choices.A), the utility matrix of the
second player (B), the vector consisting of the choice names of the
second player (choices.B), and the number of repetitions of the
algorithm (iteration). As a result of the execution of this function,
the reduced utility matrices of the players’ that are obtained after
eliminating strictly dominated choices as output.
type functionIt is aimed to show that for every player \(i\) and every rational choice \(c_i (i=1,2,…,n)\), there is a type \(t_i\), which supports that \(c_i\) is optimal under common belief in rationality.
At the beginning of the game, a type is defined for each element in the player’s choice set. However, the “type” function generates types only for rational choices because the player do not choose irrational strategies in practice.
Construction of Epistemic Model:
Let \(A^*\) be the first player’s reduced utility matrix.
\[A^* = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1m}\\ a_{21} & a_{22} & \cdots & a_{2m}\\ \vdots & \vdots & \ddots & \vdots\\ a_{n1} & a_{n2} & \cdots & a_{nm} \end{bmatrix}\]
The first player believes that the second player will likely choose the first choice with the probability \(q_1\), the second choice with the probability \(q_2, \cdots,\) and the final choice with the probability \(q_m\). In this case, according to the preferences of the second player, the utilities of the first player can be expressed by a linear equation system.
Under this belief, first player will get the utility \(U_1\), if he chooses his first strategy;
\(a_{11} q_1+a_{12} q_2+ \cdots +a_{1m} q_m=U_1\),
he will get the utility \(U_2\), if he chooses his second strategy;
\(a_{21} q_1+a_{22} q_2+ \cdots +a_{2m} q_m=U_2\)
⋮
he will get the utility \(U_i\), if he chooses his ith strategy,
\(a_{i1} q_1+a_{i2} q_2+ \cdots +a_{im} q_m=U_i\)
⋮
he will get the utility \(U_n\), if he chooses his nth strategy,
\(a_{n1} q_1+a_{n2} q_2+ \cdots +a_{nm} q_m=U_n\)
The first player prefers his \(i\)th choice if and only if the inequality \(U_i\geq U_1,U_2,…,U_{(i-1)},\\ U_{(i+1)},…,U_n\) is satisfied. Then, when is this inequality satisfied?
Let’s express this inequality in pairwise comparison;
\(U_i\geq U_1 \Longleftrightarrow U_i-U_1\geq 0\)
\(U_i\geq U_2 \Longleftrightarrow U_i-U_2\geq 0\)
⋮
\(U_i\geq U_n \Longleftrightarrow U_i-U_n\geq 0\)
Then the linear equation system is obtained by substitution of the equals of the utilities explicitly, where q is a uniform distribution on the \((m-1)-\) dimensional simplex.
\((a_{i1}-a_{11} ) q_1+(a_{i2}-a_{12} ) q_2+ \cdots +(a_{im}-a_{1m} ) q_m=U_i-U_1\geq 0\)
\((a_{i1}-a_{21} ) q_1+(a_{i2}-a_{22} ) q_2+ \cdots +(a_{im}-a_{2m} ) q_m=U_i-U_2\geq 0\)
⋮
\((a_{i1}-a_{n1} ) q_1+(a_{i2}-a_{n2} ) q_2+ \cdots +(a_{im}-a_{nm} ) q_m=U_i-U_n\geq 0\)
Suppose that the first player’s \(i\)th strategy is optimal. In this case, all the points located in the convex region consisting of the intersection of the closed half spaces and the hyperplane are those, which make the \(i\) th strategy optimal under common belief in rationality.
The mathematical model above allows us to find all types that \(c_i\) is optimal under the common belief in rationality for every player \(i\) and every rational choice \(c_i ( i=1,2,…,n)\). By solving this model, an infinite number of points are obtained. Instead of dealing with infinite number of points in practice, constructing an epistemic model that there is a type \(t_i\) for each player \(i\) and for each rational choice \(c_i (i=1,2,…,n)\) that supports \(c_i\) to be optimal under the common belief in rationality that maximizes the utility is making more sense. For this reason, a linear programming model has been established for each choice. Thus, while showing at least, there is one type making the relevant choice optimal under common belief in rationality, and it can also be found the type that maximizing the utility of the player. In this regard, the linear programming model for the ith choice is established as follows.
\(Z_{max}=a_{i1} q_1+a_{i2} q_2+ \cdots +a_{im} q_m\)
\((a_{i1}-a_{11} ) q_1+(a_{i2}-a_{12} ) q_2+ \cdots +(a_{im}-a_{1m} ) q_m\geq 0\)
\((a_{i1}-a_{21} ) q_1+(a_{i2}-a_{22} ) q_2+ \cdots +(a_{im}-a_{2m} ) q_m\geq 0\)
⋮
\((a_{i1}-a_{n1} ) q_1+(a_{i2}-a_{n2} ) q_2+ \cdots +(a_{im}-a_{nm} ) q_m\geq 0\)
\(q_1+q_2+\cdots+q_m=1\)
\(q_1,q_2,\cdots,q_m\geq 0\)
Similar models can be set up for first player’s other choices and for the second player as well. A function named “type” has been created in R programming language for solving the linear programming model described above. The features of this function are shown in Figure 2.
The “type” function uses four arguments, named A, B, choices.A and choices.B. “A” is the reduced utility matrix of the first player, and “B” is the reduced utility matrix of the second player. “choices.A” and “choices.B” represent the name of the choices of players as previously defined. This function uses the “lp” function from the lpSolve package, which provides the Simplex method for solving linear programming problems (Berkelaar and et al 2015). As a result of the execution of the “type” function, probabilities for the types are obtained, which ensure that a rational strategy is optimal under common belief in rationality and maximizes the utility of the player.
Since in epistemic game theory, it is important to comprehend why and how a choice is strictly dominated, the “esdc” function becomes crucial. Indeed, it is advisable that to execute the “esdc” function before the types are specified. In other words, the “esdc” function should be integrated into the “type” function as a prepended operation (Baser 2017b).
type |
Finding types that express common belief in rationality for optimal choices |
|---|---|
| Description | |
| This function takes the reduced payoff matrices and finds out the probabilities for | |
| the types that expresses common belief in rationality for optimal choices. | |
| Usage | |
type(A, B, choices.A, choices.B) |
|
| Arguments | |
A |
an nxm matrix representing the reduced payoff matrix of player 1 |
B |
an nxm matrix representing the reduced payoff matrix of player 2 |
choices.A |
a vector of length n representing the names of player 1’s choices |
choices.B |
a vector of length m representing the names of player 2’s choices |
| Details | |
| This function works for the games with two players. It returns infeasible solution | |
| for the irrational choices. | |
| Value | |
| Probabilities of the types that expresses common belief in rationality for optimal | |
| choices |
Figure 2: type Function
We applied the two functions to Basu’s well-known The Traveler’s Dilemma (Basu 1994) game to underscore the practical usefulness of this work. Each player has 99 strategies between 2 and 100. The utility matrices for the players are created according to the utility function of the Traveler’s Dilemma game.
Applying esdc Function
The arguments for esdc function are assigned as given below. For this
numerical example, the “iteration” argument is taken as 500. The name of
choices of both players (“choices.A” and “choices.B”) are denominated by
the numbers between 2 to 100.
n = 99
m = 99
iteration = 500
esdc(n, m, A, choices. A, B, choices. B, iteration)
The Reduced Utility Matrices
With the execution of “esdc” function the algorithm eliminates all
strictly dominated choices from the utility matrices A and B. For these
matrices 196 times elimination occurred. The reduced utility matrices
are displayed below. In the last reduced game, the players have only one
choice left, which is choosing a price of “2”. Therefore, they can only
rationally choose a price of “2” under common belief in rationality.
[1] "ELIMINATION IS OVER."
[1] "The Last Reduced Matrix For Player 1:"
2
[1,] 2
[1] "The Last Reduced Matrix For Player 2:"
[,1]
[1,]
Applying type Function
The type function is executed for finding types for rational choices
under common belief in rationality given in the reduced matrices for
both players. The definitions of arguments are shown below.
A<-matrix(c(2),1,1)
B<-matrix(c(2),1,1)
choices.A = c("2")
choices.B = c("2")
type(A, B, choices. A, choices. B)
The Output of type Function
The output of type function includes the coefficients of the linear
equation system, the types that supports relevant choice under common
belief in rationality and the maximum utility of the player. For this
example, the output of type function is displayed below.
type(A,B,choices.A,choices.B)
[1] "The utility matrix of Player 1:"
2
2 2
Player 1’s type for the strategy 2 : 1
Success: the objective function is 2
[1] "The utility matrix of Player 2:"
2 2
Player 2’s type for the strategy 2 : 1
Success: the objective function is 2
The epistemic model of the first player was created as follows using
belief probabilities from the output of type function that make every
rational choice of the first player optimal under common belief in
rationality.
Type: \(T_1=\){\(t_1^2\)}
Belief for the first player:
\(\quad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad b_1 (t_1^2 )=(2,t_2^2)\)
The epistemic model is constructed by using the values for the second
player from the output of type function as follows:
Type: \(T_2 =\){\(t_2^2\)}
Belief for the second player:
\(\quad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad b_2 (t_2^2 ) = (2,t_1^{2})\)
Consequently, the first player will choose his choice “2”, if he believes that second player will choose “2” with the probability 1. In a similar way, the second player will choose “2”, if he believes that first player will choose “2” with the probability 1 and they will end up getting two units of money each.
Game theory has been investigated with epistemic approaches in recent years. Theorists and practitioners do research for analyzing the logic underlying game theory in a broader and more realistic perspective. Although epistemic game theory has a strong theoretical background, there is a lack of tools to work on large-scale problems in practice. This study based on common belief in rationality which can be considered as the heart of epistemic game theory. In two-player games, we developed a systematic way to find out types that optimize their rational choices under common belief in rationality for every player together with maximizing their utility. Thus, this study brings flexibility to producing solutions of large-scale problems within the scope of epistemic game theory. The algorithms which have been used are transformed into software. R is preferred because of its open-source software feature, and an R package has been created to bring the program into use. It is thought that this study will serve as an example for future work in computational epistemic game theory field and it is planned to adapt this approach to \(n\)-person games as well.
EpistemicGameTheory, roxygen2, lpSolve
This article is converted from a Legacy LaTeX article using the texor package. The pdf version is the official version. To report a problem with the html, refer to CONTRIBUTE on the R Journal homepage.
Text and figures are licensed under Creative Commons Attribution CC BY 4.0. The figures that have been reused from other sources don't fall under this license and can be recognized by a note in their caption: "Figure from ...".
For attribution, please cite this work as
Başer & Cinemre, "Epistemic Game Theory: Putting Algorithms to Work", The R Journal, 2018
BibTeX citation
@article{RJ-2018-003,
author = {Başer, Bilge and Cinemre, Nalan},
title = {Epistemic Game Theory: Putting Algorithms to Work},
journal = {The R Journal},
year = {2018},
note = {https://rjournal.github.io/},
volume = {10},
issue = {1},
issn = {2073-4859},
pages = {370-380}
}