When ignorance helps: Graphical multicast cost sharing games

In non-cooperative games played on highly decentralized networks the assumption that each player knows the strategy adopted by any other player may be too optimistic or even infeasible. In such situations, the set of players of which each player knows the chosen strategy can be modeled by means of a social knowledge graph in which nodes represent players and there is an edge from i to j if i knows j. Following the framework introduced in [7], we study the impact of social knowledge graphs on the fundamental multicast cost sharing game in which all the players want to receive the same communication from a given source in an undirected network. In the classical complete information case, such a game is known to be highly inefficient, since its price of anarchy can be as high as the total number of players ρ. We first show that, under our incomplete information setting, pure Nash equilibria always exist only if the social knowledge graph is directed acyclic (DAG). We then prove that the price of stability of any DAG is at least and provide a DAG lowering the classical price of anarchy to a value between and log²ρ. If specific instances of the game are concerned, that is if the social knowledge graph can be selected as a function of the instance, we show that the price of stability is at least , and that the same bound holds also for the price of anarchy of any social knowledge graph (not only DAGs). Moreover, we provide a nearly matching upper bound by proving that, for any fixed instance, there always exists a DAG yielding a price of anarchy less than 4. Our results open a new window on how the performances of non-cooperative systems may benefit from the lack of total knowledge among players.     

When Can Limited Randomness Be Used in Repeated Games?

The central result of classical game theory states that every finite normal form game has a Nash equilibrium, provided that players are allowed to use randomized (mixed) strategies. However, in practice, humans are known to be bad at generating random-like sequences, and true random bits may be unavailable. Even if the players have access to enough random bits for a single instance of the game their randomness might be insufficient if the game is played many times. In this work, we ask whether randomness is necessary for equilibria to exist in finitely repeated games. We show that for a large class of games containing arbitrary two-player zero-sum games, approximate Nash equilibria of the n-stage repeated version of the game exist if and only if both players have Ω(n) random bits. In contrast, we show that there exists a class of games for which no equilibrium exists in pure strategies, yet the n-stage repeated version of the game has an exact Nash equilibrium in which each player uses only a constant number of random bits. When the players are assumed to be computationally bounded, if cryptographic pseudorandom generators (or, equivalently, one-way functions) exist, then the players can base their strategies on “random-like” sequences derived from only a small number of truly random bits. We show that, in contrast, in repeated two-player zero-sum games, if pseudorandom generators do not exist, then Ω(n) random bits remain necessary for equilibria to exist.     

The Impact of Social Ignorance on Weighted Congestion Games

We consider weighted linear congestion games, and investigate how social ignorance, namely lack of information about the presence of some players, affects the inefficiency of pure Nash equilibria (PNE) and the convergence rate of the ε-Nash dynamics. To this end, we adopt the model of graphical linear congestion games with weighted players, where the individual cost and the strategy selection of each player only depends on his neighboring players in the social graph. We show that such games admit a potential function, and thus a PNE. Next, we investigate the Price of Anarchy (PoA) and the Price of Stability (PoS) of graphical linear congestion games with respect to the players’ total actual cost. Our main result is that the impact of social ignorance on the PoA and on the PoS is naturally quantified by the independence number α(G) of the social graph G. In particular, we show that the PoA grows roughly as α(G)(α(G)+2), which is essentially tight as long as α(G) does not exceed half the number of players, and that the PoS lies between α(G) and 2α(G). Moreover, we show that the ε-Nash dynamics reaches an α(G)(α(G)+2)-approximate configuration in polynomial time that does not directly depend on the social graph. For unweighted graphical linear games with symmetric strategies, we show that the ε-Nash dynamics reaches an ε-approximate PNE in polynomial time that exceeds the corresponding time for symmetric linear games by a factor at most as large as the number of players.     

Chain equilibria in secure strategies

In this paper we introduce a modification of the concept of Equilibrium in Secure Strategies (EinSS), which takes into account the non-uniform attitudes of players to security in non-cooperative games. In particular, we examine an asymmetric attitude of players to mutual threats in the simplest case, when all players are strictly ordered by their relation to security. Namely, we assume that the players can be reindexed so that each player i in his behavior takes into account the threats posed by players j > i but ignores the threats of players j < i provided that these threats are effectively contained by some counterthreats. A corresponding equilibrium will be called a Chain EinSS. The conceptual meaning of this equilibrium is illustrated by two continuous games that have no pure Nash equilibrium or (conventional) EinSS. The Colonel Blotto two-player game (Borel 1953; Owen 1968) for two battlefields with different price always admits a Chain EinSS with intuitive interpretation. The product competition of many players on a segment (Eaton, Lipsey 1975; Shaked 1975) with the linear distribution of consumer preferences always admits a unique Chain EinSS solution (up to a permutation of players). Finally, we compare Chain EinSS with Stackelberg equilibrium.     

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.     

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.     

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.     

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.     

Consensus in Noncooperative Dynamic Games: A Multiretailer Inventory Application

