A generalization of the Nash equilibrium theorem on bimatrix games

In this article, we consider a two-person game in which the first player picks a row representative matrixM from a nonempty set $A$ ofm ×n matrices and a probability distributionx on {1,2,...,m} while the second player picks a column representative matrixN from a nonempty set ? ofm ×n matrices and a probability distribution y on 1,2,...,n. This leads to the respective costs ofx ^t My andx ^t Ny for these players. We establish the existence of an ?-equilibrium for this game under the assumption that $A$ and ? are bounded. When the sets $A$ and ? are compact in ?^mxn, the result yields an equilibrium state at which stage no player can decrease his cost by unilaterally changing his row/column selection and probability distribution. The result, when further specialized to singleton sets, reduces to the famous theorem of Nash on bimatrix games.     

On the set of proper equilibria of a bimatrix game

In this paper it is proved that the set of proper equilibria of a bimatrix game is the finite union of polytopes. To that purpose we split up the strategy space of each player into a finite number of equivalence classes and consider for a given >0 the set of all -proper pairs within the cartesian product of two equivalence classes. If this set is non-empty, its closure is a polytope. By considering this polytope as goes to zero, we obtain a (Myerson) set of proper equilibria. A Myerson set appears to be a polytope.     

Nash equilibria in the two-player kidney exchange game

Kidney exchange programs have been set in several countries within national, regional or hospital frameworks, to increase the possibility of kidney patients being transplanted. For the case of hospital programs, it has been claimed that hospitals would benefit if they collaborated with each other, sharing their internal pools and allowing transplants involving patients of different hospitals. This claim led to the study of multi-hospital exchange markets. We propose a novel direction in this setting by modeling the exchange market as an integer programming game. The analysis of the strategic behavior of the entities participating in the kidney exchange game allowed us to prove that the most rational game outcome maximizes the social welfare and that it can be computed in polynomial time.     

Topological degree and number of Nash equilibrium points of bimatrix games

In this paper, using the topological degree, we give a new proof of a well-known result: the number of Nash equilibrium points of a nondegenerate bimatrix game is odd. The calculation of the topological degree allows the localization of the whole set of non-degenerate equilibrium points.     

Finding all pure strategy Nash equilibria in a planar location game

In this paper, we deal with a planar location-price game where firms first select their locations and then set delivered prices in order to maximize their profits. If firms set the equilibrium prices in the second stage, the game is reduced to a location game for which pure strategy Nash equilibria are studied assuming that the marginal delivered cost is proportional to the distance between the customer and the facility from which it is served. We present characterizations of local and global Nash equilibria. Then an algorithm is shown in order to find all possible Nash equilibrium pairs of locations. The minimization of the social cost leads to a Nash equilibrium. An example shows that there may exist multiple Nash equilibria which are not minimizers of the social cost.     

Determining all Nash equilibria in a (bi-linear) inspection game

This paper addresses a “game” between an inspection agency and multiple inspectees that are subject to random inspections by that agency. We provide explicit (easily computable) expressions for all possible Nash equilibria and verify that none is left out. In particular, our results characterize situations when there exists a unique Nash equilibrium. We also explore special features of the Nash equilibria and the solution of the problem the inspection agency faces in a non-strategic environment.     

From a KKM theorem to Nash equilibria in L-spaces

Using a KKM-type theorem for L-spaces and L^∗-KKM multifunctions, we obtain some results on the existence of fixed points and Nash equilibria in compact L-spaces.     

Pure-strategy Nash equilibria in an advertising game with interference

Two manufacturers produce substitutable goods for a homogeneous market. The advertising efforts of the two manufacturers determine the demand for the goods and interfere negatively with each other. The demand of each good is a piecewise linear function of the product goodwill, and the latter is a linear function of advertising efforts. In a game with two competing profit-maximizing manufacturers who have access to a set of several advertising media, the pure-strategy Nash equilibria are characterized and their existence is shown.     

A polynomial-time method to compute all Nash equilibria solutions of a general two-person inspection game

We consider a two-person nonzero-sum simultaneous inspection game that takes place at multiple sites. The inspector has a limited inspection resource. She needs to decide which sites to inspect, and with how much effort, while adhering also to local restrictions on the permitted inspections levels at the sites. The inspectee has several employees who work on his behalf. He needs to decide how to distribute them across the sites, and how they should act there. Computation of Nash equilibria is challenging for this sort of games. Still, we develop a linear-time algorithm that determines all Nash equilibria solutions of the game, and provide explicit (easily computable) expressions for all possible Nash equilibria. We then derive some managerial insights by applying the algorithm to several examples, and examining the Nash equilibria, including an outcome that an increase in the inspection resource may induce the inspectee to cooperate more at sites without increasing the inspection levels at them.     

A distributed replicator system corresponding to a bimatrix game

Reaction–diffusion type replicator systems are investigated for the case of a bimatrix. An approach proposed earlier for formalizing and analyzing distributed replicator systems with one matrix is applied to asymmetric conflicts. A game theory interpretation of the problem is described and the relation between dynamic properties of systems and their game characteristics is determined. The stability of a spatially homogeneous solution for a distributed system is considered and a theorem on maintaining stability is proved. The results are illustrated with two-dimensional examples in the case of distribution.     

