Variational inequality formulation for the games with random payoffs

We consider an n-player non-cooperative game with random payoffs and continuous strategy set for each player. The random payoffs of each player are defined using a finite dimensional random vector. We formulate this problem as a chance-constrained game by defining the payoff function of each player using a chance constraint. We first consider the case where the continuous strategy set of each player does not depend on the strategies of other players. If a random vector defining the payoffs of each player follows a multivariate elliptically symmetric distribution, we show that there exists a Nash equilibrium. We characterize the set of Nash equilibria using the solution set of a variational inequality (VI) problem. Next, we consider the case where the continuous strategy set of each player is defined by a shared constraint set. In this case, we show that there exists a generalized Nash equilibrium for elliptically symmetric distributed payoffs. Under certain conditions, we characterize the set of a generalized Nash equilibria using the solution set of a VI problem. As an application, the random payoff games arising from electricity market are studied under chance-constrained game framework.     

Pareto efficiency,simple game stability,and social structure in finitely repeated games

Simple game (sensu Brown and Vincent, 1987) evolutionary theory, when coupled with social structure measured as non‐random encounter of strategy “clones”, often permits equilibrium refinement leading to Pareto superior outcomes (e.g., Axelrod, 1981; Myerson et al., 1991), a foundational goal of economic game theory (Myerson, 1991: 370–375). This conclusion, derived from analyses of one‐shot and infinitely repeated games, fails for finitely repeated games. While mutant cluster invasion enhances Pareto efficiency of equilibria in the former, it can depress Pareto efficiency in the latter. Cooperative equilibria of finitely repeated games (under economic analysis) can be susceptible to cluster‐invasion by even more Pareto efficient strategies which are not themselves evolutionarily stable. Evolutionary (simple) game theory's ability to eliminate Pareto inferior Nash equilibrium strategies induces vulnerabilities foreign to economic analysis. Simple game analysis of finitely repeated games suggests that social structure, modeled as perennial invasion by mutant‐clusters, can induce cyclic invasion, saturation, and loss of cooperation.     

Internal correlation in repeated games

This paper characterizes the set of all the Nash equilibrium payoffs in two player repeated games where the signal that the players get after each stage is either trivial (does not reveal any information) or standard (the signal is the pair of actions played). It turns out that if the information is not always trivial then the set of all the Nash equilibrium payoffs coincides with the set of the correlated equilibrium payoffs. In particular, any correlated equilibrium payoff of the one shot game is also a Nash equilibrium payoff of the repeated game.For the proof we develop a scheme by which two players can generate any correlation device, using the signaling structure of the game. We present strategies with which the players internally correlate their actions without the need of an exogenous mediator.     

On Nash Equilibrium Strategy of Two-person Zero-sum Games with Trapezoidal Fuzzy Payoffs

In this paper, we investigate Nash equilibrium strategy of two-person zero-sum games with fuzzy payoffs. Based on fuzzy max order, Maeda and Cunlin constructed several models in symmetric triangular and asymmetric triangular fuzzy environment, respectively. We extended their models in trapezoidal fuzzy environment and proposed the existence of equilibrium strategies for these models. We also established the relation between Pareto Nash equilibrium strategy and parametric bi-matrix game. In addition, numerical examples are presented to find Pareto Nash equilibrium strategy and weak Pareto Nash equilibrium strategy from bi-matrix game.     

Discounted and finitely repeated minority games with public signals

We consider a repeated game where at each stage players simultaneously choose one of the two rooms. The players who choose the less crowded room are rewarded with one euro. The players in the same room do not recognize each other, and between the stages only the current majority room is publicly announced, hence the game has imperfect public monitoring. An undiscounted version of this game was considered by Renault et al. [Renault, J., Scarlatti, S., Scarsini, M., 2005. A folk theorem for minority games. Games Econom. Behav. 53 (2), 208–230], who proved a folk theorem. Here we consider a discounted version and a finitely repeated version of the game, and we strengthen our previous result by showing that the set of equilibrium payoffs Hausdorff-converges to the feasible set as either the discount factor goes to one or the number of repetition goes to infinity. We show that the set of public equilibria for this game is strictly smaller than the set of private equilibria.     

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.     

