9.4.2 More Than Two Players

The ideas of Section 9.4.1 easily generalize to any number of players. The main difficulty is that complicated notation makes the concepts appear more difficult. Keep in mind, however, that there are no fundamental differences. A nonzero-sum game with players is formulated as follows.

- A set of players, , , , .
- For each player
, a finite, nonempty set called
the
*action space*for . For convenience, assume that each is a set of consecutive integers from to . Each is referred to as an*action*of . - For each player
, a function,
called the
*cost function for*.

The Nash equilibrium idea generalizes by requiring that each
experiences no regret, given the actions chosen by the other
players. Formally, a set
of actions is said
to be a (deterministic) *Nash equilibrium* if

for every .

For , any of the situations summarized at the end of Section
9.4.1 can occur. There may be no deterministic Nash
equilibria or multiple Nash equilibria. The definition of an
admissible Nash equilibrium is extended by defining the notion of *better* over -dimensional cost vectors. Once again, the minimal
vectors with respect to the resulting partial ordering are considered
*admissible* (or *Pareto optimal*). Unfortunately, multiple
admissible Nash equilibria may still exist.

It turns out that for any game under Formulation 9.9, there exists a randomized Nash equilibrium. Let denote a randomized strategy for . The expected cost for each can be expressed as

Let denote the space of randomized strategies for
. An
assignment,
, of randomized strategies to all
of the players is called a *randomized Nash
equilibrium* if

for all .

As might be expected, computing a randomized Nash equilibrium for is even more challenging than for . The method of Example 9.20 can be generalized to -player games; however, the expressions become even more complicated. There are equations, each of which appears linear if the randomized strategies are fixed for the other players. The result is a collection of -degree polynomials over which optimization problems must be solved simultaneously.

Now some costs will be defined. For convenience, let

for each . Let the costs be

(9.83) | ||||

There are two deterministic Nash equilibria, which yield the costs
and . These can be verified using
(9.79). Each player is satisfied with the outcome given
the actions chosen by the other players. Unfortunately, both Nash
equilibria are both admissible. Therefore, some collaboration would
be needed between the players to ensure that no regret will occur.

Steven M LaValle 2012-04-20