Pure Nash equilibria in player-specific and weighted congestion games

Unlike standard congestion games, weighted congestion games and congestion games with player-specific delay functions do not necessarily possess pure Nash equilibria. It is known, however, that there exist pure equilibria for both of these variants in the case of singleton congestion games, i.e., if the players’ strategy spaces contain only sets of cardinality one. In this paper, we investigate how far such a property on the players’ strategy spaces guaranteeing the existence of pure equilibria can be extended. We show that both weighted and player-specific congestion games admit pure equilibria in the case of matroid congestion games, i.e., if the strategy space of each player consists of the bases of a matroid on the set of resources. We also show that the matroid property is the maximal property that guarantees pure equilibria without taking into account how the strategy spaces of different players are interweaved.     

Profit Sharing with Thresholds and Non-monotone Player Utilities

We study profit sharing games in which players select projects to participate in and share the reward resulting from that project equally. Unlike most existing work, in which it is assumed that the player utility is monotone in the number of participants working on their project, we consider non-monotone player utilities. Such utilities could result, for example, from “threshold” or “phase transition” effects, when the total benefit from a project improves slowly until the number of participants reaches some critical mass, then improves rapidly, and then slows again due to diminishing returns.Non-monotone player utilities result in a lot of instability: strong Nash equilibrium may no longer exist, and the quality of Nash equilibria may be far away from the centralized optimum. We show, however, that by adding additional requirements such as players needing permission to leave a project from the players currently on this project, or instead players needing permission to join a project from players on that project, we ensure that strong Nash equilibrium always exists. Moreover, just the addition of permission to leave already guarantees the existence of strong Nash equilibrium within a factor of 2 of the social optimum. In this paper, we provide results on the existence and quality of several different coalitional solution concepts, focusing especially on permission to leave and join projects, and show that such requirements result in the existence of good stable solutions even for the case when player utilities are non-monotone.     

On Equilibria in Quantitative Games with Reachability/Safety Objectives

In this paper, we study turn-based multiplayer quantitative non zero-sum games played on finite graphs with reachability objectives. In this framework each player aims at reaching his own goal as soon as possible. We focus on existence results for two solution concepts: Nash equilibrium and secure equilibrium. We prove the existence of finite-memory Nash (resp. secure) equilibria in n-player (resp. 2-player) games. For the case of Nash equilibria, we extend our result in two directions. First, we show that finite-memory Nash equilibria still exist when the model is enriched by allowing n-tuples of positive costs on edges (one cost by player). Secondly, we prove the existence of Nash equilibria in quantitative games with both reachability and safety objectives.     

Competitive routing over time

Congestion games are a fundamental and widely studied model for selfish allocation problems like routing and load balancing. An intrinsic property of these games is that players allocate resources simultaneously and instantly. This is particularly unrealistic for many network routing scenarios, which are one of the prominent application scenarios of congestion games. In many networks, load travels along routes over time and allocation of edges happens sequentially. In this paper, we consider two frameworks that enhance network congestion games with a notion of time. We introduce temporal network congestion games that are based on coordination mechanisms — local policies that allow to sequentialize traffic on the edges. In addition, we consider congestion games with time-dependent costs, in which travel times are fixed but quality of service of transmission varies with load over time. We study existence and complexity properties of pure Nash equilibria and best-response strategies in both frameworks for the special case of linear latency functions. In some cases our results can be used to characterize convergence properties of various improvement dynamics, by which the population of players can reach equilibrium in a distributed fashion.     

On the Structure of Weakly Acyclic Games

The class of weakly acyclic games, which includes potential games and dominance-solvable games, captures many practical application domains. In a weakly acyclic game, from any starting state, there is a sequence of better-response moves that leads to a pure Nash equilibrium; informally, these are games in which natural distributed dynamics, such as better-response dynamics, cannot enter inescapable oscillations. We establish a novel link between such games and the existence of pure Nash equilibria in subgames. Specifically, we show that the existence of a unique pure Nash equilibrium in every subgame implies the weak acyclicity of a game. In contrast, the possible existence of multiple pure Nash equilibria in every subgame is insufficient for weak acyclicity in general; here, we also systematically identify the special cases (in terms of the number of players and strategies) for which this is sufficient to guarantee weak acyclicity.     

