Rose and Colin play the Battle of the Sexes, but Colin may first "burn" 95 utility units in full view of Rose.

[ Editor: Dreier's answer to the first question, from the original
posting: ]

Answer: it's indeterminate.  Rose wants to be at R,R, and Colin wants
to be at C,C.  If they each try for their favorite spot, they will end
up at R,C, which pays them each one.  They would like to coordinate,
but they can't.  (If they could communicate, they would fight about
whose favored spot to pick, but that's another story.)

-- Jamie Dreier <pl436000@brownvm.brown.edu>

In article <793752880snz@chch.demon.co.uk> ch@chch.demon.co.uk
(Charles Bryant) writes:
>[...] Each chooses randomly. If the result ends in (0,0) or
>(1,1) the next play repeats this strategy. When a play ends in
>(100,10) or (10,100) they co-operate by making subsequent plays
>alternate between (10,100) and (100,10). This gives an average payoff
>of 55. If there is only one play, the payoff is 27.75.

I have a better strategy.  Each chooses randomly once, and then Rose
chooses the opposite choice on the next round while Colin stays with
whatever he had.  The average payoff after the first game is still 55,
but fewer randomized rounds will occur on average, so my strategy
strictly dominates yours in any series of more than one game.

Do you object that without communication, the players have no way to
agree that Colin's random choice should determine the second game?
You're right.  But without communication, how are the players to know
that if the first match is RR, the alternation should be

  RR (first match), then CC,RR,CC,RR,CC,...

rather than

  RR (first match), then CC,CC,RR,RR,CC,CC,RR,RR,... ?

The second scheme is fairer than the first, because if the series of
games ends at a random time after the first match, either scheme might
yield equal rewards to Rose and Colin (and in fact the two schemes are
equally likely to do so), but in the second scheme, both players have
a chance to be ahead, whereas in the first scheme, only Rose can end
up ahead.  In particular, if I were Colin, I would prefer the second
scheme to the first.

In fact, if you allow enough communication (or special knowledge of
the other player) to allow each player to know what scheme of
alternation the other will adhere to, the players should know each
other well enough to figure out what the first move (RR or CC) should
be, and begin the alternation from there.

On the other hand, if there's only one game and no prior
communication, then the only option is some sort of mixed strategy,
that is, random choices by Rose and Colin.  But I would expect each of
them to more heavily weight the row or column that most favors
themselves.  The weighting .5, .5 doesn't seem to make much sense for
either player: each one could improve his or her outcome at that point
by "defecting."

-- David A. Karr <karr@cs.cornell.edu> (26 February 1995)

Charles:
> No. It's not. Each chooses randomly. [...] If there is only one play,
> the payoff is 27.75.

Well, that's a strategy for a series of iterations of the game.  I was
talking about a single play; I thought that was clear.

At the end there, you seem to be saying that there is a best solution
for a single-play version.  And you say that the payoff for this
strategy is 27.75.  But your strategy is not an equilibrium.

Suppose Rose plays R with probability .5 and C with probability .5 (a
mixed strategy, perfectly reasonable).  Then if Colin plays that mixed
strategy, his expected payoff is indeed 27.75 [Editor: "27.25" in the
original; (10+1+0+100)/4 = 27.75].  But why should he play that
strategy??  Instead he could play C with probability 1.  Then his
expected payoff is 50.5.

(My Burn Game)

Charles:
> Colin should play the burn move if random moves are not allowed. Then
> Colin's logical choice is clearly to aim for (10,5), which Rose will
> also go for. The payoff here is asymmetrical and lower than for random
> moving.

Good!  That's half of the answer, but there's more.....

If Colin plays the Burn move, then he will get 10.  Right?

So suppose he *doesn't* play it.  (Burn, C) dominates (not-Burn, R).
Since Rose knows that Colin is rational, and he knows she knows it,
etc., they both know that Colin will not play (not-Burn, R).  For a
rational player could never play a move that is strongly dominated by
an alternative.

So if Colin does not Burn, Rose knows he will play (not-Burn, C)!  So
her rational move is C.  Then Colin gets 100.

Upshot: if the Burn move is available, Colin won't play it.  But
because it is *available*, rational players are forced to C,C.  This
is very strange, I think.  How could the outcome be influenced by the
availability of an option that no rational player would ever play???

-- Jamie Dreier <pl436000@brownvm.brown.edu> (27 February 1995)

[ Editor: in "If Colin plays the Burn move, then he will get 10", the
outcome (10,5) of matrix two pays Rose 10 and Colin 5.  With 5, (Burn,
C) does not dominate (not-Burn, R), which pays Colin 10 or 0. ]

In article <793922416snz@chch.demon.co.uk> ch@chch.demon.co.uk writes:
>In article <1995Feb26.173229.21231@cs.cornell.edu>
>           karr@cs.cornell.edu "David Karr" writes:
>>
>>   RR (first match), then CC,RR,CC,RR,CC,...
>>
>>   RR (first match), then CC,CC,RR,RR,CC,CC,RR,RR,... ?
>>
>> The second scheme is fairer than the first, [...]
>> In particular, if I were Colin, I would prefer the second
>> scheme to the first.
>
>In that case, both deduce that the second series is superior to the
>first, and both use it.

Actually I made a slight misstatement.  The two schemes of alternation
each give equal expected payoffs to each player, *if* they are agreed
upon beforehand and both players stick to them.  (I am assuming that
the players agree that if the first match is CC, each RR is changed to
a CC and vice versa in the pattern of alternation.)

