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.     

Zero-sum constrained stochastic games with independent state processes

We consider a zero-sum stochastic game with side constraints for both players with a special structure. There are two independent controlled Markov chains, one for each player. The transition probabilities of the chain associated with a player as well as the related side constraints depend only on the actions of the corresponding player; the side constraints also depend on the player’s controlled chain. The global cost that player 1 wishes to minimize and that player 2 wishes to maximize, depend however on the actions and Markov chains of both players. We obtain a linear programming formulations that allows to compute the value and saddle point policies for this problem. We illustrate the theoretical results through a zero-sum stochastic game in wireless networks in which each player has power constraints     

Parametrized variational inequality approaches to generalized Nash equilibrium problems with shared constraints

We consider the generalized Nash equilibrium problem (GNEP), in which each player’s strategy set may depend on the rivals’ strategies through shared constraints. A practical approach to solving this problem that has received increasing attention lately entails solving a related variational inequality (VI). From the viewpoint of game theory, it is important to find as many GNEs as possible, if not all of them. We propose two types of parametrized VIs related to the GNEP, one price-directed and the other resource-directed. We show that these parametrized VIs inherit the monotonicity properties of the original VI and, under mild constraint qualifications, their solutions yield all GNEs. We propose strategies to sample in the parameter spaces and show, through numerical experiments on benchmark examples, that the GNEs found by the parametrized VI approaches are widely distributed over the GNE set.     

An operator solution of stochastic games

A class of zero-sum, two-person stochastic games is shown to have a value which can be calculated by transfinite iteration of an operator. The games considered have a countable state space, finite action spaces for each player, and a payoff sufficiently general to include classical stochastic games as well as Blackwell’s infiniteG _δ games of imperfect information. Research supported by National Science Foundation Grants DMS-8801085 and DMS-8911548.     

Pure strategy equilibria in symmetric two-player zero-sum games

We observe that a symmetric two-player zero-sum game has a pure strategy equilibrium if and only if it is not a generalized rock-paper-scissors matrix. Moreover, we show that every finite symmetric quasiconcave two-player zero-sum game has a pure equilibrium. Further sufficient conditions for existence are provided. Our findings extend to general two-player zero-sum games using the symmetrization of zero-sum games due to von Neumann. We point out that the class of symmetric two-player zero-sum games coincides with the class of relative payoff games associated with symmetric two-player games. This allows us to derive results on the existence of finite population evolutionary stable strategies.     

Restricted generalized Nash equilibria and controlled penalty algorithm

The generalized Nash equilibrium problem (GNEP) is a generalization of the standard Nash equilibrium problem, in which each player’s strategy set may depend on the rival players’ strategies. The GNEP has recently drawn much attention because of its capability of modeling a number of interesting conflict situations in, for example, an electricity market and an international pollution control. However, a GNEP usually has multiple or even infinitely many solutions, and it is not a trivial matter to choose a meaningful solution from those equilibria. The purpose of this paper is two-fold. First we present an incremental penalty method for the broad class of GNEPs and show that it can find a GNE under suitable conditions. Next, we formally define the restricted GNE for the GNEPs with shared constraints and propose a controlled penalty method, which includes the incremental penalty method as a subprocedure, to compute a restricted GNE. Numerical examples are provided to illustrate the proposed approach.     

Advertising coordination games of a manufacturer and a retailer while introducing a new product

Two kinds of vertical cooperative advertising program are considered in a distribution channel constituted by a manufacturer and a retailer, where the manufacturer pays part of the retailer’s advertising costs. In the first participation scheme, the manufacturer chooses his/her advertising participation rate in the retailer’s advertising effort and then each player determines the advertising effort that maximizes his/her profit. In the second scheme, the retailer chooses the manufacturer’s participation rate and then the manufacturer determines the advertising efforts of both players with the objective of maximizing the manufacturer’s profit. Each participation scheme corresponds to a special Stackelberg game: the manufacturer is the leader of the first, while the retailer is the leader of the second. The Stackelberg equilibrium advertising efforts and participation rate in both games are provided. Then the equilibrium strategies of the two players in the analyzed scenarios are compared with the Nash equilibrium in the competitive framework. Finally, the conditions which suggest a special kind of agreement to a player are analyzed. This work was supported by the Italian Ministry of University and Research and the University of Padua.     

Perfect information two-person zero-sum markov games with imprecise transition probabilities

