Game Theory is based largely on the idea of John von Neumann. von Neumann wrote a book explaining his ideas in a publication entitled "Theory of Games and Economic Behaviour" which was co-authored with Oskar Morgernsten in 1934, shortly after he re-located to the United States. For more information on him I recommend reading Teiresias's excellent node, linked above.

Game Theory is an interesting branch of mathematics that attempts to study the decision making process of two or more players in a game. In this case a game is a conflict situation where the players are either attemping to fulfil different, mutually exclusive, objectives on the same system, or they are playing for control of a finite resource. Game Theory attempts to provide a mathematical structure for selecting an Optimum Strategy in the face of an opponent who will also be trying to play to an Optimum Strategy.

In Game Theory there are certain assumptions that must be made:

  1. Each player has two or more choices at each stage of the game.
  2. Every possible combination of plays leads to a defined end-state, either win, lose or draw.
  3. Every end-state results in a pre-defined payoff for each player (such as gaining control over a certain amount of a resource). A Zero-Sum game is when, at a given end-state, the sum total of the payoffs to all the players is zero (i.e. the winnings are equal to the loses).
  4. Each player has full knowledge of the game and all its possible end-states. This means that they know the payoffs both to themselves and their opponents at any given end-state.
  5. All decisions are rational. A player will always choose the option that would result in a greater payoff to himself.

The last two points limit (to an extent) the usefullness of Game Theory in terms of its application to real-life situations. They have, however, been used to do research in economics and psycology.

There are several different types of game, but the most commonly seen type of game is an NxM game. This is any game where the outcomes can be plotted onto a Matrix of dimentions N by M, where N and M represtent the number of options that each player has available to him at that point.

Two common examples of NxM games are 'The Prisoners Dilemma' and 'Matching Pennies'

The "Prisoners Dilemma" is a NxM game of dimentions 2x2. In its simplest form it works thus: There are two prisoners who have been arrested by the police. If neither of them admit to the crime then they will both walk free. If they both admit to the crime then they will each get a sentence of five years. If one of them admits to the crime and the other denys it then the one who admitted the crime gets three years and the one who denied it gets nine years. What is the optimal strategy that they should follow?

This is best represented as a table:

   | D | A |
  ----------     Where D = Deny, A = Admit
  D|0/0|9/5|     Outcomes are given as (A/B)
A ----------

