14.12 G am e Theory Lecture NotesTheory of ChoiceM u h a met Yild iz(Lecture 2)1 The basic theory of c hoiceWe consider a set X of alternativ es. Alternative s are m u tually exclusive in the sensethat one cannot c hoose two distinct alternativ es at the same time. We also tak e the setof fe asible alternatives exh au stive so that a play e r’s c ho ices will alw ays be defined. Notethat this is a matter of modeling. For instance, if w e hav e optio ns C offee and Tea, wedefine alternativ es as C = Coffee but no Tea, T = Tea but no Coffee, CT = Coffee andTea, and NT = no Coffee and no Tea.Take a relation º on X. Note that a relation on X is a subset of X × X.Arelationº is said to be complete if and only if, given any x, y ∈ X,eitherx º y or y º x.Arelation º is said to be transitive if and on ly if , given any x, y, z ∈ X,[x º y and y º z] ⇒ x º z.Arelationisapreferenc e relation if and only if it is complete and transitive. Giv en an ypreference relation º,wecandefine strict preference  byx  y ⇐⇒ [x º y and y 6º x],and the indifference ∼ byx ∼ y ⇐⇒ [x º y and y º x].Apreferencerelationcanberepresented by a utilit y function u : X → R in thefollowing sense:x º y ⇐⇒ u(x) ≥ u(y) ∀x, y ∈ X.1The following theorem states further that a relation needs to be a preference relation inorder to be represen ted by a utilit y function.Theorem 1 Let X be finite. A relation ca n be presen ted by a u tility functio n if and onlyif it is com ple te and transitive. Mo reover, if u : X → R r epresents º,andiff : R → Ris a strictly increasing function , then f ◦ u also r epresents º.By the last statement, we call such utility functions ordinal.In or der to use this ordinal theory of choice, we should know the agen t’s preferences onthe alternatives. As we ha ve seen in the previous lecture, in gam e theory, a pla yer c hoosesbet ween his strategies; and his preferences on his strategies depend on the strategiespla yed by the other players. In order to apply this theory to games directly, w e migh tneed to restrict ourselves to the cases w here each player kno w s which strategies the otherpla yers play. This is clearly too restrictiv e, hence w e need a theory of decision-m akin gunder uncertaint y.2 Decision-making under uncertain tyWe consid er a finite set Z of prizes, and the set P of all proba bility distrib ution s p : Z →[0, 1] on Z,wherePz∈Zp(z)=1. We call these probab ility distributions lotteries. Alottery can be depicted by a tree. For examp le, in Figure 1, Lottery 1 depicts a situationin whic h if head the pla yer gets $10, and if tail, he gets $0.Lottery 11/21/2100Figure 1:In game theory and mor e broadly when agents make their decision un der uncertain ty,we do not have the lotteries as in casinos wher e the probabilities are generated by2somemachinesandaswehavedefined abo ve where the probabilities are given. It hasbeen shown b y Savage (1954 ) und er certa in conditions that a pla yer’s beliefs can berepresented by a (unique) probability distribution . Using these probabilities, w e canrepresent our acts by lotteries.We wo uld lik e to have a theory that constructs a player’s preferen ces on the lotteriesfrom his preferences on the prizes. The most w ell-known such theory is the theoryof expected utility maxim iza tion by Von Neuman n and Morg en stern. A preferencerelation º on P is said to be represen ted by a von Neum ann-Morgenstern utility functionu : Z → R if and only ifp º q ⇐⇒ U(p) ≡Xz∈Zu(z)p(z) ≥Xz∈Zu(z)q(z) ≡ U(q) (1)for e ach p, q ∈ P .NotethatU : P → R represen ts º in ordinal sense. That is, the agentacts as if he wants to ma ximize the expected value of u. For instance, the expectedutilit y of Lottery 1 for our agen t is E(u(Lo ttery 1)) =12u(10) +12u(0).1The necessary and sufficient conditions for a representation as in (1) are as follow s:Axiom 1 º is comple te and transitive.This is necessary by Theorem 1, for U represents º in ordinal sense. The secondcondition is called independen ce axiom, stating that a player’s preference between t wolotteries p and q does not ch an ge if we toss a coin and give him a fixed lottery r if “tail”come s up.Axiom 2 For any p, q, r ∈ P ,andanya ∈ (0, 1], ap +(1− a)r  aq +(1− a)r ⇐⇒p  q.Let p and q be the lotteries depicted in Figure A. Then, the lotteries ap +(1−a)rand aq +(1− a)r can be depicted as in Figure B, where w e toss a coin bet ween a fixedlottery r and our lotteries p and q. Axiom 2 stipulates that the agent w ould not changehis mind after the coin toss. Therefore, our axiom can be tak en as an axiom of “dynamicconsistancy” in this sense.The third condition is purely tec hn ical, and called continuity axiom. It states thatthere are no “infinitely good” or “infinitely bad” prizes.1If Z were a contin uum, like R, we would compute the expected utility of p byRu(z)p(z)dz.3Axiom 3 For any p, q, r ∈ P ,ifp  r, then ther e exist a, b ∈ (0, 1) such that ap +(1−a)r  q  bp +(1−r)r.Axioms 2 and 3 imply that, given any p, q, r ∈ P and any a ∈ [0, 1],if p ∼ q,thenap +(1− a) r ∼ aq +(1− a)r. (2)This has two implications:1. The indifference curves on the lotteries are straight lines.2. The indifference curves, whic h are straigh t lines, are parallel to eac h other.To illustrate these facts, consider three prizes z0,z1,andz2,wherez2 z1 z0.A lottery p canbedepictedonaplanebytakingp (z1) as the first coordinate (onthe horizontal axis), and p (z2) as the second coordinate (on the vertica l axis). p (z0)is 1 − p (z1) − p (z2). [See Figure C for the illustration.] Given an y two lotteries pand q, the con vex combinations ap +(1− a) q with a ∈ [0, 1] form the line segmentconnecting p to q.Now,takingr = q, w e can deduce from (2) that, if p ∼ q,thenap +(1− a) q ∼ aq +(1− a)q = q for each a ∈ [0, 1]. Thatthis,thelinesegmentconnecting p to q is an indifference curve. M oreov er, if the lines l and l0are parallel,then α/β = |q0| / |q|,where|q| and |q0| are the distances of q and q0to the origin,respectiv ely. H ence, taking a = α/β,wecomputethatp0= ap +(1− a) δz0and q0=aq +(1−a) δz0,whereδz0is the lottery at the origin, and giv es z0with probability 1.Therefor e, b y (2), if l is an indifferen ce curv e, l0is also an indifference curv e, sho w in gthat …