Decision networks Money B not preferred to CHAPTER 16 RATIONAL DECISION / E.a lokup table for perect tictactoe t(.S: A>B Continuity such that ·14 n ar Maximizing expected utility Rational preferences contd. preferences of a rational agent must obey comtraints. Rational preferences
Rational decisions Chapter 16 Chapter 16 1 Outline ♦ Rational preferences ♦ Utilities ♦ Money ♦ Multiattribute utilities ♦ Decision networks ♦ Value of information Chapter 16 2 Preferences An agent chooses among prizes (A, B, etc.) and lotteries, i.e., situations with uncertain prizes Lottery L = [p, A; (1 − p), B] L p 1−p B A Notation: A B A preferred to B A ∼ B indifference between A and B A ∼ B B not preferred to A Chapter 16 3 Rational preferences Idea: preferences of a rational agent must obey constraints. Rational preferences ⇒ behavior describable as maximization of expected utility Constraints: Orderability (A B) ∨ (B A) ∨ (A ∼ B) Transitivity (A B) ∧ (B C) ⇒ (A C) Continuity A B C ⇒ ∃ p [p, A; 1 − p, C] ∼ B Substitutability A ∼ B ⇒ [p, A; 1 − p, C] ∼ [p, B; 1 − p, C] Monotonicity A B ⇒ (p ≥ q ⇔ [p, A; 1 − p, B] ∼ [q, A; 1 − q, B]) Chapter 16 4 Rational preferences contd. Violating the constraints leads to self-evident irrationality For example: an agent with intransitive preferences can be induced to give away all its money If B C, then an agent who has C would pay (say) 1 cent to get B If A B, then an agent who has B would pay (say) 1 cent to get A If C A, then an agent who has A would pay (say) 1 cent to get C A B C 1c 1c 1c Chapter 16 5 Maximizing expected utility Theorem (Ramsey, 1931; von Neumann and Morgenstern, 1944): Given preferences satisfying the constraints there exists a real-valued function U such that U(A) ≥ U(B) ⇔ A ∼ B U([p1, S1; . . . ; pn, Sn]) = Σi piU(Si) MEU principle: Choose the action that maximizes expected utility Note: an agent can be entirely rational (consistent with MEU) without ever representing or manipulating utilities and probabilities E.g., a lookup table for perfect tictactoe Chapter 16 6
Typical empirical data,extrapolated with risk-prone behavio Money does not behave as a utility function pay $30 Money Utility scales e prize T with pro Standard approach to assessment of human utilities: Utilities map states to real numbers.Which numbers? Multiattribute utility 8294:998 Decision networks ach,adjust puntil half the dass votes for kttery (M=10.000) Student group utility
Utilities Utilities map states to real numbers. Which numbers? Standard approach to assessment of human utilities: compare a given state A to a standard lottery Lp that has “best possible prize” u> with probability p “worst possible catastrophe” u⊥ with probability (1 − p) adjust lottery probability p until A ∼ Lp L 0.000001 0.999999 instant death continue as before pay $30 ~ Chapter 16 7 Utility scales Normalized utilities: u> = 1.0, u⊥ = 0.0 Micromorts: one-millionth chance of death useful for Russian roulette, paying to reduce product risks, etc. QALYs: quality-adjusted life years useful for medical decisions involving substantial risk Note: behavior is invariant w.r.t. +ve linear transformation U 0 (x) = k1U(x) + k2 where k1 > 0 With deterministic prizes only (no lottery choices), only ordinal utility can be determined, i.e., total order on prizes Chapter 16 8 Money Money does not behave as a utility function Given a lottery L with expected monetary value EMV (L), usually U(L) < U(EMV (L)), i.e., people are risk-averse Utility curve: for what probability p am I indifferent between a prize x and a lottery [p, $M; (1 − p), $0] for large M? Typical empirical data, extrapolated with risk-prone behavior: +U +$ −150,000 800,000 o o o o o o o o o o o o o o o Chapter 16 9 Student group utility For each x, adjust p until half the class votes for lottery (M=10,000) p $x 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 0 500 3000 4000 5000 6000 7000 8000 9000 10000 1000 2000 Chapter 16 10 Decision networks Add action nodes and utility nodes to belief networks to enable rational decision making U Airport Site Noise Deaths Cost Litigation Construction Air Traffic Algorithm: For each value of action node compute expected value of utility node given action, evidence Return MEU action Chapter 16 11 Multiattribute utility How can we handle utility functions of many variables X1 . . . Xn? E.g., what is U(Deaths, Noise, Cost)? How can complex utility functions be assessed from preference behaviour? Idea 1: identify conditions under which decisions can be made without complete identification of U(x1, . . . , xn) Idea 2: identify various types of independence in preferences and derive consequent canonical forms for U(x1, . . . , xn) Chapter 16 12
is coser to the city dominates 5.on cost with distance from city Stochastic dominance contd. Stochastic dominance Typically define attributes such that[is monotonic in each Strict dominance Label the arcs or the +9 号
Strict dominance Typically define attributes such that U is monotonic in each Strict dominance: choice B strictly dominates choice A iff ∀ i Xi(B) ≥ Xi(A) (and hence U(B) ≥ U(A)) 1 X 2 X A B C D 1 X 2 X A B C dominates This region A Deterministic attributes Uncertain attributes Strict dominance seldom holds in practice Chapter 16 13 Stochastic dominance 0 0.2 0.4 0.6 0.8 1 1.2 -6 -5.5 -5 -4.5 -4 -3.5 -3 -2.5 -2 Probability Negative cost S2 S1 0 0.2 0.4 0.6 0.8 1 -6 -5.5 -5 -4.5 -4 -3.5 -3 -2.5 -2 Probability Negative cost S2 S1 Distribution p1 stochastically dominates distribution p2 iff ∀ t Z −∞ t p1(x)dx ≤ Z −∞ t p2(t)dt If U is monotonic in x, then A1 with outcome distribution p1 stochastically dominates A2 with outcome distribution p2: Z −∞ ∞ p1(x)U(x)dx ≥ Z −∞ ∞ p2(x)U(x)dx Multiattribute case: stochastic dominance on all attributes ⇒ optimal Chapter 16 14 Stochastic dominance contd. Stochastic dominance can often be determined without exact distributions using qualitative reasoning E.g., construction cost increases with distance from city S1 is closer to the city than S2 ⇒ S1 stochastically dominates S2 on cost E.g., injury increases with collision speed Can annotate belief networks with stochastic dominance information: X +−→ Y (X positively influences Y ) means that For every value z of Y ’s other parents Z ∀ x1, x2 x1 ≥ x2 ⇒ P(Y |x1, z) stochastically dominates P(Y |x2, z) Chapter 16 15 Label the arcs + or – SocioEcon Age GoodStudent ExtraCar Mileage VehicleYear RiskAversion SeniorTrain DrivingSkill MakeModel DrivingHist DrivQuality Antilock Airbag CarValue HomeBase AntiTheft Theft OwnDamage PropertyCost LiabilityCost MedicalCost Cushioning Ruggedness Accident OtherCost OwnCost Chapter 16 16 Label the arcs + or – SocioEcon Age GoodStudent ExtraCar Mileage VehicleYear RiskAversion SeniorTrain DrivingSkill MakeModel DrivingHist DrivQuality Antilock Airbag CarValue HomeBase AntiTheft Theft OwnDamage PropertyCost LiabilityCost MedicalCost Cushioning Ruggedness Accident OtherCost OwnCost + Chapter 16 17 Label the arcs + or – SocioEcon Age GoodStudent ExtraCar Mileage VehicleYear RiskAversion SeniorTrain DrivingSkill MakeModel DrivingHist DrivQuality Antilock Airbag CarValue HomeBase AntiTheft Theft OwnDamage PropertyCost LiabilityCost MedicalCost Cushioning Ruggedness Accident OtherCost OwnCost + + Chapter 16 18
Label the arcs or- Label the arcs or- the Value of information ++g+th Preference structure:Stochastic Hence assessn single-attribute functions;often a good approximation Theorem (Debreu,1960):mutual P.1.3 additive value function: Preference structure:Deterministic
Label the arcs + or – SocioEcon Age GoodStudent ExtraCar Mileage VehicleYear RiskAversion SeniorTrain DrivingSkill MakeModel DrivingHist DrivQuality Antilock Airbag CarValue HomeBase AntiTheft Theft OwnDamage PropertyCost LiabilityCost MedicalCost Cushioning Ruggedness Accident OtherCost OwnCost + + − Chapter 16 19 Label the arcs + or – SocioEcon Age GoodStudent ExtraCar Mileage VehicleYear RiskAversion SeniorTrain DrivingSkill MakeModel DrivingHist DrivQuality Antilock Airbag CarValue HomeBase AntiTheft Theft OwnDamage PropertyCost LiabilityCost MedicalCost Cushioning Ruggedness Accident OtherCost OwnCost + + − − Chapter 16 20 Label the arcs + or – SocioEcon Age GoodStudent ExtraCar Mileage VehicleYear RiskAversion SeniorTrain DrivingSkill MakeModel DrivingHist DrivQuality Antilock Airbag CarValue HomeBase AntiTheft Theft OwnDamage PropertyCost LiabilityCost MedicalCost Cushioning Ruggedness Accident OtherCost OwnCost + + − − Chapter 16 21 Preference structure: Deterministic X1 and X2 preferentially independent of X3 iff preference between hx1, x2, x3i and hx1 0 , x2 0 , x3i does not depend on x3 E.g., hNoise, Cost, Safetyi: h20,000 suffer, $4.6 billion, 0.06 deaths/mpmi vs. h70,000 suffer, $4.2 billion, 0.06 deaths/mpmi Theorem (Leontief, 1947): if every pair of attributes is P.I. of its complement, then every subset of attributes is P.I of its complement: mutual P.I.. Theorem (Debreu, 1960): mutual P.I. ⇒ ∃ additive value function: V (S) = ΣiVi(Xi(S)) Hence assess n single-attribute functions; often a good approximation Chapter 16 22 Preference structure: Stochastic Need to consider preferences over lotteries: X is utility-independent of Y iff preferences over lotteries in X do not depend on y Mutual U.I.: each subset is U.I of its complement ⇒ ∃ multiplicative utility function: U = k1U1 + k2U2 + k3U3 + k1k2U1U2 + k2k3U2U3 + k3k1U3U1 + k1k2k3U1U2U3 Routine procedures and software packages for generating preference tests to identify various canonical families of utility functions Chapter 16 23 Value of information Idea: compute value of acquiring each possible piece of evidence Can be done directly from decision network Example: buying oil drilling rights Two blocks A and B, exactly one has oil, worth k Prior probabilities 0.5 each, mutually exclusive Current price of each block is k/2 “Consultant” offers accurate survey of A. Fair price? Solution: compute expected value of information = expected value of best action given the information minus expected value of best action without information Survey may say “oil in A” or “no oil in A”, prob. 0.5 each (given!) = [0.5 × value of “buy A” given “oil in A” + 0.5 × value of “buy B” given “no oil in A”] – 0 = (0.5 × k/2) + (0.5 × k/2) − 0 = k/2 Chapter 16 24
VPI&(E EA)=VPIE(E+VPI66,(E)=VPIg(EA)+(E Order-independent VPlE(En Ex)4 VPIg(E)+VPIg(E) onnegative-in expect ation,not post ho Properties of VPI (VPIvalue of perfect information) alitative behaviors Suppose we knew E=then we would chaoses.t. EU(olE)=max U(S)P(SIE.a) General formula
General formula Current evidence E, current best action α Possible action outcomes Si , potential new evidence Ej EU(α|E) = max a Σi U(Si) P(Si |E, a) Suppose we knew Ej = ejk, then we would choose αejk s.t. EU(αejk |E, Ej = ejk) = max a Σi U(Si) P(Si |E, a, Ej = ejk) Ej is a random variable whose value is currently unknown ⇒ must compute expected gain over all possible values: V PIE(Ej) = Σ k P(Ej = ejk|E)EU(αejk |E, Ej = ejk) ! − EU(α|E) (VPI = value of perfect information) Chapter 16 25 Properties of VPI Nonnegative—in expectation, not post hoc ∀ j, E V PIE(Ej) ≥ 0 Nonadditive—consider, e.g., obtaining Ej twice V PIE(Ej , Ek) 6= V PIE(Ej) + V PIE(Ek) Order-independent V PIE(Ej , Ek) = V PIE(Ej) + V PIE,Ej (Ek) = V PIE(Ek) + V PIE,Ek (Ej) Note: when more than one piece of evidence can be gathered, maximizing VPI for each to select one is not always optimal ⇒ evidence-gathering becomes a sequential decision problem Chapter 16 26 Qualitative behaviors a) Choice is obvious, information worth little b) Choice is nonobvious, information worth a lot c) Choice is nonobvious, information worth little P ( U | E ) j P ( U | E ) j P ( U | E ) j (a) (b) (c) U U U U 1 U 2 U 2 U 2 U 1 U 1 Chapter 16 27