Optimal strategic reasoning with McNaughton functions

The aim of the paper is to explore strategic reasoning in strategic games of two players with an uncountably infinite space of strategies the payoff of which is given by McNaughton functions—functions on the unit interval which are piecewise linear with integer coefficients. McNaughton functions are of a special interest for approximate reasoning as they correspond to formulas of infinitely valued Lukasiewicz logic. The paper is focused on existence and structure of Nash equilibria and algorithms for their computation. Although the existence of mixed strategy equilibria follows from a general theorem (Glicksberg, 1952) [5], nothing is known about their structure neither the theorem provides any method for computing them. The central problem of the article is to characterize the class of strategic games with McNaughton payoffs which have a finitely supported Nash equilibrium. We give a sufficient condition for finite equilibria and we propose an algorithm for recovering the corresponding equilibrium strategies. Our result easily generalizes to n-player strategic games which don't need to be strictly competitive with a payoff functions represented by piecewise linear functions with real coefficients. Our conjecture is that every game with McNaughton payoff allows for finitely supported equilibrium strategies, however we leave proving/disproving of this conjecture for future investigations.     

Game theoretic approach for fertilizer application: looking for the propensity to cooperate

This paper continues the research implemented in previous work of (Schreider et al. in Environ. Model. Assess. 15(4):223–238, 2010) where a game theoretic model for optimal fertilizer application in the Hopkins River catchment was formulated, implemented and solved for its optimal strategies. In that work, the authors considered farmers from this catchment as individual players whose objective is to maximize their objective functions which are constituted from two components: economic gain associated with the application of fertilizers which contain phosphorus to the soil and environmental harms associated with this application. The environmental losses are associated with the blue-green algae blooming of the coastal waterways due to phosphorus exported from upstream areas of the catchment. In the previous paper, all agents are considered as rational players and two types of equilibria were considered: fully non-cooperative Nash equilibrium and cooperative Pareto optimum solutions. Among the plethora of Pareto optima, the solution corresponding to the equally weighted individual objective functions were selected. In this paper, the cooperative game approach involving the formation of coalitions and modeling of characteristic value function will be applied and Shapley values for the players obtained. A significant contribution of this approach is the construction of a characteristic function which incorporates both the Nash and Pareto equilibria, showing that it is superadditive. It will be shown that this approach will allow each players to obtain payoffs which strictly dominate their payoffs obtained from their Nash equilibria.     

Pure strategy Nash equilibria and the probabilistic prospects of Stackelberg players

We consider the set of all m×n bimatrix games with ordinal payoffs. We show that on the subset E of such games possessing at least one pure strategy Nash equilibrium, both players prefer the role of leader to that of follower in the corresponding Stackelberg games. This preference is in the sense of first-degree stochastic dominance by leader payoffs of follower payoffs. It follows easily that on the complement of E, the follower’s role is preferred in the same sense. Thus we see a tendency for leadership preference to obtain in the presence of multiple pure strategy Nash equilibria in the underlying game.     

A note on correlated equilibrium

The set of correlated equilibria for a bimatrix game is a closed, bounded, convex set containing the set of Nash equilibria. We show that every extreme point of a maximal Nash set is an extreme point of the above convex set. We also give an example to show that this result is not true in the payoff space, i.e. there are games where no Nash equilibrium payoff is an extreme point of the set of correlated equilibrium payoffs.     

Best response dynamics for role games

In a role game, players can condition their strategies on their player position in the base game. If the base game is strategically equivalent to a zero-sum game, the set of Nash equilibria of the role game is globally asymptotically stable under the best response dynamics. If the base game is 2 ×2, then in the cyclic case the set of role game equilibria is a continuum. We identify a single equilibrium in this continuum that attracts all best response paths outside the continuum. Received: June 2001     

Structure of extreme correlated equilibria: a zero-sum example and its implications

