Game Theory

In light of our current and forthcoming educational Unity mobile game releases (see Fuildmaze in the app store!) we are going to review the fundamentals of game theory.

Game theory is the science of multi-agent decision making. It uses mathematics to study the strategic interaction of rational decision-makers. Game theory has social, logical, and computer science applications.

Sequential games can be organized into two categories, those with perfect information (e.g., checkers) and those with imperfect information (e.g., bridge). A game of perfect information requires that all players know the strategies and payoffs available to the other players, but also the actions or moves everyone previously made.

Whereas, a game of complete information requires only that players know the strategies and payoffs available to other players. A game of incomplete information becomes a game of imperfect information when one or more players makes a move by nature, or one without a stake in a strategic outcome, effectively generating randomness.

Chess is a combinatorial game of perfect information. The combinatorial subcategory of games denotes those in which the optimal strategy is based on a myriad of possible moves. A provable optimal unifying strategy for chess has not been found. A novice chess player may experience information paralysis or a data overload due to the game’s combinatorial nature.

Alpha-beta pruning is a type of computer program that uses a search algorithm. The program stops evaluating a move when it is found to be worse than one that was examined before. Artificial neural networks train through reinforcement learning to make games like chess more computationally tractable.

A game is cooperative if players can form alliances that are externally enforced. Games in which players can form agreements but only through self-enforcement, (e.g., a credible threat) are non-cooperative. Cooperative games can be studied with coalition forming predictions, joint group actions, and collective payoffs.

The Prisoner’s Dilemma is a game that proves why two rational individuals acting in their self-interest may not cooperate to achieve an optimal outcome. This theoretical game is played as follows:

Two friends are arrested for a crime. They are held in solitary cells without means of communicating with one another. The prosecutors do not have enough evidence to imprison both people on the principal charge, but they can both be imprisoned for lesser charges.

Each person is offered the same bargain, in their cell, at the same time. They each are given the option to cooperate by remaining silent or to betray and testify that the other person committed the crime. In this game there are four possible outcomes*:

  • A and B both betray each other, and each of them serves two years in prison.
  • A betrays B, but B remains silent. A is freed, while B serves three years in prison.
  • A remains silent, but B betrays A. A serves three years in prison, while B will be freed.
  • A and B both remain silent. Both of them will serve only one year in prison for the lesser charge.

It is implied that the decision to betray or remain silent will not affect a player’s reputation or well being in the future. Imagine there are no repercussions outside of the possible prison sentences.

Below is the Payoff Matrix for Prisoner’s Dilemma:

We can see from this payoff matrix that to achieve the optimal outcome one player must betray the other. That means that two purely rational players will betray each other. Though there is a slight advantage in both players remaining silent (a shorter prison sentence), the risk of your partner defecting is very high.

The Prisoner’s dilemma is a non-cooperative game, as the players have no information about the other player’s respective choice, so there is no means of an agreement, but even if they could agree, there are no external enforcement agent binding players to their agreement.

The Prisoner’s Dilemma is a game of complete information in that each knows the payoffs and strategies available to the other, but also one of imperfect information, because, at the decisive moment, one does not know whether their co-player has kept silent or betrayed.

Leave a Reply