Saturday, January 23, 2016

Formula 1 strategy and Nash equilibrium

At first sight, Formula 1 race strategy seems to be an ideal domain for the application of game-theory. There are a collection of non-cooperative agents, each seeking to anticipate the decisions of their competitors, and choose a strategy which maximizes their pay-off. The immediate pay-off at each Grand Prix is championship points.

However, there's a subtlety of game-theory which needs to be appreciated before its most famous concept, that of Nash equilibrium, can be applied.

Let's begin with the game-theory. John Nash demonstrated that a non-cooperative n-player game, in which each player has a finite set of possible strategies, must have at least one point of equilibrium.

This equilibrium is a state in which each player's choice of strategy cannot be improved, given every other player's choice of strategy. In game-theoretic language, each player's pay-off is maximized, given every other player's choice of strategy.

In formal terms, there must be an n-tuple of strategies σ = (σ1,...,σn) in which the pay-off for each player, vi, is maximized:

vi(σ) = max vi1,...,σn),   for i = 1,...,n

where the maximum is taken over all the player-i strategies, σi.

The set of strategies adopted by the teams at each Grand Prix should possess at least one such state of Nash equilibrium, (irrespective of whether the competitors are capable of finding that optimal state). However, it's possible to define a simple and realistic scenario which, at first sight, undermines Nash equilibrium.

Suppose that a Ferrari is ahead of a Mercedes in the early laps of a race, but the Mercedes has a pace advantage. Suppose, however, that the pace delta between the cars is less than the minimum threshold for a non-zero probability of the Mercedes overtaking the Ferrari.

Now, for the sake of argument, suppose that due to aerodynamic interference from the wake of the car ahead, the Mercedes cannot follow closer than 1.5 seconds behind the Ferrari, and suppose that tyre degradation is sufficiently low that new tyres provide a 1-lap undercut worth less than 1 second. Even if Mercedes pit first, Ferrari can respond the next lap, and (assuming an error-free stop) will emerge still in the lead.

Clearly, if Mercedes are to beat Ferrari they will need to use a different strategy. Let's make this interesting by postulating that whilst a 1-stop strategy is the fastest 'deterministic' race, a 2-stop strategy is only a second or so slower.

Now, if the Mercedes switches to a 2-stop strategy, it will be out of sync with the Ferrari, will be able to circulate at its true pace, and will be able to beat the Ferrari if the Scuderia remain on a 1-stop. (For the sake of argument, we assume that there are traffic-free gaps into which the Ferrari can pit, without being delayed by other competitors).

However, if Ferrari anticipates this, and plan a 2-stop strategy, it will still win the race. If both cars are on the 2-stop strategy, Mercedes cannot utilise its superior pace.

However, however, if Mercedes anticipates that, it can win the race by sticking to the original 1-stop strategy...which Ferrari, again, can head off by sticking with the 1-stop. And so on, ad infinitum.

Clearly, there is no Nash equilibrium here. Each possible combination of strategies is such that at least one competitor can improve their pay-off by changing strategy, if the other competitor's strategy remains fixed. This structure is depicted graphically above. Each of the four cells represents a possible combination of 1-stop and 2-stop strategies. The pair of numbers in each cell represents the pay-off, in championship points, for Ferrari and Mercedes, respectively.

The coloured arrows indicate how one competitor can always improve their pay-off. For example, the top-left cell represents the case in which Ferrari and Mercedes both pursue a 1-stop strategy. The blue arrow reaching across to the top-right cell indicates that Mercedes can improve their pay-off by switching to a 2-stop strategy, if Ferrari remain wedded to the 1-stop. However, the downward red arrow in the top-right cell indicates that Ferrari can improve their pay-off by switching to a 2-stop if Mercedes remain committed to a 2-stop.

The problem here is that the strategies considered are termed 'pure' strategies in game-theoretic terms. Nash's theorem pertains not to pure strategies, but to probabilistic combinations of pure strategies, called 'mixed' strategies. If there are two possible pure strategies, A and B, a mixed strategy is one in which, for example, you resolve to follow strategy-A 30% of the time, and strategy-B 70% of the time. You must also use a random number generator to enforce the probabilistic split.

A mixed strategy, then, is a rather abstract thing, and not necessarily something which represents human strategic thinking. People often have contingency plans, alternative strategies that they will adopt if certain events occur, but they rarely frame their original strategy in terms of probabilistic mixtures.

In terms of the Formula 1 strategy scenario defined above, there is a state of Nash equilibrium: if Ferrari and Mercedes both adopt the mixed strategy of pursuing a 1-stop with 50% probability and a 2-stop with 50% probability, then neither competitor has a mixed strategy which offers an improvement in terms of their average pay-off.

However, Formula 1 teams are unlikely to adopt such a coin-tossing approach to strategy, so a Grand Prix potentially offers an interesting case study of a non-cooperative n-player game far from Nash equilibrium.

1 comment:

Ariel & Cypora Cohen said...

Further reason that this is my favourite blog.