We exhibit the rich structure of the set of correlated equilibria by analyzing the simplest of polynomial games: the mixed extension of matching pennies. We show that while the correlated equilibrium set is convex and compact, the structure of its extreme points can be quite complicated. In finite games the ratio of extreme correlated to extreme Nash equilibria can be greater than exponential in the size of the strategy spaces. In polynomial games there can exist extreme correlated equilibria which are not finitely supported; we construct a large family of examples using techniques from ergodic theory. We show that in general the set of correlated equilibrium distributions of a polynomial game cannot be described by conditions on finitely many moments (means, covariances, etc.), in marked contrast to the set of Nash equilibria which is always expressible in terms of finitely many moments.     

Nondominated Nash points: application of biobjective mixed integer programming

We study the connection between biobjective mixed integer linear programming and normal form games with two players. We first investigate computing Nash equilibria of normal form games with two players using single-objective mixed integer linear programming. Then, we define the concept of efficient (Pareto optimal) Nash equilibria. This concept is precisely equivalent to the concept of efficient solutions in multi-objective optimization, where the solutions are Nash equilibria. We prove that the set of all points in the payoff (or objective) space of a normal form game with two players corresponding to the utilities of players in an efficient Nash equilibrium, the so-called nondominated Nash points, is finite. We demonstrate that biobjective mixed integer linear programming, where the utility of each player is an objective function, can be used to compute the set of nondominated Nash points. Finally, we illustrate how the nondominated Nash points can be used to determine the disagreement point of a bargaining problem.     

Absolutely expedient algorithms for learning Nash equilibria

This paper considers a multi-person discrete game with random payoffs. The distribution of the random payoff is unknown to the players and further none of the players know the strategies or the actual moves of other players. A class of absolutely expedient learning algorithms for the game based on a decentralised team of Learning Automata is presented. These algorithms correspond, in some sense, to rational behaviour on the part of the players. All stable stationary points of the algorithm are shown to be Nash equilibria for the game. It is also shown that under some additional constraints on the game, the team will always converge to a Nash equilibrium. Dedicated to the memory of Professor K G Ramanathan     

Nash equilibrium in compact-continuous games with a potential

If the preferences of the players in a strategic game satisfy certain continuity conditions, then the acyclicity of individual improvements implies the existence of a (pure strategy) Nash equilibrium. Moreover, starting from any strategy profile, an arbitrary neighborhood of the set of Nash equilibria can be reached after a finite number of individual improvements.     

Crowding games are sequentially solvable

A sequential-move version of a given normal-form game Γ is an extensive-form game of perfect information in which each player chooses his action after observing the actions of all players who precede him and the payoffs are determined according to the payoff functions in Γ. A normal-form game Γ is sequentially solvable if each of its sequential-move versions has a subgame-perfect equilibrium in pure strategies such that the players' actions on the equilibrium path constitute an equilibrium of Γ.  A crowding game is a normal-form game in which the players share a common set of actions and the payoff a particular player receives for choosing a particular action is a nonincreasing function of the total number of players choosing that action. It is shown that every crowding game is sequentially solvable. However, not every pure-strategy equilibrium of a crowding game can be obtained in the manner described above. A sufficient, but not necessary, condition for the existence of a sequential-move version of the game that yields a given equilibrium is that there is no other equilibrium that Pareto dominates it. Received July 1997/Final version May 1998     

Bounded rationality, strategy simplification, and equilibrium

It is frequently suggested that predictions made by game theory could be improved by considering computational restrictions when modeling agents. Under the supposition that players in a game may desire to balance maximization of payoff with minimization of strategy complexity, Rubinstein and co-authors studied forms of Nash equilibrium where strategies are maximally simplified in that no strategy can be further simplified without sacrificing payoff. Inspired by this line of work, we introduce a notion of equilibrium whereby strategies are also maximally simplified, but with respect to a simplification procedure that is more careful in that a player will not simplify if the simplification incents other players to deviate. We study such equilibria in two-player machine games in which players choose finite automata that succinctly represent strategies for repeated games; in this context, we present techniques for establishing that an outcome is at equilibrium and present results on the structure of equilibria.     

On the equilibrium payoffs set of two player repeated games with imperfect monitoring

We show that any payoff, sustainable by a joint strategy of finitely repeated games, from which no player can deviate and gain by a non-detectable deviation, is a uniform equilibrium of the infinite repeated game. This provides a characterization of the uniform equilibrium payoffs in terms of the finitely repeated games.     

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.