Introduction to Decision Theory Choice Functions

(1)

Introduction to Decision Theory Choice Functions

Professor L. Blume

Cornell University

(2)

The Basic Framework

We begin by remembering basic preference theory. This is not the natural starting place for the subject, but it is common knowledge among us.

A setX of objects. The DM is expected to make a choice from X or from a subset of X, or is asked questions about preference, such as, isabetter than b?

(3)

The Basic Framework

A (strict) preference order. a≻b means that “ais better thanb. For instance,

Larry Blume Choice Functions 1

(4)

The Basic Framework

X ={a,b,c}. a≻b,b≻c anda≻c.

(5)

The Basic Framework

X ={a,b,c}. a≻b,b≻c andc≻a.

(6)

The Basic Framework

X ={a,b,c}. a≻b,b≻c andc≻a.

Recall theweak order. abifb6≻a. What is the relationship between ≻ and ?

(7)

Axioms

Asymmetry. For anyx andy in X, ifx ≻y then y6≻x.

Negative Transitivity. For anyx,y andz in X, ifx 6≻y and y 6≻z, then x 6≻z.

(8)

Axioms

Asymmetry. For anyx andy in X, ifx ≻y then y6≻x.

Negative Transitivity. For anyx,y andz in X, ifx 6≻y and y 6≻z, then x 6≻z.

Suppose X ={a,b,c}, thatb≻a anda≻c. Thenb?c.

(9)

Negative Transitivity

The familiar transitivity axiom is, x≻y and y≻z impliesx ≻z.

This is not the same thing.

Proposition.Asymmetry and negative transitivity imply transitivity.

(10)

Negative Transitivity

The familiar transitivity axiom is, x≻y and y≻z impliesx ≻z.

This is not the same thing.

Proposition.Asymmetry and negative transitivity imply transitivity.

Does Asymmetry and transitivity imply negative transitivity?

(11)

Preference Relations

Proposition. The binary relation ≻onX is negatively transitive iffx ≻z implies that, for all y, either x≻y or y ≻z.

Definition. A binary relation ≻is apreference relation iff it is asymmetric and negatively transitive.

(12)

Weak Preferences I

Definition. Forx andy in X,x isweakly preferred toy,x y, iff x ≻y andy 6≻x. The alternativex is indifferent to y,x∼y, iff 6x ≻y andy 6≻x.

(13)

Weak Preferences I

Definition. Forx andy in X,x isweakly preferred toy,x y, iff x ≻y andy 6≻x. The alternativex is indifferent to y,x∼y, iff 6x ≻y andy 6≻x.

Must the absence of strict preference in either direction be interpreted as real indifference?

Suppose X ={a,b,c}, and suppose ais not ranked relative to either b or c. Then b andc are not ranked either.

(14)

Weak Preferences II

Definition. The binary relation is completeif for all x andy in X, eitherx y or y x.

Proposition. Let ≻be a binary relation onX andthe derived weak relation. Then

≻is asymmetric iff is complete.

≻is negatively transitive iff is transitive.

(15)

Weak Preferences III

What does preference maximization mean in the presence of a top cycle?

a≻b ≻c ≻a and a,b,c ≻d. A weaker property than transitivity is acyclicity.

Definition. A binary relation ≻is acyclicifx₀ ≻x₁ andx₁ ≻x₂ and . . . and x_n−1 ≻x_n imply thatx_n6≻x₀.

(16)

Weak Preferences III

What does preference maximization mean in the presence of a top cycle?

a≻b ≻c ≻a and a,b,c ≻d. A weaker property than transitivity is acyclicity.

Definition. A binary relation ≻is acyclicifx₀ ≻x₁ andx₁ ≻x₂ and . . . and x_n−1 ≻x_n imply thatx_n6≻x₀.

Claim: If ≻is a preference relation, then≻is acyclic.

(17)

Choice Functions I

Suppose X is finite. LetP(X) denote a collection of non-empty subsets of X.

Definition. A choice functionis a map C :P(X)→2^X/∅ such that for all A∈P(X), C(A)⊂A.

(18)

Choice Functions I

