News

There will be no class on Monday, May 31 (Memorial Day), but we will meet on Tuesday and also at X-hour on Wednesday June 2 (at the regular time and Zoom place). Wednesday, which is generally the last day of spring classes, will thus be our last day as well. Don't forget: your project write-up is due, via email, to Prof. Winkler by Friday, June 4 at 9:10 am.

If your project is not yet scheduled, send Prof. Winkler an email ASAP with a proposal for presentation date---the sooner the better. Figure 5-10 minutes per person.

The written version of your project is due by 9:10 am Friday, June 4. Figure 3 pages per person, submitted by email to Prof. Winkler. If you wrote a program, include the code, brief remarks about the algorithm therein, some output, and your take on what can be learned from the output.

Two (of hundreds) Sleeping Beauty papers: the original Elga paper, here and my paper from the American Mathematical Monthly, here.

Two Absent-Minded Driver references: the original Piccione et al. paper here and the Aumann et al. paper here.

You can find Doyle and Snell's book "Random Walks and Electrical Networks" here and Aldous and Fill's famous manuscript "Reversible Markov Chains and Random Walks on Graphs" here. Of more general interest in decision theory, perhaps, is Aldous' preprint here.

You can access the paper "On Playing Golf with Two Balls" here

MATH 100 / COSC 49/149 will meet on Zoom in the B slot, MTTF 9:10 - 10:00. The link is here

There is no required text for the course, but here are several books from which course content will be obtained. There may be (virtual) handouts from these and other sources.

Howard Raiffa, Decision Analysis, Addison-Wesley, London, 1968.

Itzhak Balboa, Theory of Decision under Uncertainty, Cambridge U. Press, 2009.

Lester E. Dubins and Leonard J. Savage, How to Gamble If You Must, Dover, 1965.

Mark Thompson, Disputed Decisions of WWII, McFarland & Co., Jefferson NC, 2020.

Abstract

It is said that each of us makes about 35,000 decisions on an average day. How do we make them? How should we make them?

The relatively new science of Decision Theory constructs normative and descriptive models of decision-making, based on mathematics and especially on probability theory. These models have been of major interest in economics and increasing importance in artificial intelligence. In this class we will study both the foundations of these models, and their potential impact on how we decide what to do in our uncertain world.

Prerequisites: Mathematical background of a senior mathematics major or a beginning graduate student in mathematics or theoretical computer science, including a course in probability (e.g., MATH 20 or Math 60). If in doubt, please contact the instructor.

Here is an initial rough syllabus by weeks:

1. Normative and descriptive theories; determinism

2. Utility functions and Cantor's theorem

3. The Hagani-Dewey experiment and the Kelley rule

4. Theorems of Von Neumann-Morgenstern and De Finetti

5. Savage's Theorem and the construction of utility and probability

6. Game theory and equilibrium

7. Multi-armed bandits and the Gittins index

8. Controversies and paradoxes

9. History and future of applications

Classes

Room: virtual only, Zoom ID: 991 5203 7687
Lectures: "B" slot, in particular: Monday, Tuesday, Thursday and Friday 9:10 - 10:00.
X-hour: Wednesdays 9:10 - 10:00 am. Will be used only when so announced in class.

Staff

Instructor:

Pete Winkler -- Kemeny Hall 231
Office Hours: Mon 1:00-2:00; Tu 11:00 - 12:00; Th 2:00-3:00.
email: peter.winkler@dartmouth.edu

Teaching Assistant:

Grant Molnar -- Kemeny Hall 245
Help Sessions: Wednesdays 11-12 am.
email: Grant.S.Molnar.GR@dartmouth.edu

Office hours and help sessions will use the class Zoom link.

Textbook

Supplementary materials (for other models) will be supplied in class.

Grading

Your grade will be based on homework, class participation (this is a synchronous class---attendance is expected!), and either a final exam or a project (depending on class size). Homework and grading might be slightly different for enrollees of MATH 100/COSC 149 and enrollees of the simultaneous undergraduate course, COSC 49.

Homework

Homework will be assigned at each class period, due at the beginning of the next class.

Assignments

Due Tuesday March 30: Two marksmen shoot at the same target. The better one hits with probability 2/3, the weaker one with probability 1/3. One bullet hits; what is the probability that it came from the better marksman?

Due Thursday April 1: Before you are two identical-looking coins. One flips "heads" 75% of the time, and the other is a fair coin, but you don't know which is which. You get two flips to decide which is which. Should you flip one coin twice, or each coin once?

Due Friday April 2: Recall that in Raiffa's urn problem, your urn is of Type 1 (6 black balls, 4 red) with probability 80%, otherwise Type 2 (1 black, 9 red). If you guess it is Type 1, you win $40 if you're right and lose $20 if you're wrong; if you guess it is Type 2, you win $100 if you're right and lose $5 if you're wrong. You are also allowed to refuse to play. Your mission is to compute the value of being able to draw two random balls from the urn, before deciding how (or whether) to guess. You will be drawing with replacement if you are an undergrad or a master's student, but without replacement if you are a PhD student.