From this you can easily see that while it is temping to deny the crime as this will give the greatest payoff, the strategy with the best payoff-to-risk ratio is for both sides to admit the crime. (Personal story - I played a game like this for a group of 10yr old kids. Even after playing five times niether side was willing to take the optimal strategy. Both sides kept playing the outcome where they both lost, rather than the less risky one where both sides would have won a little. This is why it doesn't work so well in real life)

The "Matching Pennies" game is apparently played by children. It is also a 2x2 games. Each player secretly turns a coin heads up or tails up. They then show the coins to each other. If they match then A has to pay B a penny. If they differ then B pays A a penny. This games continues untill they get bored.

As a table:

   | H  |  T |
  ------------     Where H = Heads, A = Tails
  H|-1/1|1/-1|     Outcomes are given as (A/B)
A ------------

From this it is easy to see that there is no optimal strategy. In the long run it is best to play completely randomly as this means that both sides should come out even. Given that long term strategy this becomes a zero sum game.

For more information about Game Theory is a good place to start.

A few more thoughts on game theory, intended to form an addition to elem_125's excellent write-up above.

It is important to understand that game theory applies beyond the bounds of what one would usually consider "games". Certainly game theory has something to say on games like Chess and Go, but it applies equally well to any system where parties are in potential competition. I say potential because game theory also handles ideas like the emergence of co-operation! You will perhaps now be getting a feeling for how broadly game theory is actually spread.

An example of a 'game theory' emerging in a situation which is certainly not considered a game by most affected would be in the recent firemen's strike here in the UK. This is certainly a game according to our earlier definition, having competing parties - firemen and the government - and a number of end results. Yet it is of the utmost seriousness! Note also that it needn't be a zero-sum 'game'; had it been resolved earlier, both parties might have come out of it better off. As it is, both parties will probably lose public favour.

It is these non-zero-sum games that most interested the great John Nash, subject of the film A Beautiful Mind. There's a fair amount about that great hero of game theory under his node, but within the topic of this one I'd like to point out just how far-reaching his ideas were. In nature, non-zero-sum games are just as common as zero-sum ones - unlike humanly constructed games, where we would usually consider it quite strange for both sides to lose! His work on Nash equilibrium had huge implications for an array of topics. To borrow a quote from that node, Nash equilibrium was described as "the most important idea in noncooperative game theory... whether analyzing election strategies, or causes of war."

That was the first point I wanted to make. Game theory is everywhere. It makes enough sweeping assumptions to satisfy any physicist, and yet it does have applications in the real world and provides us with much interesting mathematics to study.

The second thought that I think is important in relation to game theory is the idea of "solving" games. In this context, I use "game" to mean what is more traditionally considered a game - board games, card games et al. But to solve a game often has two meanings, and I will discuss both since they are both rather interesting.

Often we are satisfied that a game has been solved when a computer can be programmed to play it to a level comparable to the best humans. This is tricky for two reasons. Firstly, because people often find it difficult to articulate exactly what processes they use in choosing a next move, and this explicite explanation is obviously necessary when designing an algorithm. Also, a number of sub-concious checks are performed by humans that discard many theoretically possible moves without much consideration. These checks are more complex to translate to declarative heuristics.

A large number of games have been solved in this way. A simple example is chess. With Deeper Blue, a computer has finally beaten a Grand Master and the chess algorithm has been advanced to such a stage that it surpasses any human player. Quite how it got to that stage is a story in itself, and indeed Kasparov has claimed that the computer was given 'human assistance' at key points in the match. That's for another node, though.

On the other hand, there are games which have not been solved even in this fairly weak sense. Perhaps the classic example of this is Go. The best algorithms for Go can, I understand, still be soundly thrashed by a reasonably highly-ranked Go professional. There are a number of reasons for this weakness in the Go playing standards. As mentioned before, Go is often played on 'instinct' and players with much experience get a feel for good moves quite unconciously. Clearly, there is no such analogue when creating computer programs; further, such a player will find it hard to describe as a procedure the processes involved in selecting a good move. A furthur problem with Go is the fairly ill-defined goal. While the game is in motion, "Territory" is a rather fuzzy notion and, as any programmer will tell you, computers do not get on well with fuzziness. Chess, by constrast, has a very well defined goal - capture the king. Certainly, positional strength in chess is comparable in complexity to that of Go, but at least the end target in chess is somewhat better defined. Therefore chess lends itself, at least in this respect, to being made into a program - Go, however, does not. In addition, the space of possible outcomes is unimaginably large - a 19 x 19 board, with potentially hundreds of stones in play, cannot be over-run by brute processing power. Go does not succumb well to pure 'crunching power', which inevitably increases with each generation of computer - it needs a rather more subtle approach. If a Go program is to ever rival a professional human, many advances in our programming approach will have to come first.

Let us now look at the other sense in which a game is 'solved'. This sense is a much more rigorously defined one, and is therefore favoured by mathematicians, and it is also strongly related to Nash equilibrium. In this use, to solve a game means to define an algorithm that will play absolutely the best strategy all the time. This is often phrased as "an algorithm that cannot be beaten", and in a game devoid of probabilistic elements (as in chess) this is quite true. However, a perfect player of, to take an extreme example, Snakes and Ladders can certainly be beaten. That is not a reflection of the quality of the algorithm; it is an inherent flaw in trying to solve any game with random elements.

For most games, this is quite a huge undertaking. In the simple example of Tic Tac Toe, the space of possible outcomes is relatively small - but it is still a fairly difficult and certainly time-consuming task to devise a perfect strategy. Of course, Tic Tac Toe has long sinced been solved in this strictest of senses, but many other games - even those of perfect knowledge - have resisted attempts to do so.

Returning to the popular topic of chess, we are certainly nowhere near a perfect strategy. The space of possible outcomes is simply too large, and despite the smaller board, may be comparable to that of Go. There is still much argument among chess players as to the best first move, let alone the several hundred that frequently follow. Even simplified versions of chess - discounting complicating technicalities such as en passant and promotion of pieces - are far beyond the computative power available today. Such deep-rooted uncertainty as to 'best strategies' is undoubtedly part of the appeal of chess, and explains how professionals of similar skill can play in vastly different ways.

That said, other games have been solved. To give a recent example, scientists published just this year a solution to the African game Bantumi. This was done in what I consider to be a rather inelegant fashion - in short, the researchers compiled a 17GB database of all possible game scenarios and the best move to follow them. I don't doubt that creating a program to discover these 'best moves' required much skill and effort, but it is perhaps symptomatic of the future of mathematics - likewise the solution to the four colour map problem. Nevertheless, Bantumi has been solved and we know it is possible to create an unbeatable algorithm - genuinly unbeatable in this case, Bantumi being a game of perfect knowledge.

There is one final aspect to this game-solving business. As was recently published in the New Scientist, it has been mathematically proven that Tetris is a 'hard' game. That is to say, even knowing the pieces to be given in advance, there is no algorithm to play the game perfectly. Brings some respite to those of us whose Tetris skills leave much to be desired.

So there we have it. Games that can be solved - Bantumi. Games that can't be solved - Tetris. And finally, games which are as yet unallocated to either category - Chess.

I hope this has broadened your mind of the fascinating topic of game theory. That is all.

Well almost. A quick thanks to JerboaKolinowski, who raised some excellent points about my slightly unfair comparison between chess and Go. That probably arose since I am much less familiar with Go than chess, but I've tried to embrace his insight without having to completely re-write this whole node.

Log in or registerto write something here or to contact authors.