Research diaries: Anarchy in Creta

20 years ago, Worst-Case Equilibria by Elias Koutsoupias and Christos Papadimitriou, presented in STACS, introduced a notion soon to be known as the Price of Anarchy (PoA). Widely recognized as the starting point of Algorithmic Game Theory, a branch of game theory dedicated to the study of systems from the computational lens, it celebrated its 20th birthday early in July 2019 with some of the most prominent researchers of the field.

It was only fitting that the celebration be held in Greece, Koutsoupias, Papadimitriou and others in their footsteps being trained in Athens, at the National Technical University. The University of Creta, in its desertic environment, overlooking a clear blue sea, offered a relaxed setting for the sixty or so attendees over four days of talks and, you guessed it, Cretan food.

Regarding how this fits into our agenda of introducing broad audiences to current research relevant for blockchains and cryptoeconomics, the interest is double.

Price of Anarchy, by definition, quantifies the (worst-case) extra inefficiency from relinquishing central control in favor of a decentralized society. We will define and spend time explaining what this means in plain English, but already you can see that this has a flavor close to blockchains.

The second motivation is to try out a new format here at hackingresear.ch, that of a research diary, to show not the research as it is presented once done and settled, but the research as it is made, in flux always. Our own points of views will be represented here, with the intent to start a conversation over the topic at hand.

In this essay, I'll follow a lecture by Elias Koutsoupias given during the conference, related in Section . It will introduce the themes of games, equilibria and deviations from the Bitcoin protocol, although the presentation is not specific to that protocol.

In Section , I'll introduce the Price of Anarchy and show its relation with measuring inefficiency in decentralized systems. Finally, Section will put it all together, where I'll discuss how this applies to specific cryptoeconomical problems.

On the last day of the conference in Creta, Elias Koutsoupias delivered a keynote on Blockchain Mining Games. Highlighting the parallels with how Price of Anarchy research started in 1999, not long after the beginnings of the Web, Koutsoupias singled out the following question from a paper published by Papadimitriou as Algorithms, Games, and the Internet in 2001 :

Of which game is TCP/IP congestion control the Nash equilibrium of?

To be clear, the question was answered in several works since . What we ask now may be instead:

Of which game is Bitcoin the Nash equilibrium of?

Of course "Bitcoin" is a vague placeholder. Let us separate two things for argument's sake.

We can now rephrase the question above:
Is the Bitcoin protocol a Nash equilibrium of the Bitcoin game?

Intuitively, the answer should be a resounding yes. But selfish mining was (to my knowledge) the first to say "Not quite!" A certain combination of parameters and luck made it so that miners could profit by deviating from the protocol.

In this case, the Bitcoin protocol, understood as honest miners releasing blocks as they are found, is not the Nash equilibrium of the Bitcoin game induced by its components! If it was, miners would not have a strict incentive to deviate from the Bitcoin protocol, where miners are honest. But since they can profit by deviating and indulging in selfish mining under some conditions, it is not a Nash equilibrium.

More holes followed. Optimal selfish mining determined how a miner can maximize its chances of performing a successful "hiding" attack. Blockchain mining games expanded and precised the strategy sets. Koutsoupias, in his lecture, stressed that more questions remain open:

The questions that agitated much of the research in algorithmic game theory are far from settled in the context of blockchains. The blueprint given by Papadimitriou in his 2001 paper seems as relevant now as it was 20 years ago to understand the dynamics of the Internet at the intersection of computation and economics. In the next sections, we will introduce what the Price of Anarchy is and see what it tells us about decentralization.

Let us start with a brief history of the Price of Anarchy (PoA). In 1999, Koutsoupias and Papadimitriou published in STACS Worst-Case Equilibria , with a concept known as the coordination ratio, later renamed Price of Anarchy. At the time, the Web and its physical layer, the Internet, were a new object of study and a question emerged early on: why should it work at all? Or as Papadimitriou frames it :

There is no central authority that designs, engineers and runs the Internet. But what if there were such master puppeteer, a benevolent dictator who, for example, micromanaged its operation, allocating bandwidth to flows so as to maximize total satisfaction? How much better would the Internet run? What is the price of anarchy?

The Internet was born out of the connections of thousands, later millions and billions of networked computers exchanging packets between each other, with no central authority showing the way to everyone. Instead, it relied on protocols to allocate flows so that it wouldn't collapse under congestion. But there is no reason why this should be optimal at all, or why realized flows minimize the congestion in the network.

Since scientists like models to isolate the one idea driving their thought, the next section introduces the famous Pigou network, the "Drosophila" of algorithmic game theory as Chotibut et al. point out in .

Arthur C. Pigou, British economist of the early 20th century, of the Pigouvian taxation fame, did a substantial amount of work to understand how externalities affect the welfare of a society . In a simple model that led to over a century of debates , he introduced the problem of carts (sic) wishing to travel from Left to Right.

The carts are assumed to be small enough that we consider a flow (like water) of mass equal to 1. To route themselves, they can choose to take one of two links.