Nash equilibria: Complexity,symmetries, and approximation

We survey recent joint work with Christos Papadimitriou and Paul Goldberg on the computational complexity of Nash equilibria. We show that finding a Nash equilibrium in normal form games is computationally intractable, but in an unusual way. It does belong to the class NP; but Nash’s theorem, showing that a Nash equilibrium always exists, makes the possibility that it is also NP-complete rather unlikely. We show instead that the problem is as hard computationally as finding Brouwer fixed points, in a precise technical sense, giving rise to a new complexity class called PPAD. The existence of the Nash equilibrium was established via Brouwer’s fixed-point theorem; hence, we provide a computational converse to Nash’s theorem.To alleviate the negative implications of this result for the predictive power of the Nash equilibrium, it seems natural to study the complexity of approximate equilibria: an efficient approximation scheme would imply that players could in principle come arbitrarily close to a Nash equilibrium given enough time. We review recent work on computing approximate equilibria and conclude by studying how symmetries may affect the structure and approximation of Nash equilibria. Nash showed that every symmetric game has a symmetric equilibrium. We complement this theorem with a rich set of structural results for a broader, and more interesting class of games with symmetries, called anonymous games.     

Equilibria,fixed points,and complexity classes

Many models from a variety of areas involve the computation of an equilibrium or fixed point of some kind. Examples include Nash equilibria in games; market equilibria; computing optimal strategies and the values of competitive games (stochastic and other games); stable configurations of neural networks; analysing basic stochastic models for evolution like branching processes and for language like stochastic context-free grammars; and models that incorporate the basic primitives of probability and recursion like recursive Markov chains. It is not known whether these problems can be solved in polynomial time. There are certain common computational principles underlying different types of equilibria, which are captured by the complexity classes PLS, PPAD, and FIXP. Representative complete problems for these classes are, respectively, pure Nash equilibria in games where they are guaranteed to exist, (mixed) Nash equilibria in two-player normal form games, and (mixed) Nash equilibria in normal form games with three (or more) players. This paper reviews the underlying computational principles and the corresponding classes.     

Partition Equilibrium Always Exists in Resource Selection Games

We consider the existence of Partition Equilibrium in Resource Selection Games. Super-strong equilibrium, where no subset of players has an incentive to change their strategies collectively, does not always exist in such games. We show, however, that partition equilibrium (introduced in (Feldman and Tennenholtz in SAGT, pp. 48–59, 2009) to model coalitions arising in a social context) always exists in general resource selection games, as well as how to compute it efficiently. In a partition equilibrium, the set of players has a fixed partition into coalitions, and the only deviations considered are by coalitions that are sets in this partition. Our algorithm to compute a partition equilibrium in any resource selection game (i.e., load balancing game) settles the open question from (Feldman and Tennenholtz in SAGT, pp. 48–59, 2009) about existence of partition equilibrium in general resource selection games. Moreover, we show how to always find a partition equilibrium which is also a Nash equilibrium. This implies that in resource selection games, we do not need to sacrifice the stability of individual players when forming solutions stable against coalitional deviations. In addition, while super-strong equilibrium may not exist in resource selection games, we show that its existence can be decided efficiently, and how to find one if it exists.     

Window-games between TCP flows

We consider network congestion problems between TCP flows and define a new game, the Window-game, which models the problems of network congestion caused by the competing flows. Analytical and experimental results show the relevance of the Window-game to real TCP congestion games and provide interesting insight into the respective Nash equilibria. Furthermore, we propose a new algorithmic queue mechanism, called Prince, which at congestion makes a scapegoat of the most greedy flow. We provide evidence which shows that Prince achieves efficient Nash equilibria while requiring only limited computational resources.     

Assignment Games with Conflicts: Robust Price of Anarchy and Convergence Results via Semi-Smoothness

We study assignment games in which jobs select machines, and in which certain pairs of jobs may conflict, which is to say they may incur an additional cost when they are both assigned to the same machine, beyond that associated with the increase in load. Questions regarding such interactions apply beyond allocating jobs to machines: when people in a social network choose to align themselves with a group or party, they typically do so based upon not only the inherent quality of that group, but also who amongst their friends (or enemies) chooses that group as well. We show how semi-smoothness, a recently introduced generalization of smoothness, is necessary to find tight bounds on the robust price of anarchy, and thus on the quality of correlated and Nash equilibria, for several natural job-assignment games with interacting jobs. For most cases, our bounds on the robust price of anarchy are either exactly 2 or approach 2. We also prove new convergence results implied by semi-smoothness for our games. Finally we consider coalitional deviations, and prove results about the existence and quality of strong equilibrium.     

