Module 5

​

Competitive game and Repeated Games

BEARYS INSTITUTE OF TECHNOLOGY

Strictly competitive game and maxminimization

• A strictly competitive game is a type of two-person game where the payoff of one player is the negative of the payoff of the other player, meaning one player's gain is the other player's loss. 
• Maximinization is a strategy where a player aims to maximize their minimum potential payoff, considering the worst-case scenario, by choosing the action that guarantees the highest minimum payoff. 

BEARYS INSTITUTE OF TECHNOLOGY

• In a strictly competitive game, the sum of payoffs for both players is always zero. 
• This means there's a direct conflict between the players; what's good for one is bad for the other. 
• Zero-sum games are a specific type of strictly competitive game where the payoffs are precisely zero. 
• Strictly competitive games can be represented by a payoff matrix where the entries are the payoffs for both players. 
• The classic example is rock-paper-scissors, where one player's win is directly the other's loss. 

​

BEARYS INSTITUTE OF TECHNOLOGY

• A Strictly Competitive Game is a type of two-player zero-sum game. In these games:
• One player's gain is exactly the other player's loss.
• The sum of their payoffs is always zero for every possible outcome.
• Players have opposing interests.

​

BEARYS INSTITUTE OF TECHNOLOGY

BEARYS INSTITUTE OF TECHNOLOGY

Examples:

• Chess (if we assign +1 for a win and -1 for a loss)
• Matching coins
• Rock-paper-scissors

• A strictly competitive game is a strategic game in which there are two players, whose preferences are diametrically opposed: whenever one player prefers some outcome a to another outcome b, the other players prefers b to a. Assume for convenience that the players’ names are “1” and “2”. If we restrict attention to pure strategies then we have the following definition.

BEARYS INSTITUTE OF TECHNOLOGY

Maximinization Explained as

Minimizing the worst-case scenario:

A player using maximinization focuses on finding the action that gives them the best possible outcome, even in the event that the opponent makes the least favorable choice. 

Choosing the most guaranteed payoff:

Instead of aiming for the highest potential payoff, a player with a maximin strategy selects the action that provides the greatest minimum payoff

​

BEARYS INSTITUTE OF TECHNOLOGY

BEARYS INSTITUTE OF TECHNOLOGY

Repeated Games�

• Repeated games are a type of game in game theory where the same basic game (usually a strategic form or normal form game) is played multiple times by the same players.
• Types of Repeated Games:
• Finite Repeated Games:
• The game is played a fixed number of times (e.g., 10 rounds).
• Players know when the game will end.
• Infinitely Repeated Games:
• The game goes on forever, or players don't know when it will end.
• Future payoffs are discounted (players care less about future rewards).

​

BEARYS INSTITUTE OF TECHNOLOGY

• A repeated game is an extensive game with perfect information and simultaneous moves. A history is a sequence of action profiles in the strategic game. After every nonterminal history, every player i chooses an action from the set of actions available to her in the strategic game.

BEARYS INSTITUTE OF TECHNOLOGY

Key terms

BEARYS INSTITUTE OF TECHNOLOGY

• Repeated games allow:
• Trust and cooperation to emerge, even in competitive settings like the Prisoner's Dilemma.
• Punishment and reward strategies (like Tit-for-Tat or Grim Trigger) to enforce good behavior.
• Players to build a reputation or retaliate against bad behavior.

Repeated games are about playing the same game multiple times, allowing strategies to depend on past actions. This opens the door for cooperation, punishment, and long-term strategy, which is not possible in one-shot games.

BEARYS INSTITUTE OF TECHNOLOGY

• The basic idea in the theory is that a player may be deterred from exploiting her short-term advantage by the “threat” of “punishment” that reduces her long-term payoff. Suppose, for example, that two people are involved repeatedly in an inter action for which the short-term incentives are captured by the Prisoner’s Dilemma with payoffs as in Figure 389.1. Think of C as “cooperation” and D as“defection”.

BEARYS INSTITUTE OF TECHNOLOGY

• The basic idea in the theory is that a player may be deterred from exploiting her short-term advantage by the “threat” of “punishment” that reduces her long-term payoff. Suppose, for example, that two people are involved repeatedly in an interaction for which the short-term incentives are captured by the Prisoner’s Dilemma , with payoffs as in Figure 389.1 below. Think of C as “cooperation” and D as“defection”

