a

r
X
i
v
:
q
u
a
n
t
-
p
h
/
0
0
0
4
0
7
6
v
1


1
9

A
p
r

2
0
0
0
Quantum Games
Jens Eisert and Martin Wilkens
Institut f ur Physik, Universit at Potsdam, 14469 Potsdam, Germany
(February 1, 2008)
In these lecture notes we investigate the implications of the identi-
cation of strategies with quantum operations in game theory beyond the
results presentedin [J. Eisert, M. Wilkens, and M. Lewenstein, Phys. Rev.
Lett. 83, 3077 (1999)]. After introducing a general framework, we study
quantum games with a classical analogue in order to esh out the pe-
culiarities of game theoretical settings in the quantum domain. Special
emphasis is given to a detailed investigation of different sets of quantum
strategies.
PACS-numbers: 03.67.-a, 03.65.Bz, 02.50.Le
I. INTRODUCTION
Game theory is the theory of decision making, which provides powerful tools
for investigating situations in which several parties make decisions according to
their personal interest [14]. It gives an account of how the parties would decide
in a situation which involves contest, rivalry, or struggle. Such have been found to
be relevant to social sciences, biology, or economics. Of particular interest to the
theory are games of incomplete information in which the parties may choose their
plan of action with complete knowledge of the situation on rational grounds, but
without knowing what decision the other parties have actually taken.
One important two player game is the so-called Prisoners Dilemma [5]. In this
game two players in the following referred to as Alice and Bob can indepen-
dently decide whether they intend to cooperate or defect. Being well aware
of the consequences of their decisions the players obtain a certain pay-off accord-
ing to their respective choices. This pay-off provides a quantitative characterisa-
tion of their personal preferences. Both players are assumed to want to maximise
their individual pay-off, yet they must pick their choice without knowing the other
players decision. Fig. 1 indicates the pay-off of Alice and Bob. The players face a
dilemma since rational reasoning in such a situation dictates the players to defect,
although they would both benet from mutual cooperation. As Alice is better off
with defection regardless of Bobs choice, she will defect. The game being symmet-
ric, the same argument applies to Bob.
s
B
A
D
s
C
D
C
(5,0)
(0,5)
(1,1)
Bob
Alice
(3,3)
FIG. 1. The pay-off matrix in the Prisoners Dilemma game. The rst entry refers to Al-
ices pay-off, the second to Bobs. If both players cooperate, they both get 3 units pay-off. If
Bob defects and Alice happens to cooperate, he obtains 5 units, while Alice is in the unfortu-
nate situation in which she does not receive any pay-off at all. Bob faces the same situation
if he chooses to cooperate while Alice prefers to defect. If both defect, they get only 1 unit
pay-off.
1
Formally, Alice has two basic choices, meaning that she can select from two pos-
sible strategies s
A
= C (cooperation) and s
A
= D (defection). Bob may also take
s
B
= C or s
B
= D. The game is dened by these possible strategies on the one
hand, and on the other hand by a specication of how to evaluate the pay-off once
the combination of chosen strategies (s
A
, s
B
) is known, i.e., the utility functions
mapping (s
A
, s
B
) on a number [2]. The expected pay-off quanties the preference
of the players.
In these lecture notes the idea of identifying strategic moves with quantum op-
erations as introduced in Refs. [6,7] is further developed. This approach appears
to be fruitful in at least two ways [69]. On the one hand several recently proposed
applications of quantum information theory can already be conceived as compet-
itive situations where several parties with more or less opposed motives interact.
These parties may, for example, apply quantumoperations on a bi-partite quantum
system [10]. In the same context, quantum cloning has been formulated as a game
between two players [11]. Similarly, eavesdropping in quantum cryptography [12]
can be regarded as a game between the eavesdropper and the sender, and there
are similarities of the extended form of quantum versions of games and quantum
algorithms [13,14]. On the other hand a generalisation of the theory of decisions
into the domain of quantum probabilities seems interesting, as the roots of game
theory are partly in probability theory. In this context it is of interest to investigate
what solutions are attainable if superpositions of strategies are allowed for [6,7].
Game theory does not explicitly concern itself with how the information is trans-
mitted once a decision is taken. Yet, it should be clear that the practical implemen-
tation of any (classical) game inevitably makes use of the the exchange of voting
papers, faxes, emails, ballots, and the like. In the Prisoners Dilemma, e.g., the
two parties have to communicate with an advocate by talking to her or by writ-
ing a short letter on which the decision is indicated. Bearing in mind that a game
is also about the transfer of information, it becomes legitimate to ask what hap-
pens if these carriers of information are taken to be quantum systems, quantum
information being a fundamental notion of information.
By classical means a two player binary choice game may be played as follows:
An arbiter takes two coins and forwards one coin each to the players. The players
then receive their coin with head up and may keep it as it is (cooperate) or turn it
upside down so that tails is up (defection). Both players then return the coins to
the arbiter who calculates the players nal pay-off corresponding to the combina-
tion of strategies he obtains from the players. Here, the coins serve as the physical
carrier of information in the game. In a quantum version of such a game quantum
systems would be used as such carriers of information. For a binary choice two
player game an implementation making use of minimal resources involves two
qubits as physical carriers.
II. QUANTUM GAMES AND QUANTUM STRATEGIES
Any quantum system which can be manipulated by two parties or more and
where the utility of the moves can be reasonably quantied, may be conceived as
a quantum game.
A two-player quantum game = (H, , S
A
, S
B
, P
A
, P
B
) is completely specied
by the underlying Hilbert space H of the physical system, the initial state
o(H), where o(H) is the associated state space, the sets S
A
and S
B
of permissible
quantumoperations of the two players, and the utility functionals P
A
and P
B
, which
specify the utility for each player. A quantum strategy s
A
S
A
, s
B
S
B
is a
quantum operation, that is, a completely positive trace-preserving map mapping
the state space on itself [15]. The quantum games denition also includes certain
implicit rules, such as the order of the implementation of the respective quantum
strategies. Rules also exclude certain actions, as the alteration of the pay-off during
the game.
2
The quantum games proposed in Refs. [6], [7], and [9] can be cast into this form.
Also, the quantum cloning device as described in [11] can be said to be a quantum
game in this sense. A quantum game is called zero-sum game, if the expected pay-
offs sum up to zero for all pairs of strategies, that is, if P
A
(s
A
, s
B
) = P
B
(s
A
, s
B
)
for all s
A
S
A
, s
B
S
B
. Otherwise, it is called a non-zero sum game.
It is natural to call two quantum strategies of Alice s
A
and s

