Tip:
Highlight text to annotate it
X
Welcome to Game Theory Online. I'm Kevin Leyton-Brown, I'm one of the three
instructors for this course. The other two are Mat Jackson and Yoav Shoham both from
Stanford University. You'll see then both in subsequent videos. This video is going
to give you a high level sense of what Game Theory is all about and the kinds of
concepts that were going to think about in the rest of the course. First of all,
before I go on, let me tell you a little bit more about what Game Theory isn't.
Game Theory doesn't use the word game in the way that most of us are used to in
common life and it certainly doesn't think particularly about computer games.
Instead, Game Theory is a way of thinking about strategic interactions between
self-interested people. For this reason, it's very important for economics and also
for computer science, political science, psychology and a variety of other
disciplines. What ties all of these disciplines together is a concern for
thinking about how self-interested participants would behave in strategic
interactions. And also, thinking about how those interactions should be structured,
for example, by a government or by the designer of a computer system in order to
lead to good outcomes. I'm gonna begin by thinking about one such example from
computer science. This is an example that involves networking, but don't be scared
off by the computer science content. It isn't representative of what will come in
the rest of the course. And, in any case, I am not going to assume that you have any
particular knowledge about how computers work in this example. I am gonna begin by
thinking about this pop-up which you might have seen in your browser before. And if
you're like most people, you realize that a pop-up in your browser that promises
slow connection detected, Click Next to correct, maybe shouldn't be trusted. It
might install a virus or otherwise harm your computer, so, you probably wouldn't
click on this. But the interesting thing is if you did, this particular pop-up
might actually help you. I'd like to think about how it works and we can use this
example to illustrate something interesting about Game Theory. Before I do
that, I need to tell you a little bit about how the TCP protocol works, which is
one of the backbones of the internet. So, as your probably know, if you're over here
on the Internet and you want to communicate with some other computer,
which is over here. What happens is that your communication gets broken up into a
bunch of different packets, which conceptually are kind of like envelopes
with a message inside them that get delivered across the network to your
recipient. And when I say, delivered across the Internet, I mean, you don't
actually have a direct connection between your computer and your desired recipient.
Instead, there's a whole sequence and different computers along the way who pass
the message one to the next to get it from you to your recipient, so you pass the
message along the network to some computer you're connected to. It passes it to
another computer and so on down the chain until it reaches your recipient. At that
point, your recipient sees that the message is addressed to it, and it sends
back an acknowledgement to you, telling you that it received the message. And that
acknowledgement, likewise, passes through a whole sequence of computers until it
gets back to you. So far, so good. Here is the catch. Sometimes a computer and the
Internet is overwhelmed with messages, let's say this one right here. And when
that happens, it handles this congestion in a pretty surprising way. It takes some
of the messages that it receives, and it just throws them away, and it doesn't tell
anyone. It just deletes the messages until it gets down to a level that it can handle
again. And then, with the stuff that it can handle again, it continues behaving as
it should passing messages on appropriately. Well, you might wonder,
then, how it is that you end up with reliable communication over the Internet
given that every now and then, some computer on the Internet throws away your
messages? Well, the way that this works is that your computer waits a certain amount
of time after sending a message to see if it gets an acknowledgement. And if it
doesn't, it assumes that the message was never received and sends it again. Here's
the part that's important for our discussion of Game Theory. Your computer
also does something else in this situation. It slows down the speed at
which it continues to send messages in the future on the assumption that there's some
congestion somewhere in the network and that this congestion can be reduced by
bombarding the network with fewer messages per unit time. And likewise, other
computers on the Internet are doing the same thing, that's why we don't have the
network completely saturated, that's why most of the time, we get pretty reasonable
throughput on the internet, because everybody is balancing the speed that they
send messages out using what's called this backoff mechanism in the TCP protocol.
Okay. That's all you need to know about the backoff mechanism. I'd like to think
about the strategic problem that you face in deciding whether to install this
somewhat suspicious looking piece of software. That is, I'd like to ask, should
you send your packets on your network connection using a correctly implemented
version of the TCP protocol which does have the backoff mechanism inside it? Or,
should you run this program and instead use a defective implementation which
disables the back off mechanism and just blasts the network all the time without
any concern for the congestion that it will cause other people or you? Well, this
is a bit of a surprising use of language, but problems like this one are what game
theorists called games. A game in general is any interaction between two or more
people where the outcomes of the interaction depend on what everybody does
and everybody has different levels of happiness for the different outcomes. So,
let's think about a two-player version of this interaction which a game theorist
would call a two-player game. You might incidentally w orry that the Internet has
a lot more than two people using it and so that this two-player restriction is going
to be a problem. You'll have to trust me, that this example skills very naturally to
hundred number of players and everything interesting about it would remain true. So
in the two-player case, we have a question of whether each of the players should use
a correct implementation? Whether one of them will use a correct implementation and
the other one a defective implementation or whether both of them will use defective
implementations. In the case, so we, so we need to say what happens in order to
analyze this. Let's say that when both players use correct implementations, they
both experience a delay of one millisecond. Let's say that if one person
uses a correct implementation and the other person uses a defective one, then
the person with the defective implementation manages to flood the
network with packets in a way that causes the other person to backoff pretty
heavily, causing the person who backed off to experience a much longer delay and the
person with the defective implementation to get their packets through virtually
immediately. Lastly, let's say, that if both people use defective implementations
of TCP, then we're again in a symmetric situation where they both experience the
same delay and they both experience a bigger delay than they would have before,
because there's now a greater chance that their packets will be lost at every stage
in the chain, and so, it will take them longer to send a message. Well, I'd like
to encourage you to play this game with a friend or to play it even just in your
head, or best of all, to play it on the online system that we've provided where
you can interact with other students in the class. What do I mean to play a game?
Well, this game might not seem very exciting to play as compared to other
things that you would call games like soccer or chess, but in principle, all of
these games are the same. There are sets of actions that players can take and after
ever ybody has chosen what they are going to do in the game, there is some result
where everybody feels a different level of happiness. This very simple game has each
player choose either to use a, a correct implementation or to use a defective
implementation. And once we know what both players will do, we can look at these
rules that I have given here and decide how happy both players would be. Of
course, nobody likes delay, so the players are trying to minimize the amount of delay
that they experience in the network. So, if you wanted to minimize the amount of
delay that you experienced, how would you play this game? That's kind of the most
natural question to think about when you're thinking about a game theoretic
setting, but I'd like to invite you to think about a bunch of other more abstract
and philosophical questions, which we'll also address throughout this course. First
of all, do you think it's the case that all users should be expected to behave the
same in a situation like this? Relatedly, if you're not one of the players of the
game, but rather you're someone who cares about how the whole system works from the
outside, for example, the designer of the network. What kinds of global patterns of
behavior would you expect to see emerge? You'll notice that these numbers that I
came up with here are a little bit arbitrary and they're not very precise.
It's reasonable to wonder how much these predictions that we can make about how the
game should be played and what behavior would occur, depend on those numbers. Is
that the case for slightly different numbers we would expect to see very
different behavior? What effect would there be if players could communicate with
each other before they played the game in a non-binding way? What effect would there
be if players could repeatedly play the game against each other either for a
finite number of repetitions or infinitely? Finally, how important is it
how I model my opponent? Is it different if I think my opponent is rational and
does something that is in his or her own best interest? Or, would I play this game
in the same way regardless of how I believe my opponent is thinking about the
game? These are examples of the kinds of questions that this course will help you
to think about and will offer you some answers too. And the TCP Backoff Game is
just one example of a real world situation that we can examine using Game Theory.
Throughout the course we'll describe many more real world examples that Game Theory
can be used to think about. Thank you for joining us in this course. We hope you
have a great experience and we look forward to seeing you in coming up videos.
Bye, bye.