Suppose X is finite. LetP(X) denote a collection of non-empty subsets of X.

Definition. A choice functionis a map C :P(X)→2^X/∅ such that for all A∈P(X), C(A)⊂A.

Preference relations define choice functions.

Definition. For a preference relation≻,

c(A,≻) ={x∈A: for ally ∈A,y 6≻x},

Proposition. C(A,≻) is a choice function.

(19)

Choice Functions II

Does every choice function come from a preference relation?

(20)

Choice Functions II

Let X ={a,b,c}.

c(X) ={a}and c({a,b}) ={b}. Any relation which defines this choice function violates asymmetry.

(21)

Choice Functions II

Let X ={a,b,c}.

c(X) ={a}and c({a,b}) ={b}. Any relation which defines this choice function violates asymmetry.

c({a,b}) ={a,b}andc({a,b,c}) ={b}. Any relation which defines this choice function violates NT.

(22)

Revealed Preference Axioms I

Axiom α. Ifx∈B ⊂Aand x∈c(A), thenx ∈c(B).

(23)

Revealed Preference Axioms I

Axiom α. Ifx∈B ⊂Aand x∈c(A), thenx ∈c(B).

Proposition. If≻is a preference relation, thenc(·,≻) satisfies α.

Proof. Suppose there are setsA,B∈P(X) with B ⊂A, x ∈c(A,≻) andx 6∈c(B,≻). Then there is a y ∈B such that y ≻x. SinceB ⊂Awe havey ∈Aandy ≻x. Thusx 6∈c(A,≻).

A contradiction.

(24)

Revealed Preference Axioms II

Axiom β. Ifx,y ∈c(A),A⊂B andy ∈c(B), then x∈c(B).

(25)

Revealed Preference Axioms II

Axiom β. Ifx,y ∈c(A),A⊂B andy ∈c(B), then x∈c(B).

Proposition. If≻is a preference relation, thenc(·,≻) satisfiesβ.

Proof. Since x∈c(A,≻) andy ∈A we havey6≻x. By definition, y ∈c(B,≻) implies that for all z ∈B,z 6≻y. By negative transitivity,y 6≻x andz 6≻y implies z 6≻x. Sincex ∈B and this holds for allz ∈B we havex∈c(B,≻).

(26)

Revealed Preference

Are there any other restricitons on c(·,≻) that follow from≻ being a preference relation? No.

Proposition. If a choice functionc satisfies Sen’s αand β, then there is a preference relation≻ such thatc(·) =c(·,≻).

(27)

Partial Orders

Completeness is questionable from both a descriptive and a normative point of view. So NT is too strong.

(28)

Partial Orders

Definition. ≻is a partial order if it is an asymmetric and transitive binary relation.

Axiomα still holds, but Axiomβ may fail.

(29)

Partial Orders

Definition. ≻is a partial order if it is an asymmetric and transitive binary relation.

Axiomα still holds, but Axiomβ may fail.

Now we would not want to define ∼as before. x 6≻y andy 6≻x could express indifference or non-comparability.

An alternative approach is to include a postive expression of indifference, i.e. preferences described by the pair (≻,∼).

(30)

Uncertain Prospects

You are dining out in a restaurant. Your choices are chicken, and quiche. Normally, you prefer chicken to quiche, but . . .

(31)

Uncertain Prospects

You are dining out in a restaurant. Your choices are chicken, and quiche. Normally, you prefer chicken to quiche, but . . . today you are uncertain about the quality of the chicken, because

(32)

Uncertain Prospects

You read this book!

(33)

Uncertain Prospects

You read this book!

You areuncertain about the outcome of your choice.

(34)

Formulation I

The standardformulation of a decision problem requires A setS ofstates of the world.

A state describes a possible realization of the world. “The chicken has salmonella!”

(35)

Formulation I

A setO of outcomes.

An outcome describes what happens. “You get sick.”

(36)

Formulation I

A setO of outcomes.

An outcome describes what happens. “You get sick.”

A setA of acts.

An act is a function that assigns to each state an outcome.

“You eat the chicken”. If the chicken has salmonella,then you get sick. If the chicken does not have salmonella,then you stay healthy.

