The Traveler’s Dilemma

When playing this simple game, people consistently reject the rational choice. In fact, by acting illogically, they end up reaping a larger reward–an outcome that demands a new kind of for­mal reasoning. Explanation by Kaushik Basu. I guess most people don’t understand Nash equilibria IRL.

Abstract Strategy Games

My recent post about the GIPF project got me thinking about starting a series of posts about this category of games. So, here we go.

Game theory

Game theory is a branch of mathematics that deals with the analysis of games (i.e., situations involving parties with conflicting interests). In addition to the mathematical elegance and complete “solution” which is possible for simple games, the principles of game theory also find applications to complicated games such as cards, checkers, and chess, as well as real-world problems as diverse as economics, property division, politics, and warfare.

Game theory has two distinct branches: combinatorial game theory and classical game theory. In classical game theory, players move, bet, or strategize simultaneously. Both hidden information and chance elements are frequent features in this branch of game theory. Combinatorial games have no chance element, and players take turns.

Abstract strategy games

The analysis of a abstract strategy game tends to fall under combinatorial game theory (CGT). To qualify as an abstract strategy game several conditions need to be met:

• There are two players (usually named Left and Right in theoretical analysis)
• Players alternate taking turns
• There is no hidden information (such as cards or tiles that a player hides)
• The game is deterministic (no dice or shuffled cards)
• Every game must end in a finite number of moves
• As soon as there are no legal moves left for a player, the game ends, and that player loses

Let’s have a closer look at these conditions.

Using only 2 players does not limit the analysis of games. If we extend the analysis to n players than the compexity just increases exponentially.

Taking turns. Games are either simultaneous or sequential. Simultaneous games are games where both players move simultaneously, or if they do not move simultaneously, the later players are unaware of the earlier players’ actions (making them effectively simultaneous). Sequential games (or dynamic games) are games where later players have some knowledge about earlier actions. This need not be perfect knowledge about every action of earlier players; it might be very little information. For instance, a player may know that an earlier player did not perform one particular action, while he does not know which of the other available actions the first player actually performed. CGT analysis sequential games. Strategy games with hidden information, bluffing or simultaneous-move elements are better served by Von Neumann-Morgenstern (classical) game theory, while those with a component of luck may require probability theory.

An important subset of sequential games consists of games of perfect information. A game is one of perfect information if all players know the moves previously made by all other players. Thus, only sequential games can be games of perfect information, since in simultaneous games not every player knows the actions of the others.
Perfect information is often confused with complete information, which is a similar concept. Complete information requires that every player knows the strategies and payoffs (rewards) of the other players but not necessarily the actions. Or, you might know the rules of the game but not what action the other player is taking. In this case we have complete but imperfect information. Examples of incomplete but perfect information are more difficult. Suppose you are playing a game of chess against an opponent who will be paid some substantial amount of money if a particular event happens (an arrangement of pieces, for instance), but you do not know what the event is. In this case you have perfect information, since you know what each move of the opponent is. However, since you do not know the payoff function of the other player it is a game of incomplete information.
Go and chess are examples of perfect information games. The card game bridge is an example of a game with imperfect information because some cards are hidden from the players.

Deterministic means there is no luck involved in the game.

Finally abstract strategy games are so-called zero-sum games. It is so named because when the total gains of the participants are added up, and the total losses are subtracted, they will sum to zero. Chess and Go are examples of a zero-sum game: it is impossible for both players to win. Or, a game ends with one player winning and one player losing. Zero-sum can be thought of more generally as constant sum where the benefits and losses to all players sum to the same value. Cutting a cake is zero- or constant-sum because taking a larger piece reduces the amount of cake available for others.

Know also that while many of us use the term ‘game’ to refer to things like “chess”, “Go” or “bridge”, CGT also uses the term game to refer to positions, a specific situation of the game (a bit confusing…, I know).

What next ?

So, now that we have defined abstract strategy games, we can start analysing them. Follow-up posts will be a combination of theory and practice. I will try to provide more insight in the theoretical concepts and results of CGT, but I will also post about real life abstract strategy games like Xiangqi (Chinese Chess), “n-in-a-row” games, go, hex and many others. And why not, the occasional ‘paper and pencil game’.

The Mathematics of Strategy

What does it mean to behave rationally? This question sounds like a problem for philosophers. Yet mathematicians also have something to say about it. In the last few decades, game theory—the mathematical study of strategies and decision-making—has shed crucial light on the nature of rational behavior.

In 1950, a young Princeton mathematics graduate student named John Nash published a two-page note in PNAS and his idea, the Nash equilibrium, has become the cornerstone of game theory (1). The Nash equilibrium abstracts the way we reason about strategies in a competitive situation: it codifies “I think he will do X because he thinks I will do Y, so I should do Z….”

The Nash equilibrium concept has become a benchmark by which economists and other scientists measure both rational behavior and the extent to which humans depart from pure rationality. Over the years, this concept has illuminated questions in economics, psychology, and even biology. In 1994, it earned Nash the Nobel prize in economics.

Further reading

• Introduction to the Nash Equilibrium at Wikipedia
• An overview at PNAS (intermediate level)
• The original article “Equilibrium Points in N-person Games“, Proceedings of the National Academy of Sciences 36 (1950), pp 48–49 (advanced)
• Nash’s home page at Princeton

The Prisoner’s Dilemma

Nigel and Amanda have been arrested for a joint crime of serious fraud. Each is interviewed separately and given the following alternatives:

• First, if they say nothing, the court has enough evidence to sentence them both to a year’s imprisonment.
• Secondly, if either Nigel or Amanda alone confesses, he or she is likely to get only a three-month sentence but the partner could get up to ten years.
• Thirdly, if both confess, they are likely to get three years each.

What should Nigel and Amanda do ?

Let us look at Nigel’s dilemma. Should he confess in order to get the short sentence ? This is better than the year he would get for not confessing. There is however an even better reason for confessing. Suppose Nigel doesn’t confess but, unknown to him, Amanda does confess. Then Nigel ends up with the long sentence (10 years). Better than this is to confess and to get no more than three years: this is the safest strategy.

Amanda is in the same dilemma. The result is simple. When both prisoners act selfishly by confessing, they both end up getting three years. Only when they collude they end up getting each one year.

Of course the police knows this and will do their best to prevent any collusion. They will keep Nigel and Amanda in separate cells and try to persuade each of them that the other is bound to confess.

Conclusion: by attempting independently to choose the best strategy for whatever the other is likely to do, each party ends up in a worse position than if they had co-operated. By eliminating the co-operation possibility, the police gets the bad guys…