Basic Concepts for Game Theory

Introduction

The past decade has witnessed a huge explosion of interest in issues that intersect network design and game theory. In recent times, algorithmic game theory has been one of the most high-profile growth areas in theoretical computer science and telecommunication (Wooldridge, 2012). Game theory is the mathematical theory of interactions between self-interested agents. In particular, it focuses on decision making in settings where each player’s decision can influence the outcomes of other players. In such settings, each player must consider how each other player will act in order to make an optimal choice. In game theory, ‘game’ means an abstract mathematical model of a multi-agent decision making setting (Wooldridge, 2012).

In game theory, a modeling situation is defined as a game to predict the outcome of complex interactions among entities. Usually, a normal game form () can be formulated with three parameters: the players, a strategy or action space for each player (i.e., strategy set), and consequences of the actions (i.e., a set of payoffs). Mathematically, can be defined as ∈ {, {S_i}_i∈, {u_i}_i∈}.

• •

   is the finite set of players.

• •

  S_i is the set of strategies with player i.

• •

  The utility function of player i (u_i) can be represented as the degree of satisfaction received by player i as the function of the strategy it chooses, s_i, and the action of other players:.

Players are decision makers, who choose how they act. A player, such as a company, a nation, a wireless node, or even a biological species, may be independent and has to make specific actions that have mutual, possibly conflicting, consequences. Usually, players are assumed to be individually rational and act in a rational manner and try to ensure the best possible consequence according to their preferences. Strategy set is the collection of various actions available to the player. Each player has a number of possible actions and can choose an action to determine the resulting outcome of the game. Any kind of action of a player should be expressed with a suitable utility function, which maps every action to a real number. A payoff (or utility) function quantifies the satisfaction that a player can get from a particular action. Usually, utility of a player corresponds to the received payment minus the incurred cost. Based on the payoff, the outcome to the different players can be evaluated. Therefore, individual decision makers (i.e., players) try to find the best actions.

The most classic game theory example is the Prisoner's Dilemma (“Prisoner's dilemma,” n.d.). The prisoner's dilemma is a canonical example of a game analyzed in game theory that shows why two individuals might not cooperate, even if it appears that it is in their best interests to do so. To put it simply, two prisoners are getting charged for a crime that they most likely did together, but the police aren't sure. So, they set up a deal where they question each suspect privately, and they can choose to cooperate (i.e., claim they did not commit the crime) or betray (i.e., admit to committing the crime). The punishments are as follows:

• 1.

  If one prisoner cooperates and the other betrays, the betrayer can be free while the cooperator must spend ten years in prison.

• 2.

  If both prisoners cooperate, the police don't want to risk wasting the lives of two innocent men, so give them each one year sentence.

• 3.

  If both prisoners betray, they will be punished for their crime with a three year sentence.

If we were to draw a matrix to represent the prisoners' payoffs, it would resemble Table 1.