(37)

Formulation II

S

s₁: chicken is not infected s₂: chicken is infected

(38)

Formulation II

S

s₁: chicken is not infected s₂: chicken is infected O

o1: eat quiche

o₂: eat chicken, don’t get sick o₃: eat chicken, get sick

(39)

Formulation II

S

s₁: chicken is not infected s₂: chicken is infected O

o1: eat quiche

o₂: eat chicken, don’t get sick o₃: eat chicken, get sick A

a₁: eat quiche. a₁(s1) =a₁(s2) =o₁ a2: eat chicken. a2(s1) =o2,a2(s2) =o3

(40)

Formulation Matrix Representation

s₁ s₂

a₁ eat quiche eat quiche

a2 eat chick, get sick eat chick, stay well

(41)

How to Specify a Problem

Sometimes it is clear what the states, outcomes and acts should be. Sometimes not.

Problem 1: The state might not have enough detail to describe choices as functions.

(42)

How to Specify a Problem

Problem 1: The state might not have enough detail to describe choices as functions.

Acts return a probability distribution over outcomes.

Put more detail into the state space.

(43)

How to Specify a Problem

Problem 2: Treating an act as a function may force you to identify two distinct acts. For example, carrying a red umbrella, carrying a blue umbrella.

(44)

How to Specify a Problem

Problem 2: Treating an act as a function may force you to identify two distinct acts. For example, carrying a red umbrella, carrying a blue umbrella.

Put more detail into the outcomes.

(45)

How to Specify a Problem

Problem 3: Labels might matter. For example, a doctor must decide whether to use a new treatment for a patient. When he reads the literature, he learns that in clinical trials, 400 patients out of 1000 survived. Another article reports that 600 out of 1000 died.

Are these statements the same? Many people don’t think so.

(46)

How to Specify a Problem

Problem 4: The states must be independent of the acts. I offer you two bets, a 100 bet on a German team to win the next European cup, and a 200 bet against50 on a French team to win.

Germany France

BRD 100 −100

Fra −50 200

(47)

How to Specify a Problem

Problem 4: The states must be independent of the acts. I offer you two bets, a 100 bet on a German team to win the next European cup, and a 200 bet against50 on a French team to win.

Win Lose BRD 100 −100 Fra 200 -50

(48)

How to Specify a Problem

Problem 5: The actual outcome or state may not be on your list.

What are the states of the world if you are trying to use monetary policy to control inflation?

(49)

Randomized Decision Rules

A contains objects such as, “eat the chicken”, or “eat the quiche”.

Sometimes we want to allow rules such as, “eat the chicken with probability 1/2, and eat the quiche with probability 1/2. Acts are functions from states to outcomes. Randomized actsare functions from states to probability distributions on outcomes.

(50)

Decision Rules

We are given S,O andA.

(51)

Decision Rules

We are given a utility function on outcomes, u :O →R.

(52)

Decision Rules

We may or may not be given a measure of likelihood on S.

(53)

Decision Rules

We may or may not be given a measure of likelihood on S.

A decision rule assigns to subsets of Aa set of choices, one or more prescribed acts to employ.

(54)

Dominance and Weak Dominance

Dominance, or admissibility, isthe basic ranking criterion.

Definition: adominates b,a≻_d b, iffu a(s)

>u b(s) for all s ∈S.

Definition: aweakly dominates b,a≻wd b, iff u a(s)

≥u b(s) for alls ∈S, with strict inequality for somes ∈S.

(55)

SEU

The most importantdecision rule.

Definition: Theexpected utility order with respect to the prior probability π hasa≻EU b iffEπ

u a(s) >Eπ

u b(s) .

(56)

Maximax

For optimists! Maximax chooses the rule with the best possible

“best-case” outcome. aMM b iff maxsu a(s)

≥maxsu b(s)

(57)

Maximax

≥maxsu b(s)

s1 s2 s3 s4

a₁ 5^∗ 0 0 2 a₂ −1 4 3 7^∗ a3 6^∗ 4 4 1 a₄ 5 6^∗ 4 3

(58)

