Implementation of algorithmic theory of games in Python with Nashpy
What is a strategic situation? Recall the types of market structures: there is perfect competition when all companies are pricing, that is, they do not need to worry about a pricing strategy, and there is a monopoly when there is only one company on the market that sets its prices. So: everything between perfect competition and a monopoly is a strategic situation.
Algorithmic game theory is at the junction of game theory and computer science and is aimed at studying and creating algorithms for strategies.
Under the cat, a short story about how you can use the theory of games in Python using the Nashpy library.
From the editor: why did we suddenly remember about game theory? Everything is simple – continuously upgrading your a platform with 900 thousand participants, we are constantly faced with situations where we need to develop various strategies. For example, on the portal NTI experts: whether to confirm everyone in a row or, conversely, not to confirm anyone, but only ask for confirmation. Another example: the struggle for resources is regularly observed at the boiling points, and there are dilemmas there – do they ask all the equipment at once, do they write real numbers in the number of participants, or overstate? Moreover, the solution of these issues should be carried out with maximum benefit for all.
Nashpy
As the name suggests, the library provides algorithmic capabilities to achieve Nash equilibrium – a set of strategies for two players, when each of them chooses the best option for their behavior based on a similar setup for the second player. Remotely, it resembles the principle of win-win, but with an orientation to minimal losses in any situation.
To understand this concept, we turn to the popular model “Prisoner’s Dilemma“.
To surrender or not to surrender
There are two players (prisoners) who must decide whether to cooperate with each other without giving another name during interrogation by the police. The usefulness of this behavior will be estimated at three points for each player, if both choose this path. The starting point here is the punishment: if the players give each other out, they can be charged with “conspiracy”, that is, “banditry”, and the punishment for them in this case will be more severe than if they acted separately.
If one player passes the other (provided that he does not pass), the utility for him will be four points, for the other player – zero points. If the prisoners surrender each other, the usefulness will be one point per brother.
To make it easier to imagine this set of options, put them on a plate, where in the cells, indicate the number of points for each prisoner, separated by a comma, depending on the choice made:
P1 – player 1, P2 – player 2, C – cooperation, NC – one player passed another
As a result, the best option for both is to hand over each other.
Why won’t the prisoners collaborate? Consider the strategy of player 1 (P1):
- if player 2 (P2) decides to cooperate with P1, the best strategy for P1 is to turn in player P2, since 4> 3
- if P2 decides to turn in P1, then P1 is more profitable to turn in to play as well, since 1> 0
So, the winning strategy for P1 is (NC; NC), which is also true for P2. Thus, the Nash equilibrium will be the strategy (NC; NC) when players P1 and P2 surrender each other to the police.
We transfer the theory to Python
First you need to install the module. This can be done by the team. pip install nashpy through the jupyter console. At the end of the installation, you can begin to set the game conditions. For two players with a non-zero result (which is the default value in Nashpy), you need to create two matrices that reflect the game situations for each player. For example, for player 1, the matrix will look like this:
| C | NC | |
| C | 3 | 0 |
| NC | 4 | 1 |
For player 2 like this:
| C | NC | |
| C | 3 | 4 |
| NC | 0 | 1 |
Let’s reproduce this in Python:
import nashpy as nash
import numpy as ns
P1=np.array([[3,0],[4,1]])
P2=np.array([[3,4],[0,1]])
prisoner_dilemma=nash.Game(P1,P2)
prisoner_dilemma
Looking at these plates, we can get an estimate of the usefulness of the interaction of the players. That is, if P1 does not give P2, and P2 gives P1, then the utility values will be (0, 4). We can get the same thing with matrix calculations in Nashphy. We take a vector of actions as a sigma (we have two of them: to collaborate or hand in another prisoner), where the value 0 is assigned to all cells except the one where the action takes place. Then for player 1, the utility of the action will be calculated as:
For player 2:
Applying the formula to the scenario, when player 1 chose a strategy for cooperation with another player, and player 2 decided to turn in player 1, we get:
Check with Nashpy:
We will find out whether the algorithm finds the Nash equilibrium, which, as we have already found out, is (NC; NC):
As you can see, the Nash equilibrium consists of two vectors, each of which reflects the actions of one player: for player 1, this [0; 1], where 1 in the second field means that player 1 has decided to turn in player 2. We see a similar picture for the second player.
P.S. what can be read on the topic
- Game Theory (Avinash Dixit and Barry Neilbuff) is a fairly recent publication from the MYTH Publishing House. In the book, with examples from cinema, sports, politics and history, the authors show how almost all companies and people are involved in interactions that are described by game theory.
- Conflict Strategy (Thomas Schelling). The book is devoted to the study of the general logic of behavior of participants in conflict situations – game theory. Released in 1960, it became a fundamental contribution to this science, laying the foundations of the theory of strategic behavior.
- Rock, Paper, Scissors: Game Theory in Everyday Life (Len Fisher) is another book about the science of collaboration. Fisher shows how game theory has helped biologists understand the evolution of collaboration in nature, and how we could apply it in our society.
