Game theory basics

Generally speaking, the stag hunt game goes back to Rousseau's work «A Discourse Upon the Origin and Foundation of the Inequality Among Mankind» quoted above; with this game Rousseau illustrates the difficulties in coordinating and establishing public institutions (by the way, note: hunters operate in untrusted environment like the islanders from the previous longread; if they trusted each other, they would always return from the hunt with a deer in their hands). And this game, along with the famous Prisoner's Dilemma, is the most famous introductory example in game theory.

It is often said that the game is a model of conflict. This is true and at the same time not true; sometimes a conflict in the game is present in a very veiled form. For example, although it seems that the hunters from our example do not directly conflict, however, each of them acting not so cleverly can leave the other without dinner. The hunter has an internal conflict between personal and public interests. That is why this same game can also be considered as a model of a situation requiring coordination: if the hunters were confident in each other, or if at least one had the opportunity to quickly convince a partner to follow the «deer» strategy, both would benefit. Therefore, a game is a model of conflict or coordination and sometimes both of them.

We will return to coordination issues, but for now our task is simpler: it is convenient to start the story about games in general and about various forms of recording them in particular with the game «Deer Hunting». So the game can be described in different ways, namely, as:

There is a couple of other important taxons in the world of strategic interactions. Let's name a few of them. First, a game can be:

Second, a game can be:

Third, a game can be:

And finally, a game can be:

We can take another important thing from the «Stag Hunt»: solution concept. In the video, I discussed what scenario (or scenarios) the game will play in general, how the players will argue, what they will take as a result. It seems that «there is no other way», but generally speaking, there can be several principles for constructing such scenarios. These principles are called decision concepts or equilibrium. There are many of them in game theory. The Nash equilibrium discussed in the video is one of the most commonly used solution concepts.

Nash equilibrium has its own particular subtypes; and there are other types of equilibria besides Nash equilibrium. In order to analyze cryptoeconomic systems, most importantly is to understand Nash equilibrium in mixed strategies and perfect for subgames as well as sequential equilibrium, zero-determinant equilibrium, Stackelberg equilibrium and average payoff equilibrium. The overview of these types of equilibria with applications in blockchains and references to the literature is observed by Liu et al. (2019).

In the articles on game theory you will often come across a few more terms. One of them is a strategy profile (good explanation of the term can be found here and here). The second is tuple which is also defined in the book by Umbhauer (2016) and Wikipedia.

Nash equilibrium is called subgame perfect if any of its subgames holds Nash equilibrium. How can you find it? The algorithm for this is called backward induction. Let's look at the following non-cooperative, asymmetric, non-zero-sum, perfect information game.

By the way, could you explain all the taxons: non-cooperative, asymmetric, non-zero-sum, perfect information game? The game is non-cooperative, because even if pirates formed coalitions by making agreement on the votes, there would be no way of enforcing these agreements. It is asymmetric, as there are always proposer and voters that substantially differ in their sets of strategies. It is clearly non-zero-sum, as in all leafs the sum of payoffs does not equal zero. And it is sequential with players perfectly informed by the moves of others.

Could you draw tree of the game for pirates game then? It would be huge! Another question: what if players think about how other players play? How deeply do they think over the steps of other players. Does the player think about his vis-à-vis in relation to the player's own moves? Class games of this kind are called p-beauty contests, and its consideration is beyond the scope of this longread. The question is simpler: what if every player knows the theory of games, knows how to compose a game tree, finds Nash equilibrium and at the same time knows that other players have the same skills? Reverse induction is another example of a solution concept that is used to find the equilibrium state in games presented in extended form. For games in normal form you can apply sequential removal of weakly dominated strategies for similar purposes.

Before we proceed, read this article about game theory and evolution of trust, play this game, and then:

Trust game is non-cooperative (cheating is allowed), symmetric (payoff matrix is symmetric), non-zero-sum (there is win-win in one of the leafs), imperfect information game.

Up to this point we studied abstract representations of strategic situations which theoretically could be found in real life. Can we reverse engineer strategic interaction and design a game deliberately to help solve some problem? Let's try to approach the answer. First, watch the video, then represent game in strategic and normal forms and think: what Nasreddin could advise traders?

Nasreddin was laconic: «Swap donkeys», he told the merchants. He clearly realized the main problem of this situation — the merchants were motivated (a) to hide the true speed of their donkeys, and (b) to find out the speed of another donkey. Controlling his donkey the merchant at least partially achieves his motivation. And since they both achieved motivation, the situation is not resolved in a positive sense. Nasreddin takes a step further than Rousseau: he does not analyze the situation as a game but designs a game to change the situation.

It seems that we have «game inside the game»: while traders play their «silly game of revelation the slowest donkey», Nasreddin plays his own game, where he himself has completely different goals and several strategies, or in our case advice. Each Nasreddin's strategy is a game itself, which he advises traders, and has its own tree resulting in different consequences for traders. Looking ahead, we will call Nasreddin mechanism designer; all the third week we would dedicate to mechanism design.

Now, let me add that if Nasreddin offered cryptographic guarantees that the owner of the slowest donkey would really get his prize, he would be the creator of real cryptoeconomic system. For example, each trader would deposit some amount in the smart contract, which upon receiving message from some oracle (let's pretend that oracle problem is successfully solved in Nasreddin's world) would automatically send the prize to the winner. Loser would have no possibility to avoid payment at all. If both traders deposit money on some escrow account, chances are that losing party would try to bribe escrow account holder or attack the system the other way. You may think that if oracle problem is not solved, all the reasoning above worth nothing as it is irrelevant in practice. Well, think about this: oracle problem is itself a problematic situation that could be solved by a mechanism designer.

Consider a different situation. Two pirates, say, Dormidont and Serapion, found an indivisible treasure. In order to decide who gets it, they suggest tossing the coin. The problem is that each pirate has his own coin, and they do not trust each other, they do not believe that the coin of the other is «fair» (that is having equal chances for «heads» and «tails»). How can Dormidont and Serapion share treasure without killing each other, even if both coins are «sawed»? Hint: start from thinking about strategies available to pirates. Is it similar to the case of Nasreddin? If not, are there any similarities?

Again we have «game inside the game» situation here: there is designer which proposes some scheme to pirates; and there are Dormidont and Serapion who just take the scheme. Note that pirates (according to them) are not inclined to strategise, to seek for optimal strategy. They demonstrate reluctance to delegate decision to stochastic Nature just as was in the case of Nasreddin and traders.

In fact, fair division is achieved when each of the pirates really delegates decision to Nature, and at the same time when both of them know for sure that the other party did the same. Again as was in the previous case, each pirate controls half of the Nature and is not motivated to achieve real stochasticity.
What can we do here? For example, we can modify the coin toss game like that: each pirate tosses a coin; if both coins fall on the same side («heads-heads» or «tails-tails»), then Serapion takes the treasure; if both coins fall on different sides («heads-tails» or «tails-heads»), then Dormidont takes the treasure. It is easy to prove that scheme would provide real stochasticity in case if one, or both, coins are deliberately unfair.

The time has come to talk about coordination games. This type of cooperative, symmetric, non-zero-sum, imperfect information games is often mentioned in the literature on distributed ledgers and blockchains and, specifically, in the context of oracles and digital currencies.

Impossibility of establishing a perfect «distributive ledger» leads to an engineering solution. They need to choose different structural and architectural data storge elements, network topology between them and other nodes, nodes motivation schemes, cryptographic protocols, and — the most important — consensus protocols. In the end, it is the consensus protocol that defines many final characteristics of the ledger including its functional characteristics and scalability as well as other architectural decisions which adjust with your consensus.