How hard is it to find extreme Nash equilibria in network congestion games?

We study the complexity of finding extreme pure Nash equilibria in symmetric (unweighted) network congestion games. In our context best and worst equilibria are those with minimum respectively maximum makespan. On series–parallel graphs a worst Nash equilibrium can be found by a Greedy approach while finding a best equilibrium is NP-hard. For a fixed number of users we give a pseudo-polynomial algorithm to find the best equilibrium in series–parallel networks. For general network topologies also finding a worst equilibrium is NP-hard.     

Stackelberg Strategies for Atomic Congestion Games

We investigate the effectiveness of Stackelberg strategies for atomic congestion games with unsplittable demands. In our setting, only a fraction of the players are selfish, while the rest are willing to follow a predetermined strategy. A Stackelberg strategy assigns the coordinated players to appropriately selected strategies trying to minimize the performance degradation due to the selfish players. We consider two orthogonal cases, namely congestion games with affine latency functions and arbitrary strategies, and congestion games on parallel links with arbitrary non-decreasing latency functions. We restrict our attention to pure Nash equilibria and derive strong upper and lower bounds on the pure Price of Anarchy (PoA) under different Stackelberg strategies.     

Distributed algorithms for the computation of noncooperative equilibria

In this paper, a general class of nonquadratic convex Nash games is studied, from the points of view of existence, stability and iterative computation of noncooperative equilibria. Conditions for contraction of general nonlinear operators are obtained, which are then used in the stability study of such games. These lead to existence and uniqueness conditions for stable Nash equilibrium solutions, under both global and local analysis. Also, convergence of an algorithm which employs inaccurate search techniques is verified. It is shown in the context of a fish war example that the algorithm given is in some aspects superior to various algorithms found in the literature, and is furthermore more meaningful for real world implementation.     

Constrained multiobjective games in general topological space

In this paper, we introduce and study a new class of constrained multiobjective games in general noncompact topological space. By employing an existence theorem of quasi-equilibrium problems due to this author, several existence theorems of weighted Nash equilibria and Pareto equilibria for the constrained multiobjective games are established in noncompact topological spaces. These theorems improve, unify, and generalize the corresponding results of the multiobjective games in recent literature.     

Equilibria problems on games: Complexity versus succinctness

We study the computational complexity of problems involving equilibria in strategic games and in perfect information extensive games when the number of players is large. We consider, among others, the problems of deciding the existence of a pure Nash equilibrium in strategic games or deciding the existence of a pure Nash or a subgame perfect Nash equilibrium with a given payoff in finite perfect information extensive games. We address the fundamental question of how can we represent a game with a large number of players? We propose three ways of representing a game with different degrees of succinctness for the components of the game. For perfect information extensive games we show that when the number of moves of each player is large and the input game is represented succinctly these problems are PSPACE-complete. In contraposition, when the game is described explicitly by means of its associated tree all these problems are decidable in polynomial time. For strategic games we show that the complexity of deciding the existence of a pure Nash equilibrium depends on the succinctness of the game representation and then on the size of the action sets. In particular we show that it is NP-complete, when the number of players is large and the number of actions for each player is constant, and that the problem is -complete when the number of players is a constant and the size of the action sets is exponential in the size of the game representation. Again when the game is described explicitly the problem is decidable in polynomial time.     

On the complexity of constrained Nash equilibria in graphical games

