Coordination games are strategic games with multiple Nash equilibria. A Nash equilibrium, as described in a recent post of ours, titled Nash Equilibria and Blockchain Platforms, is an outcome of a strategic game in which none of the participants want to change their choice of actions, given the actions of the other players.

In our previous post, we emphasized how important it is for a platform’s desired outcome to be an equilibrium. When there are multiple equilibria, all players in the game need to coordinate on the same Nash equilibrium in order for the benefits of equilibrium to be realized. This is why these games are called coordination games. When players must choose their actions simultaneously, without knowing what the other players will choose, it can be extremely difficult for the players to coordinate in this way.

Understanding coordination games is important for blockchain developers because they arise frequently and, without proper design, can lead to potentially undesirable outcomes such as hard forks or non-equilibrium outcomes. In this post, we will walk through the principal concepts in coordination games and common failures. We’ll then discuss an example for how blockchain governance can be used to prevent these failures.

For a full mathematical analysis of the governance example presented here, please see our paper Blockchain Upgrade as a Coordination Game, which we will be presenting at the P2P Financial Systems 2018 Workshop at the Federal Reserve Bank of Cleveland in July, 2018.

A simple example of a coordination game is called the Battle of the Sexes game. In the battle of the sexes game, one player (called the man) would like to attend the ballet, while the other (called the woman) would like to attend a bullfight. However, both the man and the woman would rather spend time together than to spend time apart.

The payoff matrix for the battle of the sexes looks like this:

If the man and the woman attend the bullfight together, the man gets a payoff of 2, and the woman gets a payoff of 3. If the man and the woman attend the ballet together, the man gets a payoff of 3 and the woman gets a payoff of 2. If the man and the woman attend their preferred events separately, they each get 1, and if they attend their less-preferred event alone, they each get 0.

Attending the ballet together and attending the bullfight together are both Nash equilibria of the game. Each player would prefer to attend their less-favored activity with the other person, rather than to change and attend their favorite activity alone.

The challenge in this game is for the two players to coordinate which event they will attend while having to choose at the same time without speaking to the other person.

Two types of problems that can occur in a coordination game are known as coordination failures and coordination faults.

A coordination failure takes place when the players of a strategic game do not land on an equilibrium outcome.

In the Battle of the Sexes game, the woman going to the bullfight while the man goes to the ballet, or vice versa, is a coordination failure. As both players would be better off if either player changed their choice of how to spend the evening, coordination failures can be quite costly.

A coordination fault is when the equilibria of the game can be ranked — everyone agrees that one is better than another — but the players coordinate on a suboptimal equilibrium.

Consider the variation of Battle of the Sexes game — let’s call it Harmony of the Sexes — below. Both the man and the woman prefer the bullfight to the ballet, and they prefer attending either event together than attending either event alone.

If both the man and the woman attend the ballet together, this is a coordination fault. Neither person wants to unilaterally switch to the bullfight and risk having to go alone. However, they would both prefer to coordinate and switch to the bullfight together.

Why is this important for blockchain?

In the context of blockchain, upgrading the system is often a coordination game.

Suppose that a blockchain community is considering a policy upgrade. There are three paths that the community can take:

1. The entire chain can stay with the status quo policy.
2. The entire chain can upgrade to the new policy.
3. There can be a hard fork, where the users who prefer the status quo and the users who prefer the upgrade go their own ways on separate chains.

Which path a user prefers depends on two forces:

1. Their relative preferences over the two options — how much they care about the policy upgrade compared to the status quo.

2. Their preferences with respect to network effects — how much they care about being on the same chain as other users.

As a user, I obviously prefer having my preferred policy implemented by the entire community, all other things equal. But if I prefer one policy over the other only slightly, I still might prefer to be on a large chain with my less-preferred policy than on a small chain with my more-preferred policy. This depends on the payoff I get from being on a large chain compared to a small chain. In our paper, we demonstrate the thresholds for which each outcome can be expected.

Because my preferred choice depends on what the other users choose to do, this is a coordination game. Without clear information regarding what other participants prefer and what they will do, choosing whether to upgrade is a shot in the dark. Such uncertainty could lead to a hard fork and, as a result, a costly coordination problem.

How can blockchain communities avoid coordination failures? One way to reduce the likelihood of these costly coordination problems is to introduce what is called a focal point.

A focal point is a public signal that all players understand. A focal point indicates to everyone which Nash equilibrium they should choose. A focal point can be anything.

In the Battle of the Sexes game, a focal point can be where the couple went on their previous date. It can be sun signals, or numerical codes, or a big sign that says “GO TO THE BALLET”. The only qualifying criterion for a focal point is that it must increase the chance that the players all coordinate on the same equilibrium.

In the blockchain upgrade situation, a governance system could help facilitate the coordination of the community on an equilibrium that everyone can accept.

For example, a majority rule governance system could help the community coordinate on one chain, if the members believed that everyone would accept and abide by the outcome of a vote. Under these conditions, a vote of 55% in favor of the upgrade would inform each member that everyone else will use the upgraded chain, and therefore that individual is better off also using the upgraded chain. Similarly if the vote indicated 55% in favor of the status quo, all users would choose the status quo chain.

This system would only work if the community believed that other users would abide by the outcome. In that way, the governance system serves as a focal point: It does not enforce behavior; rather, it guides users in helping them make coordinated choices so that better outcomes can be reached.

For early blockchains, the lack of governance is likely a key factor contributing to the occurrence of hard forks, which are sometimes a form of coordination fault or failure. When it becomes apparent that an upgrade to the code could be beneficial, the lack of clear information regarding what other network participants will do can result in an inability to coordinate on a beneficial equilibrium.

Introducing a system of rules for determining whether an upgrade should be implemented by way of a properly structured governance system will greatly reduce the likelihood of these hard fork coordination failures.

For decentralized systems like blockchain protocols and dapps, there may be a variety of productive activities that resemble coordination games. Upgrading a protocol is one example, but we have previously discussed multiple equilibria in token curated registries.

When designing a platform, it is important to recognize when a system has multiple equilibria so that measures can be put in place that will help coordinate the actions of users on good equilibria. You can read more about our recommendations for those measures in the context of blockchain governance in our paper: Blockchain Upgrade as a Coordination Game.