This is a question from 2008 final test. It is derived from an interesting question in Martin Osborne's Introduction to Game Theory book. The question is visible and if it is your first cut at it try to solve it before looking at the answer - to view the answer click on the "more" button below. I have some comments on student answers to this question on my course web page here. 

Figures A, B and C below provide relevant information for this question. Four people, Red(R) Blue(Blu) Green(G) and Black(Bla) must drive from A to B at the same time . There are only two routes A to X to B , which we call x for short, and A to Y to B, which we call y for short.

Figure C

Examine Figure A. The road segments from A to X and from Y to B are both narrow, with many switchbacks and cross streets, and so subject to congestion. When there is only one car on the road it takes 6 minutes on this segment, but each additional car on these links increases travel time by 3 minutes for each and every car on that section of the road. For example,if two cars drive from A to X at the same time they each take 9 minutes on that segment ; if 3 cars drive from A to X they each take 12 minutes on that segment, etc (these travel times are pencilled in along the segments in Fig A). The other portions of the trip, along segment X to B and segment A to Y are longer, but also on wider and straighter roads so congestion is less. Traveling along segment A to Y one car takes 20 minutes. Each additional car adds a moderate bit of congestion: 1 minute for each extra car is added to the travel time of every car on that road. So, for example, while one car takes 20 minutes, 2 cars traveling from A to Y take 21 minutes each, 3 cars take 22 minutes each, etc (see Figure A, segment A to Y). Traveling along segment X to B one car alone also takes 20 minutes, and each extra car adds 0.9 minutes time for every car on that road segment. So 2 cars travelling from X to B take 20.9 minutes each, 3 cars take 21.9 minutes each, etc (see Figure A, segment X to B).

Assuming the drivers make their choices simultaneously, and that drivers care only about their own personal travel time, preferring shorter to longer personal travel times, Figure C shows all possible strategy profiles and associated payoffs (in travel times) for each player. For convenience, the table is broken up into blocks of strategies according to how drivers choose their driving patterns over the two routes "x" which is A to X to B or "y" which is A to Y to B. Row 1 indicates for example that if all 4 drivers choose route y then total travel time is 38 minutes for each driver : 23 minutes along segment A to Y and 15 minutes along segment Y to B. Row 7, for another example, indicates that Red and Green choose y, for total travel times of 21+ 9=30 minutes each [based on 2 cars on each segment of that route A to Y to B], while Blue and Black choose x, for total travel times of 20.9+ 9=29.9 minutes each [based on 2 cars on each link on that route A to X to B]. While the table might look complicated at first, since the players are all in symmetric positions , the actual payoffs in each block aren't too difficult to figure out (I've done this for you). For example, there are 6 other strategy profiles in rows 6 through 11 where the 4 drivers split themselves evenly on the two routes x and y, and if you look closely all of the payoffs are simply rearrangements of the travel times of 30 and 29.9 minutes.

B4.1 (3 marks) Use the rows of Figure C and the definition of a Nash Equilibrium to explain why the strategy choices in row 1 of Figure C cannot be a Nash Equilibrium of this game.

B4.2 (3 marks) Use the rows of Figure C and the definition of a Nash Equilibrium to explain why the strategy choices in row 3 of Figure C cannot be a Nash Equilibrium of this game.

B4.3 (5 marks) Use the rows of Figure C and the definition of a Nash Equilibrium to explain why the strategy choices in row 6 of Figure C is a Nash Equilibrium of this game. Use your answer to explain briefly why any of the strategy profiles in rows 6 through 11 where the 4 drivers split themselves evenly on the two routes x and y, is a Nash Equilibrium.

Now imagine that a new straight road is built (as in Fig B on the attachment ) between X and Y, so that there are now 3 ways to get from A to B; routes x and y as before, but now also the route from A to X to Y to B., which we will call xy for short. Segment X to Y, along a nice fancy (and expensive) freeway, is fast, 7 minutes if only one car travels along it, and for each extra car on that segment travel times for all cars go up by 1 minute each: eg if there are 2 cars on segment X to Y then each takes 8 minutes, if 3 cars each takes 9 minutes, if 4 cars each takes 10 minutes. Assume that if a person takes route x and another takes route xy they travel the A to X portion at the same time, and similarly for those taking route y and route xy. {Think of constant traffic flows along these routes rather than perfect timing of arrival and departure for these 4 drivers}

B4.4 (4 marks) If (y y x x ) was the chosen Nash Equilibrium set of driving strategies in the original game before the new road was built, show that it is no longer a Nash Equilibrium in the new game after the new road is built. Show that the strategies where everyone takes the new route,(xy xy xy xy ) cannot be a Nash Equilibrium.

