Popularized by movies such as "A Beautiful Mind," game theory is the mathematical modeling of strategic interaction among rational (and irrational) agents. Beyond what we call `games' in common language, such as chess, poker, soccer, etc., it includes the modeling of conflict among nations, political campaigns, competition among firms, and trading behavior in markets such as the NYSE. How could you begin to model keyword auctions, and peer to peer file-sharing networks, without accounting for the incentives of the people using them? The course will provide the basics: representing games and strategies, the extensive form (which computer scientists call game trees), Bayesian games (modeling things like auctions), repeated and stochastic games, and more. We'll include a variety of examples including classic games and a few applications. You can find a full syllabus and description of the course here: http://web.stanford.edu/~jacksonm/GTOC-Syllabus.html There is also an advanced follow-up course to this one, for people already familiar with game theory: https://www.coursera.org/learn/gametheory2/ You can find an introductory video here: http://web.stanford.edu/~jacksonm/Intro_Networks.mp4
1-6 Strategic Reasoning
Loading...
Del curso dictado por Stanford University
Game Theory
1756 calificaciones
De la lección
Week 1: Introduction and Overview
Introduction, overview, uses of game theory, some applications and examples, and formal definitions of: the normal form, payoffs, strategies, pure strategy Nash equilibrium, dominant strategies
Conoce a los instructores
Matthew O. JacksonProfessor
Economics
Kevin Leyton-BrownProfessor
Computer Science
Yoav ShohamProfessor
Computer Science
Hi again. It's Matt,
and now we're talking more about strategic reasoning.
And in particular let's go through and and analyze the Keynes beauty contest
game now and talk about the Nash equilibria of this game.
So, remember what the structure of this game was.
Each player named an integer between 1 and 100, so you've got a population of
players, they're all naming integers.
the person who names the integer closest to 2/3 of the average integer named by
people wins, other people don't get anything.
ties are broken uniformly at random. Okay.
So again, what are other players going to do? You have to reason through that and
then what should I do in response? So these are the key ingredients of a Nash
equilibrium and the Nash equilibrium is everybody's choosing their optimal
response, the one that's going to give them the maximum chance of winning in
this game to what the other players are doing,
that's going to be a Nash equilibrium. Okay. So let's take a look.
so, how are we going to reason about this? Suppose that I think that the
average play the averaged integer named in this game is going to be some number
X. so, I, you know, including my own
integer, I think this is going to be the average.
Well, what has to be true about my reply to that, my reply should be 2/3 of X,
right? I should be naming the integer closest to 2/3 of whatever I believe the
average is going to be. So my optimal strategy should be naming
an integer closest to 2/3 of X. So here, we're just working through
heuristically, we'll, we'll get to formal definitions and analysis in a little bit,
but let's just go through the basic reasoning now.
Okay, so I should be trying to name 2/3 of what I think the average is going to
be. Well, X has to be less than a 100, right?
There's no way that the average guess can be more then 100.
So the optimal strategy for any player should be no more then 67 right? So if I
think that everybody's rational I, so, if I believe that's true, then I think that
nobody should be naming an integer bigger than 67.
Okay, so what does that mean? Well, that means that I can't think the average is
any higher than 67, right? So, if, if the average X is no bigger than
67, then I should be naming no more than 2/3 of 67.
Right? Now, you can begin to see where this is going, so that means that if I
think everybody else understands the game and understands that nobody should be
naming a number bigger than 67 and nobody should be naming numbers bigger than 2/3
of 67. we keep going on this, so nobody should
be naming anything more than 2/3 of this, of 2/3 of 67.
Now, obviously, when you, if you just keep looking, everybody's going to want
to be a little bit lower than everybody else's guess.
So wherever the average is you should be lower than that.
What's the only number which, everybody can be naming, and consistently choosing
the best response they have to what the average guess is.
the unique Nash equilibrium of this game is for every player to announce one.
Okay? Well that's, yeah, so, so we're driven all the way down to,
to announcing one and that's a unique Nash equilibrium, and what happens now,
we all announce one we all tie, and somebody wins at random.
If, if I try to deviate form that, if I try to announce a higher integer, I'd
just be higher than the average guess, so I wouldn't be at 2/3 of the mean.
So this is going to be a stable point. Okay?
So, let's see what, what actually happens when people play this.
So part of this reasoning is you're trying to form expectations of what other
players are doing and you need to make sure that those expectations actually
match reality. So let's have a peek at some plays of
this game. So this, this is a plot here where we're
actually giving you the results of the online course of when it was taught last
year, we had players play this game, and so these are the results.
And here from 2012, we had more than 10,000 people actually participate in
this particular game. What do we see? So, down here on this, we
have integers going from 0 to 100 and then over here, we have the frequency.
So, how many people named the given integer? So the, the 50 right here is
the, is the mode, so we get the mode of 50.
The most often named integer was 50, 1,600 people named 50.
Well, obviously, they hadn't gone through all the reasoning and it takes a while to
sort of figure out what the equilibrium of this game is.
what's the mean here? So the mean was 34, so actually there's some interesting
things. Some people naming 100, a number that
could never really win, right? So it's not clear exactly what what, it
could, it could end up winning if everybody named 100 then you could end up
in a tie there, but then you would be better off naming 67 instead.
So so when we, when we end up looking through this, what we end up with is some
people naming high numbers, but very few people,
then we end up with some interesting spikes a bunch of people just named 50.
Not clear exactly what the reasoning is on, on 50.
interestingly if you think that a bunch of people are going to do that you might
want to name 2/3 of 50. Okay, well, there's a big spike here at
33 where a bunch of people believed that other people were going to name 50.
if we keep going, so down here. If we keep going and looking at this,
what we see, then we see another spike at 2/3 of 33.
So some people said, okay, well, maybe a bunch of people are going to think that
the average is going to be 50, they are going to name 33.
I'm going to go one better than that. I am going to name something around 22,
23. you know what the winner in this game
was? The winner was actually 23. So 2/3 of the average guess here was
about 23 because the mean was, was 34 and so one of these people randomly would end
up being the winner of this game. Okay? there's actually a spike of people who
went all the way to the Nash equilibrium and it's interesting here, because the
Nash equilibrium works if you believe that everyone else is going to name the
integer one, then that's your best response.
But, in situations where a bunch of people don't necessarily understand the
game and haven't reasoned through it, then you actually would be better off
naming a higher number. So Nash equilibrium is a stable point if
everybody figures it out and everybody abides by it, then it's the best thing
you can do but it might be that some of the players aren't necessarily figuring
out exactly what goes on. Okay. Now suppose you, you start with
this game and they're not necessarily playing the Nash equilibrium, but now we
have them play it again. Right? So, they get to do this, play it
again, and then see what happens. Well, now, these people should realize
that they overestimated, right? There's a bunch of people here who are naming
numbers too high, they should be moving their announcements to, to lower numbers,
right? They should be moving down. And if, if, if I anticipate that
everybody's going to adjust and move downwards I should move my announcement
downwards as well. So let's have a peek at what happens.
So here is, is a subset of players actually from, from one of the classes I,
I did on campus, where they got, this is the second play
of the game. So after the first play, then we have
them play again. Now you can begin to see that things, you
know, the, the 50s have disappeared, all the numbers up here have disappeared,
people have moved down, and in fact, a lot more people have are
moving towards the equilibrium once you get to the second part, the second
chance. So if you've played this game, you begin
to see the logic of it. You played again and now we get closer to
Nash equilibrium. So, Nash equilibrium does is a better
predictor here. if from experienced players who have
played this game understood it and, and interacting with the same population, you
can begin to see things unraveling and moving back towards
all announcing one. Okay. So Nash equilibrium, basic ideas, a
consistent list of actions, so each player is maximizing his or her payouts
given the actions of the other players. Should be self-consistent and stable.
the nice parts about this, each players action is maximizing what they can get
given the other players. nobody has an incentive to deviate from
their action if an equilibrium profile is, is played.
someone does have an incentive to deviate from a profile of actions that do not
form an equilibrium. So these are the basic ideas and we'll be
looking at, at Nash equilibrium in much more detail.
So, in terms of of, of making predictions, you know, why, should we
expect Nash equilibrium to be played? Well, I, I think there is sort of
interesting logic here. in this logic, actually goes back to, to
some of the original discussion by Nash. when we want to make a prediction of
what's going on a game we want something which if players really understood
things, it would be consistent. And the interesting thing is we should
expect non-equilibria not to be stable, in the sense that, if players understood
it and see what happens in a non-equilibrium, they should move away
from that. And we saw exactly that in the, in the,
the second round of the, the beauty contest game, then people start moving
down toward the Nash equilibrium. So it's not necessarily true that we
always expect equilibrium to be played, [COUGH] but we should expect
non-equilibrium to vanish over time. And the, there'll be various dynamics and
other kinds of settings where there will be strong pushes towards equilibrium over
time, but they might have to be learned and they might have to evolve and, and so
forth. So, as this course goes on, we'll talk
more and more about some of the dynamics and, and things to push towards Nash
equilibrium.
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2018 Coursera Inc. Todos los derechos reservados.
