A beautiful mind implemented in php

If anybody saw the film A beautiful mind he may wonder what exactly makes John Forbes Nash so special?

A_Beautiful_Mind_Poster

In 1994, he received the Nobel Prize for around 25 lines that he had written in pretty much plain English in 1950:

EQUILIBRIUM POINTS IN N-PERSON GAMES

They did not give Nash the Nobel prize for mathematics, because there is no Nobel prize for mathematics (only a “Fields medal”). Therefore, they reassigned his theorem to the field of economics, even though it is equally much used in biology or physics. In reality, it is a mathematical theorem, pretty much unrelated to economics.

His original explanation re-invents the entire field of game theory. There is before, and there is after Nash.

How does it work?

There are n=2,3,4,5, … players, who are supposed to decide what move they will make next. They can choose amongst different moves. We could simplify – but this is not required – and say that players can choose from m=1,2,3,4,5, … the same choices.

The strategy-product space, consists of every possible combination of moves that the players can make. In the simplified case, the strategy-product space would consist of m^n  n-tuples.

As an example, if we have 5 players and 7 choices, we would have a total of 7^5=16807 different 5-tuples. So, one of these 5-tuples would be (4,2,5,5,7), meaning that player1 chooses move4, player2 chooses move2, player3 chooses move5, player4 chooses move5, and player5 chooses move7.

The Nash theorem is a statement about the complete set of these n-tuples.

Imagine that we have a payoff function, that says how much each player gets paid in a particular n-tuple. For example, in the 5-tuple (4,2,5,5,7) the payoff tuple could be (123,12,99,45,1).

Let’s now look at what each player would do, if he knew upfront what the payoff tuple would be, and let only him make another choice. What would he do? Well, he would obviously try to change his choice in order to receive a higher payoff. This is called a countering n-tuple. With 5 players we have 5 countering 5-tuples.

For our example, for our 5-tuple (4,2,5,5,7), the set of countering 5-tuples could be {(6,2,5,5,7), (4,8,5,5,7), (4,2,1,5,7), (4,2,5,7,7), (4,2,5,5,2) }.

Now comes the surprising claim. Nash discovered that there must be an n-tuple for which the set of countering n-tuples contains that very n-tuple. This n-tuple is called the self-countering n-tuple.

This means that if you ask the players to make another choice, none of them will. They will just play exactly again what they would play without knowing what the other players would play. In other words, it does matter to them what the other players will play. If they know what the self-countering n-tuple is, they will jump into that position, assuming the other players will also do what is best for them, and also jump into that equilibrium.

This is the inevitable result of Kakutani’s fixed point theorem.

The strategy-product space is non-empty, compact, and convex, meaning that the number combinations of player choices is finite and that all possible combinations are allowed, while the computation of countering n-tuples itself is a mapping of this strategy-product space onto “combinations” of itself. Therefore, according to Kakutani, one such n-tuple will be projected onto itself.

The existence of such self-countering n-tuple is certainly one of the top five mathematical discoveries in the 20th century. It is a beautiful result in higher-order set theory.

I have written a PHP program to illustrate the Nash theorem.

There are other programs like Gambit who also allow for exploring a game’s strategy-product space and to hunt for the self-countering n-tuple.

Gambit may have two weaknesses. First, it does not allow to formally segment the strategy space into subdivisions that can be forked off to different computing cores. In other words, in Gambit you cannot enlist an armada of cloud-based devices to engage in larger-scale number crunching. It all needs to be solved by one CPU or at least by one computer.

Secondly, Gambit requires you to provide a payoff matrix, instead of allowing you to specify an arbitrary payoff function.

These weaknesses potentially impose severe limitations on Gambit’s usefulness. I have specifically paid attention to these issues in my own implementation.

Advertisements

Published by

eriksank

I mostly work on an alternative bitcoin marketplace -and exchange applications. I am sometimes available for new commercial projects but rather unlikely right now.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s