Algorithmic Game Theory
Syllabus
Notes
Lecture 2
At the core of the course is the concept of a rational agent.
In this lecture, we will discuss a core theorem in economics, that will justify expected utility maximization, the main tool/assumption we’ll use throughout the course
Outcomes and Lotteries
- Let be a set of outcomes
A lottery is a distribution over outcomes
- We write and for the set of lotteries on
Ordinal Preferences
- A preferences relation indicates the relative preference of an agent for outcomes and lotteries
We write:
- if the agent weakly prefers to
- if the agent strictly prefers to
- if the agent is indifferent between and
- These extend to lotteries as well if the agent weakly prefers lottery to
Cardinal Preferences
- A utility function is a function
It represents a preference relation if
- A utility function expresses not only which of the outcomes is preferred, but by how much.
Ordinal vs Cardinal
- At first glance, cardinal utilities seem much stronger than ordinal utilities, but under some mild conditions, von Neumann and Morgenstern proved that ordinal utilities imply cardinal utilities
Axioms: Completeness and Transitivity
- Axiom 1 (completeness): For every pair of lotteries and :
- Axiom 2 (transitivity): For any lotteries :
In other words, the preference relation is a weak order
- This is important to prevent money pumps
- Axiom 3 (independence): For any lotteries and every :
- Axiom 3 (continuity): If for lotteries then there exists an such that
The von Neumann-Morgenstern Theorem [1947]
- A preference relation over lotteries satisfies completeness, transitivity, independence, and continuity iff there is a utility function over outcomes such that, for all lotteries and :
- Here, for
(Forward Direction)
The proof is constructive
- We will build a utility function (and then check that the expected utility reproduces )
- Lemma 1 (independence preserves indifference): If , then for every lottery and every :
- Proof: The cases and are immediate, so assume . Since , we have both and . Applying independence to each gives both mixture inequalities, which together are exactly indifference.
- Lemma 2 (independence preserves strict preference): If , then for every lottery and every :
- Proof: Suppose toward a contradiction that . Independence runs in both directions, so this would give , contradicting . Completeness implies that the mixture preference is strict.
- Lemma 3 (simultaneous substitution): Suppose for , and let be weights such that . Then:
- Proof: Apply Lemma 1 one component at a time, replacing by inside the mixture, then by , and so on. Every replacement preserves indifference, and transitivity chains the intermediate steps into one.
Step 1: A best and a worst outcome
Because is finite and is complete and transitive, the outcomes can be ranked, so there are outcomes with for every
- Call a best outcome and a worst outcome. Assume for now (we handle at the end)
For define the reference gamble
- As increases, we go from the worst to the best outcome
Lemma 4 (more probability on the best outcome is better): For all :
- Proof: The endpoints and are immediate, since is and is . Let . Applying Lemma 2 to gives .
- Now take , and set . Since , Lemma 2 gives . The LHS is just , and substituting on the RHS simplifies it to . So implies ; reversing the roles covers , and is the same lottery.
Step 2: Assign a utility number to every outcome
- Fix an outcome . Since is best and is worst,
- By continuity, there exists such that
- Define
- Uniqueness: Suppose two weights both work, and for . Transitivity implies . But by Lemma 4, if then , and if then — a contradiction. So
- Therefore, for every outcome there is a unique such that
with and
Step 3: Reduce an arbitrary lottery to a best-worst lottery
- Let . Then by definition, for weights with
- By equation (1), for every we have
- Using Lemma 3:
- Distributing and using :
- Define . Then
Step 4: Expected utility represents preferences
- Let be two arbitrary lotteries
- and
- By transitivity,
- By Lemma 4,
- So , i.e.
where preferences are expressed as expected utilities
Corner case ()
- For every , since is best and is worst,
- Since , transitivity gives , so , so , so , for every
- So for every lottery :
- Thus for every represents these preferences
What we’ve shown: given a preference relation over lotteries satisfying Completeness, Transitivity, Independence, and Continuity, there is a utility function over outcomes such that for all lotteries .
- It remains to show the converse: if there is a utility function that represents a preference relation, then the preferences satisfy the axioms (homework!)
Impact
- The von Neumann–Morgenstern theorem is one of the most (if not the most) influential theorems in Economics
Realistic?
- Are the axioms a realistic description of how people actually choose? Allais (1953) suggests not so much
Scenario 1:
- gives $1 million for sure
- gives $1 million w.p. 0.89, $5 million w.p. 0.1, and $0 w.p. 0.01
- Most people choose
Scenario 2:
- gives $1 million w.p. 0.11 and $0 w.p. 0.89
- gives $5 million w.p. 0.1 and $0 w.p. 0.9
- Most people choose
- But means , while means the opposite
- Question (homework?): which axiom is violated?