Game theory is a method of studying strategic situations where the results depend not only on your actions, but also on what others will do.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 aims to study and create 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 our platform with 900 thousand participants, we are constantly faced with situations where various strategies need to be developed. For example, on the NTI experts portal : whether to confirm everyone in a row or, conversely, not to confirm anyone, but only ask for confirmation. Another example: In Boiling Points, a struggle for resources is regularly observed, and there are dilemmas - do we ask all the equipment at once, write real numbers to the number of participants, or overstate? Moreover, the solution of these issues should be carried out with the 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 most optimal version of their behavior based on a similar setting for the second player. Remotely, it resembles the win-win principle, but with an orientation to minimal losses in any situation.To understand this concept, let us turn to the popular model “ Prisoner 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 action,” 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 the plate, where in the cells, indicate the number of points for each prisoner, depending on the choice made:
P1 - player 1, P2 - player 2, C - cooperation, NC - one player passed anotherIn the end, 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 P2, 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 the 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 nashpythrough 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:For player 2, like this: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 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 usefulness of the action will be calculated as:
For player 2:
Applying the formula to the scenario, when player 1 has chosen a strategy for cooperation with another player, and player 2 has decided to hand over player 1, we get:
Check with Nashpy:
Find out if it finds an algorithm 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 is [0; 1], where 1 in the second field means that player 1 decided to turn in player 2. We see a similar picture for the second player.PS what can be read on
- 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.