Two distinct scenarios can be studied.

  1. The optimum. A central planner cares that the average time spent on the road is minimized for the population. It is achieved if half of the carts go on the upper link (latency = 30 minutes) and half of the carts go on the lower link (latency = 60 minutes). On average, each cart spends 45 minutes on the road, and this number is the lowest achievable .
  2. The equilibrium. One can see that the optimum is untenable. The mayor of Pigouville thanks you for your service to the community while you are routed to the lower link and observe the upper link people taking half the time you take. There is not currently a world in which people care so much about public interest, so lower link carts would start moving where the grass is greener and latencies are lower to the upper link, until no one is left on the lower link. Now all carts on the upper link incur a latency of 60 minutes, away from the 45 minutes average of the optimum.

The Price of Anarchy is equal to the following ratio

\text{Price of Anarchy (PoA)} = \frac{\text{Cost(Worst Equilbrium)}}{\text{Cost(Optimum)}}

In the Pigou network, we have only one equilibrium, so \text{PoA} = \frac{60}{45} = \frac{4}{3}. In other words, the equilibrium, where decisions are decentralized, is 33% more inefficient than the optimum, where a master puppeteer decides for everyone.

What to do after Pigou? Centralization is not a desirable thing, for many reasons including:

Yet decentralization doesn't look more appealing if 33% extra energy (possibly more) is wasted by the selfishness (in the game-theoretic sense) of agents. Is there a way out?

As Papadimitriou frames it in his 2001 talk, there is.

All design problems are now mechanism design problems.

Here is an overly simplified mental map I like to think about to orient myself in the landscape of the game.

At the top-left of the chart, the master puppeteer has perfect control over the system and optimizes some metric of efficiency. This is good, but as we have seen, neither desirable nor possible in many cases. Left to its own devices, society moves towards "Anarchy", some equilibrium state that is inefficient (with respect to the centralized optimum) .

A planner might still feel wholly unsatisfied with congestion in its city being 33% more inefficient because of decentralization. The problem is then how to reach efficiency without a planner taking over, leading to the observation that All design problems are now mechanism design problems.

What does this look like in practice? In the Pigou network, a central planner can modify the network to price the congestion on the upper link. By setting a toll to the monetary equivalent of half an hour spent on the road , at equilibrium, the flows look exactly like optimum. Half of the travellers, on the upper link, incur a cost of 60 minutes (a latency of 30 minutes plus a "price" of 30 minutes), while the other half on the lower link travels for 60 minutes. From the planner's point of view, average latency is 45 minutes.

Reaching optimal equilibria, or more precisely, designing incentives such that optimum is attained as an equilibrium, is the holy grail of the profession. When Bitcoin was born, part of its attraction stemmed from the elegance in which it seemed to find an optimum equilibrium to a complex situation of decentralized decision-making. As Section showed however, this is not quite the case when strategic miners can perform a selfish mining attack.

The genius of Bitcoin was to design a mechanism to decentralize the upkeep of a distributed ledger. But "decentralization" is a multifaceted word, as Vitalik Buterin points out , so let's disambiguate some of its meanings.

The kind of decentralization we talked about in Section has more to do with the political decentralization in Vitalik's post: who are the strategic entities engaged in the game? Who has agency?

Following our mental map of Section , a "master puppeteer" can efficiently maintain a shared ledger by simply centralizing the decision-making to itself, where only it can write to the ledger. Of course, that is not desirable since it violates the very reason why Bitcoin was created in the first place, to decentralize agency among many politically separated entities.

On the other hand, at "anarchy", everyone could add to the ledger, without any care for its consistency (meaning everyone sees the same transactions) or its integrity (meaning all transactions are valid). This is a very inefficient outcome. So without a well-designed protocol, the shared ledger could not achieve logical centralization, which Vitalik describes as all agents maintaining one canonical version of the ledger.

The Bitcoin game is the mechanism that leads to efficiency, although, as we have seen in Section , it may not be optimal in all cases .

There is another way in which Price of Anarchy thinking is useful. Assume the game now is that of many agents engaged in mining and the upkeep of a shared ledger. What is the optimal state for a master puppeteer who could control each and every miner? Given a fixed budget of computing power, the puppeteer might prefer that no one miner becomes too powerful, i.e., computing power is well-distributed among miners. This is the ideal of decentralization, as imagined where agents can participate in the mining with their phones, consumer laptops or other small devices .

But of course, just as it is not possible to ask drivers in the slow link of Pigou to remain in their lane at optimum, decentralized miners start aggregating due to economies of scale. Decentralization dynamics lead to concentration of the mining power in the hands of a few entities, a somewhat paradoxical result. Price of Anarchy asks how much is lost to this decentralization, and what are the mechanisms that correct for it.

The celebration of an idea is as much the occasion to appreciate how far it has come as it is to chart a course for where the idea should go. This point was made by Christos Papadimitriou in his opening lecture on July 2nd, to underline that the Internet evolved in some parts to be everything early researchers thought it wouldn't be.

The Internet has become a plantation where the cash crop is data.

Overlooking its achievements however would be like throwing the baby out with the bathwater. Price of anarchy, algorithmic game theory likewise are not settled matters, but vibrant, topical research. I hope this essay paints a portrait of blockchains as natural applications for these concepts, and the chance to fully answer the question Christos ended his talk with:

What kind of society do we want?