B4.5 (5 marks) Show that a strategy like(y xy xy x ) where two drivers take the older "outside" routes, here Red takes y and Black takes x, while Blue and Green take the new inside route xy, is a Nash Equilibrium. Use the travel times in Figure B to calculate the total travel time for each driver in this equilibrium and compare it to the total travel times in the old road network in row 6 Fig C. What is the difference? Explain intuitively how this has happened.

…more

I set a homework exercise on inverse probability (click on "more" below the video) to see how well you understand and can use the truth tables, gigerenzer natural frequency counts, etc to explore inverse probability beliefs (ie beliefs in a game tree).

…more

Having spent muchos time thinking about payoffs under uncertainty (risk attitudes and beliefs) , this lecture uses these ideas to explain mixed strategies, and to interpret them as introducing a necessary element of surprise into strategic reasoning. (Bu first we spend 7 or 8 minutes going over the inverse probability question of how to assess a witness report about an accident involving a taxi cab)

Today we complete our analysis of beliefs viewed as probabilities.The first part of the lecture goes through the breast cancer diagnostic question to carefully distinguish tow ways of thinking intelligently about this issue, each way an "inverse" of another. If you have the disease, what are the chances the test result be positive, , ie  pick that up? If you have a positive test result, what are the chances you have the disease? Reread those sentences until you understand the difference. They ask separate questions. Then we examine an example from an employment situation. note: this clip corrects 2 intepretation errors I made in class - mayeb you can spot them!

We had to cancel yesterdays lecture (#13). Today we look at the other key idea that is useful for assessing how rational intellgient players might think about uncertainty inside of games they play: beliefs. What do people believe? How much do they believe it? eg, at the time of writing (May 11, 2008) I think Obama is likely to beat Clinton for the Democrats presidential nomination, but I'm not sure. I'd rate his chances up to 60 %, but not more than 90%, so I am not even sure how unsure I am. How do you rate your chances of passing this course?
We're all uncertain, about almost everything. The only "Nothing is certain except death and taxes" is a famous saying of Benjamin Franklin. Nothing. So if you're not sure of anything, what does the concept of "belief" really mean, and how might we measure it? ? Game theory uses the concepts of probability to answer these questions.

This lecture introduces 3 historically important ideas about the concept of probability: the frequentists , the formalists, and the subjectivists. I am a subjectivist , and I hope to convince you in this lecture to be a subjectivist too. I'd say its the only rational intelligent way to think about probability, but then I'd make too many enemies among my statistical and econometric friends. It is an excellent way to think about uncertainty and belief in game theory though! We also show two methods for operationally measuring and quantifying your uncertainty: 1) offering odds like the sports betting bookies do, and (2) deciding whether or not to take bets like sports betting bookies give . Finally we end the lecture by beginning to think about two uncertainities at once using the idea of a medical diagnostic test for breast cancer: you may be uncertain about what the test will show, and you may be uncertain about whether you have breast cancer, and lots of in between combinations, like, if the test is positive does that really mean you have breast cancer? or , if you don't have breast cancer could a test show positive that you do? Note, this ending is related to the opening 5 minutes of the lecture, where we began with a "pretest" question to see what your intution is about relating tests for breast cancer to the actual disease of breast cancer.

I've modified the actual lecture from tuesday to provide a more "user friendly" introduction to using probability weighted averages as ways of evaluating risky payoffs in games. We'll usually do just probability weighted averages of two numbers, so calculations will be easy. And graphs. But it's the concept - why are we using probability weighted averages ("expectations") to tell us something about players' preferences in the first place? The basic answer is because this gets us a leg up on the complex issue of figuring out how you and any opposing players might intelligently think about risks when they have to amke strategic deicisons.

 We review Nash Equilibrium ideas, discuss how we were really confining ourselves to games of complete and perfect information, and now begin to discuss games of imperfect information - where uncertainty really matters. In this lecture we introduce a simple card game, draw the game tree, and try to analyze  the game. The problem here is - how do we (or intelligent players)  think about payoffs under uncertainty. In this lecture we have very simple numbers and use the idea of probability weighted averages (expected payoffs)  to compute payoffs...then analyze the game. In later lectures we will revisit this  weighted average idea - to see that it relates to ideas of preferences for avoding or taking risks as well as to measuring beliefs quantitatively, via subjective probability.

