FindTreeGameStrategies

FindTreeGameStrategies[tgame]

finds an optimal strategy profile for the TreeGame tgame.

Details and Options

  • FindTreeGameStrategies is also known as subgame perfect equilibria (SPE).
  • A tree game strategy profile is a set of probability distributions specifying the behavior of any player at any given action node.
  • To specify any action node, use a list of the choices made to reach it, e.g. {1} for taking the first action, {2,1} for taking the second action, then the first action, {} for the initial (root) action node.
  • A subgame perfect equilibrium is defined as a tree game strategy profile where no player can improve their payoff by changing only one action's probability distribution.
  • For a TreeGame, FindTreeGameStrategies will attempt to find a mutually optimal set of strategies for all the players in a game.
  • A tree game strategy profile <|…,playeri<|ni,1pri,1,…,ni,mipri,mi|>,…|> specifies the action probabilities pri,j for playeri in action node ni,j for playeri.
  • For example, the strategy <|"A" <|{} {0.7, 0.3}|>, "B" <|{2} {0.4, 0.6}|>|> <|"A" <|{} {0.7, 0.3}|>, "B" <|{2} {0.4, 0.6}|>|> may be expressed as follows: a higher probability for the first choice for player "A", and a higher probability for the second choice for player "B".

Examples

open allclose all

Basic Examples  (4)

Find the optimal strategies in the Tree Matching Pennies game:

Find the optimal strategies in the Revolution game:

Visualize the strategy:

Find the optimal strategies in the Escalation game:

The first action of the Escalation game is based on probabilities, thus strategies are considered for each choice:

Generate a TreeGame:

Find all subgame perfect equilibria:

This is more easily visualized as a graph:

Scope  (3)

Find the optimal strategies in the Entry game:

Consider an Ultimatum game:

Find the optimal strategies in the game:

Determine to which actions this corresponds:

Find the optimal strategies in the sequential form of the Matching Pennies game:

Applications  (6)

Social Games  (2)

The Centipede game has two players alternate in making decisions. At each turn, a player can choose between going "down" and ending the game or going "across" and continuing it (except at the last node where going "across" also ends the game). The longer the game goes on, the higher the total payoff. However, a player who ends the game early will get a larger share. Here is one formulation of the problem:

Find the optimal strategies in this game:

As can be seen in the solution game tree, the game-theoretic best solution at any step is to end the game early:

The tree game of the Matching Pennies game is a game where each of two people chooses either Head or Tail. If the choices differ, person 1 pays person 2 a dollar; if they are the same, person 2 pays person 1 a dollar. Generate a tree game of the Matching Pennies game:

Find the optimal game strategies in this game:

Due to the sequential nature of this game, the second player has the advantage of choosing the best outcome depending on the choice of the first player. As a result, it does not matter what the first player chooses, as the {-1,1} payoff is guaranteed:

Recreational Games  (2)

Rock Paper Scissors is a zero-sum game, where either one player wins and the other loses, or there is a tie. Generate the tree version of this game, where the second player can choose an action considering the action of the first player:

Clearly, in the case of the tree game of Rock Paper Scissors, the second player can always choose the best action; thus the first player is at a disadvantage by playing first. Find the best game strategies:

Consider the game of tic-tac-toe as a three-by-three matrix where 1 represents "X", represents "O", and 0 represents empty space:

Consider a partially completed game of tic-tac-toe:

Form the TreeGame based on it:

Visualize the optimal strategies:

Historical Games  (2)

The Revolution game is as follows. A colony has the choice to either rebel of concede to the status quo. The country can either grant independence or suppress the rebellion. If the colony concedes to the status quo, the country can either tax or not tax the colony. This game is usually studied in cases where the payoffs for the suppressed rebellion are unknown. Visualize this game:

Solve the game:

The Naval Deployment Game is an extension of the Battle of Bismarck game to an army that flees and another that is pursuing:

Find the subgame perfect equilibria:

Neat Examples  (1)

In the Rainbow Warship game, there are two players: the oil company (player 1) and the environmental activists (player 2). The oil company has a single oil-harvesting platform, movable over three small contiguous regions. Each area in the ocean has a different amount of oil that can be harvested illegally every night. The activists have to catch the oil company in the act to prove the harvesting to win and end the game. They can only launch one transmitter per day, which covers one region. Input a Rainbow Warship game of three cells (left, middle, right):

Visualize the game using TreeGamePlot:

Ignoring the information sets, find optimal strategies for this game:

This is more easily visualized using TreeGamePlot:

Wolfram Research (2025), FindTreeGameStrategies, Wolfram Language function, https://reference.wolfram.com/language/ref/FindTreeGameStrategies.html.

Text

Wolfram Research (2025), FindTreeGameStrategies, Wolfram Language function, https://reference.wolfram.com/language/ref/FindTreeGameStrategies.html.

CMS

Wolfram Language. 2025. "FindTreeGameStrategies." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/FindTreeGameStrategies.html.

APA

Wolfram Language. (2025). FindTreeGameStrategies. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/FindTreeGameStrategies.html

BibTeX

@misc{reference.wolfram_2024_findtreegamestrategies, author="Wolfram Research", title="{FindTreeGameStrategies}", year="2025", howpublished="\url{https://reference.wolfram.com/language/ref/FindTreeGameStrategies.html}", note=[Accessed: 15-January-2025 ]}

BibLaTeX

@online{reference.wolfram_2024_findtreegamestrategies, organization={Wolfram Research}, title={FindTreeGameStrategies}, year={2025}, url={https://reference.wolfram.com/language/ref/FindTreeGameStrategies.html}, note=[Accessed: 15-January-2025 ]}