Artificial Intelligence - foundations of computational agents -- 10.2.1 Normal Form of a Game

Third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including the full text).

10.2.1 Normal Form of a Game

The most basic representation of games is the strategic form of a game or a normal-form game. The strategic form of a game consists of

a finite set I of agents, typically identified with the integers I={1,...,n}.
a set of actions A for each agent i∈I. An assignment of an action in A_i to each agent i∈I is an action profile. We can view an action profile as a tuple ⟨a₁,...,a_n⟩, which specifies that agent i carries out action a_i.
a utility function u_i for each agent i∈I that, given an action profile, returns the expected utility for agent i given the action profile.

The joint action of all the agents (an action profile) produces an outcome. Each agent has a utility over each outcome. The utility for an agent is meant to encompass everything that the agent is interested in, including fairness and societal well-being. Thus, we assume that each agent is trying to maximize its own utility, without reference to the utility of other agents.

Example 10.1: The game rock-paper-scissors is a common game played by children, and there is even a world championship of rock-paper-scissors. Suppose there are two agents (players), Alice and Bob. There are three actions for each agent, so that

A_Alice=A_Bob={rock,paper,scissors}.

For each combination of an action for Alice and an action for Bob there is a utility for Alice and a utility for Bob.

		Bob
		rock	paper	scissors
	rock	0,0	-1,1	1,-1
Alice	paper	1,-1	0,0	-1,1
	scissors	-1,1	1,-1	0,0

Figure 10.1: Strategic form for the rock-paper-scissors game

This is often drawn in a table as in Figure 10.1. This is called a payoff matrix. Alice chooses a row and Bob chooses a column, simultaneously. This gives a pair of numbers: the first number is the payoff to the row player (Alice) and the second gives the payoff to the column player (Bob). Note that the utility for each of them depends on what both players do. An example of an action profile is ⟨scissors_Alice,rock_Bob⟩, where Alice chooses scissors and Bob chooses rock. In this action profile, Alice receives the utility of -1 and Bob receives the utility of 1. This game is a zero-sum game because one person wins only when the other loses.

This representation of a game may seem very restricted, because it only gives a one-off payoff for each agent based on single actions, chosen simultaneously, for each agent. However, the interpretation of an action in the definition is very general.

Typically, an "action" is not just a simple choice, but a strategy: a specification of what the agent will do under the various contingencies. The normal form, essentially, is a specification of the utilities given the possible strategies of the agents. This is why it is called the strategic form of a game.

In general, the "action" in the definition of a normal-form game can be a controller for the agent. Thus, each agent chooses a controller and the utility gives the expected outcome of the controllers run for each agent in an environment. Although the examples that follow are for simple actions, the general case has an enormous number of possible actions (possible controllers) for each agent.