Semidefinite complementarity reformulation for robust Nash equilibrium problems with Euclidean uncertainty sets

Consider the N-person non-cooperative game in which each player’s cost function and the opponents’ strategies are uncertain. For such an incomplete information game, the new solution concept called a robust Nash equilibrium has attracted much attention over the past several years. The robust Nash equilibrium results from each player’s decision-making based on the robust optimization policy. In this paper, we focus on the robust Nash equilibrium problem in which each player’s cost function is quadratic, and the uncertainty sets for the opponents’ strategies and the cost matrices are represented by means of Euclidean and Frobenius norms, respectively. Then, we show that the robust Nash equilibrium problem can be reformulated as a semidefinite complementarity problem (SDCP), by utilizing the semidefinite programming (SDP) reformulation technique in robust optimization. We also give some numerical example to illustrate the behavior of robust Nash equilibria.     

Generalized Nash equilibrium problems for lower semi-continuous strategy maps

We consider a class of generalized Ky Fan inequalities (quasi-variational inequalities) in which the involved multi-valued mapping is lower semi-continuous. We present a relaxed version of the generalized Nash equilibrium problem involving strategy maps, which are only lower semi-continuous. This relaxed version may have no exact Nash equilibrium, but we prove that it has an ε-Nash equilibrium for every ε > 0. Easy examples of such problems show no existence of exact solutions, but existence of ε-solutions for every ε > 0. We give positive answers to two questions (in the compact case) raised in a recent paper of Cubiotti and Yao.     

Coalition-proof equilibria in a voluntary participation game

We examine the coalition-proof equilibria of a participation game in the provision of a (pure) public good. We study which Nash equilibria are achieved through cooperation, and we investigate coalition-proof equilibria under strict and weak domination. We show that under some incentive condition, (i) a profile of strategies is a coalition-proof equilibrium under strict domination if and only if it is a Nash equilibrium that is not strictly Pareto-dominated by any other Nash equilibrium and (ii) every strict Nash equilibrium for non-participants is a coalition-proof equilibrium under weak domination.     

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.     

Hotelling’s location model with negative network externalities

We study a variation of Hotelling’s location model in which consumers choose between firms based on travel distances as well as the number of consumers visiting each firm. The model in which the network externality is the same for all firms was proposed by Kohlberg (Econ Lett 11:211–216, 1983), who claims that no equilibrium exists for more than two firms. We assume the network effects to be linear and, in contrast to the claim in Kohlberg (Econ Lett 11:211–216, 1983), derive a condition under which a subgame perfect Nash equilibrium exists for four and six firms. Moreover, we show that for more than two firms the equilibrium locations of the firms are different from the equilibrium locations in Hotelling’s location model. Our results suggest that a subgame perfect Nash equilibrium exists if and only if the number of firms is even. We also provide examples of subgame perfect equilibria in which the network externality is different for some of the firms.     

Jet schemes and minimal toric embedded resolutions of rational double point singularities

Using the structure of the jet schemes of rational double point singularities, we construct “minimal embedded toric resolutions” of these singularities. We also establish, for these singularities, a correspondence between a natural class of irreducible components of the jet schemes centered at the singular locus and the set of divisors which appear on every “minimal embedded toric resolution”. We prove that this correspondence is bijective except for the E₈ singulartiy. This can be thought as an embedded Nash correspondence for rational double point singularities.     

Nonzero-sum non-stationary discounted Markov game model

The goal of this paper is provide a theory of K-person non-stationary Markov games with unbounded rewards, for a countable state space and action spaces. We investigate both the finite and infinite horizon problems. We define the concept of strong Nash equilibrium and present conditions for both problems for which strong Nash or Nash equilibrium strategies exist for all players within the Markov strategies, and show that the rewards in equilibrium satisfy the optimality equations.     

Nash equilibria in competitive project scheduling

We consider the problem of scheduling activities of a project by a firm that competes with another firm that has to perform the same project. The profit that a firm gets from each activity depends on whether the firm finishes the activity before or after its competitor. It is required to find a Nash equilibrium solution or show that no such solutions exist. We present a structural characterization of Nash equilibrium solutions, and a low order polynomial algorithm for the problem.     

Distributionally robust chance-constrained games: existence and characterization of Nash equilibrium

We consider an n-player finite strategic game. The payoff vector of each player is a random vector whose distribution is not completely known. We assume that the distribution of a random payoff vector of each player belongs to a distributional uncertainty set. We define a distributionally robust chance-constrained game using worst-case chance constraint. We consider two types of distributional uncertainty sets. We show the existence of a mixed strategy Nash equilibrium of a distributionally robust chance-constrained game corresponding to both types of distributional uncertainty sets. For each case, we show a one-to-one correspondence between a Nash equilibrium of a game and a global maximum of a certain mathematical program.     

The Existence and Uniqueness of Nash Equilibrium Point in an m-player Game “Shoot Later, Shoot First!”

We consider the following “silent duel” of m players with a possible economic interpretation. Each player has one “bullet”, which she can shoot at any time during the time interval [0,1]. The probability that the i-th player hits the “target” at moment t is given by an increasing accuracy function f _i (t). The winner is the player who hits the target first. Under natural assumptions on the functions f _i (t) we prove the existence and uniqueness of a Nash equilibrium point in this game, and we provide an explicit construction of this equilibrium. This construction allows us to obtain exact solutions for many specific examples. Some of them are presented.This work was partly supported by RBRF grants 03-01-00479.     

Nash equilibria in random games