Due Monday April 5: Find two urn types with the following property: To guess whether your random urn is Type I or Type II with the help of two drawings from the urn, you should draw with replacement. (You may set the prior probability that your urn is of Type I to any value you like.)

Due Tuesday April 6: Let X be the set of points in the unit square, that is, X is the set of all ordered pairs (x,y) with x and y in the unit interval [0,1]. Define (x,y) < (v,w) if either x < v, or x = v and y < w. Show that X is a weak order but is not separable.

Due Thursday April 8: In an interval order every point x is represented by a closed interval [a(x),b(x)] of real numbers, with x less than y iff b(x) is less than a(y), and x ~ y iff their intervals intersect. Show that interval orders satisfy the axiom "w less than x ~ y less than z" implies w less than z" but not necessarily the axiom "w less than x less than y ~ z implies w less than z."

Due Friday April 9, 9:10 am: Let the option set X be all real numbers greater than or equal to 1, with x < y when y > 1.01x. Find a utility function u from X to the reals such that x < y iff u(y) > u(x)+1.

Due Monday April 12, 9:10 am: Imagine that you have $25 and a coin that flips "heads" with probability 0.6. You can bet any amount of your current holdings on heads, or tails, at even money; you have time for as many as 300 bets, but you must quit when and if you reach a holding of $250 (or when you go bust). You may either: (1) Devise a strategy and test it, then report your results. Include your code if you write a program to help you do this; or (2) Using a logarithmic utility function, find the strategy that maximizes your expected utility at each bet.

Due Tuesday April 13, 9:10 am: Imagine that you have $10 and are thinking of using it to buy a lottery ticket whose chance of winning is 1/1000. Suppose your utility for x dollars is the square root of x. How much should the lottery payoff be to make it worth buying the ticket?

Due Thursday April 15, 9:10 am: Suppose you start with $100 and repeatedly bet $1 at even money on "heads" for a coin that comes up heads with probability 51%. What is the probability that you (eventually) go broke? If you do go broke, how many flips, on average, will you have made?

Due Friday April 16, 9:10 am: Up to permuting rows and/or columns, there are 24/4 = 6 2x2 matrices with entries 1, 2, 3 and 4. Which of these describe stable zero-sum games, and what are their values (to Alice)?

Due Monday April 19, 9:10 am: Your assignment is to make a decision and act appropriately. The decision is: should you get vaccinated against COVID-19 ASAP? If your answer is yes, get up earlier than usual on Monday morning, log on to https://vaccines.nh.gov and make a vaccination appointment. Write down the time of your appointment and submit it by 9:10 am as your homework. If the website is down or you are unable to get an appointment for some other reason, say so. If your decision is no, say why. Note that you'll need to be vaccinated if you want to be on campus next fall, unless you can convince Dick's House that you have a religious or medical excuse. For homework credit any excuse is accepted, including "none of your bleeping business." We'll share the anonymized statistical results in class. (As of now, as far as I know, Dartmouth has not yet persuaded the state to set up a campus vaccination site. But the current local site---at the old JCPenney's building in West Lebanon---is accessible by Advance Transit bus, and if needed, the college might provide additional transportation options.)

NOTE The COVID-19 Task Force co-chairs on Friday announced that, with the decision by the state of New Hampshire to open vaccinations to everyone age 16 or older regardless of where they reside, Dartmouth anticipates being able to offer vaccine clinics on campus in partnership with the state beginning the week of May 3.

Due Tuesday April 20, 9:10 am: You and your friend arrange a game of Rock, Paper, Scissors, but the payoffs are not the usual. Your hobby being dressmaking, you love scissors and if you win scissors over paper, your friend must pay you $2. Other wins are only worth $1. What is your equilibrium mixed strategy? How much is the game worth to you?

Due Friday April 23, 9:10 am: Use the hypotheses of Von Neumann and Morgenstern's lottery theorem to prove that if lottery P is preferred to lottery Q, that is, if P > Q, and a and b are real numbers in the unit interval with a > b, then aP + (1-a)Q > bP + (1-b)Q.

Due Monday April 26, 9:10 am: Soul-search to determine the probability p such that you are indifferent between accepting $100 for sure, or getting $1000 with probability p (else nothing). Use your result (and other similar results, for $200, $300, etc. instead of $100) to help you construct your own utility u for winning any amount of money from $0 to $1000, with u($0) = 0 and u($1000) = 1. You may present your function algebraically or graphically.

Due Tuesday April 27, 9:10 am: Which of Savage's axioms seems least plausible to you? Present an argument that a rational decision-maker need not follow that axiom. If you believe that a rational decision-maker ought to follow all seven of Savage's axioms, instead choose one that you think others might object to, and defend it as being a prerequisite for rational behavior.

