David
Blackwell and Game Theory
Sarah J. Greenwald
Appalachian State University
Boone, North Carolina
Mark C. Ginn
Appalachian State University
Boone, North Carolina
David Blackwell
One name that is sure to be near the top of any list of prominent African American mathematicians is that of David Harold Blackwell, Professor Emeritus of Statistics at the University of California at Berkeley. Professor Blackwell�s inclusion on such a list could be for many reasons: He has 80 research publications, 50 Ph.D. students, a reputation for excellent teaching, and an important role as a pioneer in the integration of African Americans into higher mathe-matics. He is also the only African American mathematician elected to membership in the National Academy of Sciences, or to be President or Vice President of the American Statistical Society. Yet, perhaps because he is still alive, resources containing classroom activity sheets on minorities in mathematics do not include him. This is unfortunate since students relate to Blackwell's openness about racial issues and his love of mathematics. In addition, Blackwell has done work in several fields such as game theory and statistical decisions so ideas related to his mathematics can easily be incorporated into various levels of classes.
David Blackwell was born in Centralia, Illinois on April 24, 1919. Early in life he seems to have been spared much of the racial prejudice of early twentieth-century America. While there were segregated elementary schools in Centralia during Blackwell�s youth, one for whites and one for blacks, he attended a school that was integrated. Blackwell describes:
Southern Illinois was probably fairly racist even when I was growing up there. � But I was not even aware of these problems � I had no sense of being discriminated against. My parents protected us from it, and I didn�t encounter enough of it in the schools to notice it.
(Albers & Alexanderson, 1985, p. 19)
Blackwell�s reaction to mathematics in grade school was mixed. While he was not very excited by algebra and trigonometry, he did enjoy geometry. In addition, even at this age Blackwell was intrigued by games such as checkers and naughts and crosses, wondering if there was a strategy so that the player making the first move could always win. He was also a member of the mathematics club in high school. The advisor of the club would challenge the club members with problems from the School Science and Mathematics journal and would submit their solutions. Blackwell was identified in the journal numerous times and one of his solutions was published.
After graduating from high school at the early age of sixteen Blackwell entered the University of Illinois in 1935 planning to be an elementary school teacher. A course on real analysis turned Blackwell to a career in mathematics. �That�s the first time I knew that serious mathematics was for me. It became clear that it was not simply a few things that I liked. The whole subject was just beautiful� (Albers & Alexanderson, 1985, p. 21). At the age of 22, Blackwell received his Ph.D. from Illinois. It was only the seventh Ph.D. in mathematics ever awarded to an African American (Williams, 2002).
Upon graduation, when Blackwell received a one-year appointment as a Rosenwald Postdoctoral Fellow at the prestigious Institute for Advanced Study in Princeton, racism reared its ugly head. It is standard practice for fellows at the Institute for Advanced Study to receive appointments as honorary faculty members at Princeton University. However, in 1941 Princeton had never even had an African American student, much less an African American faculty member, and this produced opposition within the university. The president of the university wrote to the director of the Institute for Advanced Study saying that the Institute was abusing the hospitality of the university with such an appointment. Fortunately, Blackwell was again protected from racial tension, this time by colleagues: �Apparently there was quite a fuss over this, but I didn�t hear a word about it� (Albers & Alexanderson, 1985, p. 23).
During his year in Princeton, Blackwell searched for academic appointments by sending letters only to the over 100 black colleges in the country. He did interview with Jerzy Neyman for a mathematics position at the University of California at Berkeley but no offer was made. Blackwell suggests that
[Racial discrimination] never bothered me. I�ll put it
that way. It surely shaped my expectations from the very beginning. It never
occurred to me to think about teaching in a major university since it wasn't in
my horizon at all.
(DeGroot, 1986, p. 41)
Blackwell received an offer from Southern University in Baton Rouge for an instructorship, and after a year there and a year at Clark University in Atlanta he received a permanent appointment at Howard University. Howard University, by Blackwell�s own admission, �was the ambition of every black scholar. That was the best job you could hope for� (DeGroot, 1986, p. 41). He quickly moved up the ranks, being promoted to full professor in 1947 and serving as chairman of the math department from 1947 until 1954.
In 1945 Blackwell heard Abe Girshick give a lecture on sequential analysis. He later contacted Girshick with what he thought was a counterexample to a theorem presented in the lecture. While Blackwell was incorrect about his counterexample, this contact began a fruitful collaboration between the two men that included their 1954 book Theory of Games and Statistical Decisions. Girshick�s lecture also marked the beginning of Blackwell�s work in statistics. His first publication in the area came a year later.
Blackwell revived his high school interest in the theory of games during his summer employment at Rand Corporation during the summers of 1948-50. While working at Rand, Blackwell became interested in the theory of duels. In the basic game, he first looked at two duelists who start a fixed distance apart with each having a single bullet. When the dual commences, they walk towards each other at a fixed rate. The closer each duelist gets to his opponent before firing, the more likely he is to hit him. The goal is to determine how long to wait before firing. To analyze this problem, the expected value of the dual must be calculated. This situation and other variations on this game are covered in Activity Sheet 1, which is printed on pages 15 through 17 in this issue. Blackwell�s thoughts about another game, called the Prisoner�s Dilemma, are explored in Activity Sheet 2, on page 18.
The culmination of Blackwell�s career at Howard occurred in 1954 when he gave an invited address in probability at the International Congress of Mathematicians in Amsterdam. Shortly after this, perhaps because of changing attitudes towards African Americans in our country, he finally received an appointment at the University of California at Berkeley in the newly formed Department of Statistics. While at Berkeley, Blackwell served as chair of the Statistics Department from 1956 to 1961. He was awarded several honorary doctorates and other awards and distinctions before he retired from the university in 1989. Even after his retirement he has remained active and continued to publish in mathematical journals.
The focuses of Blackwell�s research have been as varied as the universities at which he has taught. His results have applications in economics and accounting, and in 1979 he won the John Von Neumann prize for his work in operations research. However, in an interview with Don Albers (Albers & Alexanderson, 1985, p. 24) Blackwell was asked, �Of the areas in which you have worked, which do you think are most significant?� He replied, �I�ve worked in so many areas: I�m sort of a dilettante. Basically, I�m not interested in doing research and never have been � I�m interested in understanding, which is quite a different thing.� If only we all could understand so much.
References
Albers, D. & Alexanderson, G. (1985). David Blackwell. In D. Albers & G. Alexanderson (Eds.), Mathematical People: Profiles and Interviews (pp. 19-32). Boston: Birkhauser. Condensed version [On-line]. Available: http://scidiv.bcc.ctc.edu/Math/Blackwell.html
DeGroot, M. (1986). A Conversation with David Blackwell. Statistical Science, 1, 40-53.
Houston, J. (1994). David Harold Blackwell - NAM newsletter [On-line]. Available: http://www.maa. org/summa/archive/blackwl.htm
O�Connor, J.J. & Robertson, E.F.
(2002) David Harold Blackwell - MacTutor History of Mathematics Archive [On-line]. Available: http://www-gap.dcs.st-and.ac.uk/~history/
Mathematicians/Blackwell.html
Williams, S. (2002). David Blackwell
- Mathematicians of the African Diaspora
[On-line]. Available: http://www.math.buffalo.edu/ mad
/PEEPS/blackwell_david.html
Young, R. (1998). David Blackwell. In Notable
Mathematicians : From Ancient Times to the Present (pp. 62-64). Detroit: Gale
Research.
David Blackwell is cited as
one of the pioneers in the theory of duels. He describes how he and his
colleagues became interested in duels while working for the Rand Corporation in
the late 1940�s:
One day
some of us were talking and this question arose: If two people were advancing
on each other and each one has a gun with one bullet, when should you shoot? If
you miss, you�re required to continue advancing. That�s what gives it dramatic
interest. If you fire too early your accuracy is less and there�s a greater
chance of missing. It took us about a day to develop the theory of that duel�
Then I got the idea of making each gun silent. With the guns silent, if you
fire, the other fellow doesn�t know, unless he�s been hit. He doesn�t know
whether you fired and missed or whether you still have the bullet. That turned
out to be a very interesting problem mathematically.
(Albers &
Alexanderson, 1985, p. 25)
His research, which he
completed with various coauthors, was among the first rigorous analysis of the
age-old concept of a duel, a concept that had many applications in the Cold War
era. In this activity sheet, we will explore a simplified version of his work.
In the classic pistol duel,
the two duelists start back to back. On command they march a prescribed number
of paces away from each other, then turn to face each other, pistols at their
sides. Then they raise their smooth bore pistols and each fire a single bullet
at the other. If one duelist hits the other, he is considered the winner, while
if both are hit or both are missed the duel is considered a draw. It seems to
make sense that firing your pistol quickly might be advantageous as you could
hit your combatant before he fires and hence throw off his shot. On the other
hand, if you wait longer (and presumably aim more accurately) you stand a
better chance of hitting your opponent. If you wait long enough to see that
your opponent fired his weapon, and you are still standing, you could take as
long as you wanted to line up your shot.
We will simulate two
simplified versions of this dual. The first will be a �noisy duel� where each
duelist can tell when his opponent fires his weapon, and the second a �silent
duel� where this information is not available. For both of these games we will
make the following assumptions:
To simulate this game we need
two duelists with a piece of paper and a pair of dice. Before the game starts,
each duelist writes down a number from 1 to 6 representing when he plans to
fire his weapon. The two numbers are then compared. If the numbers are not
equal, the player with the lower number will roll his die to simulate firing
his weapon. If his number is i and
he rolls 1,2,�,i then he hits his
target and wins the duel. If he misses, with a roll of i+1,�6, then the other player will win as he will wait
until after 6 seconds to fire and will be guaranteed a hit. If both players
picked the same number, they both roll their die to simulate firing their
weapon and determine the outcome in the same manner.
Activity 1: Below are some strategies represented as ordered
pairs. The pair (i,j) represents
Player 1 planning to fire after i
seconds and Player 2 planning to fire after j seconds. Below each ordered pair is one or two die
rolls. In each case, determine the outcome of the duel.
Strategy |
(2,4) |
(5,1) |
(4,4) |
(1,6) |
(3,5) |
(1,6) |
Roll |
3 |
1 |
3,1 |
5 |
3 |
2 |
Winner |
|
|
|
|
|
|
Activity 2: Now get some dice and find a partner to challenge to
a duel. Simulate 10 or 15 duels, and try to find a winning strategy.
Hypothesize what you think the optimal strategy might be.
This game is simulated in the
same manner as the noisy duel unless the player who fires first misses. In this
case, the other player does not know he has fired and will continue to fire his
weapon as planned. Hence two rolls are always needed, and it becomes more
likely that both players will miss.
Activity 3: Analyze the strategies and rolls given below and see
if you can determine the outcome of each duel. The roll on the left is always
Player 1�s roll and the roll on the right is Player 2�s roll, regardless of the
order in which they fired.
Strategy |
(2,4) |
(5,1) |
(4,4) |
(1,6) |
(3,5) |
(1,6) |
Roll |
3,3 |
1,3 |
3,1 |
5,2 |
3,6 |
2,3 |
Winner |
|
|
|
|
|
|
Activity 4: Get your dice and partner and prepare to duel. Try to
hypothesize an optimal strategy as you simulate 10 or 15 duels.
To analyze these simplified
duels we must use some probability theory. In particular, we must look at the
expected value of each strategy. To do this we assign a numerical value to each
possible outcome of the game. For simplicity we will assign a weight of 1 to a
duel in which Player 1 wins and a weight of �1 to a duel in which he loses. A
draw will be assigned a value of 0. Now to determine the expected value of each
strategy we simply take the sum of each possible outcome times its probability
of occurring. One way to think about the expected value of a strategy is that
it is the average of the outcomes if this strategy is employed a large number
of times. In a duel this may be of limited use since losing once can be quite
disastrous.
Since our outcomes are based
on a roll of the dice, these probabilities are easy to compute. In real life
the calculation may be far more difficult. Also notice that we don�t need to
compute the probability of a draw in each strategy as this will be multiplied
by the value of a draw: 0. This will greatly simplify our computations.
Let�s look at the expected
value of the strategy (3,2) in a noisy duel. If this strategy is employed,
Player 2 will fire his weapon after 2 seconds. If he hits Player 1, which
happens with probability 2/6, Player 1 loses and the duel has a value of �1. If
Player 2 misses, which happens with probability 4/6, Player 1 waits for 6
seconds and hits Player 2 with probability 1. In this case the game has a value
of 1. Hence the expected value of this strategy is: .
Activity 5: Compute the expected values of the following
strategies; (2,5), (5,1), (2,2), (3,3), (3,4), and (3,2) in the noisy duel. The
entry in the ith row and jth column of the table given below is the expected
outcome of strategy (i,j).
j i |
1 |
2 |
3 |
4 |
5 |
6 |
1 |
0 |
-4/6 |
-4/6 |
-4/6 |
-4/6 |
-4/6 |
2 |
4/6 |
0 |
-2/6 |
-2/6 |
-2/6 |
-2/6 |
3 |
4/6 |
2/6 |
0 |
0 |
0 |
0 |
4 |
4/6 |
2/6 |
0 |
0 |
2/6 |
2/6 |
5 |
4/6 |
2/6 |
0 |
-2/6 |
0 |
4/6 |
6 |
4/6 |
2/6 |
0 |
-2/6 |
-4/6 |
0 |
If we are Player 1 and we
wish to live through our duel, we want to choose as our strategy the row that
has the largest minimum value. This strategy minimizes our chances of losing no
matter what strategy Player 2 adapts. Obviously rows 3 or 4 maximize the
minimum at 0, that is no matter what Player 2 does, if Player 1 picks strategy
3 or 4 he has at least as good a chance of winning as losing. One could even
make the argument that strategy 4 is better than strategy 3 as our chances of
winning against strategy 5 or 6 (should Player 2 be foolish enough to choose
either of those strategies) would be greater than with strategy 3. This may
seem counterintuitive as it says that in a duel where missing before you opponent
fires guarantees losing, waiting until you have better than a 50% chance of
success is a better strategy.
The main difference in the
analysis of the silent duel is that if the first person misses his shot, this
does not guarantee his death. If we look at the expected outcome of strategy
(3,2) again we see that Player 2 shoots first and hits Player 1 with
probability 2/6. If he misses, which happens with probability 4/6, Player 1
still has to hit his shot, which happens with probability 3/6. Thus the
expected value of this strategy is . So we see immediately that the silent duel does indeed have
different outcomes from the noisy duel.
Activity 6: Compute the expected values of the following strategies;
(2,5), (5,1), (2,2), (3,3), (3,4), and (3,2) in the silent duel. The table
below gives the expected value for all of the strategies for the silent duel.
The entry in the ith row jth column gives the value for strategy (i,j).
j i |
1 |
2 |
3 |
4 |
5 |
6 |
1 |
0 |
-4/36 |
-9/36 |
-14/36 |
-19/36 |
-24/36 |
2 |
4/36 |
0 |
0 |
-4/36 |
-8/36 |
-12/36 |
3 |
9/36 |
0 |
0 |
6/36 |
3/36 |
0 |
4 |
14/36 |
4/36 |
-6/36 |
0 |
14/36 |
12/36 |
5 |
19/36 |
8/36 |
-3/36 |
-14/36 |
0 |
16/36 |
6 |
24/36 |
12/36 |
0 |
-12/36 |
-16/36 |
0 |
Activity 7: Determine the optimal strategy for each player in the
silent duel. For Player 1 this is the row with the maximum minimum value and
for Player 2 the column with the minimum maximum value.
Conclusion: There
are many variations of this simple model of a duel. For example, we could let
the probabilities of the two duelists hitting their shots increase at different
rates, or we could assume that they had more bullets in their pistols. Of
course in real life, time does not increase in a discrete fashion and so the
duelists could fire at any time between 0 and 6. According to David Blackwell,
�[two-person duels] are the games for which the theory is clear and beautiful� (Albers &
Alexanderson, 1985, p. 25). We hope that
you have enjoyed these games and that you have developed an appreciation for
David Blackwell�s work on the theory of duels.
David Blackwell, one of the
greatest African American mathematicians, is interested in the theory of games.
We�ll look at one such game called the prisoner�s
dilemma.
Prisoner�s Dilemma Scenario: Imagine that you and your accomplice have robbed a bank.
Outside of the bank you are apprehended by police, separated, and then taken to
different interrogation rooms in the police station. The police offer you a
deal. You have to choose whether or not to implicate your accomplice. If both
of you implicate each other then you and your accomplice will each go to prison
for 2 years. However, if one of you implicates the other but the other keeps
silent, the one who has ratted out his accomplice will go free, while the other
will rot in jail for 5 years on the maximum charge. If you both keep silent,
only circumstantial evidence exists, and so you will both serve one year.
Question 1. Fill
in the following table to help organize the ramification of each option:
|
Your Accomplice Implicates You |
Your Accomplice Keeps Silent |
You Implicate Your Accomplice |
You
receive:_____years Accomplice
receives:_____years |
You
receive:_____years Accomplice
receives:_____years |
You Keep Silent |
You
receive:_____years jailtime Accomplice
receives:_____years |
You
receive:_____years Accomplice
receives:_____years |
Question
2: If you can talk to your accomplice and you trust him or her, what should you
do to minimize the time that you both spend in jail? Explain why. This is
called the co-operative strategy.
Question
3: Let�s say that you know that your accomplice is going to implicate you. What
should you do to minimize your jail time? Compare your options and explain.
Question 4: Let�s say that you know that your accomplice is going
to keep silent. What should you do to minimize your jail time? Compare your options and explain.
Question 5: You should have gotten the same answer for Questions 3
and 4. Following this strategy is best for you if you can�t trust your
accomplice (who, after all, is a criminal) because you come out ahead no matter
what the other person does. This is called the selfish strategy. If both you
and your accomplice follow the selfish strategy, how much time will you each
spend in jail?
David Blackwell
explains that:
The situation with the Soviet Union has
[had] elements like this in it. To cooperate is to disarm and to double-cross
is to re-arm with bigger and bigger weapons. That takes a lot of resources and
we would both be better off disarming. But each is afraid that if he throws
away his weapons, the other one will not and he will be at a great
disadvantage. So, when I saw that this� led to an armaments race, so to speak,
I realized I was not the one to come up with a satisfactory theory� I keep on
encouraging other people to work on it, though.
(Albers & Alexanderson, 1985, p. 26)
Question 6: What is the situation with the
Soviet Union and the arms race that David Blackwell mentions? You may want to
search the web in order to answer this question.
Question 7: What is the co-operative
strategy for the arms race with the Soviet Union? What is the selfish strategy?
Which strategy did the United States actually use?
Question 8: What are some other real-life
situations that have similar elements? Explain in detail.