Chapter 2

Decision Theory

This lecture is devoted to decision theory, which analyzes a single player’s decision. It
sets aside the strategic concerns, which are central to game theory, and focuses on how
a player makes his decision once he settles on how the other players behave. There are
many theories of decision making. This lecture describes the standard theory, known as
the expected utility theory, which will be assumed throughout the course. According to
this theory, a player has a utility function that maps the outcomes to real numbers and a
belief about the things that he does not know, which leads to a probability distribution
on the outcomes. It is assumed that the payers maximizes the expected value of the
utility function under the mentioned probability distribution.



2.1 Basic theory of choice
Consider a set X of alternatives. Alternatives are mutually exclusive in the sense that
one cannot choose two distinct alternatives at the same time. Moreover, the set of
feasible alternatives are exhaustive so that a player’s choices is always well-defined.1
We are interested in a player’s preferences on X. Such preferences are modeled
through a relation on X, which is simply a subset of X × X. A relation is said to
be complete if and only if, given any x, y ∈ X, either x y or y x. A relation is
1
This is a matter of modeling. For example consider a student who decides which courses to take.
Assume that the available options are Algebra and Biology. Then, the alternatives can be defined as
a = Algebra only, b = Biology only, ab = both Algebra and Biology, and n = neither Algebra nor
Biology.


9
10 CHAPTER 2. DECISION THEORY

said to be transitive if and only if, given any x, y, z ∈ X,

[x y and y z] ⇒ x z.

A relation is a preference relation if and only if it is complete and transitive. Given any
preference relation , one can define strict preference by

x y ⇐⇒ [x y and y x],

and the indifference ∼ by

x ∼ y ⇐⇒ [x y and y x].

Definition 2.1 (Ordinal Representation) A preference relation is represented by a
utility function u : X → R if

x y ⇐⇒ u(x) ≥ u(y) ∀x, y ∈ X. (OR)

This definition can be spelled out as follows. First, if u(x) ≥ u(y), then the player
finds alternative x as good as alternative y. Second, and conversely, if the player finds
x at least as good as y, then u (x) must be at least as high as u (y). In other words, the
player acts as if he is trying to maximize the value of u (·).
The following theorem states further that a relation needs to be a preference relation
in order to be represented by a utility function.

Theorem 2.1 Let X be finite. A relation can be presented by a utility function if and
only if it is complete and transitive. Moreover, if u : X → R represents , and if
f : R → R is a strictly increasing function, then f ◦ u also represents .

By the last statement, such utility functions are called ordinal, i.e., only the order
information is relevant.
In order to use this ordinal theory of choice, one needs to know the player’s prefer-
ences on the alternatives. As we have seen in the previous lecture, in game theory, a
player chooses between his strategies, and his preferences on his strategies depend on
the strategies played by the other players. Typically, a player does not know which
strategies the other players play. Therefore, game theoretical analysis builds on a theory
of decision-making under uncertainty.
2.2. DECISION-MAKING UNDER UNCERTAINTY 11

2.2 Decision-making under uncertainty
Consider a finite set Z of prizes, and let P be the set of all probability distributions
%
p : Z → [0, 1] on Z, where z∈Z p(z) = 1. These probability distributions are called
lotteries. A lottery can be depicted by a tree. For example, in Figure 2.2, Lottery 1
depicts a situation in which the player gets $10 with probability 1/2 (e.g. if a coin toss
results in Head) and $0 with probability 1/2 (e.g. if the coin toss results in Tail).

10
1/2
Lottery 1

1/2 0


In the above situation, the probabilities are given, as in a casino, where the probabili-
ties are generated by a machine. In most real-world situations, however, the probabilities
are not given to decision makers, who may have an understanding of whether a given
event is more likely than another given event. For example, in a game, a player is not
given a probability distribution regarding the other players’ strategies. Fortunately, it
has been shown by Savage (1954) under certain conditions that a player’s beliefs can be
represented by a (unique) probability distribution. Using these probabilities, one can
represent the decision makers’ alternatives with unknown consequences by lotteries.
We would like to have a theory that constructs a player’s preferences on the lotteries
from his preferences on the prizes. There are many of them. The most well-known–and
the most canonical and the most useful–one is the theory of expected utility maximiza-
tion by Von Neumann and Morgenstern.


Definition 2.2 (Cardinal Representation) A preference relation on P is said to
be represented by a von Neumann-Morgenstern utility function u : Z → R if and only if
' '
p q ⇐⇒ U (p) ≡ u(z)p(z) ≥ u(z)q(z) ≡ U (q) (2.1)
z∈Z z∈Z


for each p, q ∈ P .

This statement has two crucial parts:
12 CHAPTER 2. DECISION THEORY

1. U : P → R represents in the ordinal sense. That is, if U (p) ≥ U (q), then the
player finds lottery p as good as lottery q. And conversely, if the player finds p
at least as good as q, then U (p) must be at least as high as U (q). (This further
implies that is a preference relation; i.e. it is complete and transitive.)

2. The function U takes a particular form: for each lottery p, U (p) is the expected
%
value of u under p. That is, U (p) ≡ z∈Z u(z)p(z). In other words, the player acts
as if he wants to maximize the expected value of u. For instance, the expected
utility of Lottery 1 for the player is E(u(Lottery 1)) = 12 u(10) + 12 u(0).2

An essential property of von Neumann-Morgenstern utility representation is stated
in the next theorem:

Theorem 2.2 Von Neumann-Morgenstern utility representation is unique up to affine
transformations: u : Z → R and u˜ : Z → R represent the same preference relation on
P if and only if
u˜ = au + b

for some a > 0 and b ∈ R.

That is, a decision maker’s preferences do not change when we change his von
Neumann-Morgenstern (VNM) utility function by multiplying it with a positive number,
or adding a constant to it; but they do change when we transform it through a non-linear
transformation. In this sense, this representation is cardinal. Recall that, in ordinal rep-
resentation, the preferences do not change even if the transformation is non-linear, so
√
long as it is increasing. For instance, under certainty, v = u and u represent the same
√
preference relation, while (when there is uncertainty) the VNM utility function v = u
represents a very different set of preferences on the lotteries than those are represented
by u.
Another important property is that U is a linear function of probabilities. Indeed,
for Z = {z1 , z2 , . . . , zn }, a lottery p : Z → [0, 1] can be written as p = (p1 , . . . , pn ) where
p1 = p (z1 ), p2 = p (z2 ), . . . , and pn = p (zn ). With this formulation, the set P of all
lotteries is a subset of Rn , and U maps the subset P to the real line. Then, for constants
2
&
If Z were a continuum, like R, we would compute the expected utility of p by u(z)p(z)dz.
2.3. MODELING STRATEGIC SITUATIONS 13

u1 = u (z1 ), u2 = u (z2 ), . . . , and un = u (zn ), one can write U (p) as


U (p) ≡ u1 p1 + u2 p2 + · · · + un pn .


The linearity on probabilities embodies all of the properties assumed on preferences .
(For a detailed description of these properties, see Section 2.7 below.)




2.3 Modeling Strategic Situations

In a game, when a player chooses his strategy, in principle, he does not know what the
other players play. That is, he faces uncertainty about the other players’ strategies.
Hence, in order to define the player’s preferences, one needs to define his preference
under such uncertainty. In general, this makes modeling a difficult task. Fortunately,
using the utility representation above, one can easily describe these preferences in a
compact way.

Consider two players Alice and Bob with strategy sets SA and SB . If Alice plays
sA and Bob plays sB , then the outcome is (sA , sB ). Hence, it suffices to take the set of
outc...