BEARYS INSTITUTE OF TECHNOLOGY

Strategies

BEARYS INSTITUTE OF TECHNOLOGY

Strategies

BEARYS INSTITUTE OF TECHNOLOGY

Nash equilibria of the infinitely repeated Prisoner’s Dilemma

• Tit-for-tat

​

BEARYS INSTITUTE OF TECHNOLOGY

Given a Following Prisoners Dilemma

Formula�

BEARYS INSTITUTE OF TECHNOLOGY

Each player i has a payoff function ui for the strategic game and a discount factor δ between 0 and 1 such that she evaluates the sequence (a1,a2,...,aT) of outcomes of the strategic game by the sum

if the two sequences of outcomes

• In an infinitely repeated setting, mutual cooperation (Quiet, Quiet) may be sustained if the players value future payoffs enough — i.e., they are sufficiently patient. This is evaluated using the discount factor δ∈(0,1), which represents how much future payoffs are valued.
• Payoffs:

If both players cooperate forever (Quiet, Quiet):

​

​

BEARYS INSTITUTE OF TECHNOLOGY

• If a player deviates (Confess) once and the other retaliates with Tit-for-Tat:
• First round (deviation): 3
• Subsequent rounds: 1 forever

​

​

Condition for Cooperation to be Nash Equilibrium:

• To prevent deviation:

​

BEARYS INSTITUTE OF TECHNOLOGY

If δ≥0.5 Tit-for-Tat can sustain cooperation as a Subgame Perfect Nash Equilibrium

Grim trigger strategies

• The Grim Trigger Strategy is a strategy used in repeated games, particularly in Prisoner's Dilemma-type games
• A grim trigger strategy is a type of punishment strategy used to enforce cooperation in repeated games.

Under this strategy:

• A player starts by cooperating.
• They continue cooperating as long as the other player(s) do the same.
• If any player defects (i.e., deviates from cooperation even once), the grim trigger player will punish the defector by permanently defecting for the rest of the game.

​

BEARYS INSTITUTE OF TECHNOLOGY

Grim trigger strategies

• Suppose that the outcome in the first period is (C, D). Is it optimal for each player to subsequently adhere to the grim trigger strategy, given that the other player does so? In particular, is it optimal for player 1 to carry out the punishment that the grim trigger strategy prescribes? If both players adhere to the strategy then player 1 chooses D in every subsequent period while player2 chooses C in period 2 and then D subsequently, so that the sequence of outcomes in the subgame following the history (C, D)is ((D,C),(D, D),(D, D),...), yielding player 1 a discounted average payoff of

​

BEARYS INSTITUTE OF TECHNOLOGY

• If player 1 refrains from punishing player 2 for her lapse, and simply chooses C in every subsequent period, then the outcome in period 2 and subsequently is (C,C), so that the sequence of outcomes in the game yields player 1 a discounted average payoff of 2.
• If δ > 1/2 then 2 > 3−2δ, so that player 1 prefers not to punish player2 for a deviation, and hence the strategy pair in which each player uses the grim trigger strategy is not a subgame perfect equilibrium.
• The strategy pair in which each player uses the grim trigger strategy is not a subgame perfect equilibrium for any value of δ, for the following reason.
• If player 1 adheres to the grim trigger strategy, then in the subgame following the outcome (C,D), player 2 prefers to choose D in period 2 and subsequently, regardless of the value of δ

BEARYS INSTITUTE OF TECHNOLOGY

BEARYS INSTITUTE OF TECHNOLOGY

• If both stay Quiet, they each get 2 (cooperation).
• If one Confesses and the other stays Quiet, the confessor gets 3 (defection reward), the quiet one gets 0 (sucker's payoff).
• If both Confess, they each get 1.

The Grim Trigger Strategy says:

Start by cooperating (Quiet). Continue cooperating unless the other player defects (Confess).

If they ever defect, punish them forever by always defecting from then on.

BEARYS INSTITUTE OF TECHNOLOGY

• It works if both players care about the long-term rewards over short-term gains

BEARYS INSTITUTE OF TECHNOLOGY

BEARYS INSTITUTE OF TECHNOLOGY