一类博弈排序问题的纳什均衡存在性证明

研究机器带有激活费用的博弈排序问题. 机器集由两类组成: 一类是速度为1、 激活费用为B的k_1台同型机; 另一类是速度为a(>1)、激活费用为aB的k_2台同型机, 其中k_1与k_2是任意正整数. 工件作为``局中人", 其目的是极小化自身的费用, 工件的费用是由其所在机器的负载和其所承担的激活费用组成, 其中工件承担的激活费用与工件的加工时间成正比. 针对不同的情况, 设计不同的算法, 并证明各算法得到的排序都是纳什均衡.     

Limiting distributions of the number of pure strategy Nash equilibria in n-person games

We study the number of pure strategy Nash equilibria in a “random” n-person non-cooperative game in which all players have a countable number of strategies. We consider both the cases where all players have strictly and weakly ordinal preferences over their outcomes. For both cases, we show that the distribution of the number of pure strategy Nash equilibria approaches the Poisson distribution with mean 1 as the numbers of strategies of two or more players go to infinity. We also find, for each case, the distribution of the number of pure strategy Nash equilibria when the number of strategies of one player goes to infinity, while those of the other players remain finite.     

A finite step algorithm via a bimatrix game to a single controller non-zero sum stochastic game

Given a non-zero sum discounted stochastic game with finitely many states and actions one can form a bimatrix game whose pure strategies are the pure stationary strategies of the players and whose penalty payoffs consist of the total discounted costs over all states at any pure stationary pair. It is shown that any Nash equilibrium point of this bimatrix game can be used to find a Nash equilibrium point of the stochastic game whenever the law of motion is controlled by one player. The theorem is extended to undiscounted stochastic games with irreducible transitions when the law of motion is controlled by one player. Examples are worked out to illustrate the algorithm proposed.The work of this author was supported in part by the NSF grants DMS-9024408 and DMS 8802260.     

Nash equilibria on topological semilattices

A function ${u : X \to \mathbb{R}}$ defined on a partially ordered set is quasi-Leontief if, for all ${x \in X}$ , the upper level set ${\{x\prime \in X : u(x\prime) \geq u(x)\}}$ has a smallest element; such an element is an efficient point of u. An abstract game ${u_{i} : \prod^{n}_{j=1} X_j \to \mathbb{R}, i \in \{1, \ldots , n\}}$ , is a quasi-Leontief game if, for all i and all ${(x_{j})_{j \neq i} \in \prod_{j \neq i} X_{j}, u_{i}((x_{j})_{j \neq i};-) : X_{i} \to \mathbb{R}}$ is quasi-Leontief; a Nash equilibrium x* of an abstract game ${u_{i} :\prod^{n}_{j=1} X_{j} \to \mathbb{R}}$ is efficient if, for all ${i, x^{*}_{i}}$ is an efficient point of the partial function ${u_{i}((x^{*}_{j})_{j \neq i};-) : X_{i} \to \mathbb{R}}$ . We establish the existence of efficient Nash equilibria when the strategy spaces X _i are topological semilattices which are Peano continua and Lawson semilattices.     

Efficient Nash equilibria on semilattices

This contribution introduces the so-called quasi-Leontief functions. In the framework and the language of tropical algebras, our quasi-Leontief functions are the additive functions defined on a semimodule with values in the semiring of scalars. This class of functions encompasses as a special case the usual Leontief utility function. We establish the existence of efficient Nash equilibria when the strategy spaces are compact and pathconnected topological semilattices.     

Approximations of Nash equilibria

Inspired by previous works on approximations of optimization problems and recent papers on the approximation of Walrasian and Nash equilibria and on stochastic variational inequalities, the present paper investigates the approximation of Nash equilibria and clarifies the conditions required for the convergence of the approximate equilibria via a direct approach, a variational approach, and an optimization approach. Besides directly addressing the issue of convergence of Nash equilibria via approximation, our investigation leads to a deeper understanding of various notions of functional convergence and their interconnections; more importantly, the investigation yields improved conditions for convergence of the approximate Nash equilibria via the variational approach. An illustrative application of our results to the approximation of a Nash equilibrium in a competitive capacity expansion model under uncertainty is presented.     

Nash refinement of equilibria

A method for choosing equilibria in strategic form games is proposed and axiomatically characterized. The method as well as the axioms are inspired by the Nash bargaining theory. The method can be applied to existing refinements of Nash equilibrium (e.g., perfect equilibrium) and also to other equilibrium concepts, like correlated equilibrium.The authors thank the reviewers for their comments, which led to an improvement of the paper.     

On the geometry of Nash equilibria and correlated equilibria

It is well known that the set of correlated equilibrium distributions of an n-player noncooperative game is a convex polytope that includes all the Nash equilibrium distributions. We demonstrate an elementary yet surprising result: the Nash equilibria all lie on the boundary of the polytope.We are grateful to Francoise Forges, Dan Arce, the editors, and several anonymous referees for helpful comments. This research was supported by the National Science Foundation under grant 98–09225 and by the Fuqua School of Business.The use of correlated mixed strategies in 2-player games was discussed by Raiffa (1951), who noted: it is a useful concept since it serves to convexify certain regions [of expected payoffs] in the Euclidean plane. (p. 8)Received: April 2002 / Revised: November 2003     

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.