Information Technology Reference
In-Depth Information
1x10
10
1x10
9
1
2
3
4
5
6
7
8
1x10
8
1x10
7
1x10
6
1x10
5
1x10
4
1x10
3
1x10
2
1x10
1
1x10
0
10
20
30
40
50
60
# strategies
Fig. 2.
Number of distinct profiles (log scale) of a symmetric game, for various numbers of players
and strategies
Definition 1.
Γ
=
is an
N
-player normal-form game
, with
strategy
set
S
i
the available strategies for player
i
, and the
payoff function
u
i
(
s
1
,...,s
N
)
giv-
ing the utility accruing to player
i
when players choose the
strategy profile (
s
1
,...,s
N
)
.
N,
{
S
i
}
,
{
u
i
()
}
Definition 2.
A normal-form game is
symmetric
if the players have identical strategy
spaces (
S
1
=
···
=
S
N
=
S
) and
u
i
(
s
i
,s
−i
)=
u
j
(
s
j
,s
−j
)
,for
s
i
=
s
j
and
s
−i
=
s
−j
for all
i, j
. Thus we can write
u
(
t, s
)
for the payoff to any player
playing strategy
t
when the remaining players play profile
s
. We denote a symmetric
game by the tuple
∈{
1
,...,N
}
N, S, u
()
.
Our central concept is that of a
reduced
game.
Definition 3.
Let
Γ
=
be an
N
-player symmetric game, with
N
=
pq
for
integers
p
and
q
.The
p
-player reduced version of
Γ
, written
Γ
N, S, u
()
↓
p
, is given by
p, S, u
()
,
where
u
i
(
s
1
,...,s
p
)=
u
q·i
(
s
1
,...
,s
2
,...
,...,s
p
,...
q
)
.
q
q
In other words, the payoff function in the reduced game is obtained by playing the
specified profile in the original
q
times.
The idea of a reduced game is to coarsen the profile space by restricting the degrees of
strategic freedom. Although the original set of strategies remains available, the number
of agents playing any strategy must be a multiple of
q
. Every profile in the reduced
game is one in the original game, of course, and any profile in the original game can
be reached from a profile contained in the reduced game by changing at most
p
(
q
−
1)
agent strategies.
The premise of our approach is that the reduced game will often serve as a good
approximation of the full game it abstracts. We know that in the worst case it does not.
In general, an equilibrium of the reduced game may be arbitrarily far from equilibrium
with respect to the full game, and an equilibrium of the full game may not have any
