Algorithmic Game Theory (Lecture 1: Introduction and Examples)

so I want to welcome you to CS 364 a this is a course on algorithmic Ain theory which very loosely is a survey of topics on the interface of on the one hand computer science especially they're not only theoretical computer science algorithms and economics especially game theory so the plan for today's lecture is I'm just going to give you sort of a taste of what the course is going to be about the course is loosely organized around three themes and I'll give you an example for each of the three themes and if this is stuff you find interesting and exciting then I hope you'll stick with me for the rest of the quarter for those of you just coming in there are sign-up sheets going around so before you leave please put your name on the signup sheet with your email all right so let me say what the course goal is for each of the three themes of the course one at a time so the first course goes a little bit of a mouthful but I'll give you an example so it's about designing systems where you have participants and the participants are both autonomous and strategic they have their own interests not necessarily the same as yours as a designer and despite their strategic behavior you want the system to function well so let me give you an example really frankly it's more of a non-example a sort of cautionary tale of how when you don't take into account strategic behavior things can go wrong it's pretty recent example from the Olympics last year in London like every Olympics this one had its fair share of scandals but one of the scandals was in a sports which is not really known for its scandal it's not known for you know failing drug tests and that sort of thing anyone guess what I might mean bad specifically women's doubles Badman so let me tell you what happens so let me tell you how the tournament is designed for how you decide who gets the gold silver and bronze medal in women's doubles Badman in the Olympics in 2012 the tournament structure is familiar to any of you who follow World Cup although there are only half as many teams so there are two phases a round-robin phase followed by a knockout stage so phase one was the RAM Robin specifically there are 16 teams overall so they were organized into four groups of four teams each groups a B C and D round-robin just means that whatever group you're in you play the other three teams in your group and you don't play any of the twelve teams in the other groups okay and the way it works is in each group the top two teams advance to Phase two to the knockout tournament we so we begin with sixteen teams after the round-robin matches we will have narrowed it down to eight this is a good time to come in so those of you who've taken classes for me before are probably the only ones not shocked with a handwriting quality you can always ask me for clarifications I give you a promise right now I will never get upset if you can't read something I read on the board ask me as much as you want so from each of the four teams the top two teams of the group advance so those eight teams make it to phase 2 which is the knockout knockout just means you lose once and you're out so you start with a teams those are the quarterfinals the four losers are out the other four teams make it to the semis they're the two losers get knocked out so they play the bronze medal game and then the two teams that make it to the final play for the gold and the silver now let me explain why this is not necessarily a system designed to function well with strategic participants my claim is that in this tournament structure there is a fundamental misalignment at least there can be a misalignment between on the one hand what the participants want and on the other hand what the tournament designer wants so a misalignment between the participant goals and the designer goals and when this happens you have trouble so what do the participants want well that answer is straightforward every team wants the best metal that it can get okay what does the tournament designers want first of all who is that so let's basically the Olympic Committee so what's their objective well and hindsight it looks like they didn't actually think about that question very carefully frankly but in hindsight certainly what they claim to care about among other things is that every team tries us hard to win every match in which it plays so let's say I want best effort from all teams and all matches yes ah they may want that as well okay so I'm not claiming this is even their primary objective but at least certainly something they explicitly stated after the scandal unfolded now do they want you I don't think they thought about in advance frankly but let's just take on face value what they said afterwards what they said afterwards was not that there's no the primary objective but that certainly it was unacceptable if this criterion was not met okay so they stated that explicitly all right now if you didn't read about this scandal at the time you'd be right to scratch your head if you write to sale you know where is the misalignment between these two things as a team you want to do as well as possible the designer wants people to try to win you know why would you not try to win in other words how we're losing ever helped you in this tournament for example consider a knockout tournament okay like Phase two I mean what is losing do for you losing gets you out of the tournament it is obvious and a knockout tournament that you better try as hard to win every match because losing kicks you out immediately the question how could losing help a team and it's sort of subtle you know but the the teams in the tournament we're very smart and so here's what triggered the problem what triggered the problem is what as far as you know non expert like me can tell is just a truly kind of random fluke event which was in Group D on the last day of round-robin play there was a shocking upset namely the Danish team and I'm not going to embarrass myself trying to spell or pronounce these last names I'll just use initials the Danish team PJ upset the team that everybody believed was by far the best team in the world team from China eww okay bye upset I mean everybody expected qlw to win and moreover nobody I mean my interpretation is that even in light of this upset of this new information again people believe that they play again 99 times out of 100 to ww-would win people did not seem to believe that qw was not in fact the much better team even in light of this upset so let's write even though she I'll just write qw much better but of course what I mean is qw believed to be much better okay just to lend some credence to that let me just state now that at the end of the day when the tournament finally completed qw did indeed win the gold medal so it seems like this was a justified belief now it turned out so this is round-robin played remember two groups two teams from each group make it to the knockout now qw lost this match but they still made it to the knockout tournament as a results of this match PJ one group D they're the top team Q W came in second in Group D and again both of them therefore proceeded to the knockout tournament so this happened in the morning on the final day of round-robin play now here was the next match and this was the first of the two controversial matches there is another Chinese team XY that was not thought to be as good as QW and it was playing the South Korean team KH and they were both two no in Group A play so they were both assured of proceeding to the knockout tournament and this match between the two of them would just decide which of them was the group a winner and then which of them the loser of this match would be the second best team in Group D sorry in Group A so knockout was assured this was just to determine the seating and here was the issue so here was the fact just the way that should knockout tournament was arranged which led these two teams to think carefully about what they wanted to do in this match so the winner of group a that is the winner of this match between X Y and K H in the knockout tournaments would potentially meets this extremely fearsome team who w in the semi-finals it wouldn't be their first match it would be their second match assuming they won and assuming q w1 on the other hand the second best team in Group A the loser of this match would not have to face this fearsome team q w until the final and the difference between meetings Q W in the semi-finals whereupon losing then means a bronze medal is the best case scenario versus meeting them not to the final at which time a silver is assured that difference was apparently viewed by both teams to be such a big difference that both deliberately tried to lose this match if you're having trouble envisioning what it looks like when to Badman teams are at the same time trying to lose a match I'm here to tell you I found the match on YouTube and there's a link to it from the course web page so the same thing happened in a second match between the other South Korean team and an Indonesian team okay for exactly the same reason question so the so there's a good question here which is is it relevant that two of the teams of teams involved your Chinese or not it's a good question so let me so I can first tell a story under the assumption that it was irrelevant and that's the thing that's true I'm claiming it's just a useful thought experiment to proceed through the first order from again the sort of amateur you know perspective of myself I thought all teams were reasoning as if qw would just win every match that it played and that was just a given yeah the behavior that people exhibited was indistinguishable from that explanation okay and if you know you're going to lose to qw then the first order optimization problem is to meet qw as late in the tournament as possible okay because that dictates how high you're going to place now an interesting twist is that the qw team was Chinese and also one of the teams in the first controversial match XY was the other Chinese team and there is apparently lots of history with when you have want more than one team from China in the same tournament they work hard to meet each other ideally not at all but if necessary as late as possible so obviously in the final there's no other option so you know you could ask the question it wasn't relevant whether they're from China or not it's hard for me to really you know answer that an unequivocal way I just want to make the point the incentives are a problem even if all of these teams were from different countries I think both teams couldn't you couldn't cute qw upset she w's next matches in the knockout yeah QW next matches the quarterfinals so okay all right so again the results X Y K H both try to lose the match so this is what resulted in derision scandal and ultimately the disqualification of the four teams involved in the two controversial matches that I mentioned question well so I think the question is I mean how does KH view the situation QW never through any match I said upset I did not say tank yeah so the first thing I said was as far as I can tell and actually it just for the record as a failure very diligent instructor I watched some of that matches well I'll tell you it was close and again it may just be that they were better at throwing the match but I really don't think so my belief some people actually criticized you know these four to scoffs my team's not for throwing the match but for doing it so heartlessly anyways so my belief you know I'd bet a small amount of money not a large amount of money but a small amount of money that the Danish win is actually an upset it's just simply a rare event you know and it does happen you know well any of us who follow sports know that sometimes their upsets it seems like a legitimate upset also again trying to teach you to think strategically suppose you're the best team right sort of you I mean you should just win right you rightfully deserve the gold medal you expect to beat anybody you you meet along the way and again the other thing is their match was first so there was no way for you know if q-w wanted to help out X Y they probably thought winning was doing them a favor so they probably wanted to win that match even from the Senators perspective I mean again I don't there's no way I can make unequivocal statements about who meant to do what all I can do is watch the matches my belief is that qlw did not throw their match but I don't know what it would mean to prove that so the point is that when you're designing a system like a tournament or like an auction or like a computer network and you have participants that are strategic the rules of the game matter okay you cannot expect participants to behave in a way other than in their own interests that is an unreasonable assumption of the designer you must account for strategic behavior if you don't do it carefully you will get unexpected and often undesirable consequences and the first almost 50% of the class will be on principles for system design that properly take into account strategic behavior so the rules matter and the name of the field is mechanism design and again the goal of the mechanism design is exactly what I said our first course poll was how do you design systems when you have strategic participants so that the end result is something you want is a desirable outcome from the designer perspective so this is this is a theory course and I'm not going to apologize for it there'll be plenty of theorems and proofs and so on that said we will occasionally look at some detailed case studies and in particular for mechanism design so where does this stuff get used so killer apps include internet search auctions if you want to know how Google made all their money this is how they do it did it frankly the first order using option theory and internet advertising if you want to know how it came to be the television stations own so much less of the spectrum and telecom companies own so much more to serve as your wireless devices that's also through carefully crafted spectrum options to reassign that public good it's been used for now 60 years to assign medical residents to hospitals similarly schoolchildren to elementary schools and even to figure out kidney exchange so this is when you have two pairs of incompatible donors but there are cross compatibilities and so how do you do that taking into account strategic behavior mechanism design gives you tools to answer that question and design appropriate systems so this is a well developed field in microeconomics and along the way we'll certainly be covering some of the traditional econ approach to mechanism design this is a computer science class however and so there will be a consequence first of all in the applications I choose I'll show you some of the killer applications for the computer science side but even in the theorems that we prove I'll be studying recent contributions about computer science with a focus on robust guarantees and also on computational efficiency two properties that have been largely ignored on the economic side now sometimes you don't have the luxury of designing the rules of a game from scratch rather there's a game that's occurring in the wild and maybe it's in the internet if it's in a road network but it's a system it's out there you want to understand it and maybe improve it and the perspective we're going to focus on for these games in the wild that we want to understand is we're going to want to understand the consequences of strategic behavior maybe it leads to some degradation and system performance but maybe selfish behavior is essentially but not again this will be more clear with an example so let me tell you about Grace's paradox this is a very nice counter to counter intuitive example it's been around 668 amaze your friends at your next cocktail party so we're gonna have a network that can model a lot of things but just think about cars on the road it's probably the simplest thing to think about so think about this as a flow network for those of you who are familiar with them so a bunch of traffic morning morning rush hours say all leaves s at the same time this is thousands of cars and these are autonomous drivers they can take whatever path they want I've given them a network with only two paths the upper route and the lower route so the there are four roads in this network two of them are very simple another to understand two of them you should think of as being sort of long highways lots of lanes they never get congested at least up till like 2010 I would have countered highway 280 in this category so officially we have a function X is the fraction of traffic that's using this road and this is the travel time and hours so this is a constant function this says no matter how congested this road gets that traffic experiences an hour of travel time okay so the other roads are more interesting they're more like what you're used to where the more traffic uses a road the longer it takes any of that traffic to get from the beginning to the end so for simplicity let's just say it's the identity function so what this means is that a hundred if a hundred percent of the traffic uses such a road it takes a full hour if only half of the traffic uses this road it takes a half an hour and so X is the fraction of the drivers that are using that road yeah everyone starts with s let me write down a little more stuff just to make it precise so lots of cars leave s or key at same time each one can pick either route that it wants now I'm not going to give you any formal definitions today we'll have plenty in the weeks to come but you all probably have a vague sense of what an equilibrium should be a steady-state where nobody wants to move so what seems like the sensible steady state in this network so imagine you know these are the same people commuting you know at 8:00 a.m. day after day you know from Stanford to San Francisco where do you expect this to settle down what do you expect the distribution of the traffic over the two routes to be excellent at steady-state your intuition should be that this split 50/50 why well you know neither one is better or worse than the other right so each one has a combined travel time of 1 plus X and so if there's more than 50% on one of them that's going to be slower than the one that has less than 50% you listen to the traffic report you know on the way to work they're like oh man tomorrow I'm gonna take that other route it was less loud it was less loaded it was faster ok so I'm gonna just leave you with this hand wavy explanation for today it's correct though the sensible equilibrium in this network is to have a 50/50 split so how long does it take everyone to get to work then what's the common commute time that everyone experiences I don't a half right so commute time three halves so what you should be saying is yeah doesn't seem that paradoxical right oh I forgot that I wrote braces example it's called braces paradox and there's no reason you should be impressed up to this point but I heard about the newest thing coming out of Google X it's a teleporter so we're going to do is we're going to put one @v that lets you go instantaneously to W and not only that it has enough capacity for everybody okay so we change the network and effects we add this new road with teleporter going from V to W instantaneously okay cool alright so now we got to say all right so what you know what's going to change what's the new traffic routing that we expect so here's the first question right so so consider the very first day that this thing gets installed all right and you're one of these drivers and you've been going on the upper route all along are you gonna still use the upper route yeah right you want to use this newfangled device not just because it's cool but because it saves you a half an hour at least if you think of nobody else changing it saves you a half an hour alright so currently it's taking you half 30 minutes and then 60 minutes but if you switch to the zigzag all of a sudden it's 30 minutes plus zero plus 30 minutes just an hour okay so you shaved 30 minutes off your commute by using the teleporter okay alright so the only issue though is uh yeah you're not the only person in the world right you're not the only one who wants to use a teleport now maybe you're thinking yeah but the teleporter can accommodate everybody so so what there's no congestion at the teleporter it's not so simple okay everybody is going to switch to use the teleporter there's no reason not to so you'll agree that that gives us this traffic path everybody on the zig zag are we better off what's our commute time now it takes two hours now everybody takes this congested will route that's an hour teleport is free for everybody but now everybody's stuck on this WT edge and that also takes an hour two hours but it's not like people were reasoning incorrectly in this network with a teleporter it is a brain-dead strategy to use the zigzag path you should always do it it's always better than the other two alternatives no matter what everyone's doing that's called the dominant strategy okay it's a foolproof for you individually to take the zigzag but everybody does it there's lots of congestion and it's worse than when you didn't have the teleporter at all that's races paradox [Music] so corollary of braces paradox which is much more intuitive is that selfish behavior by everybody doesn't always give the best thing for everybody so in this context selfish routing need not minimize the commute son right so with the teleporter installed if instead of everybody picking routes just by themselves if instead there was some altruistic dictator that could just tell people which routes they absolutely had to take and they had no choice you can do better right if nothing else you could just reinvent that 50/50 split and go back to the 90 minute commute and in fact if you think about it there's actually nothing better you could do there's no way to make use of the teleporter in a helpful way so in that augmented network selfish routing gives you a - an altruistic dictator could give you a three hats so you could improve the commute time by 25% with centralized control and there's a concept from computer science called the price of anarchy which is exactly this measure so you look at what's the performance of a system with strategic behavior you take as a hypothetical benchmark the best possible system performance even if you could control everybody's actions and you look at the ratio so in this braces Network it's 2 over 3 halves also known as 4/3 ok when the price of Anarchy is one that's the very happy situation where a strategic behavior gives you exactly what you wanted anyways the closer the price of Anarchy is to one the more robust your system is to strategic behavior the more essentially benign selfish behavior is in that system so from an engineering perspective then the well-motivated question is well okay it's we certainly want to understand you know when is the price of Anarchy equal to one that's the best-case scenario but it turns out this theory has much wider reach when you study which application domains and what conditions allow you to guarantee the price of Anarchy is close to one say something like 4/3 so the goal of the week's of the class which we study this concepts will be for what applications and with which conditions is the price of Anarchy close to 1 and believe it or not despite the fact that people have been thinking about equilibria for decades if not centuries and certainly we've known about the inefficiency of things like Nash equilibria forever since you know well before I was born it wasn't until computer science got interested in this that they proposed the price of Anarchy and started proving theorems about it that people really started quantifying the inefficiency of equilibria that's a contribution it turns out from the computer science world so I'm going to talk about that for a few weeks sort of in the middle of the class so killer applications I will talk about network routing scheduling problems as applications for simple auction formats and why they do well even in complex situations and so on for example one thing we'll learn is that a modest amount of over provisioning of network capacity so for example just keeping a telecommunication network at a max link utilization of 90% that is condition that's already strong enough to guarantee that the price of Anarchy is close to one and so we'll give the rigorous theorems establishing that later on in the course no so I mean I mean I have to say I mean in braces paradox I mean it's not I mean this is a real phenomenon so it's not gonna come in so I mean there is some you know you can talk I mean you're basically saying you know happen you have some kind of collusion either explicit or implicit and you do see that coming up for example when you study repeated games you get some a much richer set of equilibria which can include so I mean one of the most common places people study this is the prisoner's dilemma which is really the distillation of the problem that's going on here and especially when you look at an iterated version the prisoner's dilemma this the dominant strategy becomes more and more absurd so then it's well motivated to ask you know what's a better behavioral model that explains what you see in real life honestly you know there's been experiments with braces paradox like issues in real life this is what happens so I would argue here we don't need a better behavioral model simplistic though that it is it's very predictive that said and other applications it is a relevant question I don't think we're gonna wind up seeing it in the course though but it's a good question ya know you can't do better than optimal so we've sort of concocted it so that it can't be better than one so we've put on the bottom the best thing that could happen even if we had full control over the system so just by definition it has to be at least one yeah yeah it would make sense yeah so the Army is just you can't do better than optimal yep okay so the question was about dominance strategies and do we assume you know what is our behavioral model and pretty much in this class we're always so we want to do analysis of systems with strategic participants and to do that we need some kind of behavioral model we need to have some model about what people actually do when faced with some you know decision to make and we will always at the very least assume that if players have an obvious dominant strategy then they will take it in fact they'll be taught so a focus of this course which again sort of differentiates four to a large extent the computer science approach versus the more traditional approach is trying to push toward weaker and weaker behavioral models making as few assumptions as possible so at times in the course I will make assumptions like we're going to assume players play the nash equilibrium under that assumption the following things are true but you know also there'll be a big push in the course to weaken up the assumptions significantly and it's hard to get much weaker than assuming that when you have a dominant strategy which again means it's always the best thing for you it doesn't matter what everyone else is doing that's what it Donna strategy is it's hard to get a weaker model then assuming that when that strategy exists people will play it that'll be sort of our best-case scenario as far as how weak the behavioral model will ever get so I think I have time for a quick aside so a little over 20 years ago Conan Horowitz wrote just a two-page observation in nature very cute observation which points out that braces paradox it's not really about traffic networks it's really something much more fundamental that you don't need traffic they propose the following physical experiments involving strings and springs so you take some fixed base something like this and from it from below you attach a spring to the bottom of that spring you attach a very short string that's a string right there then another spring and at the bottom you have a heavyweight okay and so when you hang this weight from below of course it stretches out both of the springs and it pulls that little tiny string taut I am also going to attach two strings at the moment seems superfluous the first one from the top of the top spring to the top of the bottom spring the second one from the bottom of the top spring down to the weights okay so they're gonna be you know just long enough so they have a tiny bit of slack okay but here's what's interesting suppose now I take a pair of scissors and I go up to that little taut string in the middle and I go snip I cut it this contraption will reposition itself somehow and the weights right three things could happen could stay in the same place could go up go down so who thinks it stays in the same place the weight when I cut the string who thinks it goes up these it goes down all right [Music] properly implemented the weight actually levitates off of the ground despite the fact it seems like you made this system weaker there's two arguments you can use to see why that's true one is a reduction one is direct the reduction is to the traffic Network we just saw the same equations that govern the physical position of these systems and strings and springs are those that govern the traffic equilibria in these networks the analogy is force through the strings and Springs corresponds to traffic flow through the traffic network travel time on the Wrights corresponds to distance on the left cutting that taut string corresponds to removing the teleporter from basis paradox recovering of the superior equilibrium with 25% less commute time in principle you can build this contraption so that this levitates so near 75% of its previous high base to wheat distance this is not just a theoretical exercise last time I taught this class I offered extra credit for students who would build a demonstration and upload it to YouTube at least three students did it maybe more but I found three there you can find links from the course webpage so it can be done no one has reached 25 percent decrease but I think someone got 10 percent or so so have a look if you think you can improve on last year's submissions on any dimension that you see fit be it either you know production dramatic contents how far up it goes any of those things again there's a extra credit redeemable by the end of the class if you like so braces paradox not just about traffic networks so let me tell you about the third biggest theme of the class which we will be talking about just for the final few weeks and it's going to be the most computer science e part of this album the game theory class we're going to see what we can say about a very fundamental question equilibria we always talk about we analyze them how do we get there do we get there our systems at equilibrium right some games are easy to play we talked about braces paradox with the teleporter we talked how using the teleporter is a dominant strategy there's no reason not to do it that game is easy to play some games are not so easy to play if you come on Wednesday we'll talk a little bit about first price auctions and you'll see just how hard some games are to play given that how do impossibly complex games players reach an equilibrium even more fundamentally do they even reach an equilibrium and what can complexity theory computational complexity theory tell us about this fundamental question ok so let me talk a little bit about equilibria again I don't want to be too formal with the definitions now I'm sure you all have a vague sense of what it means it's just a system or a game as at equilibrium if you know for each participant if everyone else keeps doing what they do I'm gonna keep doing what I do now some games it's actually a little tricky to define equilibria alright so hopefully most of you know the game rock-paper-scissors okay but maybe just to remind you what who's up for a few a few rounds anybody wants to play for house rocker okay ready one two three one two three one two three Oh senator this tournament's man so are you saying that you know about rock-paper-scissors tournaments yeah you know I think it's like pool you know what's like you get these people and then they claim like they just are better the more they drink you know but really they just are less aware of how badly they're losing the more than I love betting those people yeah okay so to remind you to rock-paper-scissors three strategies two players and one person wins one person loses so that's easy to encode and what's called by matrix game format alright so I put it up on the board for you so when there's two players you just call one the Rope player you call the other one a column player and rock-paper-scissors so in our first two rounds we tied and when you tie you both get zero payoff and then there's the cases where it one beats the other right so paper beats rock so the first number is the rope players payoff the second one is the column players payoff scissors beats Rock and you know the deal okay so in general and a by matrix game you have rows you have columns each matrix entry has a pair of numbers the first number is the row players payoff if that's the outcome the other number is the column players payoff okay now it's pretty clear in rock-paper-scissors is there's no deterministic equilibrium right so if we each pick a single action at least one of us would want to change assuming they stayed the same thing right if we both pick Rock actually both of us want to change assuming the other one does not you want to change to paper if we play different things that whoever's the loser wants to switch to the action that would beat the other player okay so defining deterministic equilibria you could try to do it but you're not going to get any in this game so what's really important in Nash equilibria by the way I hope no one here thinks they know what a Nash equilibrium is because they watched him movie A Beautiful Mind are you all like too young to see that movie it's gettin old now who's seen a beautiful mind on the first exercise set there'll be a question asking to explain why they do not correctly explain the Nash equilibrium in that movie alright so a really key idea then in defining Nash equilibria is allowing randomization okay which actually makes sense right if you're playing rock-paper-scissors against somebody else to me my opponent looks randomized I'm just trying to guess kind of which is the most likely action they're going to play next so in Nash equilibria you allow players to it's called mixing mixed strategies or randomized strategies and in rock-paper-scissors there is an equilibrium if you allow randomization okay so each player randomized is uniformly then I claim you get a Nash equilibrium and then sometimes people say mixed just to emphasize that you can randomize so what do I mean by this well if I'm picking a row uniformly random and my opponent's picking a column uniformly at random but you should check is that my expected payoff is zero okay that's an easy computation you don't see in real-time but trust me it's an easy computation and actually no matter what I switch to if my opponent just keeps randomizing uniformly it doesn't matter what I do I'm gonna get expected payoff zero no matter what I do okay so in this sense if they keep doing what they're doing I might as well keep doing what I'm doing and that sense it's an equilibrium in fact as I'll ask you to verify on the exercise set it's a unique equilibrium in the rock-paper-scissors game randomizes what's other randomization that's a good question I look I look for it I look forward to seeing your research report on the topic firsthand experiments of course well then you can be like the null hypothesis all right so you know all right so this work a so rock-paper-scissors has an equilibrium in that sense right that's pretty limited right so this is not why Nash got the Nobel Prize he got it because he showed actually forget about rock-paper-scissors every game every game not just rock-paper-scissors has a Nash equilibrium might have many but it's definitely going to have one okay I'm just gonna stay the special case here every by matrix game meaning a game of this form with any numbers at all as a Nash equilibrium in fact Nash's theorem applies with any finite number of players doesn't have to be two players yep no but you know basically everyone plays a mixed strategy and holding everyone else fixed if you do anything else your expected payoff can only go down so if everyone else keeps doing what they're doing you want to keep doing what you're doing okay right but we're gonna be R scientists right give us something we can use don't just tell me that it's there tell me how to find it okay so there's more good news which will you know I'll give you the proofs for this in due course which is for zero-sum games so that's like here but notice in every single matrix entry the two numbers sum to zero in zero-sum games not only is there a Nash equilibrium but we can find one efficiently meaning in polynomial time so one way to do this is linear programming that's relatively heavy machinery if you're willing to compute something which is almost in equilibrium then in fact very simple iterative learning strategies can be used to compute an approximate Nash equilibrium and that's very suggestive that this is a sort of meaningful equilibrium concept not only is it out there but if players learn in a natural way over time they'll actually be able to compute it on their own and again you know details in due course [Music] so nachas theorem is 51 this has been known for a long time decades and decades but a relatively recent and just quintessentially computer science II contribution to this line of work is a negative result saying that in general if it's not zero-sum then under suitable complexity theoretic assumptions in fact there is no efficient algorithm for computing a Nash equilibrium such an algorithm does not exist so this is just from 2006 cannot compute one in the poly time in general now as usual whenever some computer scientist says something about some algorithm not existing you know unless you're talking about the halting problem run decidability or something like that usually what they mean is under some complexity assumption algorithms don't exist right so like an np-complete problem often will in a Cavalier manner say there's no poly time algorithm of course we mean assuming P not equal to NP there's no pala time algorithm so this situation here is similar although interestingly this theorem is not np-complete or let me phrase it as more of a mind bender to make it actually true this problem is not np-complete unless NP equals Co MP so it's unlikely to be np-complete but it's also unlikely to be in P okay and there are rigorous statements of all of those we're not going to go through all the proofs the peers get pretty hairy but I'll give you the vocabulary so that you're totally literate and what the formal statements are and what they mean okay so it's not np-hard there's a different really until recently very obscure complexity class called PP ad which has been resurrected by this Nash equilibrium computation problem because P P ad turns out to be D complexity class it was sort of defined to be you know the one for which this is complete and again I will demystified all of this in the last couple weeks of the class but here's the point here's why this is interesting here's why you should care two reasons [Music] so what well so first of all and this is just really for the hardcore computer scientists among you on a technical level this means that nash equilibrium has furnished us with something very rare a natural computational problem intermediate to P and NP complete and in your studies of it you've seen very very few problems of that type right you take your 100 level classes even your 2 in 300 level classes everything inside the class NP seems to fall neatly into one of these two classes P and NP completes who knows if some things conjectured to be in the middle anyone sort of to quite famous examples other than this factoring good any others graph isomorphism there's another one you might have heard about the point is computing Nash equilibria the most fundamental concept in game theory furnishes a third and it is this result that establishes this fact proving at the PPID hard says there's unlikely to be any polynomial time algorithm so that's pretty cool so intermediate to P and P it seems but you know on a conceptual level it really suggests that we take a closer look at the notion of Nash equilibrium as a predictor for human behavior at least in all game theoretic scenarios most of us don't believe that you know humans can do computations systematically faster than Turing machines so if there's no polynomial time algorithm for solving a problem in general in the worst case many of us don't foresee human behaviour solving that same problem say within our lifetimes so if computers cannot find equilibria in general in the worst case perhaps strategic participants can't either so this cast doubts on using the Nash equilibrium as a universal predictor of the outcome of strategic behavior because of an intractability critique now there are of course many many complaints that people have had about Nash equilibria ever since they were defined starting with the fact that they're not unique so this is by no means the first nor even necessarily the most important critique of Nash equilibria but it's an important one and it's one that computer science is uniquely situated to make and that's why I want to highlight this negative result in that final section of the course ok so that concludes what I wanted to say by way of introduction I wanted to wrap up by just telling you a little bit about expectations how the course is going to work and taking any questions you might have so what do I want from you so you can take this course in three different ways I welcome auditors and then of course I expect nothing show up when you feel like it or not I did that with many courses and last student time even as a professor I do that sometimes you can take a pass/fail and you can take it for a letter there'll be two types of assignments they'll be what I call exercise sets they will be weekly they'll go at every Wednesday they'll go out the following Wednesday my goal for the exercise sets is modest in any graduate course like this one I think the most important thing to do is spend some time afterwards going back through the notes slowly to make sure you understand it this is the kind of class where perhaps you know depending on what kind of undergrad you were you may have a experience with following classes in real time even in depth that's very difficult to do with it it's classes like this so it's really key reinforced the lecture material afterwards the exercise sets are literally just a mechanism for me to force you to do that they are going to be working out examples filling in proofs that I've skipped in class and so on they are not meant to be especially time consuming there will be weekly however they'll be graded just on A+ check - kind of system if you do all of the exercise sets that's already going to be good enough for a B and particularly if you take the class pass/fail that's all you need that's all you got to do so what's the rest of the work there's going to be bi-weekly problem sets these will be more difficult they're meant not to reinforce the lecture material but they actually extend it that is I intend to teach you some new things relevant to the course of course for new things through these problem sets probably they'll have the format where you choose k out of n problems so maybe I'll give you six problems I want you to do three they're also meant to be solved collaboratively so it's not mandated but that's strongly encouraged so you can form groups of up to three to work on the problem sets and we're only going to accept a single write-up from each group so there'll be five of those overall the fifth one we'll just go ahead and call it a take-home final why not so those are the expectations I have for you the floor is open for questions either on the lecture content or on the course mechanics oh boy in the back there is a course website the easiest way to find it right now is probably just go to my website and there's a link toward the top of my home page and definitely keep an eye on the course that so I will be posting readings for each lecture on the website this reminds me of a couple other things the lectures are being videotaped that's really just you know there aren't a lot of courses like this one and so I just wanted to kind of there's nothing fancy that religiously just plopped me a camcorder in the back pointed at the blackboard and it's you know to make sure people who aren't at Stanford can watch these lectures if they want but obviously a side effect you know if you happen to miss a class then you know you're obviously welcome to watch that later hopefully they'll be posted just within a few days of the actual lecture itself I'm also hoping to generate lecture notes though that less of a promise that's more just a goal the videos will actually appear course notes I've written them for this lecture you know as time permits I'll post them as well to the website so keep an eye on the website for those extra materials and the readings yeah they'll go Wednesday it'll go in two days yep oh right so I mean on some level I don't care what your background is but to be useful let me kind of tell you who my kind of archetypal student is that I'm talking to so you know what so when I prepare the lectures and I think about what level do explain things that I'm sort of have in mind you know a master student maybe a first year PhD student not necessarily with a theory concentration but certainly someone who didn't hate Theory you know and sort of you know enjoyed their Theory classes at undergrad as much as any of the other ones I'm not so I you know I will assume basic undergrad CS theory meaning algorithms and NP completeness not much beyond that not assuming anything in economics or game theory conversely this class certainly won't substitute for a proper course in game theory or microeconomics will learn it only on a need-to-know basis so we'll only get sort of small pieces of those traditional fields correct oh yeah so my office hours will be after class so you know I'll start by just hanging out around here after a lecture and then I'll make my way over to my office and gates 462 those will go till 4:30 on Monday Wednesday this is also up in the web page by the way oh and then I shouldn't reduce the TAS so you stand up guys all right so on the left is oka and his office hours when are they Tuesday one two 424a and then Costas is on the right and the black shirt and he's Thursdays 9 to noon also and gates be 24 a I will have office hours this week they will not okay so they're starting next week mine start today and that's all on the website other questions oh yeah whole using Piazza we are so there's a Piazza website there's a link to it from the course home page and to be honest I will be looking at it not every day so certainly when it's important that I respond to something on it I will do so but the TAS will be monitoring it you know relatively closely so in addition to the office hours Piazza is a great way to clarify lecture or homework issues yeah thanks yeah well you know I want to see potentially somebody ask the question again so who here this would be good a be test I should have counted before the lecture in acid lecture a great way to kind of evaluate the quality of your first lecture so who who is at least you know 95 percent sure that they're going to attend most of the lectures in this class okay who is less than 95 percent sure they can attend most of the lectures in the rest of this class yeah I'm gonna I'm going to wait a lecture or two before deciding on the room well to be honest I've already done some groundwork and it's bleak with the room so yeah so I'm hoping we kind of fit but I mean if it's really you know if it stays at this size I'll have to have to find something else to do but if we drop say ten people from this I think maybe it's vaguely tolerable it's easier for me I'm at the fun right with all this space but so keep keep I'll keep I mean if you let me put it this way if you're uncomfortable with the room please ask me again okay the jury is out that's that that's the answer with the room other questions yep so the the first exercise set will go out Wednesday and it'll be due a week from Wednesday and that will have some of these you know questions about just from lecture so like today I'll ask you to you know there are a couple things I mentioned the course of class so like prove that the unique equilibria of Rock Paper Scissors is randomizing uniformly so just basic stuff filling in the holes and then the first problem set will also go out Wednesday probably I'll give you about two and a half weeks to do the problem sets so that'll be for a while okay so I'll stick around after class for more people who have further questions but that's it for today hopefully see you Wednesday

Channel: Tim Roughgarden Lectures

Views: 156,102

Keywords: algorithmic game theory, stanford, tim roughgarden

Id: TM_QFmQU_VA

Length: 69min 24sec (4164 seconds)

Published: Wed Sep 25 2013