EFS 693A - STANFORD UNIVERSITY
Listening Comprehension
EFS 693A - STANFORD UNIVERSITY
Listening Comprehension
EFS 693A
Listening Comprehension
Notes Week 4-2
I. Class discussion of www.manythings.org
II. Review: Importance of vocabulary - How many words do you know? How many words do native English speakers know? What do you know when you know a word?
1.
General service list;
Academic word list (also
called University Word List)
These are ones you should know by heart.
2. www.er.uqam.ca/nobel/r21270/levels/: How did you do on the UWL test?
3. Babylon:
www.babylon.com;
Google definitions.
Note that for listening, you need to connect to the sound
4. Keeping a list and
reviewing it:
a) note new words that you've seen before or that
seem important
b) get the word, its definition, and a sentence from
the context you saw it in
c) collect in groups of 10-20 and review regularly
(till you know them)
d) try actively to notice these words in other
contexts
5. Idioms: word combinations with specific meanings.
See the idiom quizzes at
http://a4esl.org/q/h/idioms.html
6. Collocations:
words that commonly occur together.
See the quizzes at
www.better-english.com/strongcoll.htm
7. Learner dictionaries, such as Oxford's
III. Introduction to discourse markers in lectures.
A. What are
discourse markers? Phrases that signal
1) transitions (changes of topic)
2) information about the structure of the lecture
3) the relative importance of information
4) reminders of previously presented information
5) the relationship of one point to another
(comparison, contrast, cause and effect, chronological order, etc.)
6) the distinction between fact and opinion
7) uncertainty (hedging)
8) defining...and many others
B. Practice with discourse markers (see Hillier transcript, below)
IV. Lecture practice: Ali Abbas, Introduction to Decision
Analysis
http://vodreal.stanford.edu/ling/efs/080103.ram
Homework (for 10/23)
1. Below is the transcript of an earlier version of the game theory lecture you viewed. Notice the discourse markers in boldface: what function are they serving in the lecture? Try to find at least ten other phrases like these in the transcript and come to class Tuesday prepared to discuss them. (Note, you will need to print this out and bring it to class: click here for the Word file).
2. Listen to the remainder of the lecture on Decision Analysis at http://vodreal.stanford.edu/ling/efs/080103.ram. Stop at 45:10 (you'll see why). Take good notes and bring them to class--I will give you a quiz on the lecture and you may use your notes during the quiz.
3. Using a combination of the Hillier transcript and the decision analysis lecture, find at least 10 words or phrases that you didn't know before or were not sure of, and put them in a list with definitions and part or all of the sentence they occurred in. If you have problems with finding definitions (especially for phrases), use Google--you'll often see the definition link at the top of the page. If you can't find it there, put in the phrase "a X is a", "X means" or "X refers to" (where you replace X with the word or phrase) and you can often find a definition for items not in a regular dictionary. Be sure to keep the quotation marks so that you get an exact match. For example for parlor game you could try "a parlor game is a" and you'll find the definition.
| Word/Phrase | Definition | Example phrase/sentence |
| parlor game | A parlor game is a game that is meant to be played indoors. Parlor games are games that are played at a table or in a comfortable room in your home | this theory of games can be applied to playing simple parlor games. |
4. Send me (efs@stanford.edu) a short report by 6:00 PM Monday the 22nd. The report should contain your vocabulary list. Note that if you are unable to identify 10 new words/phrases in the two lectures, then you can use words you have encountered in English Baby, in your academic readings or in articles on Google News
Introduction to the Theory of Games
Frederick
Hillier, Professor Emeritus
Operations Research/Management Science and Engineering
Good morning.
It's always a pleasure for me to come each summer and give this lecture and to help welcome you and your predecessors to this country. I understand that about 75% of you this summer are from Japan, and I've...if you're from Japan, I've visited your country several times. I enjoyed it very much. I had the pleasure of being a co-general chairman of a conference in Osaka about ten years ago and had a wonderful experience there. So to all of you, welcome to the United States, welcome to Stanford University, welcome to this lecture series.
As Phil mentioned, the topic today is an introduction to the theory of games. And, the word "game" implies that, yes, this theory of games can be applied to playing simple parlor games. However, I think a better name for this theory would be the theory of competition or competition theory, because most of the applications of this theory are to competitive situations in general. Not just to games that you play in your parlor at home, but such things as armies competing against each other, or politicians competing against each other at a...at elections, or business firms competing against each other in their marketing strategies. Competition of these various types.
Now this morning we are going to focus on just the simplest type of game or competition: what is known as the two-person, zero-sum game. "Two person" because there are two players, where the two players might be business firms, or armies, or teams, but we just refer to them as "the players." "Zero-sum": what that means is that the sum of the winnings for the two players is zero. So if one player wins a dollar, that automatically means that the other player is losing a dollar. So you sum the two winnings--plus one, minus one--is zero.
OK. Now let's start with a simple example. A game called odds-and-evens game. And it's possible that a few of you may have played this game at some time. In this game the two players will simultaneously put up either one finger or two fingers. And they'll do this over and over again. And, one player is the evens player, which means that if they simultaneously put up a total number of fingers that is even--four is even, two is even--then the evens player wins the game. But if one player puts up one finger and the other player puts up two fingers, then the odds player wins the game.
OK. Let's suppose that each time they play the game, that they play for a dollar. OK. And let's say that player one is the evens player. Now what game theory--the theory of games--would tell us to do in formulating this competitive situation is to fill out what is called a "payoff table," where this payoff table gives the payoffs for each combination of strategies for the two players. OK. So what are the possible strategies? Well, for either player there are only two strategies: either put up one finger or put up two fingers. OK. So for player one, you list those two strategies, and then we do the same for player two. OK. Now remember that we are assuming that player one is the evens player, and they are playing for a dollar each time. So, at this point in the payoff table, we're saying if both players put up one finger, then the winnings for player one is...[elicits from audience] is a dollar, is a plus one. I'll leave off the dollar sign. OK, so, a winning of one. But if the evens player puts up one finger, and the odds player, player two, puts up two fingers, then the winnings for player one is...[elicits from audience] minus one. OK, and how about down here? Minus one, because we have an odd number for the total number of fingers showing. And then over here is a plus one. OK, sound like an interesting game? Perhaps we can play it just before lunch today.
Now, let me ask you...I'll let you play the...be the evens player, and my question for you is: what strategy will you be choosing? I'll be the odds player. And if we're playing, what strategy will you be choosing when we...each time we play this game? OK, so one of your possibilities is to always put up one finger; another is to always put up two fingers. Now let me ask: how many of you would choose the strategy of always putting up one finger? Do I get a volunteer here? OK, how many of you would choose the strategy of always putting up two fingers? No takers this year. Ah. OK, in past summers, I usually get somebody to put up their hand. And, of course it is a trick question, because it would be a foolish strategy to always put up the same number of fingers, because then I would know in advance what you're going to do, and I would put up the number of fingers to allow me to win. So if you say, "I'm always going to put up one finger," and I'm the odds player then I would always put up two fingers--I would win every time. But I guess I'm not going to make any money this summer.
OK, so, what does game theory say, then, is the right way to play this game? The theory of game says it's very important that you be unpredictable. Therefore, you must randomize. You must randomize. The only way to be completely unpredictable is to randomize, and by that I mean, in this case, you can simply take out a coin, flip a coin, and if it comes up heads, then you would put up one finger, if it comes up tails, then you would put up two fingers. Now, you can try in your own head to randomize, but it's a little bit unreliable. Because there may be a tendency to put up one finger more often than two fingers, and then your opponent can take advantage of that to win the majority of the time. So game theory says, "Be sure you randomize."
Now, game theory has two key assumptions. The first assumption is that both players are rational. Both players are rational. That is, they...that they use logical thinking for making their decisions. They're not basing their decisions on emotion. That's the first assumption. The second assumption is that both players choose their strategies solely to promote their own welfare. In other words, they have no compassion for their component...opponent. They are never feeling sorry for their opponent and allowing the opponent to win some of the time. This is not the situation where you have a parent playing a game with his or her child, and allowing the child to play...to win part of the time. Now, here we're "out for blood," as we say in this country. No compassion. OK, so, those then are the two key assumptions for game theory.
OK, now, in general, how does game theory say we should go about choosing our strategy? I mentioned randomizing, but sometimes...in...for some competitive situations, that's not the thing to do. And so, let's us next turn to a second example. And we'll use three variations of this example, to show three ways in which game theory says we should determine our strategy. OK, the example involves a political campaign. Since we're in this country, let's suppose that it's a campaign in this country, and suppose that it's two politicians running for the United States Senate. In a big state, where the state has two big cities, and then lots of small farm communities and small towns. OK, so the two big cities--Bigtown and Megalopolis--are the key places to win many votes. Now, this...let us assume further that the campaign is now very close to the end, and that it is a very close campaign. Just a toss-up as to which of the two politicians is going to win. And so the last two days of the campaign are going to be crucial; whoever does better in those last two days is likely to pull out a very close win. So the two politicians are now making...determining what they their strategies should be for what to do in these last two days. Well, they know that they need to focus on these two big cities, and they know that they don't want to waste time by traveling between the cities during the day because they would be losing valuable campaigning time. And so the only strategies that they want to consider are: strategy one--to spend one day in each city (that's one option). And so to accomplish that, what they would do would be to fly overnight from one city to the other, so that they would not be losing any campaigning time. A second strategy would be to stay in Bigtown, and spend both days in Bigtown campaigning. And then the third possibility then would be to spend both days instead in Megalopolis. OK, is the situation clear? OK, thank you.
OK, so now applying the theory of games, remember that we begin by formulating the game using a payoff table. And we'll do this in terms of player one, who is politician one. So the winnings here are the winnings for politician one and the losses for politician two. OK, and then we list the strategies: one, two, three. In this case, both players have the same strategies, but that's not necessary; in other competitive situations, the strategies may be quite different. OK, then the campaign managers need to estimate the payoff for each combination of the strategies. And what are the payoffs here? Well, what are the politicians trying to do? They're trying to win votes. OK, so a natural way of formulating this would be to let the payoffs be the number of votes won, the number of net votes won, and we'll actually do this in units of thousands of net votes won. So a plus one would mean that we're saying that if we put it here, that if both politicians spend one day in each city, that politician one would win a net thousand votes. OK. Now politician one might persuade two thousand people who were undecided to vote for her, but politician two might persuade one thousand to vote for him, and so politician one would have a net gain of a thousand votes.
OK, so the campaign managers make their estimates, and for variation one of this example, here are the payoffs. A one here, two, four, one, zero, five, zero, one, minus one. OK, so now let's focus on the question of choosing the best strategy for each player. Let's first put on the hat of player one. OK, if you're player one, is there some strategy here that you really don't like. Anybody that really doesn't like strategy one? Anybody really doesn't like strategy two? Anybody who really doesn't like strategy three? Ah, very good! And why don't you like strategy three? Well, you can see a lot of small numbers down here, but let's compare these payoffs for strategy three with the payoffs for strategy one. If the opponent plays this strategy, then if you play strategy one, one is better than zero. If the opponent plays this strategy, then two is better than one. If the opponent plays this strategy, then four--a gain of four--is better than a loss of one. So regardless of what the opponent does, strategy three is always worse than strategy one. OK, so we say then that strategy three is dominated by strategy one. That in general, strategy one--the dominating strategy--in general is one that is always at least as good, and sometimes better, regardless of what the opponent does. OK, so strategy three is a dominated strategy. So because we are talking about rational players here, remember assumption one, it would only be rational for player one to eliminate strategy three.
Well, player two is also rational and knows that player one is rational, and so know that player one would eliminate this strategy. And so now let's put on the hat of player two. And if you're player two, are there any dominated strategies here? Do I hear a vote for strategy one? Anybody who votes for strategy two as being dominated, one we can eliminate? Anybody who votes for strategy three? OK, let me remind you. These numbers are the losses for player two. OK. Now is there a strategy you really don't like? Strategy three. OK, because strategy three is dominated by either of these other two strategies. Regardless of what player one does, either of these strategies is always better than this strategy for player two. OK, so the rational player two will eliminate strategy three.
OK, now we take off the hat of player two, put back on the hat of player one. You know that your opponent is rational and therefore will eliminate this strategy. So if you're player one, is there now a dominated strategy? Two. Why? Because regardless of what the opponent does, strategy one is always at least as good as strategy two and sometimes better. One is the same as one, but a gain of two is better than zero. OK, so strategy two would be eliminated as being a dominated strategy.
OK, now we take of the hat of player one, put on the hat of player two. If you're player two, is there a dominated strategy? Strategy two. Because a loss of two is not as good as a loss of one. OK, so player two would now eliminate that strategy. And therefore, the conclusion is, that using the concept of dominated strategies, that both players would choose strategy one. OK.
So that's variation one. And now I'm going to turn to variation two. And in a moment, I'm going to erase all of this, so if you wanted to copy it down, please do so quickly.
So now the campaign managers come running into the room, and say, "Hold, wait, hold everything. These numbers are wrong. And now here are my new estimates of what the number of thousands of net votes would be for each combination of strategies." OK, so we put the strategies back up. And now here are the new numbers. Very different from before: minus three, minus two, six, two, zero, two, five, minus two, minus four.
Now let's try to determine which strategy to choose for each player. Let's start with player one. We'll put on the hat of player one. OK, do we have any dominated strategies for player one? OK, well, I've never discovered one yet; I don't think we have any dominated strategies here. OK, so we cannot use this concept of dominated strategies to help player one choose her strategy. OK, so now what do we do? Well, one option would be to focus on, for each strategy: what's the best we could do? For strategy one, we could have a gain of six. That'd be great. For strategy three, we could have a gain of five. For strategy two, the best we could do would be a gain of two. OK, so, if you are a born optimist, then you might grab strategy one and hope to get this gain of six. Now what's wrong with that line of reasoning? Remember the two assumptions of game theory. Both players are rational, so your opponent is rational, and your opponent is going to be promoting his own welfare. Not...and therefore trying not to allow you to get any big gains. OK, so against this rational opponent, if you get greedy, and choose strategy one, what is most likely to happen is that instead of a gain of six, you going to get stuck with a loss of minus two or a minus three...a loss of two or a loss of three. And similarly down here. OK, so against a rational opponent, game theory says it's better to be conservative. It's better to focus on what's the worse that can happen with this for each strategy, because we can then guarantee that we'll not do any worse than that outcome. And therefore game theory says let's look at the minimum payoff for each strategy. OK, for strategy one, the minimum is minus three. So if we choose strategy one, we can only guarantee not doing worse than a loss of three. For strategy three, the minimum is minus four, and so the best guarantee is that we wouldn't lose more than four. But if we choose strategy two, the minimum is zero, then we can guarantee that we would definitely not lose anything, and if we're lucky, we might even actually gain something. OK, so game theory says then that player one should choose strategy two. And this number of zero is referred to as the "max of min" value, because what are we doing here: we're maximizing the minimum, taking the maxima...maximum of these minima. OK, "Max of Min."
OK, now, we'll take off the hat of player one, put on the hat of player two. If you're player two using the same philosophy, you're focusing on what's the worse that can happen to me. So with strategy one, the worse that can happen would be a loss of five. And so for player two, since these are now losses, you want to focus on the maximum loss. OK, so if you choose strategy one, you can do as badly as a loss of five. If you choose strategy three, you can do as badly as a loss of six. But, gee, if you choose strategy two, the worse that could happen to you is a loss of zero, breaking even. And so game theory says then that player two should choose strategy two. OK, so the zero is referred to as the "min of max" value. "Min of max" because we're taking the minimum of these maxima. "Min of max." And so this criterion for how to choose your strategy is often referred to as the "min of max" criterion. Minimize your maximum loss.
OK, that's variation two. So in a moment I'm going to erase those numbers, and turn to our last variation: variation three. OK, so let's erase these. OK, so now the campaign managers come running into the room again, and say, "Wait, hold everything. My numbers were wrong. Here are the correct numbers." And I think they are about to be fired, but...So here are the numbers: zero, minus two, plus two, five, four, minus three, two, three, minus four. OK, so now we begin by trying to apply the first two approaches, looking for dominated strategies. And do we see any dominated strategies? I don't think so. OK, so if that doesn't work then we turn to applying the min of max criterion. And so, for player one we now look at the minimum for each. So here we have a minimum of minus two. For strategy two we have a minimum of minus three. And here we have a minimum of minus four. OK, so the max of min value in this case, maximum of these minima, would be the minus two.
OK, for player two, we're focusing on the maximum loss. So here we have a plus five. Here we have a plus four. And here the worse that can happen is a loss of two. So the min of max value, the minimum of these maxima, is two. OK, so player one would choose strategy one; player two would choose strategy three. But now let's look at the implications of that. If you're player two, and you deduce or predict that player one, being rational, is going to choose strategy one, then if you're player two, are you happy with choosing this strategy? Here you have a loss of two, and you're deducing that player one is going to choose this strategy, so what would you then do if you're player two. You would switch over to strategy two. OK. So rather than sticking with strategy three, you would now switch to strategy two, and instead of having a loss of two, you would now have a gain of two.
OK, now let's put on the hat of player one. If you're player one, you know your opponent is rational, and so your opponent will know that you're going to be inclined to play strategy one, and therefore your opponent is going to switch over to here, and so what do you do if you're player one? Well, here you have a loss of two, here you have a gain of four. And so player one would want to switch down to strategy two.
OK, now put on the hat of player two again. If you're player two...player two knows that player one knows that player two knows that player one is going to be inclined to play this strategy, and therefore two is going to switch to here and one is going to switch to here, and so player two, you're looking at a loss of four or you could get a gain of three. And so player two is going to be inclined to switch over here.
OK, now put on the hat of player one. Player one knows that player two knows that player one knows that player two knows that player one is going to be inclined to do this, so two will switch to here, so one will switch to here, so two will switch to here, and so player one will be inclined to...[elicits from audience] switch back to one.
Now does it stop there? Around and around we go. OK. Well, this is referred to as an "unstable solution." "Unstable" because if you can predict what you're opponent is going to do, you can take advantage of that information to improve your own position. OK. It's very much like the odds and evens game up there. If you knew your opponent was going to put up one finger every time, then you would automatically take advantage of that information. OK, so we have an unstable solution here; whereas for variation two, everything seemed to be OK.
Let me go back to variation two and now look at why for variation two we were OK but here everything blows up. So here are the numbers again for variation two. OK, remember when we were choosing...the strategy that gave us the max...the...let's see, I want the minimum here, don't I? We had minus two and zero, minus four...pardon me? Minus three? Thank you. Here we have a maximum of five, zero, and six. OK, now what was different about this situation? OK, say you're player two. You deduce that player one, being rational, is going to choose this strategy, so if you're player two, can you take advantage of that information to improve your situation? You know that player one is going to do this, and you were initially inclined to do this. Can you improve your position by switching? No, here you have a loss of zero, but if you switch then you have a loss of two. OK, if you're player one and you deduce that player two is going to choose this strategy, can you improve your position? No, because if you switch, instead of a gain of zero, you'll have a loss of two. OK, so here in variation two, we have a stable gain...a "stable solution." And the reason it's a stable solution is because the max of min value and the min of max value come from what is called a "saddle point." The zero here is called a saddle point, because it is a value in your payoff table that is the minimum of its row and the maximum of its column. And incidentally, the reason why it's called a saddle point is if you think of these numbers as representing the height of something at your building, then in one direction its going up on both sides, like a saddle from back to front, and in the other direction its going down on both sides, like a saddle. OK, so if you have a saddle point, then you have a stable solution. And indeed, each player should stick...should choose and stick with strategy two in this variation. Here, we don't have a saddle point. Two is the maximum of its column, but it's not the minimum of its row. Minus two is the minimum of its row, but it's not the maximum of its column. And so, you don't have a saddle point. That's what leads to this being unstable. Around and around we go.
OK, so what does game theory say we should do about this situation? Well, what did game theory say we should do about the odds and evens game? It said we should randomize; we need to keep our opponent guessing. We cannot become predictable. OK, so what we need to do is to take out a coin, but now it's going to be a weighted coin. We'll have more complicated probabilities. It's going to be a weighted coin. And we'll flip this coin, and if it comes up heads, player one will choose a certain strategy, if it comes up tails, he will choose another strategy. OK, so let's add another row here and another column here. And what game theory says to do is for player one to flip a weighted coin that comes up heads seven elevenths of the time, and it comes up tails four elevenths of the time. And if it comes up heads, then politician should choose strategy one; if it comes up tails, he should choose strategy two. OK, for politician two, the weighted coin should come up heads five elevenths of the time, and tails six elevenths of the time. So with eleven flips, on the average, it will be heads five times, tails six times. If it comes up heads then politician two should choose strategy two; if it comes up tails then choose strategy three. OK, that was hocus pocus. Where did I come up with those numbers? Well, that's another lecture.
What game theory does to obtain those numbers is to use another technique of operations research called "linear programming." By formulating a linear programming model--an appropriate linear programming model and solving it--you would then obtain these numbers. Now if you want to learn all about linear programming and more about game theory, then there's a book that I would recommend--a book by myself and Gerald Liebermann--Introduction to Operations Research. And Chapter Eleven of this book, we have the chapter on game theory, and that chapter goes through the...today's lecture including today's examples, and linking up to applying linear programming. And then in several early chapters of the book, it tells you about linear programming. So if you want to read further, by all means be my guest. It's published by McGraw-Hill.
OK, any questions at this point? I would be happy to talk with you individually after the lecture, but let's have a few questions now perhaps.