5-3 Stochastic Games

Loading...

来自 Stanford University 的课程

博弈论

1696 个评分

Stanford University

博弈论

1696 个评分

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

从本节课中

Week 5: Repeated Games

Repeated prisoners dilemma, finite and infinite repeated games, limited-average versus future-discounted reward, folk theorems, stochastic games and learning.

5-1 Repeated Games 6:17

5-2 Infinitely Repeated Games: Utility 6:31

5-3 Stochastic Games 5:37

5-4 Learning in Repeated Games 15:43

5-5 Equilibria of Infinitely Repeated Games 28:44

5-6 Discounted Repeated Games 13:25

5-7 A Folk Theorem for Discounted Repeated Games 10:54

与讲师见面

Matthew O. Jackson
Professor
Economics
Kevin Leyton-Brown
Professor
Computer Science
Yoav Shoham
Professor
Computer Science

Let's now speak briefly about stochastic games. This is a topic that lends itself

to a very long discussion and it's, it's quite a complicated one, but we'll touch

on the, the main points and position it in the landscape of topics we're discussing.

And so, the, the starting point are repeated games. as we know, a repeated

game is simply a game in normal form, for example, that we repeat over and over

again. For example, we play Prisoner's Dilemma once, twice, three times, maybe a

finite time, maybe an infinite number of time. Then, we accumulate all the rewards

all the time to sum overall rewards. A stochastic game really is a generalization

of it, where we play a game repeatedly, but not necessarily the same game. So, we

play a game depending on how we play the game, let's say, Prisoners Dilemma, we

each got some payoff. But depending on how we play the game, we also

probabilistically transition to some other game, play that in turn, and the, the, and

the process continues. A graphical way to look at it is here. If, if, if this here

is a, is a repeated game, where you play the same game over and over again, here,

you play the game and then if you happen to play this, you'll transition to this

game. If you happen to play this, you'll maybe transition to the same game. If you

play this, you, you'll transition here. If you play this, maybe you'll play this game

again, and so on. From each game, you transition probabilistically to, to, to

other games. this is a stochastic game. formally speaking, it's, it's, it's the

following tuple. It's a lot of notation, but the concept is exactly what we, we

saw. We have a, a finite set of state Q. We have a set of players. we have a set of

actions where actions are available to, to, to, to specific players of A sub i, is

the action available to play i. And then, we have two, two functions. We have the

transition probability function. So, this is, depending on the state we're in and on

the actions we took, we move to each of any of the other state s or the, the very

same state with a certain probability as governed by this probability distribution.

And, and similarly, our reward is the reward function which tells us if in a

certain state, a certain action profile was taken by the agents, then this is a

reward to, to that particular agent to, to each of the agents. So, r sub i is a

reward to, to agent i. that's the formal definition. notice that you sort of assume

the implicity that you have the same action spaces here but you, you could

define it otherwise. It simply would involve more notation. There's nothing

inherently important about the action spaces being the same in the different

games within the stochastic game. So, just a few final comments on it. First of all

as we as we saw, this obviously generalizes a notion of a repeated game.

But also, it generalizes a notion of an MDP or a Markov Decision Process. If a, if

it's a stochastic game, if a repeated game is a stochastic game with only one game, a

Markov Decision Process or MDP, is a game with only one player. And so, you have

states there that, where the agents take, agent takes an action, receives a

remuneratory reward, and probably moves to some other state.

And the only difference is that, that he's the only actor in the setting. I mention

this because while MDPs have been studied substantially in a variety of disciplines

from optimization to Computer Science to pure Math and beyond, but also, these two

perspectives of a generalization repeated games, and of MDPs, give you a sense for

the theory and investigations into stochastic games. So, from repeated games,

we inherit the definitions of different ways of aggregating rewards over time. You

can have limited average rewards, future discountage rewards whereas, from the, the

literature on optimization and on MDPs, we get a notion such as stationarity and

Markovian strategies. These have to do with, we also have a

notion of reachability about the structure of the underlying transition probability.

And so again, these are issues that are involved that we won't get to into more in

this lecture but at least we flagged their existence.

探索我们的目录

免费加入并获得个性化推荐、更新和优惠。

Coursera 致力于普及全世界最好的教育，它与全球一流大学和机构合作提供在线课程。

© 2018 Coursera Inc. 保留所有权利。

通过 App Store 下载

通过 Google Play 获取