We consider Nash equilibria in 2‐player random games and analyze a simple Las Vegas algorithm for finding an equilibrium. The algorithm is combinatorial and always finds a Nash equilibrium; on m × n payoff matrices, it runs in time O(m²nloglog n + n²mloglog m) with high probability. Our result follows from showing that a 2‐player random game has a Nash equilibrium with supports of size two with high probability, at least 1 − O(1/log n). Our main tool is a polytope formulation of equilibria. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

How to find Nash equilibria with extreme total latency in network congestion games?

We study the complexity of finding extreme pure Nash equilibria in symmetric network congestion games and analyse how it is influenced by the graph topology and the number of users. In our context best and worst equilibria are those with minimum or maximum total latency, respectively. We establish that both problems can be solved by a Greedy type algorithm equipped with a suitable tie breaking rule on extension-parallel graphs. On series-parallel graphs finding a worst Nash equilibrium is NP-hard for two or more users while finding a best one is solvable in polynomial time for two users and NP-hard for three or more. additionally we establish NP-hardness in the strong sense for the problem of finding a worst Nash equilibrium on a general acyclic graph.     

Stay-in-a-set games

There exists a Nash equilibrium (ε-Nash equilibrium) for every n-person stochastic game with a finite (countable) state space and finite action sets for the players if the payoff to each player i is one when the process of states remains in a given set of states G _i and is zero otherwise. Received: December 2000     

Negotiation-proof Nash equilibrium

This paper defines “negotiation-proof Nash equilibrium', a notion that applies to environments where players can negotiate openly and directly prior to the play of a noncooperative game. It recognizes the possibility that a group of self-interested players may choose, voluntarily and without binding agreement, to coordinate their choice of strategies and make joint objections; moreover, it takes the perfect foresight of rational players fully into account. The merit of the notion of negotiation-proof Nash equilibrium is twofold: (1) It offers a way to rectify the nestedness assumption and myopia embedded in the notion of coalition-proof Nash equilibrium. (2) The negotiation process is formalized by a “graph”, which serves as a natural extension to the approach that models preplay communication by an extensive game. Received: October 1998/Final version: May 2000     

On the Selection of One Feedback Nash Equilibrium in Discounted Linear-Quadratic Games

We study a selection method for a Nash feedback equilibrium of a one-dimensional linear-quadratic nonzero-sum game over an infinite horizon. By introducing a change in the time variable, one obtains an associated game over a finite horizon T > 0 and with free terminal state. This associated game admits a unique solution which converges to a particular Nash feedback equilibrium of the original problem as the horizon T goes to infinity.     

Advertising Strategies in a Differential Game with Negative Competitor’s Interference

We consider a duopolistic industry where the current sales of each firm is proportional to its goodwill stock. The evolution of the latter depends positively on own advertising effort and negatively on competitor’s advertising. A standard assumption in the literature in differential games of advertising is that the players remain active throughout the whole (infinite) duration of the game. We relax this assumption and characterize the circumstances under which a firm finds it optimal to remain or exit the industry. Among other things, it is shown that, if both players are “strong”, then the unique Nash equilibrium is the same that one would obtain in the absence of interference from competitor’s advertising. Research supported by Ministry of University and Research of Italy, University of Padua and NSERC, Canada.     

Multilateral non-cooperative bargaining in a general utility space

We consider an n-player bargaining problem where the utility possibility set is compact, convex, and stricly comprehensive. We show that a stationary subgame perfect Nash equilibrium exists, and that, if the Pareto surface is differentiable, all such equilibria converge to the Nash bargaining solution as the length of a time period between offers goes to zero. Without the differentiability assumption, convergence need not hold.     

A theorem of the maximin and applications to Bayesian zero-sum games

Consider a family of zero-sum games indexed by a parameter that determines each player’s payoff function and feasible strategies. Our first main result characterizes continuity assumptions on the payoffs and the constraint correspondence such that the equilibrium value and strategies depend continuously and upper hemicontinuously (respectively) on the parameter. This characterization uses two topologies in order to overcome a topological tension that arises when players’ strategy sets are infinite-dimensional. Our second main result is an application to Bayesian zero-sum games in which each player’s information is viewed as a parameter. We model each player’s information as a sub-σ-field, so that it determines her feasible strategies: those that are measurable with respect to the player’s information. We thereby characterize conditions under which the equilibrium value and strategies depend continuously and upper hemicontinuously (respectively) on each player’s information.     

Asymptotic Analysis of Linear Feedback Nash Equilibria in Nonzero-Sum Linear-Quadratic Differential Games

In this paper, we discuss nonzero-sum linear-quadratic differential games. For this kind of games, the Nash equilibria for different kinds of information structures were first studied by Starr and Ho. Most of the literature on the topic of nonzero-sum linear-quadratic differential games is concerned with games of fixed, finite duration; i.e., games are studied over a finite time horizon t _f. In this paper, we study the behavior of feedback Nash equilibria for t _f.In the case of memoryless perfect-state information, we study the so-called feedback Nash equilibrium. Contrary to the open-loop case, we note that the coupled Riccati equations for the feedback Nash equilibrium are inherently nonlinear. Therefore, we limit the dynamic analysis to the scalar case. For the special case that all parameters are scalar, a detailed dynamical analysis is given for the quadratic system of coupled Riccati equations. We show that the asymptotic behavior of the solutions of the Riccati equations depends strongly on the specified terminal values. Finally, we show that, although the feedback Nash equilibrium over any fixed finite horizon is generically unique, there can exist several different feedback Nash equilibria in stationary strategies for the infinite-horizon problem, even when we restrict our attention to Nash equilibria that are stable in the dynamical sense.