Introducing more players

Involving more players poses no great difficulty, other than complicating the notation. For example, suppose that a set of $ n$ players, $ {{\rm P}_1}$, $ {{\rm P}_2}$, $ \ldots $, $ {{\rm P}_n}$, takes turns playing a game. Consider using a game tree representation. A stage is now stretched into $ n$ substages, in which each player acts individually. Suppose that $ {{\rm P}_1}$ always starts, followed by $ {{\rm P}_2}$, and so on, until $ {{\rm P}_n}$. After $ {{\rm P}_n}$ acts, then the next stage is started, and $ {{\rm P}_1}$ acts. The circular sequence of player alternations continues until the game ends. Again, many different information models are possible. For example, in the stage-by-stage model, each player does not know the action chosen by the other $ n-1$ players in the current stage. The bottom-up computation method can be used to compute Nash equilibria; however, the problems with nonuniqueness must once again be confronted.

A state-space formulation that generalizes Formulation 10.4 can be made by introducing action sets $ U^i(x)$ for each player $ {{\rm P}_i}$ and state $ x \in X$. Let $ u^i_k$ denote the action chosen by $ {{\rm P}_i}$ at stage $ k$. The state transition becomes

$\displaystyle x_{k+1} = f(x_k,u^1_k,u^2_k,\ldots,u^n_k) .$ (10.120)

There is also a cost function, $ L_i$, for each $ {{\rm P}_i}$. Value iteration, adapted to maintain multiple equilibria and cost vectors can be used to compute Nash equilibria.

Steven M LaValle 2012-04-20