Who should change first? Substitutions, game trees and backward induction

The football question

It's 70 minutes and you're 1–0 up at home. You're thinking of taking off a striker and sending on a defender. The other manager is thinking about a third striker. Should you make your change now, or wait and see what he does?

In Parts 1 to 3, both sides chose at the same moment: the penalty taker and the keeper, two teams at Gijón. A substitution is different. Everyone can see it, and the other bench has time to answer. When moves happen in turn, the order matters, and game theory has a clean way to work out how.

The concept

A game where players move in turn can be drawn as a game tree. It starts with the first player's choice, branches out to the second player's possible replies, and ends with what each path is worth to each side.

Trees are solved by backward induction: start at the end and work back.

• At the last choice, each player simply picks whatever is best for them.
• One step earlier, the player choosing knows what will follow each option, so they compare those outcomes and pick the best.
• Keep going back until you reach the first choice.

The answer is a plan for every point in the game, not just the moves that end up being played. Because each choice has to be the best one at that point, it rules out threats that nobody would carry out when the moment came. A plan like that is called a subgame-perfect equilibrium.

A football example

The home manager can keep going or shut up shop. The away manager can stay patient or go all-out. Here are the home side's chances of a win, draw and loss for each pair of choices. They're made-up numbers, chosen to have a shape most managers would recognise.

Each side cares about points, and a team's expected points are

$$\text{points} = 3 \times \text{win chance} + \text{draw chance}$$

Look at each manager's best reply to the other:

• Against a patient side, the home team should shut up shop (2.34 against 2.21). But against an all-out side it should keep going (2.28 against 2.02). Parking the bus against three strikers invites pressure, while keeping a striker on catches them on the break.
• Against a team that keeps going, the away side should stay patient (0.59 against 0.54): going all-out leaves gaps for the counter. Against a team that shuts up shop, it should go all-out (0.76 against 0.42).

Each manager's best change depends on what the other does, and each wants the opposite of what the other hopes. That's why the order of the changes matters.

Solving the tree

If the home manager changes first, start at the end. Whatever he does, the away manager replies with his best answer: patient if the home side keeps going, all-out if it shuts up shop. So the home manager is really choosing between 2.21 (keep going, away stays patient) and 2.02 (shut up shop, away goes all-out). He keeps going, and the match ends up at 2.21 / 0.59.

If the away manager changes first, the home side answers. If away stays patient, home shuts up shop and away gets 0.42. If away goes all-out, home keeps going and away gets 0.54. He goes all-out, and the match ends up at 2.28 / 0.54.

And if neither can see the other's change, because both decide at once, it's a guessing game like the penalty in Part 1. Each should mix it up: the home side shuts up shop 13% of the time and the away side goes all-out 33% of the time.

Both managers do better when the other one moves first. The home side gets most when it can answer the away side's change, and the away side gets most when it can answer the home side's. In this game, waiting is worth something to both.

Why waiting can pay

Moving second helps whenever your best move depends on the other side's. The same thing happens at the penalty spot. As Part 2 noted, a taker who can wait for the keeper to move is playing a different and much easier game, which is why keepers try to hold their position as long as they can.

That gives a game-theory reason for something managers do anyway: keeping a substitution in hand. A manager who has used all his changes can't answer, so whatever the other bench does, it effectively moves second. Here that's worth 0.07 points a match to the home side, the gap between 2.28 and 2.21. That's small in one game but worth about two and a half points over a 38-game season, if it came up every week.

Moving first isn't always worse. When an early move forces the other side's hand, so that its best reply suits you, getting in first is an advantage. A tree shows which kind of game you're in, before you have to guess.

Promises and threats

Before the change, the away manager might want the home bench to believe "we'll stay patient whatever you do". If they believed it, the home side would shut up shop (2.34). But once they had, staying patient would earn the away side 0.42, and going all-out 0.76. He wouldn't keep the promise, and the home bench, working backwards, knows that.

Backward induction only allows moves that are best at the moment they're made. So promises and threats count only if carrying them out would really be the player's best move when the time came. That's the "perfect" in subgame-perfect: the plan has to make sense at every point in the game, not just at the start.

Why it matters

A substitution, a change of shape, a move to a back three: each one is seen and answered. Game trees turn "what will they do then?" into something you can work out, and backward induction says how to choose knowing the answer is coming. Two lessons go well beyond football: know whether your game rewards moving first or moving second, and judge an opponent's threats by whether carrying them out would really be best for them at the time.

For what the numbers say about protecting a lead, see Is 2–0 the most dangerous lead? and the Hold the lead model. Part 5 looks at games played again and again, where today's choice changes what the opponent expects next time.

