CS 684 Algorithmic Game Theory Scribe:´Eva TardosInstructor: Eva Tardos Friday, August 26, 2005Game theory is concerned with situations when users of a system interact, and effect eachother. In this class we w ill be concerned with games that model some issues in computer science.We will start the semester by considering three classes of games: routing, network design, andfacility location.The routing game we will consider has been originally studies in civil engineering as a modelof car-traffic. It is also used to mod el packet traffic on the Internet, but for now let’s considercars. Clearly every morning each car decides which way to drive to work. It is pretty reasonableto assu me that cars choose their route the selfishly minimize driving time. However, many carsselecting the same rode causes congestion, and that slows the cars down. This makes it a game:each car effects the driving time of many other cars by its choice of roads. Packets in the Internetdon’t actually “select” their paths: we will discuss how, and to what extent can th is model beviewed as modeling packet-traffic.Clearly the p rocess that builds and maintains the Internet, and locates certain facilities (suchas DNS name servers) is a game in the similar sense. The Internet is built by a set of IndependentNetwork Providers (ISP), where each provider bu ilds its own portion of the network in a s elfishfashion, while using the other providers when possible. Looking at the Internet from this perspec-tive, it is magic th at it works as well as it does, and we need to strive to understand this better.For network design we will consider highly simplifies games, as so far no unified and convincingmodel has emerged that helps explain the good beh avior of the Internet.The first question we need to ask is what will happens in such a game. The most natural,and commonly used concept, that we will study in much of this course, is Nash equilibrium. Astrategy for each player (say car in the routing game) is a Nash equilibrium if no player can improvehis payoff (or value) by changing strategy alone. Note that here defin e a deterministic, or p ureNash equilibrium, where each player has to choose a single strategy. L ater we w ill also talk aboutrandomized strategies, where players can decide to randomize between strategies. In the first halfof the cour s e, we will consider the quality of Nash equilibria, th at is, will compare how good areNash equilibria compared to a centrally built and enforced solution. The ratio of the quality of aNash equilibrium and a centrally built solution is called the price of anarchy: a price one pays tonot have to build and manage a complicated central solution.The next s egment of the source will consider ways to find an equilibrium. It is one of the mainopen problems in theory to decide if there is a general polynomial time algorithm to fi nd a Nashequilibrium of a game. We will consider special games where such algorithms are known, and tryto understand the issues underlying this open problem. A related question one needs to ask if towhat extend can be expect players to find an equilibrium, e.g., does natural game play somehowconverge to such a solution.Finally, we will spend time on the general topic of mechanism design: when the price of anarchyis bad, or a Nash equilibrium is hard to fi nd, it would make sense to try to modify the game tomake it better for the users. Mechanism design has a large literature, easily can teach a wholecourse just on this topic. Here we will focus on some issu es that relate to the rest of the course, orto some natural computer science topics.The simplest and maybe most common description or a game uses a game matrix. For example,a two player game where each player has two possible strategies, can be described by a two-by-twomatrix, that gives the payoff (the value obtained) by the player. For example, a very simplifiedversion of a goal-kick game involves two player, a goalie and a shooter. Assume the shooter hastwo option: to shoot left or right, and the goalie has two options: to drive left of right. Now asimple game matrix would look as follows. The shooter chooses a column, and the goalie choosesa row, and th e first number in each square is the value for the shooter, while the second number isthe value for the goalie.L RL −1, 1 1, −1R 1, −1 −1, 1In this game, there is no pair of fixed strategies that the players can play that neither regrets:the player loosing can always change his strategy and win. There are also game where there aremultiple Nash equilibria. Maybe the simplest is the coordination game. Say two players want toattend a game together, either softball or baseball game. They both prefer to be together, but theydisagree on which game they prefer. Here is the payoff matrix.B SB 2, 5 0, 0S 0, 0 5, 2Now both of them selecting the same game is an equilibr ium for both choices. Note that even if thetwo players share their preference (see below) there still will be two equilibria: attending baseballremains an equilibr ium as no player can alone change his s trategy and improve his outcome.B SB 2, 2 0, 0S 0, 0 5, 5A similarly simple game that models an economic ”pollution game” is defi ned as follows. Saythere are n countries, and each country must decide whether they will have a clean air act. Aclean-air act cost them 4 units, but if any country has a clean air act, th en all countries gain avalue of 3. So for example when there are two countries (n = 2) we get the following game matrix.P CP 0, 0 3, −1C −1, 3 2, 2Here is use value 0 to denote the value of no country has a clean-air act. Clearly the best valuestate is that all countries enact a clean-air act, this results in a value of 3n − 4 for each of them: again of 3n from clean air in all n countries, and a cost of 4 for implementing the clean-air act athome.In the pollution game there is a unique Nash equilibrium, unfortunately, it is for each countryto pollute. First, this is an equilibrium, if a single country decides to have a clean air act, all othercountries gain 3 in their value, but th e country with the clean air act, looses value 1 (cost 4 andgain of 3). Note that no solution, where any country has a clean air act is a Nash equilibrium: eachs tx1 x1wv(a) Befores tx1 x10vw(b) AfterFigure 1: Braess’s Paradoxcountry is better of not paying its own cost of 4. Notice that this unique Nash equilibrium is ofreally bad quality (value 0) compared to the best