Maximax

≥maxsu b(s)

s1 s2 s3 s4

a₁ 5^∗ 0 0 2 a₂ −1 4 3 7^∗ a3 6^∗ 4 4 1 a₄ 5 6^∗ 4 3 So a₂≻MM a₄∼MM a₃ ≻MM a₁

(59)

Maximin

The Maximinrule chooses the act with the best possible

“worst-case” outcome. amm b iff minsu a(s)

≥minsu b(s)

(60)

Maximin

≥minsu b(s)

s₁ s₂ s₃ s₄ a₁ 5 0^∗ 0^∗ 2 a2 −1^∗ 4 3 7 a₃ 6 4 4 1^∗ a₄ 5 6 4 3^∗

(61)

Maximin

≥minsu b(s)

s₁ s₂ s₃ s₄ a₁ 5 0^∗ 0^∗ 2 a2 −1^∗ 4 3 7 a₃ 6 4 4 1^∗ a₄ 5 6 4 3^∗ Soa₄ ≻mm a₃ ≻mm a₁ ≻mm a₂

(62)

Rawls’ Example

s1 s2

a₁ 0 n a₂ 1/n 1

(63)

Rawls’ Example

s1 s2

a₁ 0 n a₂ 1/n 1

The maximin rule is alwaysa₂, for alln >0.

(64)

Minimax Regret

First formalized by Savage’s (1951) reading of Wald (1950).

Regret in states is the loss associated with not having chosen the optimal act in for s. Minimize maximum regret:

(65)

Minimax Regret

u^∗(s) = max

a∈A u a(s) r_a(s) =u^∗(s)−u a(s)

(66)

Minimax Regret

u^∗(s) = max

a∈A u a(s) r_a(s) =u^∗(s)−u a(s)

a≻mmr b iff max_sr_a(s)<max_sr_b(s).

(67)

Minimax Regret Example

Payoffs s₁ s₂ s₃ s₄ a₁ 5 0 0 2 a2 −1 4 3 7 a₃ 6 4 4 1 a₄ 5 6 4 3

a4 ≻mmr a1 ∼mmr a3 ≻mmr a2

(68)

Minimax Regret Example

Payoffs s1 s2 s3 s4

a₁ 5 0 0 2 a₂ −1 4 3 7 a3 6 4 4 1 a₄ 5 6 4 3 u^∗ 6 6 4 7

a₄ ≻mmr a₁ ∼mmr a₃ ≻mmr a₂

(69)

Minimax Regret Example

Payoffs s1 s2 s3 s4

a₁ 5 0 0 2 a₂ −1 4 3 7 a3 6 4 4 1 a₄ 5 6 4 3 u^∗ 6 6 4 7

Regret s₁ s₂ s₃ s₄ a₁ 1 6 4 5 a2 7 2 1 0 a₃ 0 2 0 6 a₄ 1 0 0 4

(70)

Minimax Regret Example

Payoffs s1 s2 s3 s4

a₁ 5 0 0 2 a₂ −1 4 3 7 a3 6 4 4 1 a₄ 5 6 4 3 u^∗ 6 6 4 7

Regret s₁ s₂ s₃ s₄ a₁ 1 6 4 5 a2 7 2 1 0 a₃ 0 2 0 6 a₄ 1 0 0 4

(71)

Minimax Regret IIR

Replace a₂ with the act b whose utility payoffs are u b(s)

= (8,0,0,0).

The ordering now is

a₃≻mmr a₄≻mmr a₁ ≻mmr b

Replacing last placea₂ with last place b changes the first-best outcome!

(72)

Pairwise Minimax Regret

Definition: a≻pmr b iff on the setA^′ ={a,b},a≻mmr b.

(73)

Pairwise Minimax Regret

Definition: a≻pmr b iff on the setA^′ ={a,b},a≻mmr b.

Problem: Construct an example to show that the Pairwise Minimax Regret order can be intransitive.

(74)

The Hurwicz Criterion

For 0≤α≤1, define U^α(a) =αmax

s u a(s)

+(1−α) min

s u a(s) . a≻^α b iffUα(a)>Uα(b).