Duel

Prerequisites: Chapters 1, 2, 3, 4, 5, and for Section 4 the advanced chapter on Unit Square Games.

In this Chapter we will discuss several rather cruel-looking games which may model a real-world 19th Century duel. Since dueling is certainly a "male game", we will use the names Adam and Bob for the players.

1. One-bullet, sequential

Of course, by changing these payoffs we would be able to create even more variants, but we will stick to these numbers 1, -1, and -2 at least until in the projects.

This game may be considered a model for a duel, but it may also serve as a model for less violent real-world situations. An example is market entry. Two companies are working on a new product. They know that whoever releases it first may have success or fails. In the case of success, this product will gain the whole market rather quickly, and the other company will not be able to put their new product in the market. Thus the company successfully releasing their product first did win. But in the second case, if the product fails, the same company cannot release the product later again. In that case, the other company that did not release the product yet can wait as long as necessary, and then release the perfect product, which will be accepted. Thus in the second case the company that did not release the product will win. Obviously the probability for success will raise over time, since the product gets better and better.

We have a sequential game with randomness. The extensive form, already solved using backwards analysis, is given below: Although the game is not symmetric, for this special sequence of hitting probabilities the expectations for both players are equal. They are both negative, the game is not zero-sum. If one player gets hurt, the loss for that player is higher than the gain for the winning player. Duel really is not a game you want to play!

In principle, variants of this sequential one-bullet game, where the hitting probabilities (and maybe the payoffs) are different, can all be solved using backward induction. It may be a little tedious, but again Excel could help. Thus all we would need is a computer and Excel and someone to prepare the Excel sheet for us, or knowledge to create such an Excel sheet, or one hour of spare time. But would a "Just wait half an hour and I will tell you the solution" be an appropriate answer to somebody asking us about a new variant, let's say where the hitting probabilities grow like 0.1, 0.15, 0.25, 0.3, 0.4, ... just to give an example? Is "We can solve it" all we can say about variants of the game, or are there some patterns to find?

1.1 Analysis of DUEL(1,1|0.1,0.2,...) without computer help

Yes, there are patterns, and Excel could also help finding them. We would analyze ten different cases, and see whether some pattern is visible. But isn't it true that sometimes a clever idea can spare us all that? We will see in what follows how asking the right questions and using the deduction power of the human mind will find some patterns without computer help. Of course, there may be more pattern hidden.

1. Monotonicity: In the solution above, both players decide to walk in early situations, with low hitting probabilities, and decide to shoot later. Intuitively this may be very obvious, but is this true for all variants? Would a player who would shoot at some distance never decide to walk later? This is the question we are asking, and note how it is based on experience and even on common sense. For each individual play, this is quite irrelevant since the player would never see these later situations anyway---he would have shot before and the game would be finished--- but for the analysis this may be an important question. Let's look at any situation (I) where Adam, playing rationally and optimally, decides to shoot, as in the part of the tree shown below.

   

   The only assumptions we make is that the probabilities are monotonous for each player, meaning that each player has a higher hitting probability if the distance is reduced. That means we assume p1 < p3, but we don't have to assume p1 < p2 or p2 < p3.

   Now assume optimally-playing Bob would decide to walk when in situation II. But this would imply that Adam could expect at least 2p3-1 in situation III, and therefore also in situation II. But then he would not have chosen to shoot in situation I, since p1 < p3, a contradiction to our first assumption. Therefore Bob would shoot in situation II. With the same reasoning again, this would also imply that Bob would shoot in situation III, and so on. If there is a distance where one of both would fire, then both would fire at every distance smaller than that.

2. When to start shooting: Now we only have to focus at the situation in the extensive form where one player, here Bob, shoots. In which case would Adam in the step before shoot too? Let again p1 and p2 denote the corresponding hitting probabilities. Then Adam has an expectation of p1·1 + (1-p1)·(-1) = 2·p1-1 when he shoots. When he waits, Bob shoots, and Adam's expectation in that case equals p2·(-2) + (1-p2)·1 = 1-3·p2. Therefore Adam will wait provided 2·p1-1 ≤ 1-3·p2, or
   

   2·p1+3·p2 ≤ 2, and shoot otherwise. Of course, the corresponding also holds for Bob.

   If the probabilities grow very slowly and are the same for both players (meaning that both players have equal skills, like in our variant described above), p1 and p2 are almost identical, therefore the players wait until the probability reaches about 2/5=0.4.

1.2 Analysis of DUEL(1,1|m, 2m, 3m, ...)

Let's now return to our initial assumption of constant increments for the probabilities. We consider the one-shot game DUEL(1,1|m,2m,3m, ...) with fixed m a little more precisely. If Adam moves first, his hitting probability in his kth choice would be a_k=(2k-1)m, and Bob's hitting probability at his kth choice would be b_k=2km.

