April 19, 2013
Nash games describe a branch of game theory where two evenly matched players compete to each minimize an objective function by choosing from a fixed set of input values.
Suppose Player 1 has one control variable , which can take on values or , , or . Likewise Player 2 has one control variable , which can take on values , , or . The objective functions for players 1 and 2 are and , respectively. The game below shows the values of the objective functions for each combination of , .
So in this example and . In most games both players attempt to minimize their respective object functions. A Nash solution is some such that both of these relationships are true:
Where is the set of all possible values of and is the set of all possible values of . In other words, if player 2 chooses a certain value of , player 1 will choose the least value of in the corresponding column.
The game play might proceed like this:
- Player 2 choose , so player 1 chooses
- Player 2 then reacts by choosing , so player 1 changes to
- Player 2 is unwilling to change, since does not have any values for lower than 1.2
The game has reached a point where neither player will change their input. This is called the Nash equilibrium. We say that is a Nash solution.
We can place any game into one of the following three categories:
- Games with no Nash solutions
- Games with exactly one Nash solution
- Games with more than one Nash solution
It turns out that we can categorize games this way without knowing the objective functions and . We need to know only the least value for in each column, and the least value for in each row. Since the players are attempting to minimize their objective functions, the other values don’t matter. If we represent the least value of in each column and the least value of in each row with a 1, and make the other values 0, the game above looks like this:
Then any where and is a Nash solution. This game has a single Nash solution at . So no matter which player starts the game, and which input that player initially chooses, the game will always end with player 1 using value and player 2 using value .
For a game of a given size, there are a finite number of possible outcomes. So it is possible to write an algorithm to categorize all of the possible games of a given size into one of the three categories above.
This algorithm is interesting to use in the study of scalability of an implementation to multiple processors. It is not too difficult to write an implementation which is CPU-bound and does not have any real data sharing. That is, the categorization of each game is independent of all other games. Therefore, it should be possible to implement this algorithm so that it scales linearly to any number of processors.