Suppose there are two players, and , that each have to make a decision. Each has a finite set of actions, and , respectively. The set can be viewed as the ``replacement'' of from Formulation 9.3 by a set of actions chosen by a true opponent. Each player has a cost function, which is denoted as for . An important constraint for zero-sum games is
In light of (9.41) it is pointless to represent two cost functions. Instead, the superscript will be dropped, and will refer to the cost, , of . The goal of is to minimize . Due to (9.41), the goal of is to maximize . Thus, can be considered as a reward for , but a cost for .
A formulation can now be given:
Before discussing what it means to solve a zero-sum game, some additional assumptions are needed. Assume that the players know each other's cost functions. This implies that the motivation of the opponent is completely understood. The other assumption is that the players are rational, which means that they will try to obtain the best cost whenever possible. will not choose an action that leads to higher cost when a lower cost action is available. Likewise, will not choose an action that leads to lower cost. Finally, it is assumed that both players make their decisions simultaneously. There is no information regarding the decision of that can be exploited by , and vice versa.
Formulation 9.7 is often referred to as a matrix game because can be expressed with a cost matrix, as was done in Section 9.2. Here the matrix indicates costs for and , instead of the robot and nature. All of the required information from Formulation 9.7 is specified by a single matrix; therefore, it is a convenient form for expressing zero-sum games.
Steven M LaValle 2012-04-20