Pure strategy Nash equilibrium points and the Lefschetz fixed point theorem

A pure strategy Nash equilibrium point existence theorem is established for a class ofn-person games with possibly nonacyclic (e.g. disconnected) strategy sets. The principal tool used in the proof is a Lefschetz fixed point theorem for multivalued maps, due to Eilenberg and Montgomery, which extends their better known. Eilenberg-Montgomery fixed point theorem (EMT) [Eilenberg/Montgomery, Theorem 1, p. 215] to nonacyclic spaces. Special cases of the existence theorem are also discussed.     

Uniqueness of equilibrium points in bimatrix games

Bimatrix games are constructed having a given pair (x, y) as the unique equilibrium point within the class of all mixed strategy pairs whose nonzero components are the same as (resp., among) those of (x, y). In each case, necessary and sufficient conditions on (x, y) for the existence of such a game are obtained. All games having the first property are constructed. The work extends and complements recent (separate) works ofMillham [1972],Raghavan [1970] and the author. The methods and results are valid in the context of any ordered field.     

Stability of pure strategy sampling equilibria

The idea of procedurally rational players was introduced in [4]. Among other procedures, the sampling procedure was proposed. The resulting equilibrium was called a sampling equilibrium. Evolutionary approach to the notion of a sampling equilibrium was developed in [7], where some instability results were proved. Using the concept of first-order stochastic dominance, we introduce the notion of a superior strategy and prove a stability result. The paper was supported by the Polish Government Grant No. KBN 5P03A 025 20. Author wishes to thank an anonymous referee for useful comments and suggestions.     

From winning strategy to Nash equilibrium

Game theory is usually considered applied mathematics, but a few game‐theoretic results, such as Borel determinacy, were developed by mathematicians for mathematics in a broad sense. These results usually state determinacy, i.e., the existence of a winning strategy in games that involve two players and two outcomes saying who wins. In a multi‐outcome setting, the notion of winning strategy is irrelevant yet usually replaced faithfully with the notion of (pure) Nash equilibrium. This article shows that every determinacy result over an arbitrary game structure, e.g., a tree, is transferable into existence of multi‐outcome (pure) Nash equilibrium over the same game structure. The equilibrium‐transfer theorem requires cardinal or order‐theoretic conditions on the strategy sets and the preferences, respectively, whereas counter‐examples show that every requirement is relevant, albeit possibly improvable. When the outcomes are finitely many, the proof provides an algorithm computing a Nash equilibrium without significant complexity loss compared to the two‐outcome case. As examples of application, this article generalises Borel determinacy, positional determinacy of parity games, and finite‐memory determinacy of Muller games.     

Refinements of the Nash equilibrium concept

Selten's concept of perfect equilibrium for normal form games is reviewed, and a new concept of proper equilibrium is defined. It is shown that the proper equilibria form a nonempty subset of the perfect equilibria, which in turn form a subset of the Nash equilibria. An example is given to show that these inclusions may be strict.     

Single-payoff farsighted stable sets in strategic games with dominant punishment strategies

We investigate farsighted stable sets in a class of strategic games with dominant punishment strategies. In this class of games, each player has a strategy that uniformly minimizes the other players’ payoffs for any given strategies chosen by these other players. We particularly investigate a special class of farsighted stable sets, each of which consists of strategy profiles yielding a single payoff vector. We call such a farsighted stable set as a single-payoff farsighted stable set. We propose a concept called an inclusive set that completely characterizes single-payoff farsighted stable sets in strategic games with dominant punishment strategies. We also show that the set of payoff vectors yielded by single-payoff farsighted stable sets is closely related to the strict \(\alpha \)-core in a strategic game. Furthermore, we apply the results to strategic games where each player has two strategies and strategic games associated with some market models.     

On stability of perfect equilibrium points

We consider stability of Selten's perfect equilibrium point against slight imperfections of rationality of players. As its stability is not sufficient, we strengthen the perfectness concept and define astrictly perfect equilibrium point. We provide sufficient conditions for this equilibrium point.     

Stabilization of solutions of the Cauchy problem for the reaction-nonlinear diffusion equation to a dominant equilibrium

We consider the Cauchy problem for the reaction-nonlinear diffusion equation in a space of arbitrary dimension. On the basis of the original data of the equation, we compute the potential function, whose maximum corresponds to a dominant equilibrium distribution. For the solutions of the problem with initial distributions in a rather broad class, we prove the convergence to the dominant distribution on bounded subsets.     

Multimodel design of a Nash strategy

For interconnected systems with slow and fast modes, we analyze a multimodel design of a Nash equilibrium strategy. Decision makers use different models of the same system to obtain a composite strategy that approximates the exact Nash strategy. It is discussed in what sense this approximation holds.This work was supported by the Department of Energy, Electrical Energy Systems Division, under Contract No. EX-76-C-01-2088. The author wishes to thank Professor P. V. Kokotovic for his helpful suggestions in the course of this work.     

A concept of equilibrium for a game under uncertainty

In this paper, we introduce a new concept of equilibrium for an n-person game involving undetermined parameters when the players know the domain where these parameters can vary but completely ignore their behaviour. We call it ZS-equilibrium. Then we give some of its properties and sufficient conditions for its existence.     

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.     

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.     

Mixed equilibrium problems with Z*-bifunctions and least element problems in Banach lattices

