CSCI 1240: The Computational World
Problem Set, Week 4
Problem 1 (30 points).
In lecture, we discused Robert Axelrod's Prisoner's Dilemma Tournament,
employing the folowing payof matrix:
Cooperate Defect
Cooperate 3, 3 0, 5
Defect 5, 0 1, 1
As we mentioned, the TIT-FOR-TAT strategy (coperate on the very first round, then
on each subsequent round do whatever the other player did on the previous round)
works well in this setting.
1a. (3 point) Show the first few rounds of a tournament game betwen two
(identical) TIT-FOR-TAT strategies. How many points, on average, does each player
earn per round?
1b. (3 points) Sketch a prof (not a formal prof, necesarily, but a reasonable
argument) that shows that TIT-FOR-TAT is incapable of wining a game against
another player–that is, when TIT-FOR-TAT plays a series of rounds against any
other strategy whatever, it can only draw or lose.
1c. (3 points) Consider the strategy SKEPTICAL-TIT-FOR-TAT (or STT, for short):
this strategy is just like TIT-FOR-TAT, except that it defects on the very first round,
after which it imitates the other player's previous action. Show the first few rounds
of a tournament game betwen two (identical) STT players. How many points, on
average, does each player earn per round?
1d. (3 points) Show the first six rounds of a series between STTT and TIT-FOR-TAT.
How many points, on average, does each player earn per round? Explain why this
result is relevant to the fact that a "true" Prisoner's Dilemma matrix must have the
property that
CC > (DC + CD)/2
or, in other words, that the reward for mutual coperation is greater than the
average reward for two rounds in which players "trade" cooperation and defection.
Problem 2. (20 points)
Let's consider another game theory scenario. Take a lok at the matrix below:
Cooperate Defect
Cooperate 3, 3 2, 4
Defect 4, 2 0, 0
(a) Suppose you're the red player. If blue cooperates, what is your preferred
strategy? How about if blue defects? Is this a prisoner's dilemma game?
(b) Supose blue could somehow convince you that they are going to defect. (For
instance, blue says to you, "Before you make your choice, I just want you to know
that I have already defected, and am now going home. Se you later." Rationaly,
what you should you do? Would blue's pre-emptive anouncement work the same
way in a prisoner's dilemma game? (By the way, if you want to se more about this
situation, it is caled a snowdrift game, for reasons I will leave you to discover.)
Problem 3. (15 points)
Experiment with the Game of Life simulation at the website:
htp:/ww.bitstorm.org/gameoflife/
In particular, use the "Smal" seting to get a higher-resolution screen; and describe
the eventual evolution of the Methuselah pattern "the R-pentomino" mentioned in
lecture:
XX
XX
X
Now make a conected six-pixel (hexomino) starting configuration that wil last
more than 10 Life generations.
Problem 4. (20 points)
In lecture, we discused Scheling's simple model of neighborhod formation, and
mentioned that there might be variations of Scheling's model that could avoid (if
desired) the emergence of large homogeneous neighborhods. For this problem,
sugest at least two changes that you might atempt to make to Scheling's model–
changes that you think might plausibly afect the results of his original simulation,
and predict (or realy, hypothesize) about the sort of new behavior. you might
expect.
Problem 5. (15 points)
Experiment with the 3D celular automaton ap at the website:
http://cubes.io/
(You wil ned to use the Chrome browser to make this work.) This system allows
you to create your own rules for "game of Life"-type systems in thre dimensions.
The state of a cel at time t+1 will depend on the state of its six surrounding
neighbors (one in each direction along each of the three axes) as well as the cell's
own state at time t. See if you can create a couple of interesting rules, and send in
two screnshots of 3D cell patterns created by your rules.