Based on an extension of the controlled Markov set-chain model by Kurano et al. (in J Appl Prob 35:293–302, 1998) into competitive two-player game setting, we provide a model of perfect information two-person zero-sum Markov games with imprecise transition probabilities. We define an equilibrium value for the games formulated with the model in terms of a partial order and then establish the existence of an equilibrium policy pair that achieves the equilibrium value. We further analyze finite-approximation error bounds obtained from a value iteration-type algorithm and discuss some applications of the model.     

连续区间策略下二人零和对策问题研究

考虑连续区间策略下的二人零和对策问题,研究其均衡策略的存在性。首先分析了完全信息下的二人零和对策问题,证明了该问题均衡策略的存在性并给出求解方法。然后进一步研究了收益函数不确定的不完全信息二人零和对策问题,在各局中人都认为对方是风险厌恶型的假设下,分析该类对策纯策略均衡的存在性,并通过研究纯策略均衡存在的充要条件给出判断并寻找纯策略均衡解的方法。最后给出一个数值算例,验证本文所提出方法的可行性。     

Pricing and Advertising of Private and National Brands in a Dynamic Marketing Channel

We consider a marketing channel where a retailer sells, along the manufacturer’s brand, its own store brand. We assume that each player invests in advertising in order to build the brand’s goodwill. One distinctive feature of this paper is the introduction of the negative effect of own advertising on other player’s goodwill stock evolution. We characterize feedback-Nash pricing and advertising strategies and assess the impact of the store brand and national brand’s goodwill stocks on these strategies in different settings. The main findings suggest first that investing in building up some equity for each brand reduces the price competition between them and propels the market power for both. Second, the retailer will pass to consumer an increase in its purchasing cost of the national brand in all situations as no coordination is taken into account to counter the double marginalization problem. Finally, the higher the brand equity of the store brand, the more the retailer invests in advertising.     

Distributed consensus in noncooperative inventory games

This paper deals with repeated nonsymmetric congestion games in which the players cannot observe their payoffs at each stage. Examples of applications come from sharing facilities by multiple users. We show that these games present a unique Pareto optimal Nash equilibrium that dominates all other Nash equilibria and consequently it is also the social optimum among all equilibria, as it minimizes the sum of all the players’ costs. We assume that the players adopt a best response strategy. At each stage, they construct their belief concerning others probable behavior, and then, simultaneously make a decision by optimizing their payoff based on their beliefs. Within this context, we provide a consensus protocol that allows the convergence of the players’ strategies to the Pareto optimal Nash equilibrium. The protocol allows each player to construct its belief by exchanging only some aggregate but sufficient information with a restricted number of neighbor players. Such a networked information structure has the advantages of being scalable to systems with a large number of players and of reducing each player’s data exposure to the competitors.     

Continuity of the value and optimal strategies when common priors change

We show that the value of a zero-sum Bayesian game is a Lipschitz continuous function of the players?? common prior belief with respect to the total variation metric on beliefs. This is unlike the case of general Bayesian games where lower semi-continuity of Bayesian equilibrium (BE) payoffs rests on the ??almost uniform?? convergence of conditional beliefs. We also show upper semi-continuity (USC) and approximate lower semi-continuity (ALSC) of the optimal strategy correspondence, and discuss ALSC of the BE correspondence in the context of zero-sum games. In particular, the interim BE correspondence is shown to be ALSC for some classes of information structures with highly non-uniform convergence of beliefs, that would not give rise to ALSC of BE in non-zero-sum games.     

Prediction with Expert Advice: A PDE Perspective

This work addresses a classic problem of online prediction with expert advice. We assume an adversarial opponent, and we consider both the finite horizon and random stopping versions of this zero-sum, two-person game. Focusing on an appropriate continuum limit and using methods from optimal control, we characterize the value of the game as the viscosity solution of a certain nonlinear partial differential equation. The analysis also reveals the predictor’s and the opponent’s minimax optimal strategies. Our work provides, in particular, a continuum perspective on recent work of Gravin et al. (in: Proceedings of the twenty-seventh annual ACM-SIAM symposium on discrete algorithms, SODA ’16, (Philadelphia, PA, USA), Society for Industrial and Applied Mathematics, 2016). Our techniques are similar to those of Kohn and Serfaty (Commun Pure Appl Math 63(10):1298–1350, 2010), where scaling limits of some two-person games led to elliptic or parabolic PDEs.     

