Separable and low-rank continuous games

In this paper, we study nonzero-sum separable games, which are continuous games whose payoffs take a sum-of-products form. Included in this subclass are all finite games and polynomial games. We investigate the structure of equilibria in separable games. We show that these games admit finitely supported Nash equilibria. Motivated by the bounds on the supports of mixed equilibria in two-player finite games in terms of the ranks of the payoff matrices, we define the notion of the rank of an n-player continuous game and use this to provide bounds on the cardinality of the support of equilibrium strategies. We present a general characterization theorem that states that a continuous game has finite rank if and only if it is separable. Using our rank results, we present an efficient algorithm for computing approximate equilibria of two-player separable games with fixed strategy spaces in time polynomial in the rank of the game. This research was funded in part by National Science Foundation grants DMI-0545910 and ECCS-0621922 and AFOSR MURI subaward 2003-07688-1.     

Algorithms for generalized potential games with mixed-integer variables

We consider generalized potential games, that constitute a fundamental subclass of generalized Nash equilibrium problems. We propose different methods to compute solutions of generalized potential games with mixed-integer variables, i.e., games in which some variables are continuous while the others are discrete. We investigate which types of equilibria of the game can be computed by minimizing a potential function over the common feasible set. In particular, for a wide class of generalized potential games, we characterize those equilibria that can be computed by minimizing potential functions as Pareto solutions of a particular multi-objective problem, and we show how different potential functions can be used to select equilibria. We propose a new Gauss–Southwell algorithm to compute approximate equilibria of any generalized potential game with mixed-integer variables. We show that this method converges in a finite number of steps and we also give an upper bound on this number of steps. Moreover, we make a thorough analysis on the behaviour of approximate equilibria with respect to exact ones. Finally, we make many numerical experiments to show the viability of the proposed approaches.     

On Nikaido-Isoda type theorems for discounted stochastic games

We present a class of countable state space stochastic games with discontinuous payoff functions satisfying some assumptions similar to the ones of Nikaido and Isoda for one-stage games. We prove that these games possess stationary equilibria. We show that after adding some concavity assumptions these equilibria are nonrandomized. Further, we present an example of input (or production) dynamic game satisfying the assumptions of our model. We give a closed-form solution for this game.     

Games with the total bandwagon property meet the Quint–Shubik conjecture

This paper revisits the total bandwagon property (TBP) introduced by Kandori and Rob (Games Econ Behav 22:30–60, 1998). With this property, we characterize the class of two-player symmetric \(n\times n\) games, showing that a game has TBP if and only if the game has \(2^{n}-1\) symmetric Nash equilibria. We extend this result to bimatrix games by generalizing TBP. This sheds light on the (wrong) conjecture of Quint and Shubik (Int J Game Theory 26:353–359, 1997) that any nondegenerate \(n\times n\) bimatrix game has at most \(2^{n}-1\) Nash equilibria. We also provide an equilibrium selection criterion to two subclasses of games with TBP.     

A Globally Convergent Algorithm to Compute All Nash Equilibria for <Emphasis Type="Italic">n</Emphasis>-Person Games

In this paper we present an algorithm to compute all Nash equilibria for generic finite n-person games in normal form. The algorithm relies on decomposing the game by means of support-sets. For each support-set, the set of totally mixed equilibria of the support-restricted game can be characterized by a system of polynomial equations and inequalities. By finding all the solutions to those systems, all equilibria are found. The algorithm belongs to the class of homotopy-methods and can be easily implemented. Finally, several techniques to speed up computations are proposed.     

Computation of equilibria and the price of anarchy in bottleneck congestion games

We study Nash and strong equilibria in weighted and unweighted bottleneck games. In such a game every (weighted) player chooses a subset of a given set of resources as her strategy. The cost of a resource depends on the total weight of players choosing it and the personal cost every player tries to minimize is the cost of the most expensive resource in her strategy, the bottleneck value. To derive efficient algorithms for finding equilibria in unweighted games, we generalize a transformation of a bottleneck game into a congestion game with exponential cost functions introduced by Caragiannis et al. (2005). For weighted routing games we show that Greedy methods give Nash equilibria in extension-parallel and series-parallel graphs. Furthermore, we show that the strong Price of Anarchy can be arbitrarily high for special cases and give tight bounds depending on the topology of the graph, the number and weights of the users and the degree of the polynomial latency functions. Additionally we investigate the existence of equilibria in generalized bottleneck games, where players aim to minimize not only the bottleneck value, but also the second most expensive resource in their strategy and so on.     

A Shared-Constraint Approach to Multi-Leader Multi-Follower Games