The purpose of this paper is to study the relations among a mixed equilibrium problem, a least element problem and a minimization problem in Banach lattices. We propose the concept of Z*-bifunctions as well as the concept of a feasible set for the mixed equilibrium problem. We prove that the feasible set of the mixed equilibrium problem is a sublattice provided that the associated bifunction is a strictly α-monotone Z*-bifunction. We establish the equivalence of the mixed equilibrium problem, the least element problem and the minimization problem under strict α-monotonicity and Z*-bifunction conditions.     

Essential collections for equilibrium concepts

The aim of this study is to identify and characterize the parts of an extensive form game that are ??relevant?? to determining whether the outcome of a certain strategy profile is an equilibrium outcome. We formally define what we mean by ??relevant?? and refer to the associated collection of information sets as essential. We apply this idea to a number of classic equilibrium concepts and discuss some implications of our approach.     

Particle swarm with equilibrium strategy of selection for multi-objective optimization

A new ranking scheme based on equilibrium strategy of selection is proposed for multi-objective particle swarm optimization (MOPSO), and the preference ordering is used to identify the “best compromise” in the ranking stage. This scheme increases the selective pressure, especially when the number of objectives is very large. The proposed algorithm has been compared with other multi-objective evolutionary algorithms (MOEAs). The experimental results indicate that our algorithm produces better convergence performance.     

Discriminatory power and pure strategy Nash equilibrium in the lottery Blotto game

This paper highlights the role of discriminatory power in showing the existence of pure strategy Nash equilibrium in a two-player lottery Blotto game. Precisely, when the discriminatory power of the contest success function in every battle is less than or equal to one, a pure strategy Nash equilibrium always exists for any prizes and budgets. However, we construct examples in which pure strategy Nash equilibrium fails to exist as long as the discriminatory power of only one battle exceeds one.     

The equilibrium generalized assignment problem and genetic algorithm

The well-known generalized assignment problem (GAP) is to minimize the costs of assigning n jobs to m capacity constrained agents (or machines) such that each job is assigned to exactly one agent. This problem is known to be NP-hard and it is hard from a computational point of view as well. In this paper, follows from practical point of view in real systems, the GAP is extended to the equilibrium generalized assignment problem (EGAP) and the equilibrium constrained generalized assignment problem (ECGAP). A heuristic equilibrium strategy based genetic algorithm (GA) is designed for solving the proposed EGAP. Finally, to verify the computational efficiency of the designed GA, some numerical experiments are performed on some known benchmarks. The test results show that the designed GA is very valid for solving EGAP.     

Randomized strategy equilibrium in the action commitment game with costs of leading

We investigate a two-player action commitment game where one simultaneous-move and two sequential-move pure strategy equilibria exist when the cost of leading is zero, while the simultaneous-move outcome is not an equilibrium when the leading cost is small positive. We show that this discontinuity disappears if we consider randomized strategy equilibria. We investigate a price competition model and show that randomized strategy equilibria exist and any of them converges to the Bertrand equilibrium when the leading cost converges to zero.     

An equilibrium efficiency frontier data envelopment analysis approach for evaluating decision-making units with fixed-sum outputs

Based on the minimal reduction strategy, Yang et al. (2011) developed a fixed-sum output data envelopment analysis (FSODEA) approach to evaluate the performance of decision-making units (DMUs) with fixed-sum outputs. However, in terms of such a strategy, all DMUs compete over fixed-sum outputs with “no memory” that will result in differing efficient frontiers’ evaluations. To address the problem, in this study, we propose an equilibrium efficiency frontier data envelopment analysis (EEFDEA) approach, by which all DMUs with fixed-sum outputs can be evaluated based on a common platform (or equilibrium efficient frontier). The proposed approach can be divided into two stages. Stage 1 constructs a common evaluation platform via two strategies: an extended minimal adjustment strategy and an equilibrium competition strategy. The former ensures that original efficient DMUs are still efficient, guaranteeing the existence of a common evaluation platform. The latter makes all DMUs achieve a common equilibrium efficient frontier. Then, based on the common equilibrium efficient frontier, Stage 2 evaluates all DMUs with their original inputs and outputs. Finally, we illustrate the proposed approach by using two numerical examples.     

Average shadow price and equilibrium price: A case study of tradable pollution permit markets

Shadow prices indicate implicit values of limited resources at the margin and provide important information in decision making for resource management. In continuous economic models, shadow prices associated with demand-supply balance constraints represent consumers’ willingness to pay and producers’ marginal cost, hence they correspond to market equilibrium prices. As well known, however, marginal analysis fails in the case of discrete optimization, such as mixed integer programming. An alternative concept has been introduced in the literature to measure the value of an extra unit of a limited resource in such cases. This concept is based on average rather than marginal values, thus called the average shadow price, and interpreted in the same way as conventional shadow prices. Whether average shadow prices in a discrete economic model can serve as market equilibrium prices has not been addressed in the related literature. The present paper addresses this issue in an empirical setting. Using a tradable pollution permit market as an example, where firms’ YES/NO type technology adoption decisions are represented by binary variables, we show that the average shadow price of tradable permits can be interpreted as the equilibrium price only when certain conditions related to the cost structure and emission levels hold. On the other hand, we show that an iterative procedure based on individual firms’ cost minimizing behavior presents a better approach for finding a price that can eliminate or reduce the gap between demand and supply of permits in the market.