• Then in the above situation we have p1=(2k-1)m and p2=2km for some fixed k. Adam will walk if 2·p1 + 3·p2 ≤ 2, that is, if 2·(2k-1)m + 3·2km ≤ 2, or [4k-2+6k]m ≤ 2, or k ≤ (m+1)/(5m).
• In the corresponding situation with Adam and Bob interchanged, we have Bob's hitting probability p1=2km and Adam's hitting probability in the following move p2=(2l+1)m. Therefore Bob will walk if 2·p1 + 3·p2 ≤ 2, i.e. if 2·2km + 3·(2k+1)m ≤ 2, or [4k+6k+3]m ≤ 2, or k ≤ (2-3m)/(10m).

So who will shoot first? It all depends on the two numbers (m+1)/(5m) and (2-3m)/(10m). More precisely, it depends on the so-called "ceilings" of these numbers, which are obtained by "rounding up". If both these numbers are equal, or if the ceiling of (m+1)/(5m) is less than the ceiling of (2-3m)/(10m), then Adam shoots, and otherwise Bob. Of course, nobody shoots second in the 1-bullet version, as was explained above.

By the design of the game, the expectations for Adam and Bob are those of Adam and Bob in the situation where one starts shooting. If this is Adam, if Adam shoots at move k, Adam's expected payoff is 2(2k-1)m-1 and Bob's expected payoff is 1-3(2k-1)m. If Bob shoots first, at his kth move, Adam's expected payoff equals 1-3(2km)=1-6km and Bob's expected payoff equals 2(2km) -1 = 4km-1.

To give just one example, take m=0.07. Our first task is to compute (m+1)/(5m)=3.06 and (2-3m)/(10m)=2.56. The ceilings are 4 and 3, which implies that Bob shoots first, in his 3rd move. Then Adam's expected payoff is 1-6km = 1-18·0.07 = -0.26, and Bob's expected payoff equals 4km-1 = 12·0.07 - 1 = -0.16.

2. Two-bullets, sequential

This game seems much more complicated than the previous 1-bullet version. If one shoots, only in one case we get an outcome with payoffs attached. In the other case the game continues. Therefore at these positions a whole new tree would grow. We use abbreviations like A(1,2,0.2) or B(2,1,0.3) or B(1,1,0.5) for positions. The first letter, "A" or "B", tells whether Adam or Bob have to move. The two numbers after the parenthesis indicate how many bullets Adam and how many bullets Bob have left. The last number indicates the hitting probability at the position (of course with the understanding that the probabilities would grow as given in the context if the shoot would not hit and the game would continue). In the game tree below, at any position labeled, a complete subtree has been pruned. Actually, each of these subtrees looks almost like the one given ,except that it may be shorter, depending on the starting probability. However, these pruned subtrees, which refer to the 1 versus 2 bullet subgames, would also have positions where subtrees are attached. In a nutshell, the whole game tree is huge.

However we could also use a game digraph instead of a game tree. There are many ways to arrive at a position like A(1,1,0.7), but it is rather irrelevant how we arrived there---what's important are the expectations for Adam and Bob in this situation. In the 0.1, 0.2, ... version, we have 80 different positions where Adam or Bob move: A(2,2,p), B(2,2,p), A(1,2,p), B(1,2,p), A(2,1,p), B(2,1,p), A(1,1,p), and B(1,1,p), with p=0.1, 0.2, ... 1. Only half of these positions could occur, starting at A(2,2,0.1), but this is not too relevant for us. Of course, there are also the random move positions, but we don't need names for them.

At position A(n,m,p), either Adam makes a step and we arrive at B(n,m,p+0.1), or Adam shoots in which case we arrive at a random move position. But we could also say that in this cases we arrive either at the end position carrying a payoff of 1 for Adam and -2 for Bob (Bob is hurt) with probability p, or at position B(n-1,m,p) with probability (1-p). If n=1, this second position is also an end position---Adam has lost and gets a payoff of -1, whereas the payoff for Bob equals 1. Then backward induction can be performed by computing expected values first for all positions A(1,1,p) and B(1,1,p), see the section above, and then for the positions A(1,2,p) and B(1,2,p), and A(1,2,p) and B(1,2,p), and finally for all positions A(2,2,p) and B(2,2,p). In particular, even if we are not interested in the duel game where one has one bullet and the other two, we have to deal with these kind of games (assign expected values to the positions A(1,2,p) and so on) in order to be able to solve the 2 and 2 bullet version. This is done in the Excel sheet Duel.xls.

2.1 A few cases of DUEL(2,2|m, 2m, 3m, ...)

Here are a few cases, analyzed using this Excel sheet:

