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
6-2 Bayesian Games: First Definition
Loading...
Do curso por Stanford University
Game Theory
1760 classificações
Na lição
Week 6: Bayesian Games
General definitions, ex ante/interim Bayesian Nash equilibrium.
Conheça os instrutores
Matthew O. JacksonProfessor
Economics
Kevin Leyton-BrownProfessor
Computer Science
Yoav ShohamProfessor
Computer Science
It turns out that there's several ways to determine how to find Bayesian games.
This video is going to give the first definition.
So before thinking about Bayesian Games everything we've thought about has
assumed that all of the players know what game is being played.
That is, everybody knows how many players there are in the world.
What actions are available to every player.
And what pay-offs would result given a complete action profile or action vendor
by everybody. So, let me give you a chance to stop and
think about why this is still true and imperfect information games because
intuitively it might seem to you like it isn't true.
So you might want to pause the video now. And think about that, and then I'll tell
you the answer. So the reason why imperfect information
games still have all of these things being true, is that when you don't
remember in an imperfect information game is what actions other players have played
at the moment when you're about to take your own action.
But it's still the case that you know, what actions are available to everybody
and it's still the case that if you know what everybody fully did a complete
action profile by everybody, what payoff would result.
Now we want to think about games where these assumptions aren't true anymore.
So, what we are still going to make some new assumptions, so let me tell you about
that. So what we're relaxing is that all
players know what game is being played. So we're now going to think about the
idea that there's more than one possible game that the players can think about.
And, among all the possible games that the players will reason about.
They're all going to be games that have the same number of agents, and the same
strategies based for each agent. So.
How their going to be different is just in the utility functions.
And that's important because, it's just difficult to model a situation where
you're not quite sure what strategies base you have, it wouldn't be clear how
to act. Now, you might find it useful to reason
about games in which you're not sure what other agents there are.
And it turns out that's actually possible to capture within this framework.
In that case you would just always believe that the maximum number of agents
were present in every game, but you'd set up the utility functions in a way where
sometimes it doesn't matter that some of the agents are present because they are
not able to affect anything. The second assumption that we're going to
make, it has to do with the beliefs that agents have about these different
possible games. So, in order for this to work, it has to
be the case that agents still have well-defined beliefs about what is
possible in the world. And we're going to say that the agents
start out with a common prior, so that is everyone has the same beliefs about what
it is that's possible in the world, what what games it is that are possible.
And then, they might get individual private information about in fact what
game is being played and then, they'll do Bassion updating, so they'll end up with
a posterior belief which is obtained by studying from this common prior and
updating it based on their private information.
So, that's an assumption, we could believe that the agents had different
prior beliefs but, but that's not what we assume in the case of Bassion games.
So here's one definition of Bayesian Games in terms of information sets.
So, a Bayesian Game is a set of games that differ only in their payoffs.
Also a common prior defined over these games.
And a partition structure over the games for each agent.
So in other words, a Bayesian game is defined by four elements.
The first is a set of agents. The second is a set of games.
Recall that a game is defined [SOUND] as a set of agents, a set of action profiles
sorry a, a set of action sets, one for each agent.
And a set of utility functions, one for each agent.
so we're going to restrict the set of games here.
To all have in common, the same set of agents.
And also the same action sets so these games are only going to differ in the
utility functions. Then P is going to be an element of the
set of all possible probability distributions over games.
This is going to be our prior distribution.
So this is going to tell us how likely each of these games from the set G is.
And finally, we're going to have a set of partitions of G, one for each agent.
So this is going to be a set of equivalence classes that will say from
the point of view of an agent, certain games are indistinguishable from each
other and others are not. Let's look at an example.
So this example is a little bit contrived.
Ordinarily we're going to use Beijing games to model something that, that
kind of makes some sort of sense in the world.
And here really we're, we're looking at something kind of artificial.
But it's a small example that still lets us think about everything important about
a Beijing game. So, the first thing to notice is that
there are four possible games that might be played.
Matching Pennies, Prisoner's Dilemma, Coordination or Battle of the Sexes.
Incidentally, Prisoner's Dilemma here is being played with different payoffs then
you might have seen before, but that doesn't matter, it's, it's strategically
the same game. And we have a common prior over the
games, so there's a 30% chance that the game that the players will in fact be
playing is matching pennies. There's a ten% chance that they will in
fact be playing presidential dilemma, twenty% chance of coordination, and a 40%
chance of battle of the sexes. Now haven't marked the actions in these
games but our assumption is that they have to be the same.
So let's say player one has two choices top or bottom.
He gets to choose the top or bottom action and it's the same in every game.
And likewise, player two can choose left or right, and he gets the left or right
action in each game. So.
What is interesting here of course is that we have this information sets.
So player one gets to find out. Which of these two sets the game is in.
What that means is. In fact, nature is going to decide which
game gets played. So, randomly it's going to be decided
which of the four games being played, according to the common prior.
Let's say the most likely thing happens, and the players end up playing Battle Of
The Sexes. In that case, what player one is going to
find out is that he is in this equivalence class than this one.
So, that means, he is going to know for sure that he is not playing Imagine
Pennies or Prisoner's dilemma, but he's going to think that he might be playing
either coordination or battle of the sexes.
He's going to have no way of turning them apart.
Now player two has different equivalence classes.
So player two. Considers these two games to be
indistinguishable, and likewise considers these two games to be indistinguishable.
And, continuing our example from before. If this was really the game that was
randomly chosen by nature, then player two would find out that he was in this
equivalence class, rather than this one. Meaning, that he would think the game
being played was either Prisoner's Dilemma or Battle of the Sexes.
And, the ground, the ground truth would be in fact Battle of the Sexes was being
played. He would consider it possible that
Prisoner's Dilemma was being played. And we've already seen that player one
would consider it possible The Coordination was being played.
And what this means is that when the players are deciding what, what action to
take, they're going to have to play an action without fully knowing what game is
going to be played. And they're going to have to reason about
what their opponent is doing without fully knowing what the opponent is going
to think. They will, they do know everything about
the setup. So this whole kind of picture is
something that the players know. They know the common prior.
They know their own equivalence classes and they know their opponent's
equivalence classes. So if I'm player one and I want to reason
about what player two is going to do and I know.
That I'm in this equivalence class. That I also know that player two, that if
the game is really coordination, which I believe is possible, then player two
thinks he's in this equivalence class. And thinks that matching pennies is
possible, even though I know it's not possible.
Or, on the other hand, if Battle of the Sexes is the real game that's being
played, then I know that player two thinks he's in this equivalence class,
which means he's going to think prisoner's dilemma's possible although I
know it's not possible. And I'll, I'll leave for a future video
actually how we reason about these games. But what we've learned here is how to
define a bastion game, by writing it as a probability distribution, a common
probability distribution over multiple different normal form games.
All of which share the same number of players and the same action sets.
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