A widely accepted rational behavior for non-cooperative players is based on the notion of Nash equilibrium. Although the existence of a Nash equilibrium is guaranteed in the mixed framework (i.e., when players select their actions in a randomized manner) in many real-world applications the existence of “any” equilibrium is not enough. Rather, it is often desirable to single out equilibria satisfying some additional requirements (in order, for instance, to guarantee a minimum payoff to certain players), which we call constrained Nash equilibria.In this paper, a formal framework for specifying these kinds of requirement is introduced and investigated in the context of graphical games, where a player p may directly be interested in some of the other players only, called the neighbors of p. This setting is very useful for modeling large population games, where typically each player does not directly depend on all the players, and representing her utility function extensively is either inconvenient or infeasible.Based on this framework, the complexity of deciding the existence and of computing constrained equilibria is then investigated, in the light of evidencing how the intrinsic difficulty of these tasks is affected by the requirements prescribed at the equilibrium and by the structure of players’ interactions. The analysis is carried out for the setting of mixed strategies as well as for the setting of pure strategies, i.e., when players are forced to deterministically choose the action to perform. In particular, for this latter case, restrictions on players’ interactions and on constraints are identified, that make the computation of Nash equilibria an easy problem, for which polynomial and highly-parallelizable algorithms are presented.     

On the Performance of Approximate Equilibria in Congestion Games

We study the performance of approximate Nash equilibria for congestion games with polynomial latency functions. We consider how much the price of anarchy worsens and how much the price of stability improves as a function of the approximation factor ε. We give tight bounds for the price of anarchy of atomic and non-atomic congestion games and for the price of stability of non-atomic congestion games. For the price of stability of atomic congestion games we give non-tight bounds for linear latencies. Our results not only encompass and generalize the existing results of exact equilibria to ε-Nash equilibria, but they also provide a unified approach which reveals the common threads of the atomic and non-atomic price of anarchy results. By expanding the spectrum, we also cast the existing results in a new light.     

Bounded budget betweenness centrality game for strategic network formations

In computer networks and social networks, the betweenness centrality of a node measures the amount of information passing through the node when all pairs are conducting shortest path exchanges. In this paper, we introduce a strategic network formation game in which nodes build connections subject to a budget constraint in order to maximize their betweenness in the network. To reflect real world scenarios where short paths are more important in information exchange in the network, we generalize the betweenness definition to only count shortest paths with a length limit ? in betweenness calculation. We refer to this game as the bounded budget betweenness centrality game and denote it as ?- B³C game, where ? is the path length constraint parameter.We present both complexity and constructive existence results about Nash equilibria of the game. For the nonuniform version of the game where node budgets, link costs, and pairwise communication weights may vary, we show that Nash equilibria may not exist and it is NP-hard to decide whether Nash equilibria exist in a game instance. For the uniform version of the game where link costs and pairwise communication weights are one and each node can build k links, we construct two families of Nash equilibria based on shift graphs, and study the properties of Nash equilibria. Moreover, we study the complexity of computing best responses and show that the task is polynomial for uniform 2- B³C games and NP-hard for other games (i.e. uniform ?- B³C games with ?≥3 and nonuniform ?- B³C games with ?≥2).     

Quantum games and quaternionic strategies

It is well-known that the phenomenon of entanglement plays a fundamental role in quantum game theory. Occasionally, games constructed via maximally entangled initial states (MEIS) will have new Nash equilibria yielding to the players higher payoffs than the ones they receive in the classical version of the game. When examining these new games for Nash equilibrium payoffs, a fundamental question arises; does a suitable choice of an MEIS improve the lot of the players? In this paper, we show that the answer to this question is yes for at least the case of a variant of the well-known two player, two strategy game of Chicken. To that end, we generalize Landsburg’s quaternionic representation of the payoff function of two player, two strategy maximally entangled states to games where the initial state is chosen arbitrarily from a circle of maximally entangled initial states and for the corresponding quantized games show the existence of superior Nash equilibrium payoffs when an MEIS is appropriately chosen.     

Non-cooperative routing in loss networks

The paper studies routing in loss networks in the framework of a non-cooperative game with selfish users. Two solution concepts are considered: the Nash equilibrium, corresponding to the case of a finite number of agents (such as service providers) that take routing decisions, and the Wardrop equilibrium, in which routing decisions are taken by a very large number of individual users. We show that these equilibria do not fall into the standard frameworks of non-cooperative routing games. As a result, we show that uniqueness of equilibria or even of utilizations at equilibria may fail even in the case of simple topology of parallel links. However, we show that some of the problems disappear in the case in which the bandwidth required by all connections is the same. For the special case of a parallel link topology, we obtain some surprisingly simple way of solving the equilibrium for both cases of Wardrop as well as Nash equilibrium.