A
equivalent, if
P
A
(s
A
, s
B
) = P
A
(s

A
, s
B
) and P
B
(s
A
, s
B
) = P
A
(s

A
, s
B
) for all possible s
B
. That
is, if s
A
and s

A
yield the same expected pay-off for both players for all allowed
strategies of Bob. In the same way strategies s
B
and s

B
of Bob will be identied.
(s , s )
B A
P , P
B A
FIG. 2. The general setup of a quantum game.
A solution concept provides advice to the players with respect to the action they
should take. The following solution concepts will be used in the remainder of this
lecture. These denitions are fully analogous to the corresponding denitions in
standard game theory [2].
A quantum strategy s
A
is called dominant strategy of Alice if
P
A
(s
A
, s

B
) P
A
(s

A
, s

B
) (1)
for all s

A
S
A
, s

B
S
B
. Analogously we can dene a dominant strategy for Bob.
A pair (s
A
, s
B
) is said to be an equilibrium in dominant strategies if s
A
and s
B
are
the players respective dominant strategies. A combination of strategies (s
A
, s
B
) is
called a Nash equilibrium if
P
A
(s
A
, s
B
) P
A
(s

A
, s
B
), (2a)
P
B
(s
A
, s
B
) P
B
(s
A
, s

B
) (2b)
for all s

A
S
A
, s

B
S
B
. A pair of strategies (s
A
, s
B
) is called Pareto optimal, if it
is not possible to increase one players pay-off without lessening the pay-off of the
other player.
Asolution in dominant strategies is the strongest solution concept for a non-zero
sum game. In the Prisoners Dilemma defection is the dominant strategy, as it is
favourable regardless what strategy the other party picks. Typically, however, the
optimal strategy depends on the strategy chosen by the other party. A Nash equi-
librium implies that neither player has a motivation to unilaterally alter his or her
strategy from this equilibrium solution, as this action will lessen his or her pay-off.
Given that the other player will stick to the strategy corresponding to the equi-
librium, the best result is achieved by also playing the equilibrium solution. The
concept of Nash equilibria is of paramount importance to studies of non-zero-sum
games. It is, however, only an acceptable solution concept if the Nash equilib-
rium is unique. For games with multiple equilibria the application of a hierarchy
of natural renement concepts may nally eliminate all but one of the Nash equi-
libria. Note that a Nash equilibrium is not necessarily efcient. In the Prisoners
Dilemma for example there is a unique equilibrium, but it is not Pareto optimal,
meaning that there is another outcome which would make both players better off.
III. TWO-QUBIT QUANTUM GAMES
In the subsequent investigation we turn to specic games where the classical ver-
sion of the game is faithfully entailed in the quantum game. In a quantum version
3
of a binary choice game two qubits are prepared by a arbiter in a particular initial
state, the qubits are sent to the two players who have physical instruments at hand
to manipulate their qubits in an appropriate manner. Finally, the qubits are sent
back to the arbiter who performs a measurement to evaluate the pay-off. For such
a bi-partite quantum game the system of interest is a quantum system with under-
lying Hilbert space H = H
A
H
B
, H
A
= H
B
= C
2
, and associated state space
o(H). Quantum strategies s
A
and s
B
of Alice and Bob are local quantum opera-
tions acting in H
A
and H
B
respectively [16]. That is, Alice and Bob are restricted to
implement their respective quantum strategy s
A
and s
B
on their qubit only. In this
step they may choose any quantum strategy that is included in the set of strategies
S. They are both well aware of the set S, but they do not know which particular
quantum strategy the other party would actually implement. As the application of
both quantum strategies amounts to a map s
A
s
B
: o(H) o(H), after execution
of the moves the system is in the state
= (s
A
s
B
)(). (3)
Particularly important will be unitary operations s
A
and s
B
. They are associated
with unitary operators U
A
and U
B
, written as s
A
U
A
and s
B
U
B
. In this case
the nal state is given by
= (U
A
U
B
)(U
A
U
B
)

