The Complexity of pure Nash equilibria in weighted Max-Congestion Games

The Complexity of Pure Nash Equilibria in Weighted Max-Congestion Games Carme ` Alvarez and Guillem Franc`es ? [email protected] [email protected] Universitat Polit`ecnica de Catalunya, ALBCOM Research group. Edifici Ω, Campus Nord. Jordi Girona, 1-3, Barcelona 08034, Spain. Abstract. We study Network Max-Congestion Games (NMC games, for short), a class of network games where each player tries to minimize the most congested edge along the path he uses as strategy. We focus our study on the complexity of computing a pure Nash equilibria in weighted NMC games. We show that, for single-commodity games with non-decreasing delay functions, this problem is in P when either all the paths from the source to the target node are disjoint or all the delay functions are equal. For the general case, we prove that the computation of a PNE belongs to the complexity class PLS through a new technique based on semi-potential functions and a slightly modified definition of the usual local search neighborhood. We further apply this technique to a different class of games (which we call Pareto-efficient) with restricted cost functions. Finally, we also prove some PLS-hardness results, showing that computing a PNE for Pareto-efficient NMC games is indeed a PLS- complete problem. 1 Introduction During the last years, a great effort has been devoted to the development of mathematical tools for the modelling of computer networks such as the Internet. Given the decentralized and non-cooperative nature of these networks, Game Theory [1] arises as one of the most suitable instruments to characterize the behaviour of its selfish users1.Network Congestion Games, for instance, provide a useful means of studying the behaviour of such users when they try to minimize the total congestion of the network paths through which they route their packets. One of the fundamental and most studied concepts of Game Theory is that of ?Both authors partially supported by FET pro-actives Integrated Project 15964 (AEOLUS) and by Spanish CICYT under grants TIN2005-09198-C02-02 (ASCE) and TIN2007-66523 (MEFOALDISI). The second author is also supported by a UPC research grant. 1As stated by C. Papadimitriou on his seminal paper [2], “... the mathematical tools and insights most appropriate for understanding the Internet may come from a fusion of algorithmic ideas with concepts and techniques from Mathematical Economics and Game Theory”. the Nash Equilibrium [3], which intends to describe stable states of the system, i.e. states in which no user has an incentive to unilaterally change his route in the network. In this article, we study a model of network games which has not received much attention until the moment, and which we call Network Maximum Congestion Games (NMC games). In this class of games, players try to minimize the congestion of the most congested link (instead of the sum of congestions of all links, as it happens in classical Network Congestion Games) of the network path they use. We believe that the study of this new model may be useful in a context where the bandwidth of the network is limited and users want to route their packets through paths with minimum bandwidth usage. Our study is focused on the analysis of the computational complexity of computing pure Nash Equilibria (PNE) in some types of Network Congestion Games. Statement of results. We consider the general case where all players may have different weights, as well as different kinds of delay functions. We show that the cost functions, which depend essentially on these weights and delay functions, strongly affect the complexity of the PNE computation. After giving some formal definitions in Sect. 2, in Sect. 3 we study the problem of computing a PNE for weighted single-commodity NMC games with nondecreasing delay functions. If we consider only network topologies where all the (s-t) paths are disjoint, then the problem can be solved in polynomial time. For general network topologies, the problem remains polynomial-time computable as long as all the edges have identical delay functions. For general NMC games, though, we prove that the same problem belongs to PLS. Since there are games of this kind which have no potential function [4], our proof relies on an alternative technique based on what we call semi-potential functions and on a particular neighborhood structure. As far as we know, this is the first time that the problem of computing a PNE for a game is expressed as a local search problem in which the cost function to be minimized is not a potential function. In Sect. 4, we investigate the hardness of computing a PNE for a different kind of NMC games, which we call Pareto-efficient games and which have the property that no player can worsen the cost that other players assume by improving his own strategy. Following the aforementioned technique, we show that Pareto-efficient games always have a PNE and that its computation can also be expressed as a PLS optimization problem. Furthermore, we prove that is is a PLS-complete problem through a PLS-reduction from the Maxcut problem. Related Work. With respect to the class of Network Congestion Games, most of the issues we study here have already been addressed. Any unweighted Congestion Game (including those defined over networks) possesses at least one Pure Nash Equilibria [5], whereas there exist weighted games with piecewise delay functions which possess no PNE [6]. However, weighted games with linear delay functions do always possess a PNE [7]. The computation of a Pure Nash Equilibria can be carried out in polynomial time in single-commodity unweighted Network Congestion Games, while the same problem is, in general Network Congestion Games, PLS-complete (see [8] for the first proof or [9] for a simpler but later one). With respect to Network Max-Congestion games, their study has been initialized in [10, 4, 11, 12]. All these papers analyze the existence of PNE as well as other aspects. Libman and Orda [10] prove the existence of a PNE for weighted single-commodity NMC games with increasing delay functions. They also analyze parallel links games with a broad class of residual capacity functions, a case where max-congestion games cannot be distinguished from traditional congestion games. Fotakis et al. [13] deal with weighted parallel links NMC games with a specific type of linear delay functions, and show that a PNE always exists and can be computed in polynomial time. Caragiannis et al. [4] present some results with respect to the existence and complexity of PNE for NMC games with again a specific type of linear delay functions. It is shown that these games always have PNE, and that the computation of the best PNE is NP-complete for weighted single-commodity NMC games but can be done in polynomial time for unweighted NMC games where all users share either the source or the target nodes. Finally, Banner and Orda [11] consider both weighted NMC games with splittable and unsplittable traffic, the former being games where the players can split their traffic among different paths, the latter being our scenario. They prove the existence of PNE for both cases when the delay functions are continuous and increasing, and show that best response dynamics for the unsplittable case always converge, though it may take an exponential number of steps to do so. They also investigate the efficiency of the PNE with respect to the social optimum and show that computing an optimal PNE is NP-hard. 2 Definitions and Preliminaries AStrategic game can be formally defined as a tuple Γ= (N, (Pi)i∈N,(ci)i∈N) where Nis a set of n≥2players and, for each player i∈N,Piis a set of actions or strategies available to him and ci:Π=P1× · · · × Pn→Rhis cost function. Each element πof this set Πis said to be a strategy profile (profile, for short) and reflects the choice of each player. Given a profile π= (p1, . . . , pn), we say that pi∈Piis the strategy chosen by player i∈Nin π, while ci(π) is the cost assumed by the same player under that same profile π. We denote by (π−i, p) the strategy profile resulting from replacing by pthe strategy of player iin π. If the cost functions of a strategic game are defined in such a way that all the improving movements that a player may do provoke no harm to the other players, that is, if for any profile π, player iand strategy p∈Piit holds that ci(π−i, p)< ci(π)⇒ ∀j∈N cj(π−i, p)≤cj(π), then we say that the game is Pareto-efficient. A strategy profile π= (p1, . . . , pn) is a Pure Nash Equilibrium (PNE) if for each player i∈Nand for each strategy p∈Pithat player imay adopt, it holds that ci(π)≤ci(π−i, p) (that is, all players are satisfied with their current strategies). Both weighted Congestion Games and Max-Congestion Games are strategic games defined by a tuple Γ= (N, E, (Pi)i∈N,(wi)i∈N,(de)e∈E), where now the set of actions Pi⊆2Eavailable to each player i∈Nis composed by a number of subsets of the set of resources E. In addition, each player ihas a weight wi∈IN+. We say that a (max-) congestion game is unweighted if all players have equal weight2. Finally, each resource e∈Ehas a delay function de: IN →IR, which we assume to be polynomial-time computable. When considering only games with non-decreasing delay functions, we call them non-decreasing delay games. In this two classes of games, the cost function is given implicitly by means of these weights and delay functions. We say that, under a given strategy profile π= (p1, . . . , pn), the load λe(π) of the resource e∈Eis the total weight of the players using it, λe(π) = P{i∈N|e∈pi}wi, and the delay (or the congestion) caused by resource eis de(λe(π)). The cost assumed by the players is then computed as a function of the delays caused by the different resources he is using. For congestion games, the cost assumed by player iunder profile πis ci(π) = Pe∈pide(λe(π)), whereas for max-congestion games this cost is defined as ci(π) = maxe∈pide(λe(π)). Network Congestion Games and Network Max-Congestion Games are congestion games where the sets of strategies of the players are concisely represented by means of a directed graph. These games are defined by a tuple Γ= (N, G, ((si, ti))i∈N,(wi)i∈N,(de)e∈E(G)), where Gis a directed graph, the resources are the edges of the graph and the set Pi⊆2E(G)of strategies available to each player i∈Nis the set of all paths from his origin node sito his destination node ti(that is, the set of all (si-ti) paths, where by (s−t) path we mean path from sto t). Note that these paths are not given explicitly. As before, we denote by λe(π) the load of edge ein the strategy profile π, and each edge causes a delay de(λe(π)). The cost assumed by player iunder profile πis ci(π) = Pe∈pide(λe(π)) when we are dealing with network congestion games, whereas this cost is ci(π) = maxe∈pide(λe(π)) in the case of network max-congestion games. When all players have the same pair of nodes (si, ti)=(s, t), we say that the network (max-) congestion game is single-commodity; otherwise, we say that it is multi-commodity. We will also consider the specific case of single-commodity games called parallel links network [14], where the graph is made up exclusively of a set of edges between the nodes sand t. The function φ:Π→IR is said to be an ordinal potential for a strategic game Γ= (N, (Pi)i∈N,(ci)i∈N) if for every π∈Π,i∈N,p∈Pi, it holds that 2From now on, we will refer to weighted games unless explicitly stated. ci(π−i, p)< ci(π)⇔φ(π−i, p)< φ(π), and it is said to be an exact potential if for every π∈Π,i∈N,p∈Pi, it holds that ci((π−i, p)) −ci(π) = φ((π−i, p)) − φ(π). It can be easily seen that every game that possesses an ordinal potential function (which is called an ordinal potential game) has a PNE [15]. It is also well-known that every unweighted congestion game is a potential game (i.e., a game possessing an exact potential function) [5], and that every (finite) potential game is isomorphic to an unweighted congestion game [15]. Finally, an optimization problem with a given neighborhood structure belongs to the complexity class PLS (for Polynomial-time Local Search) [16] if (a) all solutions are polynomially bounded and an initial solution can be computed in polynomial time, (b) the cost of any solution can be computed in polynomial time and (c) given a solution, we must be able in polynomial time to decide if it is locally optimal with respect to the given neighborhood structure and, if not, to compute a neighboring solution with better cost. 3 Non-decreasing Delay NMC Games We first study NMC games with non-decreasing delay functions, and identify some cases for which the computation of a PNE can be done in polynomial time. 3.1 A polynomial time upper bound for some particular cases We present an algorithm that computes PNE profiles for some kinds of weighted single-commodity non-decreasing delay. The algorithm BDP (for Best Disjoint Path) proceeds in two phases. First, it computes a maximal set Mof (s−t) disjoint paths, and then it assigns players to paths in Mstep by step: at each step, the player iwith maximum weight (from the set of players still unassigned) is assigned to the path p∈Mthat yields him the minimum cost, that is, the path that minimizes the value maxe∈pde(λe(π) + wi), where πis the (partial) strategy profile we are constructing. Let’s now analyze the properties of the profiles computed by the algorithm. Lemma 1. After each iteration of the BDP algorithm, no player already assigned to some path in the (partial) profile πhas an incentive to change his strategy for another path from M. Proof. The claim obviously holds after the first iteration. By induction, suppose that it also holds for the (partial) profile πkobtained after the k-th iteration, let ibe the player assigned to path pon the iteration k+ 1 and let us consider the profile πk+1 = (πk −i, p) computed after this (k+1)-th iteration. By construction, player iis satisfied with his strategy in πk+1. Let’s now suppose that for some player jalready assigned to pin πkthere is an incentive to change his strategy to another path p0∈M. This means that maxe∈p0de(λe(πk)+wj)<maxe∈pde(λe(πk)+wi). Since wi≤wjand the delay functions are non-decreasing, maxe∈p0de(λe(πk)+wi)≤maxe∈p0de(λe(πk)+wj), but this implies that maxe∈p0de(λe(πk) + wi)<maxe∈pde(λe(πk) + wi), which contradicts the fact that phas been chosen to minimize this last value. Thus, no player assigned to phas incentive to change his strategy. Now, let us suppose that for some player jassigned to a path p06=p∈M there is an incentive to change his strategy to another path in M. The cost induced by paths different than phas clearly remained unchanged from πkto πk+1 (since we are considering only disjoint paths), while the cost induced by path pcannot be lower in πk+1 than in πk, for the delay functions are nondecreasing. Thus, this contradicts our inductive hypothesis that all players in πk were satisfied with their path. Hence, all players in πk+1 are satisfied. ut For graphs where all the (s−t) paths are disjoint (which include parallel links), the set Mcomputed by the BDP algorithm coincides with the set of all the strategies available to players. Hence, the computed profile is a PNE. Corollary 1. For single-commodity NMC games where the graph consists only of a number of (s−t)disjoint paths, the profile computed by the BDP algorithm is a PNE. Also, if we consider general graph topologies but we restrict the delay functions of the edges to be identical, we have that, although there may be strategies other than the disjoint paths, none of them will yield a better cost. Corollary 2. For single-commodity NMC games where all the delay functions are identical, the profile computed by the BDP algorithm is a PNE. Proof. Notice that the profiles computed by the algorithm have the property that, for any path p∈M, all edges e∈phave the same load λe. Thus, we now have that the delay induced by all edges of pis equal. Since Mis maximal, any (s−t) path p0shares at least one edge ewith some path p∈M, and this edge einduces a delay equal to the delay induced by the whole path p. Hence, a player choosing p0would have to assume a cost at least as large as if he chose p, which (by the previous lemma) is no better than the cost of the path he has been assigned to in π.ut Given that a maximal set of disjoint paths can be obtained in polynomial time and that our algorithm runs also in polynomial time, we can state the following theorem. Theorem 1. A PNE can be computed in polynomial time for both (a) Weighted single-commodity NMC games with identical non-decreasing delay functions and (b) Weighted single-commodity NMC games with non-decreasing delay functions where all the (s−t)paths of the graph are disjoint. 3.2 A PLS upper bound for the general case Now we move to the study of multi-commodity NMC games. The next lemma states that there exists a total ordering among strategy profiles that has an important property. Lemma 2. Let A(π)be a tuple A(π) = (ci1(π), ci2(π),...cin(π)) such that ci1(π)≥ci2(π)≥ · · · ≥ cin(π). Let <l: INn→INnbe the usual (total) lexicographical order defined over all possible pairs of tuples A(π),A(π0). Let Γ be a non-decreasing delay NMC game and π,π0two strategy profiles such that π= (π−i, p)and π0= (π−i, p0)for some strategies p6=p0of player i. Then, ci(π0)< ci(π)⇒A(π0)<lA(π) Proof. The proof of the statement follows from the proof of Theorem 3 in [11] (which can be directly generalized to the case of arbitrary non-decreasing delay functions). ut This ordering suggests a natural way to prove the existence of PNE profiles. Theorem 2 ([11]). Any non-decreasing delay NMC game has a PNE. Proof. Since Πis finite, there must exist a profile π∗∈Πsuch that ∀π∈ Π A(π∗)<lA(π). Suppose that, in π∗, a player ihas incentive to change his strategy to p0; then, by Lemma 2 we have that A(π∗ −i, p0)<lA(π∗), a contradiction. Thus, π∗is a PNE. ut Notice that, unlike what happens with unweighted congestion games, there exist unweighted non-decreasing delay NMC games which have no potential function [4], so the existence of PNE profiles cannot be proved directly by means of this potential function. Furthermore, the absence of a potential function also prevents us to directly prove (as it can be proved for congestion games, see [8]) that the computation of a PNE for this kind of games is in PLS. However, consider the function γthat maps each profile πto the value of A(π) seen as a n-digit number in base D+ 1 (that is, γ(π) = P0≤j≤nA(π)j· (D+1)j), where D= maxe∈Ede(W) and W=Pi∈Nwi. It can be seen that γis computable in polynomial time and that A(π0)<lA(π)⇔γ(π0)< γ(π), for any π, π0∈Π. Recalling Lemma 2 and the definition of an ordinal potential function, it thus seems appropriate to call this function a semi-potential function, since it meets only one of the two implications of the definition. The use of this function (together with a special definition of the neighborhood structure of the search problem, as we will see) allows us to prove the aforementioned membership in PLS. Theorem 3. Computing a PNE for weighted multi-commodity non-decreasing delay NMC belongs to PLS. Proof. Consider the search problem of finding a local optimum of γ, where the set of feasible solutions contains all valid strategy profiles of our game and the neighborhood N(π, Γ ) of a solution πis the set of all profiles π0where exactly one player has changed his strategy for a better one: N(π, Γ ) = {π0∈Π| ∃i∈N∃p∈Piπ0= (π−i, p)∧ci(π0)< ci(π)} Notice that this last condition (ci(π0)< ci(π)) implies that (i) the neighborhood of πis empty if and only if πis a PNE and (ii) For any neighbor π0∈N(π, Γ ) of a given profile π, it holds that γ(π0)< γ(π) (by definition of γ and Lemma 2). Thus, finding a PNE is equivalent to finding a local minimum of the function γwith respect to the neighborhood defined above. This search problem belongs to PLS, since (a) an initial solution can be produced in polynomial time by assigning to every player an arbitrary strategy, (b) The cost γ(π) of any profile πcan be computed in polynomial time. (c) deciding whether N(π, Γ ) = ∅(i.e. πis a local optimum) or, if this is not the case, computing a strategy profile π0∈N(π, Γ ) s.t. γ(π0)< γ(π) can be done in polynomial time using a modification of the Dijkstra algorithm where the shortest path computation is done considering that the length of an edge eis de(λe(π)) and the length of a path pis maxe∈pde(λe(π)). ut Notice that the previous proof can be immediately generalized to the case of general max-congestion games. We only have to see that, since the representation of the game explicitly contains the set of actions for each player, deciding if a given profile is a local optimum with respect to the neighborhood can be done in polynomial time by computing the cost of all neighbors of the profile. As we stressed before, the neighborhood used in the above proof is not the neighborhood that one may initially think of when considering the nature of games (see, for instance, [8, 17]), where the neighbors of a given profile πare all profiles π0= (π−i, p) (for some i∈Nand p∈Pi). Given that max-congestion games are not potential games and that we only have at our disposal a semipotential function, we have to restrict the neighbors to those profiles where the deviating player improves his cost in order to get a search problem whose local optima coincide with the PNE profiles of the game. Finally, let us say that the requirement of the delay functions being nondecreasing is essential to the proof of Lemma 2, so the above technique can not be trivially extended to games with arbitrary delay functions. In the next section, though, we will see a particular class of games with delay functions that are not restricted to be non-decreasing which does actually possess a semipotential function. This will allow us to prove that the problem of computing a PNE for this class of games belongs to PLS. 4 Hard NMC Games Let σdenote the function σ(π) = Pi∈Nci(π). For Pareto-efficient games, we have that whenever a player changes his strategy to decrease his cost, the cost assumed by the rest of players does not increase. Thus, the sum of all costs strictly decreases. Proposition 1. Let Γbe a Pareto-efficient game and π,π0two strategy profiles such that π= (π−i, p)and π0= (π−i, p0)for some strategies p6=p0of player i. Then, ci(π0)< ci(π)⇒σ(π0)< σ(π) Note that the implication holds only in one direction, so all we can say about σis that it is a semi-potential function, but not a potential one. The existence of this function makes it possible to use the same proof ideas that we used in the previous section to prove both the existence of PNE profiles and the membership in PLS of the problem of computing them in this kind of games. Theorem 4. Any Pareto-efficient game has a PNE. Proof. The proof is analogous to the proof of theorem 2; the profile π∗that minimizes σ(π∗) is again a PNE. ut The problem of computing a PNE for Pareto-efficient NMC games can be seen to be equivalent to the problem of finding a local optimum of the function σ. Theorem 5. Computing a PNE for weighted multi-commodity Pareto-efficient NMC is in PLS. Proof. This problem is equivalent to the problem of finding a local minimum of the function σwith respect to the neighborhood defined in the proof of theorem 3. Notice that this result can be directly extended to Pareto-efficient strategic games the sets of strategies of each player are explicitly given. Corollary 3. Computing a PNE for Pareto-efficient strategic games is in PLS. Although the Pareto-efficiency may seem too strong a restriction, we next prove that the computation of a PNE for Pareto-efficient weighted parallel links NMC games is a PLS-hard problem. The proof is based on a PLS-reduction from the Maxcut problem with the flip neighborhood, for which finding a local optimum is known to be PLS-hard [18]. In this problem, we are given an undirected graph with weights on the edges and we have to find a partition of the nodes into two disjoint sets Aand Bsuch that the cut of the partition (i.e. the sum of weights of edges between nodes assigned to different sets) cannot be increased by changing one single node from Ato Bor vice versa. Theorem 6. Computing a PNE for weighted Pareto-efficient parallel links NMC games is PLS-hard.