Introduction to game theory: Nash equilibria and multiple equilibria
Game theory is that mathematical science developed in order to understand what is the best strategy for a subject to implement in situations that change not only as its decisions change but also those of its related subjects. This theory, as can be easily guessed, is applied to many areas, for example, those in which we aim to study a profitable marketing plan or policy.
An example that we recommend can be found below:
We define game as any situation in which:
Every player in general will seek to maximize his or her own profit but this may not necessarily be his or her only interest; in fact, he or she may also seek to maximize the return of other players, and if so, the concept of profit will have to be revised so that it fully describes the degree of satisfaction of the subject.
Central to game theory is the concept ofNash equilibrium developed by John F. Nash, an American economist and mathematician, whose studies within this field led to the development of what is called, the “prisoner’s dilemma.” Below we see a schematic representation of it.
Now let’s introduce some new definitions.
A choice of strategies, one for each player, is socially optimal if it maximizes the sum of the payoffs of all players, while it isPareto-optimalif there is no other combination of moves such that it improves the payoffs of at least one player without decreasing that of the others. We will not demonstrate it here for the sake of brevity, but if a solution is socially optimal then it is also Pareto-optimal.
We will assume that each player is fully familiar with the structure of the game (i.e., that the game is complete) and thus is aware of all the possible strategies and gains of each participant. In addition, we will assume that each participant is intelligent (i.e., able to figure out, without making mistakes, given a set of possible strategies which one is the most advantageous) and rational (i.e., such that, once he or she recognizes the highest-profit strategy(s), he or she prefers it to the others [14]).
Models in which such assumptions are not made can become extremely complicated, and we will not go into them in the course of this discussion.
Students' example
Consider the following example from the sixth chapter of [2].
A student faces an exam and a presentation for the following day but cannot adequately prepare for both. For simplicity, let us assume that he is able to estimate with excellent accuracy what grade he will get (calculated in hundredths) from both tests as his preparation varies.
Specifically, as far as the exam is concerned, the student expects a grade of 92 if he/she studies and 80 otherwise. The presentation, on the other hand, has to be done with a partner and in case both work on it the relative grade will be 100, if only one of them (regardless of who) works on it 92 and if no one does it 84. The partner also has to choose whether to study for the exam or to concentrate on preparation and his or her predictions on grades are the same.
Finally, assume that the two fellows cannot communicate and thus agree on what to do. The goal for both is to maximize the average value of the two votes, which will then go on to constitute the final vote. Let us outline the possible outcomes below:
We can therefore conclude that the best thing to do would be, in any case, to study for the exam.
When, as in the example presented, a player has one strategy that is strictly more convenient than the others, regardless of the behavior of the other players, we will call that choicestrictly dominant strategyand, assuming the rationality of the subject, we will assume that he adopts it.
In the previous example, due to the same nature of the problem, we expect symmetrical behavior from the two players who will therefore both choose to study obtaining the overall grade of 88.
However, it is interesting to note that if the students could have agreed to both prepare the presentation the final result would not have varied, in fact, in that case, the student would have expected an average grade of 90 and therefore would have decided to study for the exam knowing that the other would have prepared the presentation, in fact this would allow him to achieve 92.
In fact, such a plan would not have worked because, upon closer inspection, one realizes that the partner, in a mechanically rationalistic view focused on maximizing his own profit, would also have implemented in the same way, and thus both would have achieved an average score of 88, while, by not playing rationally, they could have achieved the score of 90.
One last “definition” before explaining a central theme of game theory: without getting into technicalities we will say that in practice the best response is the most convenient choice that a player, who believes in a given behavior of other players, can make.
Nash Equilibrium
We highly recommend watching this video from the very famous movie “A Beautiful Mind” before continuing.
Given a game, if none of the participants has a strictly dominant strategy, to predict how the situation will evolve, we introduce the concept ofNash equilibrium, according to which, in such a situation, we should expect players to use the strategies that give the best responses to each other.
Refer to [13] for a more precise definition, but in practice, if a game admits at least one Nash equilibrium, each participant has at least one S1 strategy at his disposal to which he has no interest in deviating if all the other players have played their Sn strategy. This is because if player i played any other strategy available to him while everyone else played his own se strategy, he could only make his gain worse or, at most, leave it unchanged. Since this applies to all players if there is one and only one Nash equilibrium, it constitutes the solution of the game since none of the players has any interest in changing strategy.
In other words, Nash equilibrium is defined asa profile of strategies (one for each player) with respect to which no player has an interest in being the only one to change.
However, there are games that have more Nash balances.
Multiple balances: coordination games
Suppose, taking up the previous example, that the students have to prepare, once they have divided the work, the slides of the presentation. The student, with no possibility of communicating with his or her partner, must decide whether to create the slides with program A or program B considering that it would be much easier to merge them with his or her partner’s slides if they were made with the same software.
Such a game is called a coordination game because the goal of the two players is to coordinate. In this case we notice that there are multiple Nash equilibria, namely (A,A) and (B,B). What should be expected?
The theory of focal points(also called Schelling’s points) tells us that we can use inherent characteristics of the game to predict which equilibrium will be the one chosen, i.e., the one that is able to give all players the greatest gain. Thomas Schelling in The Strategy of Conflict describes a focal point as: “each player’s expectation of what others expect him to do.”[7]
For example, returning to the student game, if student S1 knew that partner S2 prefers A, then he would choose A, in fact knowing that S2 in turn knows that he is aware of this fact will assume that the latter will indeed choose A knowing that S1 will comply accordingly.
Schelling illustrates this concept through the following example, “Tomorrow you have to meet a stranger in New York, what place and time would you choose?”
This is a coordination game, where all times and all places in the city can be a balancing act. Proposing the question to a group of students he found that the most common answer was “at Grand Central Station at noon.” The GCS is not a place that would lead to a higher payoff (the player could easily meet someone at the bar, or in a park), but its tradition as a meeting place makes it special and is, therefore, a Schelling point. In game theory, a Schelling point is a solution that players tend to adopt in the absence of communication because it appears natural, special, or relevant to them.
Game theory combines well with graph theory, and we will introduce it in future articles to see other examples of how there can be a possible conflict between individual rationality, in the sense of maximizing self-interest, and efficiency, that is, the search for the best possible outcome, both individual and collective.
We have also seen that applying an individualistic strategy sometimes results in a lower outcome than if an agreement can be reached, and that if a Nash equilibrium exists and is unique, it is the solution to the game since none of the players have an interest in changing strategy.
Bibliography and sitography
[1] R. Dawkins, The Selfish Gene, I edition Oscar essays series, Arnoldo Mondadori Editore, 1995.
[2] D. Easley and J. Kleinberg, Networks, Crowds, and Markets: Reasoning about a Highly Con- nected World, Cambridge University Press, 2010.
[3] R. Gibbons, Game Theory, Bologna, Il Mulino, 2005.
[4] S. Rizzello and A. Spada, Cognitive economics and interdisciplinarity, Giappichelli Editore, 2011.
[5] G. Romp,Game Theory: Introduction and Applications, Mishawaka, Oxford University Press, 1997
[6] T. C. Schelling, The Strategy of Conflict, Cambridge, Massachusetts: Harvard, University Press, 1960.
[7] P. Serafini, Graph and Game Theory, a.y. 2014-15 (revised: Nov. 28, 2014).
[8] http://it.wikipedia.org/wiki/Equilibrio_di_Nash accessed 12/05/2015.
[9] http://www.oilproject.org/lezione/teoria-dei-giochi-equilibrio-di-nash-e-altri-concetti-introduttivi-2471.html accessed on 05/13/2015.
[10]https://www.youtube.com/watch?v=jILgxeNBK_8 accessed on 19/01/2021.
[11]https://it.wikipedia.org/wiki/Teoria_dei_giochi
[12]https://fiscomania.com/teoria-dei-giochi-prigioniero-nash/