Watch videos with subtitles in your language, upload your videos, create your own subtitles! Click here to learn more on "how to Dotsub"

1-1 Game Theory Intro - TCP Backoff

0 (0 Likes / 0 Dislikes)
Hi folks, welcome back. So this is Matt Jackson, and we are talking now about defining games and we work to some basic definitions of the key ingredients in, in games. So let's take a look at some of those. So obviously one of the most obvious ones is the players in a game. So who is making the decisions, are they people? Are we talking about governments negotiating over trade agreements? Are we talking about companies, choosing astrologies for developing the products? do we, do we want to get down to the, the point of modeling people within a firm, as opposed to the company as a whole? so this whole, there's a whole series of questions about how we're going to choose the players, but they're, they're going to be the central decision makers in what we're doing. next we have to decided how we're going to model the actions. So what can players, what actions can players actually take? So, when we're, later on in the course we'll be looking at auctions, they'll have bids, so they can enter a number of bids. when we're talking about bargaining, it might be deciding whether or not to strike. when we're thinking about investing, it could be that an investor is deciding how much of a stock to buy or sell, when to buy or sell it. how they should react to other people in the market, how they should be conditioning their decisions on, on prices. when we think about voters, how do they vote. So, there's gonna be a whole series of actions, and we'll want to be careful in making sure that we have the essential actions modeled. finally, payoffs. So, what's motivating the players? Do they care simply about some sort of profit. Do they care about other players? So how are they receiving utility as a function of what, what the actions lead to in the context of the game? So there's basically two standard representations of games. one is, is what's known as the normal form, and that's what we'll be starting with in the course, and what it does is it, it's a, a very simple and, and stark representation of a game. So it lists what payo ffs players get as a function of their actions. normally, it's, it's thought of as, as, as if players were moving simultaneously, but strategies, and we'll talk about this in more detail, can, can encode many things. So, the other alternative representation is what's known as the Extensive Form, and that includes more explicit timing in the game. So who moves at what, at what point in time. So that's going to be represented often as a tree. So, for instance in chess one player moves first. the white player generally moves first, and the, the black player can see the, the move by the other player, react to that. And so far. So that's going to be better represented as a tree than, than in normal form. So keeps track of also what players know when they move. So in poker, somebody moves first. They may give a bet, but the other player only sees the bet and not necessarily the card that other player sees. So in some cases we'll have sequential games, where players will have different information at different place and time. We'll wanna talk about modeling that explicitly too. So we're gonna start out with the normal form, and then we'll move later in the course to the extensive form, and we'll talk about the relationship between these two in more details. okay, so normal form games. What are the key ingredients? again, players. So we're going to have generally we're going to think of finite sets of players. So one through n, little n will represent the set of players. Generally, we'll index these things by an i so we'll use a little i to represent the, a generic player. The action set for, for players. we'll represent by a sub i. Okay, so we'll let that represent the actions of player i, and then we'll talk about profiles of actions which will just be a list of what every player is doing. So for instance are they the, the, deciding to, cooperate or not to cooperate with other players, for instance. In the, in the Prisoner's Dilemma, that we'll take about. the utility function is then a payoff function, which indicates as a function of all the actions that are played What's the payoff for the different players? So for each player i, we end up with a function which tells us how they evaluate outcomes of the game. And again, how they evaluate these things could, could encapsulate many things, and it's going to be very important to make sure that we were getting the right representation of what really motivates people. Okay. So, often, when we, when we represent normal form games, a very simple ways of doing that is just matrix representation. So, let's just look at, at, the, the most standard representation of very simple games. writing at two player game as a matrix. So we'll have one player one, will be the role player. Player two will have, be a column player. So they're gonna choose actions that'll be represented in a column of the matrix. And the cells, inside the cells will then represent the payoffs. So for instance, the TCP Backoff game that was talked about in the earlier video, can be written as a matrix as follows. So, the roleplayer, player one can be written as either C or D. So this is player 1's choice, generally known as the row player. This is player 2's, the column player, and they represent the, the choices that they have, and in inside the cells are the payoffs to the different players. So if player one cooperates and player two cooperates, then these are the payoffs to the two players. The first payoff, player one, second playoff, player two. So this is going to the column player, this one is going to the row player. Okay? Then we end up, you know, for instance, if the row player chooses D, and the column player chooses C, then we end up with a payoff here of zero to the row player, and minus four to the column player. So the matrix is a very simple way of representing all of the, basic elements of the normal form game visually, so that we can actually keep track of exactly what the strategic interaction is, and, and what players would like to do as a function of the game Okay. let's talk about another game that we won't be able to write down in such a simple form. so let's think of a large collective action, game. So, for instance, whether or not a population wants to revolt against its government So here, we have many more players. So let's imagine that we have a to write that down as a, as a matrix on our screen, so we can do that more abstractly. But we'll have ten million players, whether they, whether their actions here, let's keep it very simple. So they have a choice here of either revolting or not. So the action set is binary, two choices. then the payoffs are gonna be critical thing in this game. what happens? Well, let's say that in order for revolt to be successful, you need at least two million people to participate. So in this particular stylized example, what do we end up with then? We, we can represent the successful revolt as the player getting a path of one so "Ui" of the action profile "A" is equal to one. If the number of people here, the number of, of players, j, such that they picked to revolt, the number of this is at least two million. So, if we end up with at least two million people, revolting, then player i, gets one, and note here that this is true regardless of whether I as one of the revolt's participants, so this is a game where you care about the end outcome, not necessarily getting utility out of the participation.We could change this and have people get enjoyment out of the participation or have cost of the participation directly as well. Okay, so what's, what happens if, if things fail. here, if we end up with less 2,000,000, then it depends on whether you were a participant in the revolt or not. So, if you, if player i was a participant in the revolt and it fails, then they get a payoff of negative one. So, this could be in a situation where they're punished by the government, or face some other kinds of sanctions, and they get a path of zero if they were both not successful and they didn't participate so they weren't one of the people that wa s actually revolting. Now obviously this is very stylized, but what it does capture is that players have to strategically analyze and predict what other players are going to do and their pay-offs depend not only on what they're doing, right so here we have a situation where player i's payoff depends on whether they revolt or not but it also depends on what other players are doing and it can depend in fairly complicated ways on what all the players in the game are doing. Okay, so just in summary, in defining games we have two different forms, the normal form and the extensive form. For now, we're starting with the, normal form critical ingredients, players, actions and pay-offs. Later, when we get to the extensive form, that's gonna bring in timing, information, and so forth. So, extra things, that will account for more detailed, representations of, of the, strategic interaction by players.

Video Details

Duration: 11 minutes and 23 seconds
Country: Spain
Language: English
Genre: None
Views: 61
Posted by: q21250 on Jan 16, 2013

1-1 Game Theory Intro - TCP Backoff

Caption and Translate

    Sign In/Register for Dotsub to translate this video.