We’ve all been there. A good-natured dispute among friends escalates; one party insults the honour of another; and the situation can only be resolved with a duel. The two parties face each other down with pistols, and take alternating steps toward one another. They must decide when to shoot. Victory means life and honour restored; loss means death and dishonour. What will the outcome be?
Of course, duels are no longer as common a dispute-resolution mechanism as they used to be. But should you ever find yourself participating in one, you might like to know what the best strategy is. Should you shoot first? Or should you wait? Fortunately, game theory can provide some pointers. The purpose of this post is to run through a simple game theoretical analysis of a duel.
1. The Classic Duel Game
To start off, we need to outline the structure and rules of the game. When performing any game theoretical analysis, the first thing to do is to break the game down into its basic component parts: (i) players; (ii) actions/strategies; or (iii) payoffs.
In the duel, there are two players in the game (Player1 and Player2). They start off carrying their pistols, loaded with one bullet, and positioned a certain distance apart (it does not really matter how far apart they are, though to make it interesting you must assume that the probability of them hitting the target at the starting point is well below 1).
The players then have a decision to make. The duel runs through multiple alternating rounds. During each round, the player can either take one full step forward, or they can try to take a shot with their pistol. They cannot do both in one round. Thus, the choice is a strictly binary one. The tricky thing is that if they take a shot and miss; the other player will have a certain victory. For then, that player can simply take as many steps forward as they like and fire from point-blank range. The payoffs in the game are pretty simple: you either get shot (and presumably die or be seriously injured) or you don’t get shot (and survive).
The diagram below depicts the game. Don’t read too much into the fact that there are only four steps for each player. That’s entirely arbitrary, caused by the space restrictions of the diagram. As I said above, the actual distance in the game is not too important.
If you were a player in this game, the key strategic question would be: when should I take a shot? The answer to this depends on several factors (to be discussed below), but in the first instance what matters is your probability of hitting the target. We can assume, pretty safely, that this probability diminishes the further away from the other player that you are. Thus, at d=0 (i.e. no distance between Player1 and Player2) we assume that the probability of both hitting the target is 1. This probability drops off as d increases. This is depicted in the next diagram. One nice thing about this diagram is that it doesn’t assume that both players are of equal ability. Instead, it assumes that Player2 is the better shot. This is nice because it helps to demonstrate how the analysis we are about to perform works for all probability distributions.
Anyway, looking at the graph of the respective probabilities of hitting the target, and knowing the rules of the game, can we say anything sensible about who should shoot first? Let’s see.
2. Who Should Shoot First?
A simple argument would be to claim that the better shot should fire first. This makes a certain amount of sense since this player has the higher probability of hitting the target. The problem is that if the other player knows this, they might be tempted to pre-empt the better shot by “having a go”. But then the better shot should be aware of the other player’s temptation to pre-empt and should, in turn, try to shoot earlier. This logic can continue back to the start of the game.
This is the wrong way to think about it. To solve this game (i.e. to figure out when the first shot should be fired) you need to use a combination of dominance and backwards induction reasoning. These are two classic techniques for solving strategic games of this sort. Dominance reasoning holds that you should never adopt a strategy that is dominated by others, i.e. one that yields a worse expected payoff than all the available alternatives. (There is a more formal definition of this concept, but we don’t need that here.) Backwards induction is, as the name suggests, a way of analysing multi-round games by looking first to the last possible move in the game and working backwards from there. The idea being that this will allow to pick a clear “path” through the various decision points in the game.
As I say, a combination of both methods of reasoning tells us when the first shot in the duel should be fired. We can prove this, in the abstract, using a minimal amount of formal notation. Let Pn(d) represent the probability of player n (in our case either “1” or “2”) hitting the target at any particular distance, d. Now take the perspective of Player1, at some particular distance, and ask yourself whether you should shoot or not.
Before answering the question, keep in mind two different possible facts that could determine whether or not you should shoot.
Fact A: Player2 will not shoot in the next round.
Fact B: Player2 will shoot in the next the next round.
If Fact A is true, should you shoot at d? Obviously not. If you can be confident that Player2 will not take a shot in the next round, you should definitely take a step forward. You run no risk of being shot, and you increase your chances of winning since you get closer to the target. Hence, if Fact A obtains, taking a step forwards dominates taking a shot.
What if Fact B is true? Then it’s more complicated. Then it depends on both your probability of hitting the target at d, and Player2’s probability of missing in the next round (d - 1). Why? Well, if your probability of hitting the target at d is greater than or equal to Player2’s probability of missing at d - 1, then you should take a shot. Doing so gives you the best chance of winning. Conversely, if Player2’s probability of missing is higher than your probability of hitting, you should take a step forward. Why? Because, once again, doing so gives you the best chance of winning.
This tells us something interesting. It tells us that there is an inequality we can use to solve the game. Basically, if the following inequality is true at distance d, then player 1 should take a shot:
P1(d) ≥ 1 - P2(d - 1)
Or, to put it another way, (by adding P2(d −1) to both sides of the inequality) the shot should be taken whenever:
P1(d) + P2(d - 1) ≥ 1
Obviously, we don’t know at which distance in the game this is true. We are looking at the game purely in the abstract, but if we work out the players’ respective probability distributions, then we know for sure that there is some distance — call it d* — at which this inequality first holds true and at which the first shot should be taken.
How do we know this for sure? This is where the combination of dominance and backwards induction comes into play. At every point prior to d*, taking a step forward dominates taking a shot. This is because taking a step forward always increases your probability of winning the duel. At d* we run into a problem. We must use backwards induction to figure out whether to take the shot. This means we jump forward to the last possible distance in the game and figure out what would be the rational choice at that point. So let’s assume that at the last step (d = 0) in the game it is Player2’s turn:
At d=0, Player2 should take the shot since at that point their probability of winning the game is equal to 1.
This implies that:
At d=1, Player1 should take a shot. At that point, their probability of hitting the target exceeds Player2’s probability of missing the target during the next round (since Player2 definitely won’t miss in the next round).
This, in turn, implies that:
At d=2, Player2 should take a shot. Why? Because they know Player1 will take a shot in the next round, and they know that their probability of hitting the target at d=2 is higher than Player1’s probability of missing at d=1.
This pattern of reasoning iterates backwards to whatever distance it is in the game at which the inequality outlined above first obtains. This distance is d*. Whoever’s turn it is at that distance, should take a shot.
3. Conclusion
So there you have it, a very simple game theoretical analysis of the duel. Obviously, this analysis has its limitations. One of the major limitations is that is assumes we know what the respective probability distributions of the players is. In real world cases, we often won’t know this for sure. Instead, we’ll have to guess. Yet, even if you are only guessing, the same reasoning process can help (though how helpful it will be will depend on the accuracy of your guess).
One final point: although the story behind this analysis refers to pistol-duelling, the analysis holds in other analogous contexts. For example, companies often face duel-like decisions when they and a competitor are trying to be the first to launch a viable product onto a market. The same reasoning can apply in these cases.
No comments:
Post a Comment