Multi-leader multi-follower games are a class of hierarchical games in which a collection of leaders compete in a Nash game constrained by the equilibrium conditions of another Nash game amongst the followers. The resulting equilibrium problem with equilibrium constraints is complicated by nonconvex agent problems and therefore providing tractable conditions for existence of global or even local equilibria has proved challenging. Consequently, much of the extant research on this topic is either model specific or relies on weaker notions of equilibria. We consider a modified formulation in which every leader is cognizant of the equilibrium constraints of all leaders. Equilibria of this modified game contain the equilibria, if any, of the original game. The new formulation has a constraint structure called shared constraints, and our main result shows that if the leader objectives admit a potential function, the global minimizers of the potential function over this shared constraint are equilibria of the modified formulation. We provide another existence result using fixed point theory that does not require potentiality. Additionally, local minima, B-stationary, and strong-stationary points of this minimization problem are shown to be local Nash equilibria, Nash B-stationary, and Nash strong-stationary points of the corresponding multi-leader multi-follower game. We demonstrate the relationship between variational equilibria associated with this modified shared-constraint game and equilibria of the original game from the standpoint of the multiplier sets and show how equilibria of the original formulation may be recovered. We note through several examples that such potential multi-leader multi-follower games capture a breadth of application problems of interest and demonstrate our findings on a multi-leader multi-follower Cournot game.     

Common resources, optimality and taxes in dynamic games with increasing number of players

In the paper we examine the problem of exploitation of a common renewable resource. We use two kinds of models of this problem: games with finitely many players and games with a continuum of players. Equilibria in both cases are calculated and the payoffs are compared with payoffs in the situation in which each player behaves as a single owner of the resource. Various concepts of optimality are considered: optimality in the sense of property, Pareto optimality, maximization of a social welfare function of specific type and environmental sustainability. Another issue is the problem of enforcement of assumed profiles by so-called “linear” tax systems. Special attention is paid to the comparison of games with finitely many players and their continuum-of-players limit game.     

Characterizing the Shapley value in fixed-route traveling salesman problems with appointments

Starting from her home, a service provider visits several customers, following a predetermined route, and returns home after all customers are visited. The problem is to find a fair allocation of the total cost of this tour among the customers served. A transferable-utility cooperative game can be associated with this cost allocation problem. We introduce a new class of games, which we refer as the fixed-route traveling salesman games with appointments. We characterize the Shapley value in this class using a property which requires that sponsors do not benefit from mergers, or splitting into a set of sponsors.     

Unit-sphere games

This paper introduces a class of games, called unit-sphere games, in which strategies are real vectors with unit 2-norms (or, on a unit-sphere). As a result, they should no longer be interpreted as probability distributions over actions, but rather be thought of as allocations of one unit of resource to actions and the payoff effect on each action is proportional to the square root of the amount of resource allocated to that action. The new definition generates a number of interesting consequences. We first characterize the sufficient and necessary condition under which a two-player unit-sphere game has a Nash equilibrium. The characterization reduces solving a unit-sphere game to finding all eigenvalues and eigenvectors of the product matrix of individual payoff matrices. For any unit-sphere game with non-negative payoff matrices, there always exists a unique Nash equilibrium; furthermore, the unique equilibrium is efficiently reachable via Cournot adjustment. In addition, we show that any equilibrium in positive unit-sphere games corresponds to approximate equilibria in the corresponding normal-form games. Analogous but weaker results are obtained in n-player unit-sphere games.     

Equilibrium strategies for multiple interdictors on a common network

In this work, we introduce multi-interdictor games, which model interactions among multiple interdictors with differing objectives operating on a common network. As a starting point, we focus on shortest path multi-interdictor (SPMI) games, where multiple interdictors try to increase the shortest path lengths of their own adversaries attempting to traverse a common network. We first establish results regarding the existence of equilibria for SPMI games under both discrete and continuous interdiction strategies. To compute such an equilibrium, we present a reformulation of the SPMI game, which leads to a generalized Nash equilibrium problem (GNEP) with non-shared constraints. While such a problem is computationally challenging in general, we show that under continuous interdiction actions, an SPMI game can be formulated as a linear complementarity problem and solved by Lemke’s algorithm. In addition, we present decentralized heuristic algorithms based on best response dynamics for games under both continuous and discrete interdiction strategies. Finally, we establish theoretical lower bounds on the worst-case efficiency loss of equilibria in SPMI games, with such loss caused by the lack of coordination among noncooperative interdictors, and use the decentralized algorithms to numerically study the average-case efficiency loss.     

Welfare-maximizing correlated equilibria using Kantorovich polynomials with sparsity

We provide motivations for the correlated equilibrium solution concept from the game-theoretic and optimization perspectives. We then propose an algorithm that computes ${\varepsilon}$ -correlated equilibria with global-optimal (i.e., maximum) expected social welfare for normal form polynomial games. We derive an infinite dimensional formulation of ${\varepsilon}$ -correlated equilibria using Kantorovich polynomials, and re-express it as a polynomial positivity constraint. We exploit polynomial sparsity to achieve a leaner problem formulation involving sum-of-squares constraints. By solving a sequence of semidefinite programming relaxations of the problem, our algorithm converges to a global-optimal ${\varepsilon}$ -correlated equilibrium. The paper ends with two numerical examples involving a two-player polynomial game, and a wireless game with two mutually-interfering communication links.     

Common pool resources with support

We examine the role of support for coalition stability in common pool resource games such as fisheries games. Some players may not want to join a coalition that jointly manages a resource. Still, because they benefit from spillovers, they may want to support the coalition with a transfer payment to set incentives for others to join. We find that the impact of support on equilibria of this game is limited to games with three or five players. Recommendations for Resource Managers