Due Thursday April 29, 9:10 am: Recall that for events A, B that are subsets of S, we say A <* B if x A y <* x B y for some outcomes x and y with x < y. Prove that if a decision-maker ascribes to all seven of Savage's rationality axioms, then <* is an archimedean probability relation.

Due Friday April 30, 9:10 am: Let u be a strictly concave utility function. Suppose P is a lottery on the monetary amounts x₁, . . . ,x_n that takes the value x_i with probability p_i. Show that the utility of P is less than the utility of P's expected value.

Due Monday May 3, 9:10 am: What's your strategy for turning $2 into $5 at roulette, playing at an American roulette table with $1 chips? Compute the probability that your strategy succeeds. (To do this calculation, you might need to consider the probability p_F of success for each possible intermediate fortune F that your strategy might obtain for you, not just for your starting value F=$2.)

Due Tuesday May 4, 9:10 am: Let Q³ be the ``cube graph," that is, the graph whose vertices are binary sequences of length 3, with two such sequences adjacent if they differ in exactly one coordinate. How many steps, on average, does it take for a simple random walk on Q³ to get from (0,0,0) to (1,1,1)?

Due Thursday May 6, 9:10 am: Let Q³ be the ``cube graph," that is, the graph whose vertices are binary sequences of length 3, with two such sequences adjacent if they differ in exactly one coordinate. What is the ``grade" g(0,0,1) of the vertex (0,0,1), with respect to the target vertex (1,1,1)?

Due Tuesday May 11, 9:10 am: Compute the (exact!) grades of the vertices at distance at most 2 to the target in the plane square grid.

Due Thursday May 13, 9:10 am: Suppose you flip a coin until you get 4 heads in a row. Describe this game as an absorbing 5-state Markov chain, by (1) drawing its weighted digraph, and (2) writing out its transition matrix. What is the grade of its start state (0 heads in a row) with respect to absorption (4 heads in a row)?

Honor Code

Students are encouraged to work together to do homework problems. What is important is a student's eventual understanding of homework problems, and not how that is achieved. The honor principle applies to homework in the following way. What a student turns in as a written homework solution is to be his or her own understanding of how to do the problem. Students must state what sources they have consulted, with whom they have collaborated, and from whom they have received help. Students are discouraged from using solutions to problems that may be posted on the web, and as just stated, must reference them if they use them. The solutions you submit must be written by you alone. Any copying (electronic or otherwise) of another person's solutions, in whole or in part, is a violation of the Honor Code.

If you have any questions as to whether some action would be acceptable under the Academic Honor Code, please speak to me, and I will be glad to help clarify things. It is always easier to ask beforehand than to have trouble later!

Notification to Student re Recording

(1) Consent to recording of course meetings and office hours that are open to multiple students. By enrolling in this course, a) I affirm my understanding that the instructor may record meetings of this course and any associated meetings open to multiple students and the instructor, including but not limited to scheduled and ad hoc office hours and other consultations, within any digital platform, including those used to offer remote instruction for this course. b) I further affirm that the instructor owns the copyright to their instructional materials, of which these recordings constitute a part, and my distribution of any of these recordings in whole or in part to any person or entity other than other members of the class without prior written consent of the instructor may be subject to discipline by Dartmouth up to and including separation from Dartmouth. (2) Requirement of consent to one-on-one recordings: By enrolling in this course, I hereby affirm that I will not make a recording in any medium of any one-on-one meeting with the instructor or another member of the class or group of members of the class without obtaining the prior written consent of all those participating, and I understand that if I violate this prohibition, I will be subject to discipline by Dartmouth up to and including separation from Dartmouth, as well as any other civil or criminal penalties under applicable law. I understand that an exception to this consent applies to accommodations approved by SAS for a student’s disability, and that one or more students in a class may record class lectures, discussions, lab sessions, and review sessions and take pictures of essential information, and/or be provided class notes for personal study use only.

If you have questions, please contact the Office of the Dean of the Faculty of Arts and Sciences.

Disabilities

I encourage any students with disabilities, including "invisible" disabilities such as chronic diseases and learning disabilities, to discuss appropriate accommodations that might help you with this class, either after class or during office hours. Dartmouth College has an active program to help students with disabilities, and I am happy to do whatever I can to help out, as appropriate.

The Student Disabilities Center is located at 318 Wilson Hall, ext. 6-9900, http://www.dartmouth.edu/~accessibility, if you have any questions. Any student with a documented disability requiring academic adjustments or accommodations is requested to speak with me by the end of the second week of the term. All discussions will remain confidential, although the Academic Skills Center may be consulted to verify the documentation of the disability and advise on an appropriate response to the need. It is important, however, that you talk to me soon, so that I can make whatever arrangements might be needed in a timely fashion.