Limitations

• The chances are made up. They show how a tree works, not what really happens at 70 minutes. Our match data has no substitutions, so we can't test them.
• Real matches have many moves. Each manager has several changes, the score can change between them, and both benches react again. Bigger trees work the same way, but they grow quickly.
• Both managers are assumed to know the numbers. In practice each has his own idea of how a change will work, and they may not agree.
• The 0.07 points is for this table only. In a game where the first move forces the other side's hand, holding a change back would cost points instead.

Try it yourself

Change one number so that the home side would rather move first. Hint: make shutting up shop so strong against an all-out side that the away manager's best reply to it becomes staying patient. Then the snippet below shows whether the home side now gains by changing early.

Reproduce the analysis

This builds the tree for each order of moves, solves it by backward induction, and works out the both-at-once mix as in Part 1. Nothing to download.

# Made up. 70 minutes, the home side 1-0 up. The home manager keeps going or shuts up shop (a defender on for a
# striker); the away manager stays patient or goes all-out (a third striker). The home side's chances (%) of a win,
# draw and loss for each pair of choices:
chances = {("keep going", "patient"): (67, 20, 13), ("keep going", "all-out"): (70, 18, 12),
           ("shut up shop", "patient"): (70, 24, 6), ("shut up shop", "all-out"): (60, 22, 18)}
points = {k: ((3 * w + d) / 100, (3 * l + d) / 100) for k, (w, d, l) in chances.items()}   # expected (home, away)
HOME, AWAY = 0, 1
home_moves, away_moves = ["keep going", "shut up shop"], ["patient", "all-out"]


def tree(first):
    """The game as a tree: the first manager chooses, the second sees it and replies."""
    second = AWAY if first == HOME else HOME
    moves = (home_moves, away_moves)
    pair = lambda a, b: (a, b) if first == HOME else (b, a)
    return {"who": first, "moves": {a: {"who": second, "moves": {b: {"points": points[pair(a, b)]} for b in moves[second]}}
                                    for a in moves[first]}}


def backward(node):
    """Backward induction: solve the last choices first, then the ones before, knowing what will follow.
    Returns the points at the end of best play and the moves that get there."""
    if "points" in node:
        return node["points"], []
    options = [(backward(child), move) for move, child in node["moves"].items()]
    (pts, path), move = max(options, key=lambda o: o[0][0][node["who"]])
    return pts, [move] + path


def at_once():
    """Both choose without seeing the other: each mixes so the other gains nothing either way, as in Part 1."""
    h = lambda a, b: points[a, b][HOME]
    w = lambda a, b: points[a, b][AWAY]
    (k, s), (p, o) = home_moves, away_moves
    shut = (w(k, p) - w(k, o)) / ((w(k, p) - w(k, o)) + (w(s, o) - w(s, p)))   # leaves the away side indifferent
    allout = (h(s, p) - h(k, p)) / ((h(s, p) - h(k, p)) + (h(k, o) - h(s, o)))  # leaves the home side indifferent
    home = (1 - allout) * h(k, p) + allout * h(k, o)
    away = (1 - shut) * w(k, p) + shut * w(s, p)
    return shut, allout, home, away


print("Expected points (home, away):")
for k, (hp, ap) in points.items():
    print(f"  {k[0]:<13} v {k[1]:<8} {hp:.2f}  {ap:.2f}")
print()
for first, label in [(HOME, "Home manager changes first"), (AWAY, "Away manager changes first")]:
    (hp, ap), path = backward(tree(first))
    print(f"{label}: {' then '.join(path)}; home {hp:.2f}, away {ap:.2f}")
shut, allout, hp, ap = at_once()
print(f"Both at once: home shuts up shop {shut:.0%}, away goes all-out {allout:.0%}; home {hp:.2f}, away {ap:.2f}")

It prints:

Expected points (home, away):
  keep going    v patient  2.21  0.59
  keep going    v all-out  2.28  0.54
  shut up shop  v patient  2.34  0.42
  shut up shop  v all-out  2.02  0.76

Home manager changes first: keep going then patient; home 2.21, away 0.59
Away manager changes first: all-out then keep going; home 2.28, away 0.54
Both at once: home shuts up shop 13%, away goes all-out 33%; home 2.23, away 0.57

The backward function works on a tree of any size: give it more moves, more changes or more managers, and it solves them the same way, from the end.

Further reading

• Backward induction, Wikipedia. The method, with its use in game theory and beyond.
• Subgame perfect equilibrium, Wikipedia. Why credible plans matter, with the standard examples.
• Sequential game, Wikipedia. Games where players move in turn, and how they're drawn as trees.