The point at which the second scheme appears "fairer" is only after
the first match, when we know which player will come out ahead in the
first scheme.  At that point, the second scheme gives the other player
back some of the disadvantage that he or she just received by missing
the first match.  But this "evening out" comes at the expense of the
player who just matched.  So if the first match is RR, Colin will want
scheme 2, but Rose would be better off with scheme 1.

Furthermore, I see no reason to believe that there isn't an even
"better" scheme for the alternation.  Presumably, a rational player
will follow the "best" scheme, but we don't know what it is.  Could
it be that there is no "best" scheme (or several "best" schemes that
we are unable to rank)?  This again would make rational play
indeterminate.

>Actually, the 0.5, 0.5 weighting is not optimal. The optimum is
>54/109, 55/109. Since the situation is symmetrical, neither player can
>reasonably expect to achieve better than this (27.75229).

This seems like it's aiming at a super-rational solution.  Isn't
there still a high incentive for one player to "defect" at this
point?

-- David A. Karr <karr@cs.cornell.edu> (28 February 1995)

In article <1995Mar5.165732.21578@cs.cornell.edu>
           karr@cs.cornell.edu "David Karr" writes:
> In article <794367563snz@chch.demon.co.uk> ch@chch.demon.co.uk writes:
> >It [the incentive to defect?  --DAK]
> >depends on the nature of the reward and the
> >relationship between the populations of players.
>
> "Nature of the reward" and "relationship between the populations"
> suggest that there are utilities of the reward that are not expressed
> in the payoff matrix.  But it was a premise of the problem that this
> is not so.

I'll come back to this at the end.

> Suppose Colin knows that Rose is going to play C approximately half
> the time (54/109 or 55/109, I'm not sure which you intended for
> which).  Then it seems to me Colin should just play C (this is what I
> meant by "defecting").  Instead of an expected payoff less than 28,
> this gets Colin an expected payoff of about 50.  (That's what I call
> an "incentive.")

The 54/109 is for the play with (0,0), and the 55/109 covers (1,1).
The values are derived by assuming that each player chooses what to
play with the same probability as the other player, and solving for
the maximum expected return.  The players must use the same probability
as the problem is symmetrical, so if there is a solution it must be
the same for both players.

> Of course now it is no longer optimal for Rose to play C and R with
> such nearly equal probabilities.  In fact, if she knows Colin is
> going to play C, she might as well play C too, raising her expected
> outcome from about 5 to 10 (and raising Colin's to 100, but that's
> irrelevant to Rose by definition).
>
> Not that I'm trying to claim both players will end up at C all the
> time, merely that the 54/109, 55/109 "solution" doesn't appear to
> hold up.

That means that there is no solution.  The strategy depends on the
opponent, not the game.  I mentioned the "nature of the reward" because
I was thinking of how a simulation would be set up to test different
strategies.  This might select the best strategies from a large number,
in order to run more simulations with these.  This would alter the
population of opponents which a strategy would face, which would
introduce a bias favouring certain strategies over others.  I suspect
that such a simulation would produce quite interesting results.

-- Charles Bryant <ch@chch.demon.co.uk> (9 March 1995)

In article <794790851snz@chch.demon.co.uk> ch@chch.demon.co.uk writes:
>The 54/109 is for the play with (0,0), and the 55/109 covers (1,1).
>[...] The players must use the same probability
>as the problem is symmetrical, so if there is a solution it must be
>the same for both players.

The problem with this reasoning is that you can't assume a priori that
there *is* a solution.  Even when there is a solution to such a
problem, it isn't always the one that maximizes the return to both
players when they play equally: compare the Prisoner's Dilemma, where
"not confessing" has the best outcome if both prisoners take it, yet
it is not the best strategy for either prisoner.

>I mentioned the "nature of the reward" because
>I was thinking of how a simulation would be set up to test different
>strategies. This might select the best strategies from a large number,
>in order to run more simulations with these. This would alter the
>population of opponents which a strategy would face, [...]

It would also quite likely alter the utilities in the payoff matrix.
Remember that "utility" was defined not as an amount of any specific
reward, but rather the total subjective value of an outcome to the
player.  If you add a "selection" process that "rewards" the players
with certain outcomes by allowing them to continue to the next round,
then the chance of being selected becomes an extra component of the
subjective value of the outcome, and so has to be added somehow to the
utilities in the table.

The setup where the same two players play a series of games is also
interesting.  Again we have the problem that the effects on future
games might alter the utility of the outcomes of this round.  But
perhaps we could look at rounds with fixed rewards (not utilities) and
see what each player could do to maximize his or her reward over the
entire series of games.  I think the general idea would be to try to
"teach" the other player a cooperative strategy of some sort, perhaps
one of the alternating sequences we discussed before.  I don't know if
an optimal strategy for this can even be worked out, but there ought
to be some techniques that work if a very long series of games, of
known fixed length, is to be played.  For example, try a certain
short, fixed pattern for a few games, hoping the other player will
cooperate.  If the other player also appears to be trying to teach a
pattern, switch to the pattern that cooperates with the other player.
Of course this may backfire if the other player switches over to your
scheme at the same time you switch to hers.  So you switch again, but
randomly timed, and perhaps with exponential backoff to avoid this
contention (though that may be unnecessary).  Any better ideas?

-- David A. Karr <karr@cs.cornell.edu> (10 March 1995)