Nash Equilibrium and Graph Theory

Every once in awhile, there are really big ideas in academia, ideas that change the way we think about the world. Nash equilibrium is one of those ideas.

Equilibria

John Nash wrote about games where people make decisions based on the way they think other people will behave, eventually reaching an equilibrium where no individual can improve their own situation by changing. This equilibrium, however, does not mean that the entire group has achieved an optimal result.

For example, consider the famous “prisoner’s dilemma” where the police speak to two detainees separately. Each one is given two choices: (1) rat out your partner or (2) keep your mouth shut. If both keep their mouth shut, the two will each be locked up for a year. If both confess, they serve the full sentence of 10 years. However, if one confesses and the other stays quiet, the rat gets out while the other serves the full sentence.

While it’s clearly best all around if both of them clam up, each prisoner faces a situation that can only get better by ratting out his partner. The following diagram comes from the Economist:

20160820_ebc991

So imagine you’re prisoner A. You have no idea whether your partner will throw you under the bus or not. You should tell on him because there’s no possible way your situation could get worse. After all, if he told on you, you’re getting the same amount of time. But if he kept quiet, you just shaved a year off your sentence. Not too bad. Let’s just hope prisoner B doesn’t have a friend on the outside.

Harder Equilibria

The prisoner’s dilemma problem is an easy one to pick strategies on because it’s so simple. But most games in life are quite a bit harder.

Consider the traffic problem, for example. When you drive in a crowded area, you’re faced with a lot of choices. Do you execute a u-turn at a complicated intersection or pull into a parking lot before swinging around? How fast should you go? When do you change lanes in preparation for your exit? Each of these choices affects others around you, an observation that usually only becomes evident when an offender makes the selfish choice.

In recent years, algorithm experts have begun to classify these kinds of games in terms of their computational complexity. For example, Daskalakis, Fabrikant and Papadimitriou showed in 2006 that games like the prisoner’s dilemma and traffic navigation belong to a complexity class called PPAD-complete (Polynomial Parity Arguments on Directed graphs), a subset of class NP (Nondeterministic Polynomial). In less technical terms, this means that finding an equilibrium gets exponentially harder as you add more elements, choices, and/or participants.

To help illustrate just how hard NP-class problems are, consider the game of guessing my one-digit PIN. It wouldn’t take you too long, since you’ve only have to try ten possibilities. A two-digit PIN isn’t much harder – with enough effort, you’d probably guess it. But good luck guessing a 10-digit PIN. It’s got 10 billion possibilities. NP-class problems require a lot of computation in order to reach an equilibrium. When you’ve got to decide between speed, fuel economy, and the chances of that semi braking for you, you had better hope everybody is choosing compatible equilibria.

Enter Graph Theory

But games are really boring without other players. And that’s where graph theory comes in. Graph theory is a way of notating the world in terms of nodes and connections, like in the illustration below. graph-theory

Now imagine that each one of those blue nodes is a person and each connecting line is some relationship that people have with one another. To go back to the traffic example, you can see the cars immediately surrounding you, but not necessarily all the same cars that your neighbors can see. If a semi three lanes over decides to swerve, you’ll need to get that information transmitted along to you through your neighbors.

This is where things get really cool.

In June, Davoud Taghawi-Nejad and Vipin P. Veetil wrote a paper called The Complexity of Coordination, in which they used a graph to propagate information across a network. Their model allows each person (or node) to look at its neighbors after some amount of time and change its state to match popular consent surrounding them. Starting from totally random states, they showed that the graph would very quickly reach equilibrium. Here’s an example

knip1

Imagine that you’re the little gray node in the middle. What color should you choose to be? Certainly not purple or brown, since nobody else is choosing that. But green and yellow seem like good choices. Let’s make that decision and wait for a few moments.

knip2

Whoops. Seems as though your neighbors are leaning toward blue now. Let’s make that switch and wait again.

knip3

This looks much better. And sure enough, the whole graph is about to reach equilibrium, not just our little section in the middle

knip4

Run this experiment over and over again and you’ll discover that time to convergence doesn’t increase exponentially when you add more states or nodes. This finding is big news! It shows that propagating the equilibrium across the graph only took polynomial time.

Limitations

Unfortunately, there are some pretty serious limitations to these findings. Although Taghawi-Nejad and Veetil have shown a network converging to equilibrium in polynomial time, that equilibrium may not necessarily represent a Nash equilibrium. Recall that in order to be a Nash equilibrium, each player must not be able to improve their situation by changing state/strategy. Another famous game theory problem helps illustrate this point.

The two-thirds problem is a contest which has been published in several major newspapers and magazines, including recently the New York Times. The game is simple. There are only three rules:

  • Each player is allowed only one guess
  • Each player may guess an integer 0-100 (inclusive)
  • Whichever player guesses closest to 2/3 of the average of all the guesses wins the prize

Seems simple, right? If the average of all the guesses is 100 (very unlikely), you’d need to guess 66 to win. If everybody guessed randomly, the average would be 50 and you’d need to guess 33 in order to win. Of course, most anybody could figure that out, and so you’ll need to guess even less in order to outsmart them. Of course, really smart people will also know this, so they’ll lowball their guesses as well. Play this game several times with a group of friends, and you’ll quickly see everybody’s guesses drop down to 0. That’s the Nash equilibrium!

Our graphs up above don’t do so well on this kind of a problem. Since they only seek to choose the most popular state of their neighbors, each node will finish in a state which is probably not the Nash equilibrium. In other words, if the network converges to everybody selecting the number 15, you should change your guess to 10 and ignore your neighbors.

Conclusion

Taghawi-Nejad and Veetil have undoubtedly broken some important ground on the computation of equilibria, especially when they concern complex games. However, their findings are limited to a very specific kind of game, a very small part of a large set. Nash’s theory refers to all games where individuals can’t improve their situation by changing away from equilibrium. This network model is limited to games where equilibrium and popularity are intertwined.

Leave a Reply

Your email address will not be published. Required fields are marked *