Sensitive equilibria for ergodic stochastic games with countable state spaces

We consider stochastic games with countable state spaces and unbounded immediate payoff functions. Our assumptions on the transition structure of the game are based on a recent work by Meyn and Tweedie [19] on computable bounds for geometric convergence rates of Markov chains. The main results in this paper concern the existence of sensitive optimal strategies in some classes of zero-sum stochastic games. By sensitive optimality we mean overtaking or 1-optimality. We also provide a new Nash equilibrium theorem for a class of ergodic nonzero-sum stochastic games with denumerable state spaces.     

Repeated bargaining with reference-dependent preferences

We consider a two-player bargaining model in which one or both players have reference-dependent preferences, but are otherwise perfectly rational. Our behavioural assumption is that players with reference-dependent preferences prefer impasse to consuming strictly less than their current reference points. Reference points adjust each period according to some exogenously specified law of motion. When reference points do not adjust following disagreement, we show that disagreement does not arise in equilibrium, but they do influence the division of the pie. In contrast, when reference points adjust downwards following disagreement, disagreements arise and players may try to manipulate the reference point of their opponent. When reference points adjust downwards following a rejection, for a particular Markov equilibrium, we show that the set of feasible allocations can be divided into agreement and disagreement regions. In particular, there are thresholds such that if one (or more) player’s reference point is above the threshold, disagreement necessarily arises.     

Stationary,completely mixed and symmetric optimal and equilibrium strategies in stochastic games

In this paper, we address various types of two-person stochastic games—both zero-sum and nonzero-sum, discounted and undiscounted. In particular, we address different aspects of stochastic games, namely: (1) When is a two-person stochastic game completely mixed? (2) Can we identify classes of undiscounted zero-sum stochastic games that have stationary optimal strategies? (3) When does a two-person stochastic game possess symmetric optimal/equilibrium strategies? Firstly, we provide some necessary and some sufficient conditions under which certain classes of discounted and undiscounted stochastic games are completely mixed. In particular, we show that, if a discounted zero-sum switching control stochastic game with symmetric payoff matrices has a completely mixed stationary optimal strategy, then the stochastic game is completely mixed if and only if the matrix games restricted to states are all completely mixed. Secondly, we identify certain classes of undiscounted zero-sum stochastic games that have stationary optima under specific conditions for individual payoff matrices and transition probabilities. Thirdly, we provide sufficient conditions for discounted as well as certain classes of undiscounted stochastic games to have symmetric optimal/equilibrium strategies—namely, transitions are symmetric and the payoff matrices of one player are the transpose of those of the other. We also provide a sufficient condition for the stochastic game to have a symmetric pure strategy equilibrium. We also provide examples to show the sharpness of our results.     

A note on Bayesian Nash equilibria in imperfectly discriminating contests

The literature on imperfectly discriminating contests has almost exclusively focused on complete information. We study such contests assuming players have private information. We identify a general class of imperfectly discriminating contests for which findings by  Athey (2001) imply the existence of a Bayesian Nash equilibrium in monotone pure strategies. The main assumptions are that a player’s valuation of winning is increasing in the signal he observes and that a player’s probability of winning is continuous in the efforts of all players as well as increasing in his own effort.     

On purification of equilibrium in Bayesian games and expost Nash equilibrium

Treating games of incomplete information, we demonstrate that the existence of an ex post stable strategy vector implies the existence of an approximate Bayesian equilibrium in pure strategies that is also expost stable. Through examples we demonstrate the ‘bounds obtained on the approximation’ are tight. The main results of this paper first appeared in University of Warwick Department of Economics Discussion Paper #710. 2004.     

Some projection-like methods for the generalized Nash equilibria

A generalized Nash game is an m-person noncooperative game in which each player’s strategy depends on the rivals’ strategies. Based on a quasi-variational inequality formulation for the generalized Nash game, we present two projection-like methods for solving the generalized Nash equilibria in this paper. It is shown that under certain assumptions, these methods are globally convergent. Preliminary computational experience is also reported.     

Strategically zero-sum games: The class of games whose completely mixed equilibria cannot be improved upon

In this paper we propose a new class of games, the “strategically zero-sum games,” which are characterized by a special payoff structure. We show that for a large body of correlation schemes which includes the correlated strategies “à la Aumann”, strategically zero-sum games are exactly these games for which no completely mixed Nash equilibrium can be improved upon.