m	Adam	Bob	Adam	Bob	Adam	Bob	Adam's payoff	Bob's payoff
0.05	step	step	step	shoot	step	shoot	-0.2	-0.2
0.055	step	step	shoot	step	shoot		-0,3026	-0,0461
0.06	step	step	shoot	step	shoot		-0,2464	-0,1304
0.07	step	step	shoot	step	shoot		-0,1376	-0,2936
0.073	step	step	shoot	shoot	shoot		-0,28776747	-0,324907295
0.08	step	shoot	step	shoot			-0,0848	-0,2768

Looking at different cases, a few observations can be made:

• It seems that the "monotonicity" discussed above also holds for the 2-bullet game. Players walk until they have reached a certain probability, which now seems to lie somewhere between 0.16 and 0.18. With hitting probabilities higher than that, they would always shoot provided both have still both bullets.
• However, if one of the players has only one bullet left and the other still has both, both wait a little longer, but the one with the two bullets waits still a little longer. That may seem even a little counterintuitive: Even though the player can spare one bullet, he still will wait a little longer.

3. One-Bullet Time Game

Since there is no way the players can react to the other's shot, a strategy for a player is just the threshold for the hitting probability at which the player will shoot. Thus before the game each player decides on a number between 0 and 1, and when the hitting probability reaches this value, he shoots. Thus there are infinitely many strategies---it is a unit square game.

Before we look into how to solve this game, let us look at a discrete approximation. We restrict the possible strategies for both players to the 101 values of 0, 0.01, 0.02, ... ,0.99, 1. Then we have a normal form with 101 columns and 101 rows. We can analyze this bimatrix game rather easily using the best response concept. The best response to x with x ≤ 0.4 are all values larger than x. The best response to x with x > 0.4 is x-0.01. Therefore there are two pure Nash equilibria: 0.4 versus 0.41, and also the other way. The payoffs for both players are -0.2. They should just try to avoid shooting at the same time, since this has payoffs of -0.56 or -0.58 for both.

This best response concept can also be applied in the continuous case. Assume Bob chooses the time y and Adam a time x.

• If x < y, then Adam shoots first, and the expected value for Adam is x·1 + (1-x)·(-1) = 2·x-1 < 2·y-1.
• If x> y, then Bob shoots first and the expected value for Adam is y·(-2) + (1-y)·1 = 1-3·y.
• If x=y, then both shoot at the same time, and the expected value for Adam equals y·(-2) + (1-y)·x·1 + (1-y)·(1-x)·0 = -y-y².

Moreover, if y≤0.4, then 1-3·y ≥ 2·y-1 > 2·x-1, therefore the best responses to Bob's choice of y are all x>y. On the other hand, if y>0.4, then there is no best response to y, but x should be smaller than y, and the closer it gets to y, the better. Thus the game consists in both players avoiding 0.4, but choosing a value smaller than 0.4, but very slightly smaller only.

4. Additional Option: Waiting

If we put an additional option of waiting---neither shooting nor walking one step and thereby reducing the distance---into the game, we get something funny: Both players may wait from the very beginning, wait and wait and wait ....

With this variant we get a so-called infinite game, a game that may never end. Of course, backwards induction is impossible in this case (why?). .........

Exercises

1. Project: Drunk Adam
   a) How would the analysis of the one-shot sequential duel change if Adam's probability for hitting is, for every given distance, half the probability for Bob hitting.
   b) What would change in the 2-bullet game?
   
   
   Show/Hide solution
   The drunk will shoot in any case. The expected payoffs are positive for Bob and more negative for drunk Adam. If Adam moves first, we would have pA=(2k-1)m and pB=2km, k=1,2,... , but since Adam is drunk we get pA=(2k-1)m/2. ................... If Bob moves first, we get pB=(2k-1)m and pA=2km, k=1,2,... , but since Adam is drunk we get pA=km. ...................
2. Project: How more dangerous weapons affect the state budget and the health of the citizens: Assume the payoff of -2 when someone is hurt is combined by -1 for losing and another -1 for the persons share for cost for doctors and recovery. Assume the state always has expenses matching this share. The question to investigate is: If weapons become more dangerous, let's say doubling these costs, meaning that the payoff for the player when hurt decreases to -3 (-1 for losing and -2 for these costs), would the costs taken by the state (which is now twice the number of people hurt) also double, assuming that the total number of duels remain constant? Would the percentage of people being hurt remain the same? Investigate both the sequential one bullet and the two-bullet models.
   
   
   Show/Hide solution
   .....
3. Project 3: Selecting m between 0.04 and 0.13
   a) Assume Adam can choose the step width m in DUEL(1,1|m,2m,...) or in DUEL(2,2|m,2m,...). Which m should he choose to maximize his expectations?
   b) Assume Bob can choose the step width m in DUEL(1,1|m,2m,...) or in DUEL(2,2|m,2m,...). Which m should he choose to maximize his expectations?
   c) Assume the state can choose the step width m in DUEL(1,1|m,2m,...) or in DUEL(2,2|m,2m,...). Which m should he choose to minimize the percentages of injuries?
   
   
   
   Show/Hide solution
   

---

---

---