• Coalitions may be able to effectively manage common pool resources such as fisheries but such coalitions are often not stable due to free-rider incentives.
• We explore the impact of a transfer scheme that can improve this coalition stability which would lead to larger and more effective coalitions.
• Our results show that this new transfer scheme works only for cases where the number of players is small.

     

Some interesting properties of maximin strategies

Since the seminal paper of Nash (1950) game theoretic literature has focused mostly on equilibrium and not on maximin (minimax) strategies. We study the properties of these strategies in non-zero-sum strategic games that possess (completely) mixed Nash equilibria. We find that under certain conditions maximin strategies have several interesting properties, some of which extend beyond 2-person strategic games. In particular, for n-person games we specify necessary and sufficient conditions for maximin strategies to yield the same expected payoffs as Nash equilibrium strategies. We also show how maximin strategies may facilitate payoff comparison across Nash equilibria as well as refine some Nash equilibrium strategies.     

An axiomatization of the Shapley value using a fairness property

In this paper we provide an axiomatization of the Shapley value for TU-games using a fairness property. This property states that if to a game we add another game in which two players are symmetric then their payoffs change by the same amount. We show that the Shapley value is characterized by this fairness property, efficiency and the null player property. These three axioms also characterize the Shapley value on the class of simple games. Revised August 2001     

Independent mistakes in large games

Economic models usually assume that agents play precise best responses to others' actions. It is sometimes argued that this is a good approximation when there are many agents in the game, because if their mistakes are independent, aggregate uncertainty is small. We study a class of games in which players' payoffs depend solely on their individual actions and on the aggregate of all players' actions. We investigate whether their equilibria are affected by mistakes when the number of players becomes large. Indeed, in generic games with continuous payoff functions, independent mistakes wash out in the limit. This may not be the case if payoffs are discontinuous. As a counter-example we present the n players Nash bargaining game, as well as a large class of “free-rider games.” Received: November 1997/Final version: December 1999     

Zero-sum risk-sensitive stochastic games on a countable state space

Infinite horizon discounted-cost and ergodic-cost risk-sensitive zero-sum stochastic games for controlled Markov chains with countably many states are analyzed. Upper and lower values for these games are established. The existence of value and saddle-point equilibria in the class of Markov strategies is proved for the discounted-cost game. The existence of value and saddle-point equilibria in the class of stationary strategies is proved under the uniform ergodicity condition for the ergodic-cost game. The value of the ergodic-cost game happens to be the product of the inverse of the risk-sensitivity factor and the logarithm of the common Perron–Frobenius eigenvalue of the associated controlled nonlinear kernels.     

Linear Transformation of Products: Games and Economies

In this paper, we introduce situations involving the linear transformation of products (LTP). LTP situations are production situations where each producer has a single linear transformation technique. First, we approach LTP situations from a (cooperative) game theoretical point of view. We show that the corresponding LTP games are totally balanced. By extending an LTP situation to one where a producer may have more than one linear transformation technique, we derive a new characterization of (nonnegative) totally balanced games: each totally balanced game with nonnegative values is a game corresponding to such an extended LTP situation. The second approach to LTP situations is based on a more economic point of view. We relate (standard) LTP situations to economies in two ways and we prove that the economies are standard exchange economies (with production). Relations between the equilibria of these economies and the cores of cooperative LTP games are investigated.     

Forecast Horizon for a Class of Dynamic Games

In theory, a Markov perfect equilibrium of an infinite-horizon nonstationary dynamic game requires from the players the ability to forecast an infinite amount of data. In this paper, we prove that early strategic decisions are decoupled effectively from the tail game in nonstationary dynamic games with discounting and uniformly bounded rewards. This decoupling is formalized by the notion of a forecast horizon. In words, the first-period equilibrium strategies are invariant with respect to changes in the game parameters for periods beyond the forecast horizon. We illustrate our results in the context of dynamic games of exploitation of a common pool resource and make use of the rather natural monotonicity properties of finite-horizon equilibria.     

Robust game theory

We present a distribution-free model of incomplete-information games, both with and without private information, in which the players use a robust optimization approach to contend with payoff uncertainty. Our ``robust game' model relaxes the assumptions of Harsanyi's Bayesian game model, and provides an alternative distribution-free equilibrium concept, which we call ``robust-optimization equilibrium,' to that of the ex post equilibrium. We prove that the robust-optimization equilibria of an incomplete-information game subsume the ex post equilibria of the game and are, unlike the latter, guaranteed to exist when the game is finite and has bounded payoff uncertainty set. For arbitrary robust finite games with bounded polyhedral payoff uncertainty sets, we show that we can compute a robust-optimization equilibrium by methods analogous to those for identifying a Nash equilibrium of a finite game with complete information. In addition, we present computational results. The research of the author was partially supported by a National Science Foundation Graduate Research Fellowship and by the Singapore-MIT Alliance. The research of the author was partially supported by the Singapore-MIT Alliance.