Problem 459639 · hard · Economics · Level 04 Strategy and Growth

Threats That Would Not Be Carried Out

sequential game · game tree · backward induction · subgame perfect equilibrium · recursion

In a sequential game the players move one after another, each seeing the earlier moves. It is drawn as a game tree, given here as nested Python values:

  • a leaf (the game is over) is a tuple of whole-number payoffs, one per player: payoffs[k] is player k's payoff (players are numbered 0, 1, 2, ...);
  • a decision node is a dict {"name": ..., "player": k, "moves": [(label, subtree), ...]}: player k picks one of the moves (at least one), and play continues in that move's subtree. Node names are distinct strings.

Backward induction solves the game from the end: at a node whose moves all lead to solved subtrees, the mover picks the move whose outcome gives it the highest payoff; if several moves tie for that payoff, it picks the first of them in the list. The node's outcome is then the outcome of the chosen move. Doing this at every node gives a subgame perfect equilibrium: a plan that says what each player would do at every node, even nodes that are never reached, and in which no player would want to change any choice it is asked to make.

Write subgame_perfect(tree) that returns a tuple (payoffs, path, plan):

  1. payoffs: the tuple of payoffs at the leaf where play ends;
  2. path: the list of move labels played from the root to that leaf ([] if the tree is a single leaf);
  3. plan: a dict mapping every decision node's name to the label it chooses.

The tests build trees with four helpers you can also call with Run. entry_game(): a café chain (player 0, node "chain") decides whether to open a branch in a town where a bakery (player 1, node "bakery") already sells coffee:

{"name": "chain", "player": 0, "moves": [
    ("enter", {"name": "bakery", "player": 1, "moves": [
        ("price war", (-2, 1)), ("share", (3, 4))]}),
    ("stay out", (0, 10))]}

three_friends(): three players, where player 1 is indifferent at node "B":

{"name": "A", "player": 0, "moves": [
    ("left", {"name": "B", "player": 1, "moves": [("up", (1, 2, 3)), ("down", (4, 2, 0))]}),
    ("right", {"name": "C", "player": 2, "moves": [("x", (2, 0, 1)), ("y", (0, 5, 5))]})]}
  • split_offer(total): player 0 (node "proposer") offers player 1 a whole number x of the total coins, moves "offer 0", ..., "offer <total>". Player 1 (node "reply <x>") then chooses "accept", giving (total - x, x), or "reject", giving (0, 0), in that order.
  • take_or_pass(stages): players 0 and 1 take turns at nodes "stage 0", "stage 1", ...; at stage k the mover chooses "take" (the game ends with k + 2 for the mover and k for the other) or "pass", in that order. If all stages movers pass, both get stages.

Examples

Input:  tree = entry_game()
Output: ((3, 4), ['enter', 'share'], {'chain': 'enter', 'bakery': 'share'})
Explanation: once the chain is in, a price war would give the bakery 1 instead of 4,
so the threat of one is not believed, and the chain enters.

Input:  tree = three_friends()
Output: ((1, 2, 3), ['left', 'up'], {'A': 'left', 'B': 'up', 'C': 'y'})
Explanation: B ties at 2 and takes the first move, "up". C is never reached but
still has a choice in the plan.

Input:  tree = split_offer(3)
Output: ((3, 0), ['offer 0', 'accept'], {'proposer': 'offer 0', 'reply 0': 'accept',
         'reply 1': 'accept', 'reply 2': 'accept', 'reply 3': 'accept'})

Constraints

  • trees have at most a few thousand nodes and are at most 300 moves deep

Goals

  • Solve a game tree from its leaves up, each mover choosing the move best for itself
  • Record a choice at **every** decision node, including those the play never reaches
  • Apply a stated tie rule, and see how it changes other players' payoffs
Starting Python…