We focus on Nash equilibria and Pareto optimal Nash equilibria for a finite horizon noncooperative dynamic game with a special structure of the stage cost. We study the existence of these solutions by proving that the game is a potential game. For the single-stage version of the game, we characterize the aforementioned solutions and derive a consensus protocol that makes the players converge to the unique Pareto optimal Nash equilibrium. Such an equilibrium guarantees the interests of the players and is also social optimal in the set of Nash equilibria. For the multistage version of the game, we present an algorithm that converges to Nash equilibria, unfortunately, not necessarily Pareto optimal. The algorithm returns a sequence of joint decisions, each one obtained from the previous one by an unilateral improvement on the part of a single player. We also specialize the game to a multiretailer inventory system.     

Network Design with Weighted Players

We consider a model of game-theoretic network design initially studied by Anshelevich et al. (Proceedings of the 45th Annual Symposium on Foundations of Computer Science (FOCS), pp. 295–304, 2004), where selfish players select paths in a network to minimize their cost, which is prescribed by Shapley cost shares. If all players are identical, the cost share incurred by a player for an edge in its path is the fixed cost of the edge divided by the number of players using it. In this special case, Anshelevich et al. (Proceedings of the 45th Annual Symposium on Foundations of Computer Science (FOCS), pp. 295–304, 2004) proved that pure-strategy Nash equilibria always exist and that the price of stability—the ratio between the cost of the best Nash equilibrium and that of an optimal solution—is Θ(log k), where k is the number of players. Little was known about the existence of equilibria or the price of stability in the general weighted version of the game. Here, each player i has a weight w _i ≥1, and its cost share of an edge in its path equals w _i times the edge cost, divided by the total weight of the players using the edge. This paper presents the first general results on weighted Shapley network design games. First, we give a simple example with no pure-strategy Nash equilibrium. This motivates considering the price of stability with respect to α-approximate Nash equilibria—outcomes from which no player can decrease its cost by more than an α multiplicative factor. Our first positive result is that O(log w _max)-approximate Nash equilibria exist in all weighted Shapley network design games, where w _max is the maximum player weight. More generally, we establish the following trade-off between the two objectives of good stability and low cost: for every α=Ω(log w _max), the price of stability with respect to O(α)-approximate Nash equilibria is O((log W)/α), where W is the sum of the players’ weights. In particular, there is always an O(log W)-approximate Nash equilibrium with cost within a constant factor of optimal. Finally, we show that this trade-off curve is nearly optimal: we construct a family of networks without o(log w _max/ log log w _max)-approximate Nash equilibria, and show that for all α=Ω(log w _max/log log w _max), achieving a price of stability of O(log W/α) requires relaxing equilibrium constraints by an Ω(α) factor. Research of H.-L. Chen supported in part by NSF Award 0323766. Research of T. Roughgarden supported in part by ONR grant N00014-04-1-0725, DARPA grant W911NF-04-9-0001, and an NSF CAREER Award.     

Establishing Nash equilibria of strategic games: a multistart Fuzzy Adaptive Simulated Annealing approach

This paper's proposal is to show some significant results obtained by the application of the optimization algorithm known as Fuzzy Adaptive Simulated Annealing (Fuzzy ASA) to the task of finding all Nash equilibria of normal form games. To that end, a special version of Fuzzy ASA, that utilizes space-filling curves to find good seeds, is applied to several well-known strategic games, showing its effectiveness in obtaining all Nash equilibria in all cases. The results are compared to previous work that also used computational intelligence techniques in order to solve the same problem but could not find all equilibria in all tests. Game theory is a very important subject, modeling interactions between generic agents, and Nash equilibrium represents a powerful concept portraying situations in which joint strategies are optimal in the sense that no player can benefit from changing her/his strategy while the other players do not change their strategies as well. So, new techniques are always welcome, mainly those that can find the whole set of solutions for a given strategic game.     

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.     

On the Rate of Convergence of Fictitious Play

Fictitious play is a simple learning algorithm for strategic games that proceeds in rounds. In each round, the players play a best response to a mixed strategy that is given by the empirical frequencies of actions played in previous rounds. There is a close relationship between fictitious play and the Nash equilibria of a game: if the empirical frequencies of fictitious play converge to a strategy profile, this strategy profile is a Nash equilibrium. While fictitious play does not converge in general, it is known to do so for certain restricted classes of games, such as constant-sum games, non-degenerate 2×n games, and potential games. We study the rate of convergence of fictitious play and show that, in all the classes of games mentioned above, fictitious play may require an exponential number of rounds (in the size of the representation of the game) before some equilibrium action is eventually played. In particular, we show the above statement for symmetric constant-sum win-lose-tie games.     

On the Complexity of Pareto-Optimal Nash and Strong Equilibria