This is our last lecture on simultaneous games. The first half of the class takes up time playing a simple classroom game called colour matching. I use the game to highlight the difficulties of coordination in one-shot simultaneous games with multiple (here 3) equilibria. ut it turns out that once you are aware of the coordinating problem, and that the other player is also aware of it, and that you are aware that she is aware that yo are aware.....we can enter into a focal point type calculation: What might help us bring about a convergence of our expectations...here a selection of a Nash Equilibrium. The next classroom game has over 15000 equilibria (no, you don't have to write them down) , but two randomly chosen students got how to play the game right away!!, and the rest of us could have predicted this...using focal point type reasoning. But the neatest part of this class is the discussion/analysis of the Battle of the Sexes game with a pregame message. First this starts to put together reasoning from simultaneous and sequential games. Second, by carefully identifying and slowly interpreting all the Nash Equilibria in this game, we see that Nash Equilibria concepts are very compatible with several different styles of communicating and relating in relationships. Eg a guy who is inconsistent about saying what he wants and doing something different with a lady who ignores whatever he says, or a guy who says what he wants and does it with a lady who listens to the guy and does what he says, but lives in hope that if he said what she wanted she would do that too....and many other interesting variants. Check it out.

In this lecture we begin to connect the dots. Dot 1 is simultaneous games analysis (dominance and best-response and NAsh equilibria) while Dot 2 is sequential games (observability, adaptability, rollback reasoning). Firs we show how to introduce the idea of making choices in a "simultaneous game way" -  ie not being able to directly observe what another player has done- into our analysis of sequential games, using  the idea of an "information set". Next we analyze the entry deterrence games and Kreps' simpler threat game a sequential game as a simultaneous game - ie developing a payoff matrix and looking for Nash Equilibria. We saw, in these cases,  some interesting results - multiple equilibria. Some of the equilibria correspond to rollback reasoning strategies, some don't. The former belong to a type of thinking called Sub Game Perfect equilibria, the later dont'. In all of this we (well me) keep harping on the idea that the "equilibria" involved here are a combination of human social behaviours and beliefs that players might expect about one another and themselves, given what they know about the game situation (PDIP). Just remember, equilibrium doesn't imply mechanical balance of forces, but mutually consistent beliefs and rational responses to those beliefs. We might call these beliefs and behaviours a Nash type rational , self
reinforcing culture or convention...rather than an equilibrium...but we
don't.The name "Nash equilibrium" is here to stay. Tomorrow we put a bit more flesh on the multiple equilibria idea by playing (and carefully examining/interpreting strategies) some coordination games in class, using Schelling's idea of a focal point. As a homework exercise I suggested you take the  two version of the sequential Trust Game from the midterm exam and analyze each of those as a simultaneous game, looking for non-credible promises and explaining how Nash equilibria relate to rollback equilibria; ditto for Kreps' simpler trust game. 

Continuing our discussion of simultaneous games we look at games with several Nash Equilibria. The minimum effort coordination game and a 3 player stag-hunt game are examined, then we look quickly at the standard 2x2 coordination games : Pure Coordination, Assurance, Battle of the Sexes, Chicken, etc then one game with no Nash Equilibrium at all! I went prety quickly over this material - have a look at last years lecture on this topic (about 21 minutes in) for a slower paced introduction.

In this I suggested that you modify the payoff table in class by incorporating a salary of $2 payable to each plaer (in the table we used, the slary was $0). The main reason for doing this is to get some practice constructing the payoff table for a game with a few more moves than just two. So this is a bit like the homework for the VCM game. The clip starts off with the explanation I gave last year (2007) but halfway though incoporates a useful explanation about the payoff numbers. If you download the .mov file you should find some chapter marks to help you navigate around....

This is a short clip explaining the process of iterated elimination of dominated alternatives using a stylized 2 player simultaneous game from Dixit and Skeath. The idea is to provide and illustrate operational definitions for a strategy being dominated by another strategy. When you're trying to think intelligently about what you or other players might do, if it is difficult to think about what is a best response , for them of for you, you might try thinking about what might be a worst response - ie definitely worse than other things a player could do, matter what the other playuers do.

WE continue our study of simultaneous games looking at how far we can run with the idea of a dominant strategy. It turns out...not very far, depending on the game. So then we look at the idea of trying to predict what other players won't do, ie identify dominated strategies. When we can use this technique it is a neat idea: "they won't do this, which means I won't do that, which means they won't do that.....etc" . Through an iterative process of successively eliminating strategies players won't do (won't be expected to do -do you know why? in the theory?) we might end up with a definite prediction. Another approach is to identify (conditional) best responses in a payoff table, using conditional reasoning like IF A does "this" THEN B is best to do that. Using this technique of thinking systematically, we loop through all the strategies for A to find out what B's best response is . Remember Best here is a conditional best response, ie given some assumption about what A will do, an assumption that might be reasonable to expect or not, B is best to do blah blah.... Then we apply the same thought processes to find A's best responses : IF B does this, THEN A is best to do that. This fills the payoff table with lots of "noughts and crosses". Any cell that has both noughts and crosses in it identifies strategies for each player that are mutual best responses. We call these guys Nash Equilibrium strategies.We make a start at looking at coordination games, introducing the stag-hunt game.

many students have a problem with the first multiple choice question in 2007 (and similar ones in other years). CLick on the "more" buton below to see the question in all it's gory glory...otherwise check out this video clip that will help you develop a strategy for answering such questions. The hard part here is setting up the payoff matrix - once that's done everything else is pretty straightforwrd 2x2 analysis. Let me know whether this video helps

…more

This is the first of four lectures introducing simultaneous games of strategy. We start with a classroom game called the Voluntary Contributions Mechanism (VCM) game, 2 students, each with an endowment of four chocolate bars have to decide, independently and without communication, how many to give to a group account. The group account is a "fund" of cholcate bars that grows magically - for every two chocolate bars in the fund I will add another one. Players can consume (keep) whatever cholcate bars they decide not to put into the group accound, but they also each receive half of whatever is in the group account (after fountain's top-up) . We investigate the line of reasoning that identifes dominant strategies, and find this is a "prisoner's dilemma" type game. Then we take a step back and look at the general structure of prisoner's dilemma type payofffs: a temptation payoff and a sucker payoff. The game has a strategic tension - what appears to be individually rational play leads to outcomes (payoffs) for both worse than jointly "irrational" play. Hmmmm. Read ch 1 of Binmore's Playing for Real - read about it on Amazon Playing for Real: A Text on Game Theory- for a stimulating discussion of how social scientists, policy makers, philosophers and....(mis) interpret the one-shot prisoner's dilemma as indicating the death knell for "society as we know it" : decentralized individual strategic behaviour having any hope of yielding cooperative outcomes.

In this short clip we take the all or none VCM game (the voluntary contributions game) and let players decide whether to give only some of their endowment into the group account that gets augmented. I suggested this as a homework question in Lecture 6.

This is our last lecture introducing sequential games. In it we play a structured alternating offer bargaining game, with a shrinking pie, in class, then develop the game tree for this more complicated sequential game, then analyse it using rollback reasoning. Along the way we discuss a short sequential game called the "ultimatum" game (divide a pie of a fixed size, with a take it or leave it offer...and no future comebacks!)

This is a short clip using simple sequential game reasoning (like we have been using in our various entry deterrence, trust, threat, centipede , alternating offer bargaining sequential games) to get a general strategic "take" on the interesting detailed examples of switching costs, hold-up, and lock-in used in chapters 5 and 6 of Varian and Shapiro's book [the link takes you to Amazon where you can buy it used for $3...the best $3 you'll spend this year ] Information Rules

Continuing on , we develop a simple trust game....but in the context of a strategic game played against yourself. The basic example comes from Dixit and Skeath...on whether to try smoklng or not. The issue is, will you (in the future) be able (more to the point, willing) to stop? The lecture tells some stories about problems playing games with yourself (it's not what u think ) in a variety of contexts -but the best place to understand this is to read Thomas Schelling (links at week 2 of the course outline). I show an excerpt from a PBS documentary called living old ...what sort of person will you be when you get past 85 (if you get there?) ...not what you want to be now as your present self but what "self" you will find when you get to 80+? now look forward and reason back

We still have about 20-25 minutes left on sequential games....coming up next lecture (neat topics: bargaining, ultimatums, and lock-in and hold-up) [downladdable clip has chapter markers]

We review the analysis of our simple 2x2 game tree, change the order of the moves to make a different prediction about the strategic outcome, and find a "first mover" advantage. This seemingly trivial language conceals an important strategic tradeoff: the value of inflexibility and commitment vs the value of flexibility and adapting to others' behaviour. Next we relate our ideas to two simpler sequential games (simpler in terms of their tree structure) , a "threat game" and a "trust game"...all of which carries over to lecture 4. [note: the downloadable file has chapter markers in it to help you find the relevant bits and pieces...]

After a little admin we review the results of Stop Go from yesterday, as a basis for thinking about what a theory of games might do. We use the acronym PDIP to outline a structure for our theory and we look for a "solution" as our prediction as to what will happen. Taking a nice simple 2x2 sequential game (read Ch 3 of the text) game we develop some mind tools (a game tree, and a method of analysis called rollback reasoning) to develop a prediction about how rational intelligent players might play this simple game. The attached ".mov" file (see the blue link next to "Download" at the bottom right of the player) is about 35Mb.

A small flash (ie for viewing in the browser) version of lecture 1. The first 15 minutes or so is administrative stuff...so you can probably skip that. In this class we play a simple game with a growing pie of chocolate bars - well 4 pairs of students play it and the rest of the students watched on. I moved around the lecture theatre so there are large patches of the video where not much is happening visually - in particular i wasn't able to record names , decisions in the game,  and outcomes live in the lecture theatre. We also were squeezed for time a bit - so the summary description and analysis is presented in the first part of lecture 2 .