11.2 Representations of Games

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

11.2.1 Normal Form Games

The most basic representation of games is the normal form game also known as the strategic form game. A normal form game consists of

  • •

    a finite set I of agents, typically identified with the integers I={1,…,n}

  • •

    a set of actions Ai for each agent i∈I. An action profile is a tuple ⟨a1,…,an⟩, which specifies that agent i∈I carries out action ai, where ai∈Ai

  • •

    a utility function ui 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. Each agent is trying to maximize its own utility. The utility for an agent is meant to encompass everything that the agent is interested in, including fairness, altruism and societal well-being.

Example 11.1.

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

AA⁢l⁢i⁢c⁢e=AB⁢o⁢b={r⁢o⁢c⁢k,p⁢a⁢p⁢e⁢r,s⁢c⁢i⁢s⁢s⁢o⁢r⁢s}.

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
r⁢o⁢c⁢k p⁢a⁢p⁢e⁢r s⁢c⁢i⁢s⁢s⁢o⁢r⁢s
r⁢o⁢c⁢k 0,0 -1,1 1,-1
Alice p⁢a⁢p⁢e⁢r 1,-1 0,0 -1,1
s⁢c⁢i⁢s⁢s⁢o⁢r⁢s -1,1 1,-1 0,0
Figure 11.1: Normal form for the rock-paper-scissors game

This is often drawn in a table as in Figure 11.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 ⟨s⁢c⁢i⁢s⁢s⁢o⁢r⁢sA⁢l⁢i⁢c⁢e,r⁢o⁢c⁢kB⁢o⁢b⟩, 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.

More generally, 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.