. (4)
Fromnowon both the sets of strategies of Alice and Bob and the pay-off functionals
are taken to be identical, that is,
S
A
= S
B
= S and P
A
= P
B
= P, (5)
such that both parties face the same situation.
The quantum game = (C
2
C
2
, , S, S, P, P) can be played in the following
way: The initial state is taken to be a maximally entangled state in the respective
state space. In order to be consistent with Ref. [6] let = [)[ with
[) = ([00) + i[11))/

2, (6)
where the rst entry refers to H
A
and the second to H
B
. The two qubits are for-
warded to the arbiter who performs a projective selective measurement on the nal
state with Kraus operators
CC
,
CD
,
DC
, and
DD
, where

CC
= [
CC
)
CC
[, [
CC
) = ([00) + i[11))/

2, (7a)

CD
= [
CD
)
CD
[, [
CD
) = ([01) i[10))/

2, (7b)

DC
= [
DC
)
DC
[, [
DC
) = ([10) i[01))/

2, (7c)

DD
= [
DD
)
DD
[, [
DD
) = ([11) + i[00))/

2. (7d)
According to the outcome of the measurement, a pay-off of A
CC
, A
CD
, A
DC
, or
A
DD
is given to Alice, Bob receives B
CC
, B
CD
, B
DC
, or B
DD
. The utility function-
als, also referred to as expected pay-off of Alice and Bob, read
P
A
(s
A
, s
B
) = A
CC
tr[
CC
] + A
CD
tr[
CD
] + A
DC
tr[
DC
] + A
DD
tr[
DD
], (8a)
P
B
(s
A
, s
B
) = B
CC
tr[
CC
] + B
CD
tr[
CD
] + B
DC
tr[
DC
] + B
DD
tr[
DD
]. (8b)
It is important to note that the Kraus operators are chosen in such a way that the
classical game is fully entailed in the quantum game: The classical strategies C and
D are associated with particular unitary operations,
C

1 0
0 1

, D

0 1
1 0

. (9b)
4
C does not change the state at all, D implements a spin-ip. If both parties
stick to these classical strategies, Eq. (8a) and Eq. (8b) guarantee that the expected
pay-off is exactly the pay-off of the corresponding classical game dened by the
numbers A
CC
, A
CD
, A
DC
, A
DD
, B
CC
, B
CD
, B
DC
, and B
DD
. E.g., if Alice plays C
and Bob chooses D, the state after implementation of the strategies is given by
= (C D)() = [
CD
)
CD
[, (10b)
such that Alice obtains A
CD
units and Bob B
CD
units pay-off (see Fig. 1). In this
way the peculiarities of strategic moves in the quantum domain can be adequately
studied. The players may make use of additional degrees of freedom which are
not available with randomisation of the classical strategies, but they can also stick
to mere classical strategies. This scheme can be applied to any two player binary
choice game and is to a high extent canonical.
A. Prisoners Dilemma
We now investigate the solution concepts for the quantum analogue of the Pris-
oners Dilemma (see Fig. 1) [17],
A
CC
= B
CC
= 3, A
DD
= B
DD
= 1, (11a)
A
CD
= B
DC
= 0, A
DC
= B
CD
= 5. (11b)
In all of the following sets of allowed strategies S the classical options (to defect
and to cooperate) are included. Several interesting sets of strategies and concomi-
tant solution concepts will at this point be studied. The rst three subsections
involve local unitary operations only, while in the last subsection other quantum
operations are considered as well.
1. One-parameter set of strategies.
The rst set of strategies S
(CL)
involves quantum operations s
A
and s
B
which
are local rotations with one parameter. The matrix representation of the corre-
sponding unitary operators is taken to be
U() =

cos(/2) sin(/2)
sin(/2) cos(/2)

(12)
with [0, ]. Hence, in this simple case, selecting strategies s
A
and s
B
amounts
to choosing two angles
A
and
B
. The classical strategies of defection and coop-
eration are also included in the set of possible strategies, C U(0), D U(). An
analysis of the expected pay-offs P
A
and P
B
,
P
A
(
A
,
B
) = 3[ cos(
A
/2) cos(
B
/2)[
2
+ 5[ cos(
B
/2) sin(
A
/2)[
2
+ [ sin(
A
/2) sin(
B
/2)[
2
, (13a)
P
B
(
A
,
B
) = 3[ cos(
A
/2) cos(
B
/2)[
2
+ 5[ sin(
B
/2) cos(
A
/2)[
2
+ [ sin(
A
/2) sin(
B
/2)[
2
, (13b)
shows that this game is the classical Prisoners Dilemma game [6]. The pay-off
functions are actually identical to the analogous functions in the ordinary Prison-
ers Dilemma with mixed (randomised) strategies, where cooperation is chosen
with the classical probability p = cos
2
(/2). The inequalities
P
A
(D, s
B
) P
A
(s
A
, s
B
), (14a)
P
B
(s
A
, D) P
B
(s
A
, s
B
) (14b)
5
hold for all s
A
, s
B
S
(CL)
, therefore, (D, D) is an equilibrium in dominant strate-
gies and thus the unique Nash equilibrium. As explained in the introduction this
equilibrium is far from being efcient, because P
A
(D, D) = P
B
(D, D) = 1 instead
of the Pareto optimal pay-off which would be 3.
2. Two-parameter set of strategies
A more general set of strategies is the following two-parameter set S
(TP)
. The
matrix representation of operators corresponding to quantum strategies from this
set is given by
U(, ) =

e
i
cos(/2) sin(/2)
sin(/2) e
i
cos(/2)

(15)
with [0, ] and [0, /2]. Selecting a strategy s
A
, s
B
then means choosing
appropriate angles
A
,
A
and
B
,
B
. The classical pure strategies can be realised
as
C U(0, 0) and D U(, 0). (16)
This case has also been considered in Ref. [6]. The expected pay-off for Alice, e.g.,
explicitly reads
P
A
(
A
,
A
,
B
,
B
) = 3 [cos(
A
+
B
) cos(
A
/2) cos(
B
/2)[
2
(17)
+ 5 [sin(
A
) cos(
A
/2) sin(
B
/2) cos(
B
) cos(
B
/2) sin(
A
/2)[
2
+[sin(
A
+
B
) cos(
A
/2) cos(
B
/2) + sin(
A
/2) sin(
B
/2)[
2
.
It turns out that the previous Nash equilibrium (D, D) of S
(CL)
is no longer an
equilibrium solution, as both players can benet from deviating from D. However,
concomitant with the disappearance of this solution another Nash equilibrium has
emerged, given by (Q, Q). The strategy Q is associated with a matrix
Q U(0, /2) =

i 0
0 i

. (18)
This Nash equilibrium is unique [6] and serves as the only acceptable solution of
the game. The astonishing fact is that P
A
(Q, Q) = P
B
(Q, Q) = 3 (instead of 1) so
that the Pareto optimum is realised. No player could gain without lessening the
other players expected pay-off. In this sense one can say that the dilemma of the
original game has fully disappeared. In the classical game only mutual coopera-
tion is Pareto optimal, but this pair of strategies does not correspond to a Nash
equilibrium.
3. General unitary operations
One can generalise the previous setting to the case where Alice and Bob can im-
plement operations s
A
and s
B
taken from S
(GU)
, where S
(GU)
is the set of general
local unitary operations. Here, it could be suspected that the solution becomes
more efcient the larger the sets of allowed operations are. But this is not the case.
The previous Pareto optimal unique Nash equilibrium (Q, Q) ceases to be an equi-
librium solution if the set is enlarged: For any strategy s
B
S
(GU)
there exists an
optimal answer s
A
S
(GU)
resulting in
(s
A
s
B
)() = [
DC
)
DC
[, (19)
6
with given in Eq. (6). That is, for any strategy of Bob s
B
there is a strategy s
A
of
Alice such that
P
A
(s
A
, s
B
) = 5 and P
B
(s
A
, s
B
) = 0 : (20)
Take
s
A

a b
c d

, s
B

ib a
d ic

, (21)
where a, b, c, d are appropriate complex numbers. Given that Bob plays the strat-
egy s
B
associated with a particular Nash equilibrium (s
A
, s
B
), Alice can always
apply the optimal answer s
A
to achieve the maximal possible pay-off. However,
the resulting pair of quantum strategies can not be an equilibrium since again, the
game being symmetric, Bob can improve his pay-off by changing his strategy to
his optimal answer s

B
. Hence, there is no pair (s
A
, s
B
) of pure strategies with the
property that the players can only lose from unilaterally deviating from this pair
of strategies.
Yet, there remain to be Nash equilibria in mixed strategies which are much
more efcient than the classical outcome of the equilibrium in dominant strate-
gies P
A
(D, D) = P
B
(D, D) = 1. In a mixed strategy of Alice, say, she selects a
particular quantum strategy s
A
(which is also called pure strategy) from the set of
strategies S
A
with a certain classical probability. That is, mixed strategies of Alice
and Bob are associated with maps of the form
=

i,j
p
(i)
A
p
(j)
B
(U
(i)
A
U
(j)
B
)(U
(i)
A
U
(j)
B
)

, (22)
p
(i)
A
, p
(i)
B
[0, 1], i, j = 1, 2, ..., N, with

i
p
(i)
A
=

j
p
(j)
B
= 1. (23)
U
(i)
A
and U
(j)
B
are local unitary operators corresponding to pure strategies s
(i)
A
and
s
(j)
B
.
The map given by Eq. (27) acts in H
A
and H
A
as a doubly stochastic map, that is,
as a completely positive unital map [18]. As a result, the nal reduced states tr
B
[]
and tr
A
[] must be more mixed than the reduced initial states tr
B
[] and tr
A
[] in
the sense of majorisation theory [19]. As the initial state is a maximally entangled
state, all accessible states after application of a mixed strategy of Alice and Bob are
locally identical to the maximally mixed state 1/dim(H
A
) = 1/dim(H
B
), which is
a multiple of 1.
The following construction, e.g., yields an equilibrium in mixed quantum strate-
gies: Allow Alice to choose from two strategies s
(1)
A
and s
(2)
A
with probabilities
p
(1)
A
= 1/2 and p
(2)
A
= 1/2, while Bob may take s
(1)
B
or s
(2)
B
, with
s
(1)
A

1 0
0 1

, s
(2)
A

i 0
0 i

, (24a)
s
(1)
B

0 1
1 0

, s
(2)
B

0 i
i 0

. (24b)
His probabilities are also given by p
(1)
B
= 1/2 and p
(2)
B
= 1/2. The quantum strate-
gies of Eq. (24a) and Eq. (24b) are mutually optimal answers and have the property
that
P
A
(s
(i)
A
, s
(i)
B
) = 0, P
B
(s
(i)
A
, s
(i)
B
) = 5, (25a)
P
A
(s
(i)
A
, s
(3i)
B
) = 5, P
B
(s
(i)
A
, s
(3i)
B
) = 0, (25b)
7
for i = 1, 2. Due to the particular constraints of Eq. (25a) and Eq. (25b) there exists
no other mixed strategy for Bob yielding a better pay-off than the above mixed
strategy, given that Alice sticks to the equilibrium strategy. This can be seen as
follows. Let Alice use this particular mixed quantum strategy as above and let Bob
use any mixed quantum strategy
s
(1)
B
, ..., s
(N)
B
(26)
together with p
(1)
A
, ..., p
(N)
A
. The nal state after application of the strategies is
given by the convex combination
=

i=1,2

j
p
(i)
A
p
(j)
B
(s
(i)
A
s
(j)
B
)(), (27)
This convex combination can only lead to a smaller expected pay-off for Bob than
the optimal pure strategy s
(k)
B
in Eq. (26), k 1, ..., N. Such optimal pure strate-
gies are given by s
(1)
B
and s
(2)
B
as in Eq. (24b) leading to an expected pay-off for
Bob of P
B
(s
A
, s
B
) = 2.5; there are no pure strategies which achieve a larger ex-
pected pay-off. While both pure strategies s
(1)
B
and s
(2)
B
do not correspond to an
equilibrium, the mixed strategy where s
(1)
B
and s
(2)
B
are chosen with p
(1)
B
= 1/2
and p
(2)
B
= 1/2 actually does. Nash equilibria consist of pairs of mutually opti-
mal answers, and only for this choice of Bob the original mixed quantum strategy
of Alice is her optimal choice, as the same argument applies also to her, the game
being symmetric.
This Nash equilibrium is however not the only one. There exist also other four-
tuples of matrices than the ones presented in Eq. (24a) and Eq. (24b) that satisfy Eq.
(25a) and Eq. (25b). Such matrices can be made out by appropriately rotating the
matrices of Eq. (24a) and Eq. (24b). In the light of the fact that there is more than
one equilibrium it is not obvious which Nash equilibrium the players will realise.
It is at rst not even evident whether a Nash equilibrium will be played at all. But
the game theoretical concept of the focal point effect [20,2] helps to resolve this issue.
To explore the general structure of any Nash equilibrium in mixed strategies we
continue as follows: let
U
(1)
A
, ..., U
(N)
A
(28)
together with p
(1)
A
, ..., p
(N)
A
specify the mixed strategy pertinent to a Nash equilib-
rium of Alice. Then there exists a mixed strategy U
(1)
B
, ..., U
(N)
B
, p
(1)
B
, ..., p
(N)
B
of Bob
which rewards Bob with the best achievable pay-off, given that Alice plays this
mixed strategy. Yet, the pair of mixed strategies associated with
QU
(1)
A
Q

, ..., QU
(N)
A
Q

, QU
(1)
B
Q

, ..., QU
(N)
B
Q

(29)
with p
(1)
A
, ..., p
(N)
A
, p
(1)
B
, ..., p
(N)
B
is another Nash equilibrium. This equilibrium leads
to the same expected pay-off for both players, and is fully symmetric to the previ-
ous one. Doubly applying Q as QQU
(1)
A
Q

, ..., QQU
(N)
A
Q

results again into a

situation with equivalent strategies as the original ones. For a given Nash equilib-
rium as above the one specied by Eq. (29) will be called dual equilibrium.
However, there is a single Nash equilibrium (R, R) which is the only one which
gives an expected pay-off of P
A
(R, R) = P
B
(R, R) = 2.25 and which is identical to
its dual equilibrium: it is the simple map
= 1/dim(H). (30)
Indeed, there exist probabilities p
(1)
A
, ..., p
(N)
A
and unitary operators U
(1)
A
, ..., U
(N)
A
such that

i
p
(i)
A
(U
(i)
A
1)(U
(i)
A
1)

= 1/dim(H) [19]. If Alice has already selected

8
s
A
= R, the application of s
B
= R will not change the state of the quantum system
any more.
Assume that Eq. (28) and Eq. (29) are associated with equivalent quantum strate-
gies. This means that they have to produce the same expected pay-off for all quan-
tum strategies s
B
of Bob. If Alice and Bob apply s
A
s
B
they get an expected
pay-off according to Eq. (8a) and Eq. (8b); if Alice after implementation of s
A
ma-
nipulates the quantum system by applying the local unitary operator Q 1, they
obtain
P

A
(s
A
, s
B
) = A
DD
tr[
CC
] + A
DC
tr[
CD
] + A
CD
tr[
DC
] + A
CC
tr[
DD
], (31a)
P

B
(s
A
, s
B
) = B
DD
tr[
CC
] + B
DC
tr[
CD
] + B
CD
tr[
DC
] + B
CC
tr[
DD
]. (31b)
The only s
A
with the property that P

A
(s
A
, s
B
) = P
A
(s
A
, s
B
) and P

B
(s
A
, s
B
) =
P
B
(s
A
, s
B
) for all s
B
is the map given by Eq. (30).
In principle, any Nash equilibrium may become a self-fullling prophecy if the
particular Nash equilibrium is expected by both players. It has been pointed out
that in a game with more than one equilibrium, anything that attracts the players
attention towards one of the equilibria may make them expect and therefore realise
it [20]. The corresponding focal equilibrium [2] is the one which is conspicuously
distinguished from the other Nash equilibria. In this particular situation there is
indeed one Nash equilibrium different from all the others: it is the one which is
equivalent to its dual equilibrium, the map which simply maps the initial state
on the maximally mixed state. For all other expected pay-offs both players are
ambivalent between (at least) two symmetric equilibria. The expected pay-off the
players will receive in this focal equilibrium
P
A
(R, R) = P
B
(R, R) = 2.25 (32)
is not fully Pareto optimal, but it is again much more efcient than the classically
achievable outcome of 1 [21].
4. Completely positive trace-preserving maps corresponding to local operations
In this scenario both Alice and Bob may perform any operation that is allowed
by quantum mechanics. That is, the set of strategies S
(CP)
is made up of (s
A
, s
B
),
where both s
A
and s
B
correspond to a completely positive trace-preserving map
(s
A
s
B
)() =

j
(A
i
B
j
)(A
i
B
j
)

(33)
corresponding to a local operation, associated with Kraus operators A
i
and B
j
with
i, j = 1, 2, ... . The trace-preserving property requires

i
A

i
A
i
= 1 and

i
B

i
B
i
=
1. This case has already been mentioned in Ref. [6]. The quantum strategies s
A
and s
B
do no longer inevitably act as unital maps in the respective Hilbert spaces
as before. In other words, the reduced states of Alice and Bob after application of
the quantum strategy are not necessarily identical to the maximally mixed state
1/dim(H
A
).
As already pointed out in Ref. [6], the pair of strategies (Q, Q) of the two-
parameter set of strategies S
(TP)
is again no equilibrium solution. It is straight-
forward to prove that the Nash equilibria of the type of Eq. (24a) and Eq. (24b) of
mixed strategies with general local unitary operations are, however, still present,
and each of these equilibria yields an expected pay-off of 2.5.
In addition, as strategies do no longer have to be locally unital maps, it is not
surprising that new Nash equilibria emerge: Alice and Bob may, e.g., perform a
measurement associated with Kraus operators
A
1
= [0)0[ A
2
= [1)1[, B
1
= D[0)0[ B
2
= D[1)1[. (34)
9
This operation yields a nal state = (s
A
s
B
)() = ([01)01[+[10)10[)/2. Clearly
neither Alice nor Bob can gain from unilaterally deviating from their strategy.
One can nevertheless argue as in the previous case. Again, all Nash equilibria
occur at least in pairs. First, there are again the dual equilibria from S
(GU)
. Sec-
ond, there are Nash equilibria (s
A
, s
B
), s
A
,= s
B
, with the property that (s
B
, s
A
)
is also a Nash equilibrium yielding the same expected pay-off. The only Nash
equilibrium invariant under application of Q and exchange of the strategies of the
players is again (R, R) dened in the previous subsection, which yields a pay-off
P
A
(R, R) = P
B
(R, R) = 2.25. This is the solution of the game is the most general
case. While both players could in principle do better (as the solution lacks Pareto
optimality), the efciency of this focal equilibrium is much higher than the equilib-
rium in dominant strategies of the classical game. Hence, also in this most general
case both players gain from using quantum strategies.
This study shows that the efciency of the equilibrium the players can reach in
this game depends on the actions the players may take. One feature, however is
present in each of the considered sets: both players can increase their expected
pay-offs drastically by resorting to quantum strategies.
B. Chicken
In the previous classical game the Prisoners Dilemma an unambiguous so-
lution can be specied consisting of a unique Nash equilibrium. However, this
solution was not efcient, thus giving rise to the dilemma. The situation of the
players in the Chicken game [2,3],
A
CC
= B
CC
= 6, A
CD
= B
DC
= 8, (35a)
A
DC
= B
CD
= 2, A
DD
= B
DD
= 0, (35b)
can be described by the matrix of Fig. 3.
B
s
s
A
Alice
Bob
(6,6)
(8,2) (0,0)
C
(2,8) C
D
D
FIG. 3. The pay-off matrix of the so-called Chicken game.
This game has two Nash equilibria (C, D) and (D, C): it is not clear how to antic-
ipate what the players decision would be. In addition to the two Nash equilibria
in pure strategies there is an equilibrium in mixed strategies, yielding an expected
pay-off 4 [2].
In order to investigate the new features of the game if superpositions of classical
strategies are allowed for, three set of strategies are briey discussed:
1. One-parameter set of strategies
Again, we consider the set of strategies S
(CL)
of one-dimensional rotations. The
strategies s
A
and s
B
are associated with local unitary operators
U() =

cos(/2) sin(/2)
sin(/2) cos(/2)

(36)
10
with [0, ],
C U(0) =

1 0
0 1

, D U() =

0 1
1 0

. (37)
Then as before, the quantum game yields the same expected pay-off as the classical
game in randomised strategies. This means that still two Nash equilibria in pure
strategies are present.
2. Two-parameter set of strategies
The players can actually take advantage of an additional degree of freedom
which is not accessible in the classical game. If they may apply unitary operations
from S
(TP)
of the type
U(, ) =

e
i
cos(/2) sin(/2)
sin(/2) e
i
cos(/2)

(38)
with [0, ] and [0, /2] the situation is quite different than with S
(CL)
.
(C, D) and (C, D) with C U(0, 0) and D U(, 0) are no longer equilibrium
solutions. E.g., given that s
A
= D the pair of strategies (D, Q) with Q U(0, /2)
yields a better expected pay-off for Bob than (D, C), that is to say P
B
(D, Q) = 8,
P
B
(D, C) = 2. In fact (Q, Q) is now the unique Nash equilibrium with P
A
(Q, Q) =
P
B
(Q, Q) = 6, which follows from an investigation of the actual expected pay-
offs of Alice and Bob analogous to Eq. (17). This solution is not only the unique
acceptable solution of the game, but it is also an equilibrium that is Pareto optimal.
This contrasts very much with the situation in the classical game, where the two
equilibria were not that efcient.
3. Completely positive trace-preserving maps corresponding to local operations
As in the considerations concerning the Prisoners Dilemma game, more than
one Nash equilibrium is present, if both players can take quantum strategies from
the set S
(CP)
, and all Nash equilibria emerge at least in pairs as above. The focal
equilibrium is given by (R, R), resulting in a pay-off of P
A
(R, R) = P
B
(R, R) = 4,
which is the same as the mixed strategy of the classical game.
IV. SUMMARY AND CONCLUSION
In these lecture notes the idea of implementing quantum operations as strategic
moves in a game is explored [6]. In detail, we investigated games which could
be conceived as a generalisation into the quantum domain of a two player bi-
nary choice game. As a toy model for more complex scenarios we studied quan-
tum games where the efciency of the equilibria attainable when using quan-
tum strategies could be contrasted with the efciency of solutions in the cor-
responding classical game. We investigated a hierarchy of quantum strategies
S
(CL)
S
(TP)
S
(GU)
S
(CP)
. Again [6,7], we found superior performance
of quantum strategies as compared to classical strategies.
The nature of a game is determined by the rules of the game. In particular, the
appropriate solution concept depends on the available strategic moves. Obviously,
a player cannot make a meaningful choice without knowing the options at his or
her disposal. So it comes to no surprise that also the actual achievable pay-off in
such a game depends on the set of allowed strategies. Roughly speaking, one can
11
say that the possibility of utilising strategies which are not feasible in the analogous
classical game implicates a signicant advantage. In the models studied in detail
two kinds of dilemmas were resolved: (i) On the one hand there are quan-
tum games with an efcient unambiguous solution, while in the classical analogue
only an inefcient equilibrium can be identied. By taking advantage of appropri-
ate quantum strategies much more efcient equilibria could be reached. In certain
sets of strategies even a maximally efcient solution the Pareto optimum was at-
tainable. (ii) On the other hand, there exist quantum games with a unique solution
with a classical equivalent which offers two Nash equilibria of the same quality.
This paper deals with simple set-ups in which information is exchanged
quantum-mechanically. The emphasis was to examine how situations where
strategies are identied with quantum operations applied on quantum mechani-
cal carriers of information are different from the classical equivalent. It is the hope
that these investigations may enable us to better understand competitive structures
in a game theoretical sense in applications of quantum information theory.
V. ACKNOWLEDGEMENTS
We would like to thank Maciej Lewenstein, Onay Urfaloglu, Joel Sobel, Tom
Cover, Charles H. Bennett, Martin B. Plenio, and Uta Simon for helpful sugges-
tions. We also acknowledge fruitful discussions with the participants of the A2
Consortial Meeting. This work was supported by the European Union and the
DFG.
[1] J. von Neumann and O. Morgenstern, The Theory of Games and Economic Behaviour
(Princeton University Press, Princeton, 1947).
[2] R.B. Myerson, Game Theory: An Analysis of Conict (MIT Press, Cambridge, 1991).
[3] W. Poundstone, Prisoners Dilemma. John von Neumann, Game Theory, and the Puzzle of the
Bomb (Doubleday, New York, 1992).
[4] M.D. Davis, Game Theory. A Nontechnical Introduction (Dover, New York, 1970).
[5] A.W. Tucker, unpublished (1950).
[6] J. Eisert, M. Wilkens, and M. Lewenstein, Phys. Rev. Lett. 83, 3077 (1999).
[7] D. Meyer, Phys. Rev. Lett. 82, 1052 (1999).
[8] P. Ball, Nature, Science Update 991021-3 (1999); G.P. Collins, Scientic American, Jan-
uary issue (2000).
[9] L. Goldenberg, L. Vaidman, and S. Wiesner, Phys. Rev. Lett. 82, 3356 (1999).
[10] M.B. Plenio and V. Vedral, Contemp. Phys. 39, 431 (1998).
[11] R.F. Werner, Phys. Rev. A 58, 1827 (1998).
[12] C.H. Bennett and G. Brassard, in Proceedings of the IEEE International Conference on Com-
puters, Systems, and Signal Processing, Bangalore, India (IEEE, New York, 1984); C.H. Ben-
nett, F. Bessette, G. Brassard, L. Salvail, and J. Smolin, J. Crypto. 5, 3 (1992).
[13] P.W. Shor, SIAM J. Comput. 26, 1484 (1997).
[14] A. Ekert, Phys. Rev. Lett. 67, 661 (1991).
[15] E.g., Alice may allow a coupling of the original quantum system to an auxiliary quan-
tum system and let the two unitarily interact. After performing a projective measure-
ment on the composite system she could eventually consider the original system again
by taking a partial trace with respect to the auxiliary part.
[16] The quantum strategies sA 1 and 1 sB are in the following identied with sA and
sB, respectively.
[17] Froma game theoretical viewpoint, any positive numbers satisfying the symmetry con-
ditions ACC = BCC, ADD = BDD, ACD = BDC, ADC = BCD and the inequalities
12
ADC > ACC > ADD > ACD and ACC (ACD + ADC)/2 dene a (strong) Prisoners
Dilemma.
[18] P.M. Alberti and A. Uhlmann, Stochasticity and Partial Order: Doubly Stochastic Maps and
Unitary Mixing (VEB Deutscher Verlag der Wissenschaften, Berlin, 1982).
[19] A.W. Marshall and I. Olkin, Inequalities: Theory of Majorisation and its Applications (Aca-
demic Press, New York, 1979);
[20] T.C. Schelling, The Strategy of Conict (Harvard University Press, Cambridge (MA),
1960).
[21] In the classical game both players could also play C and D with probabilities p = 1/2
yielding the same expected pay-off of 2.25 for both players, but this pair of mixed
strategies would be no equilibrium solution, as any player could benet from simply
choosing the dominant strategy D.
13