# 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.