Bishop-Cannings Theorem

The Bishop-Cannings Theorem

Comment -- Bishop and Cannings also showed that we can take this a step further. Suppose that there are different mixes (we'll call them mix1, mix2, etc). and they are subsets of the inclusive mix.

Now, if mix is an ESS, then:

eq. 2b: E(mix, mix) =E(mix(1),mix)= E(mix(2),mix) =... =E(mix(n),mix)

So we need not be worried about the simplifying assumption we made above to limit our consideration to contests of involving 'var' and pure supporting strategies (various flavors or fix(x)).

Summary: On this page we review the Bishop-Cannings theorem. This theorem is vital to our understanding of mixed strategies that might be an ESS. The important result to us will be to show that the payoffs to any of these mixed or pure strategies against the mixed strategy are constant and equal. Let mix be a strategy that plays pure display costs a, b, c, etc. at certain frequencies. Thus, we want to show that:

E(mix, mix) = E(a, mix) = E(b, mix) = E(c, mix) .. E(n, mix) = k

The discussion on much of this page very closely mirrors that provided by Maynard Smith (1982) in his Appendix C. I have changed some of the strategy names to make this treatment consistent with the rest of this site's consideration of the war of attrition (I use these names since they seem to work better for most students). It differs from Maynard Smith's treatment in that the commentary on explanation of the steps is greatly expanded for the convenience of students who may be less comfortable with math and who are not yet masters of the jargon of game theory.

Contents:

Introduction
- Background and Nomenclature
- The Problem
The Proof
References

Introduction

Background and Nomenclature: Assume that we have a mixed strategy of all possible display costs in our war of attrition. Thus, in the case of the mix of costs strategy, there are an infinite number of display times (costs), all of which are played with a certain unique probability. We can label each of the display costs (times) as a, b, c, ..., n where n is the most costly (longest) display (actually infinitely long, but we can approximate it to some very long time in a discrete solution).

Don't let the fact that there are 14 letters between a and n inclusive lead you to believe that there are just 14 costs. There are an infinite number; these letters are used for convenience to give you the idea of a series that eventually stops at infinity. You'll see that this shorthand in no way detracts from the proof.

In any contest, we can imagine a mix strategist as playing one of these "component strategies". For instance, one time it will play c (display up to cost c), another time a, etc.

Support for a Mixed Strategy: Up to now, I have used the term "component strategies" to describe the relationship between a through n to a mixed strategy. I use this term only to introduce an important idea -- the idea (which we have seen before) that a mixed ESS consists of a number of pure strategies. For example, we saw that with certain costs and benefits, there were mixed ESS solutions to the hawk and dove game. The mixed solution was to play the pure hawk and dove strategies each at some fixed probability (e.g., play hawk 58% and dove 42%). With the war of attrition, we have the same situation where each display time (cost) a to n represents a pure strategy and any mixed strategy composed of these pure strategies.

Bishop and Cannings say that strategies a through n "support" the mix strategy (or that hawk and dove support a mixed hawk-dove strategy). They define supporting strategies as pure strategies that are played with a probability greater than zero as part of the mixed (inclusive) strategy. Thus, for a child playing rock paper scissors who plays a mixed strategy called rsp that consists of random plays of rock, scissors, and paper, then rock, scissors and paper are all strategies in support of rsp.

Note however, that it is not necessary that all supporting strategies be played at the same frequency (for example, we looked at a number of examples of the hawk dove mixed ESS where the two strategies were not equal in frequency).

Back to the top of the frame

The Problem: Bishop and Cannings wanted to show that if a mixed strategy consisting of a number of supporting strategies fix(a), fix(b), fix(c), etc. is an ESS the following statement is true:

1. E(mix, mix) = E(fix(a),mix) = E(fix(b), mix) = E(fix(c), mix) ... E(fix(n), mix) = E(any fix(x), mix)

What does E(fix(a),mix) mean in the context of our war of attrition? Let's be sure we understand this before we go any further. It is the payoff to an individual playing the specific display time a against a variable strategist or a population that consists of a mix of pure strategists. The variable strategist, of course, can be playing any display time, including a.

To prove eq. 1 we must be able to DISPROVE BOTH of the following statements:

2a. E(any fix(x), mix) > E(mix, mix)
AND
2b. E(any fix(x), mix) < E(mix, mix)

Notice that both 2a and 2b say that:

E(any fix(x), mix) DO NOT EQUAL E(mix, mix)

so they both directly contradict eq. 1

Let's look at them in a little bit of detail. Statement 2a tell us mix is not stable against fix(a). Thus, if statement 2a is true, then mix is not an ESS, But we are looking for a solution where mix is an ESS. So, we can dismiss 2a as inconsistent with our supposition that mix is an ESS.

On the other hand, statement 2b amounts to nothing more than our old friend rule#1 for determining an ESS (press here to review rule #1). It is perfectly consistent with mix being an ESS.

However, recall that it is not the only situation where mix might be evolutionarily stable.
Statement 2b could be incorrect but mix would could still be evolutionarily stable if E(mix,mix)=E(fix(a),mix) AND E(mix,fix(a))>E(fix(a),fix(a)).

So, if we can prove that statement 2b is incorrect, then we have used the technique of proof by contradiction to show that if mix is an ESS, then

E(mix,mix)=E(fix(a),mix)

AND

E(mix,fix(a))>E(fix(a),fix(a))

must be true.

The Proof: So, let's show that statement 2b is false:

2b. E(any fix(x), mix) < E(mix, mix)

so, to make it concrete we'll substitute in the supporting strategy fix(a) for any fix(x):

E(fix(a), mix) < E(mix, mix)

Now, let x = either a fixed or mixed strategy that mix uses when it does not act as a. Thus, a is a pure strategy supporting mix.

And, since the frequency that a is played as freq(a), then the frequency at which x (all other strategies that support mix) is played is:

3. freq(x) = 1 - freq(a)

Now, using the fact that mix must play either a or x (all other possibilities besides a), we can write an expanded definition for E(var,var) that indicates the proportion of the payoff coming from supporting strategies a and all other supporting strategies (x):

4. E(mix,mix) = E(fix(a), mix)*freq(a) + E(x, mix)*(1-freq(a))

Confused by eq 4? (skip this box if it is clear) -- all eq 4 says is that the payoff to mix against mix can be expressed as the sum of the payoff to fix(a) vs. mix, adjusted for the frequency of this encounter, and the payoff of all other values of mix (called x) adjusted for the frequency of these encounters -- i.e., as the weighted average of the two.

Now, we can substitute eq.4 into eq. 2b:

5. E(mix, mix) < E(mix, mix)* freq(a) + E(x, mix)*(1- freq(a))

Now, if we solve expression 5:

5. E(mix,mix) < E(mix, mix)* freq(a) + E(x, mix)*(1- freq(a))

first by moving (E(mix,mix)* freq(a)) to the left side:

6a. E(mix, mix) - E(mix, mix) * freq(a) < E(x, mix) * (1- freq(a))

and then by factoring the left side:

6b. E(mix, mix) * (1 - freq(a)) < E(x, mix) (1- freq(a))

and finally by dividing through by (1- freq(a)):

6c. E(mix, mix) < E(x, mix)

Now, expression 6c cannot be true if mix is an ESS (as we supposed at the start). We now have our proof by contradiction: expression 6c, which follows from our starting point (expression 2b) cannot be true if mix is an ESS.

To summarize:

2b. E(fix(a), mix) < E(mix,mix) -- is FALSE since it leads to an incorrect expression (E(mix, mix) < E(x, mix) -- cannot be true if mix is an ESS)

AND since

2a. E(fix(a), mix) > E(mix, mix) is FALSE

Therefore if mix is an ESS then:

7. E(fix(a), mix) = E(mix, mix)

OK, now we are just about done. The only other thing we need to keep in mind is that we can use exactly the same proof for any other strategies in support of mix. Thus, we could start with:

E(fix(b), mix) > E(mix, mix) AND E(fix(b), mix) < E(mix, mix)

or

E(fix(c), mix) > E(mix, mix) AND E(fix(c), mix) < E(mix, mix)

or any support strategy instead of fix(a)

and by following the same steps we saw above end up with the same result. Thus, if mix is a mixed ESS with support from pure strategies fix(a), fix(b), fix(c), ..., fix(n) then:

1. E(mix, mix)=E(fix(a), mix)=E(fix(b), mix)=E(fix(b), mix) ... =E(n, mix)

Back to the top of this page

References

Bishop, D.T. and C. Cannings. 1978. A generalized war of attrition. J. Theor. Biol.

Maynard Smith, J.1982. Evolution and the Theory of Games. Cambridge Univ. Press.

Back to the top of this page