We consider the computational complexity of coalitional solution concepts in scenarios related to load balancing such as anonymous and congestion games. In congestion games, Pareto-optimal Nash and strong equilibria, which are resilient to coalitional deviations, have recently been shown to yield significantly smaller inefficiency. Unfortunately, we show that several problems regarding existence, recognition, and computation of these concepts are hard, even in seemingly special classes of games. In anonymous games with constant number of strategies, we can efficiently recognize a state as Pareto-optimal Nash or strong equilibrium, but deciding existence for a game remains hard. In the case of player-specific singleton congestion games, we show that recognition and computation of both concepts can be done efficiently. In addition, in these games there are always short sequences of coalitional improvement moves to Pareto-optimal Nash and strong equilibria that can be computed efficiently.     

N-person credibilistic strategic game

This paper enlarges the scope of fuzzy-payoff game to n-person form from the previous two-person form. Based on credibility theory, three credibilistic approaches are introduced to model the behaviors of players in different decision situations. Accordingly, three new definitions of Nash equilibrium are proposed for n-person credibilistic strategic game. Moreover, existence theorems are proved for further research into credibilistic equilibrium strategies. Finally, two numerical examples are given to illustrate the significance of credibilistic equilibria in practical strategic games.     

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.     

Convergence analysis for pure stationary strategies in repeated potential games: Nash,Lyapunov and correlated equilibria

In game theory the interaction among players obligates each player to develop a belief about the possible strategies of the other players, to choose a best-reply given those beliefs, and to look for an adjustment of the best-reply and the beliefs using a learning mechanism until they reach an equilibrium point. Usually, the behavior of an individual cost-function, when such best-reply strategies are applied, turns out to be non-monotonic and concluding that such strategies lead to some equilibrium point is a non-trivial task. Even in repeated games the convergence to a stationary equilibrium is not always guaranteed. The best-reply strategies analyzed in this paper represent the most frequent type of behavior applied in practice in problems of bounded rationality of agents considered within the Artificial Intelligence research area. They are naturally related with the, so-called, fixed-local-optimal actions or, in other words, with one step-ahead optimization algorithms widely used in the modern Intelligent Systems theory.This paper shows that for an ergodic class of finite controllable Markov games the best-reply strategies lead necessarily to a Lyapunov/Nash equilibrium point. One of the most interesting properties of this approach is that an expedient (or absolutely expedient) behavior of an ergodic system (repeated game) can be represented by a Lyapunov-like function non-decreasing in time. We present a method for constructing a Lyapunov-like function: the Lyapunov-like function replaces the recursive mechanism with the elements of the ergodic system that model how players are likely to behave in one-shot games. To show our statement, we first propose a non-converging state-value function that fluctuates (increases and decreases) between states of the Markov game. Then, we prove that it is possible to represent that function in a recursive format using a one-step-ahead fixed-local-optimal strategy. As a result, we prove that a Lyapunov-like function can be built using the previous recursive expression for the Markov game, i.e., the resulting Lyapunov-like function is a monotonic function which can only decrease (or remain the same) over time, whatever the initial distribution of probabilities. As a result, a new concept called Lyapunov games is suggested for a class of repeated games. Lyapunov games allow to conclude during the game whether the applied strategy provides the convergence to an equilibrium point (or not). The time for constructing a Potential (Lyapunov-like) function is exponential. Our algorithm tractably computes the Nash, Lyapunov and the correlated equilibria: a Lyapunov equilibrium is a Nash equilibrium, as well it is also a correlated equilibrium. Validity of the proposed method is successfully demonstrated both theoretically and practically by a simulated experiment related to the Duel game.     

Matrix games with missing,interval, and ambiguous lottery payoffs of pure strategy profiles and compound strategy profiles

In a matrix game, the interactions among players are based on the assumption that each player has accurate information about the payoffs of their interactions and the other players are rationally self‐interested. As a result, the players should definitely take Nash equilibrium strategies. However, in real‐life, when choosing their optimal strategies, sometimes the players have to face missing, imprecise (i.e., interval), ambiguous lottery payoffs of pure strategy profiles and even compound strategy profile, which means that it is hard to determine a Nash equilibrium. To address this issue, in this paper we introduce a new solution concept, called ambiguous Nash equilibrium, which extends the concept of Nash equilibrium to the one that can handle these types of ambiguous payoff. Moreover, we will reveal some properties of matrix games of this kind. In particular, we show that a Nash equilibrium is a special case of ambiguous Nash equilibrium if the players have accurate information of each player's payoff sets. Finally, we give an example to illustrate how our approach deals with real‐life game theory problems.     

Flipping the winner of a poset game

Partially-ordered set games, also called poset games, are a class of two-player combinatorial games. The playing field consists of a set of elements, some of which are greater than other elements. Two players take turns removing an element and all elements greater than it, and whoever takes the last element wins. Examples of poset games include Nim and Chomp. We investigate the complexity of computing which player of a poset game has a winning strategy. We give an inductive procedure that modifies poset games to change the nim-value which informally captures the winning strategies in the game. For a generic poset game G, we describe an efficient method for constructing a game ¬G such that the first player has a winning strategy if and only if the second player has a winning strategy on G. This solves the long-standing problem of whether this construction can be done efficiently. This construction also allows us to reduce the class of Boolean formulas to poset games, establishing a lower bound on the complexity of poset games.