CS 684 Algorithmic Game Theory Scribe: Selin ErdoganInstructor: Eva Tardos Friday, October 14, 2005In today’s lecture we will talk about finding some sort of equilibria instead of evaluating thequality of the equilibria as we have done in the previous lectures. Specifically, we will talk aboutpotential games and finding the deterministic Nash equilibria.Reminder: In potential games, we have a potential function Φ which keeps track of the changein objective function value when one of the players changes his strategy while others keep theirstrategies.Example: The selfish routing game is an example of the potential games. In this game, weare given a network and k users. Each user i wants to route 1 unit of flow from source sito sinktiusing a path Pibetween the source and the sink. In any solution of the game, if we have xeusers on edge e, the delay suffered by the xeusers is given by the delay function le(xe). The delayfunction is usually assumed to be monotonically increasing which is a realistic assumption but thismaybe removed.In this routing game each user i wants to minimize his delay, i.e. minPe∈Pile(xe), and thepotential function is equivalent to Φ =Pe∈EPxek=1le(k).Today we will provide a generalization of this game:General Discrete Potential Game (Congestion Game):In a General Discrete Potential Game, we are given k users (1,2,..,k), a ground set E, and delayfunctions le(x) for each element e in E where x denotes the number of users using e. Each user iis associated with a set Si, which denotes the set of allowed subsets of E for user i, and chooses anaction Pifrom set Si. Like the routing game, xedenotes the number of users i s.t. e ∈ Pi, eachuser i suffers delayPe∈Pile(xe), and the potential function is equal to Φ =Pe∈EPxek=1le(k).Note that the General Discrete Potential Game in which we have actions from a discrete set(instead of paths) is in perfect analogy with the routing game. The network structure and thepaths of the routing game are not relevant to the game structure and the general discrete potentialgame is also a potential game.Since the delay of each user on an edge depends on the number of other users using the sameedge, general discrete potential game is also referred as the Congestion Game.Theorem 1 (Monderer and Shapley, 1997) All discrete potential games are of the form givenabove, i.e. they coincide with the congestion games introduced by Rosenthal.Recall that in a potential game, a solution which minimizes Φ is a Nash equilibrium. A naturalquestion arises at this point: Can we find a solution which minimizes the potential function Φ?Special case: If all users have the same source-sink pair then we can find the solution whichminimizes the potential function in polynomial time using the minimum cost flow algorithm. Inorder to use this algorithm, we replace each e ∈ E with k copies with capacity 1 and cost le(i) forithcopy. So the first copy has the delay on the edge when there is one user using the edge e, secondhas the delay when there are two users, and so on...Theorem 2 Minimum cost flow of value k is equal to the set of paths that minimizes Φ (when thedelay function leis monotone increasing).We needed that the delay function is increasing, as the minimum cost flow prefers to use thecheapest copy of each edge, and with the monotone delay function, the first copies are alwayscheaper.Note that, this is a very special case. For most of the congestion games, minimizing Φ is N P -hard. (Since this is not the feasibility version we use the term N P -hard, instead of N P -complete.)We must also be aware of the fact that previous paragraph states that finding the Nash thatminimizes the potential function is N P -hard, but it does not give information about the difficultyof finding any Nash. Actually, finding any Nash solution in polynomial time for the congestiongame is still an open problem. However, we have some information about the difficulty level:Theorem 3 (Fabrikant, Papadimitriou, and Talwar, 1997) Finding Nash in general conges-tion game is P LS-complete.P LS-Complete(Polynomial Local Search-Complete):A local search problem L is defined by an optimization problem, such as the traveling salesmanproblem, or max-3SAT where we want to satisfy the maximum number of clauses in a 3SAT formula.The goal of the problem is NOT to find the true optimum, but rather to find a local optimum. Tomake this meaningful, we need to also add to the problem definition a local move. For example,a natural local step for the 3SAT problem is to change the truth value of one variable. So if wechange a variable xifrom true to false (or the other way around), this may make some clauses truethat used to be false, and turn some other clauses false. The change is a local improvement, if theoverall number of true clauses increased. In other words, the goal of the local search is to find asolution where a single switch of variable will not improve the number of satisfied clauses.More generally, the class P LS (Polynomial Local Search) is defined by an optimization problem,and a local step. A local optimum is a solution with no improving local step, and the problem is tofind a local optimum. We require that given a solution, we can decide in polynomial time if there isa local steps that improves the solution. In the case of the 3SAT problem defined above, this is easyto do: simply try swapping the truth value of each variable in turn, and see if it improves the total.In this local search problem, there are only a polynomial number of possible local steps (one foreach variable), and hence we can try them all. Other local search problems can allow many morepossible local steps, even exponentially many. The only requirement is that an improving local stepcan be found in polynomial time, if one exists. For example, in disjoint path routing problems, alocal step would be to change one of the paths, and we may use a shortest path subroutine, to seeif an improving path exists.First note that the problem of finding a Nash equilibrium in a potential game is in P LS,assuming the problem the users face in finding their best move given the strategies of all otherplayers in polynomial time solvable. For example, finding a Nash in the routing problem is in P LS(with the shortest path subroutine needed to find improving local steps). This is easy to see, as weknow that local optima of the potential function Φ are exactly the Nash equilibria.A problem L ∈ P LS is P LS-complete,