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.     

Some results on cooperative interval games

Uncertainty is a daily presence in the real world. It affects our decision-making and may have influence on cooperation. On many occasions, uncertainty is so severe that we can only predict some upper and lower bounds for the outcome of our actions, i.e. payoffs lie in some intervals. A suitable game theoretic model to support decision-making in collaborative situations with interval data is that of cooperative interval games. Solution concepts that associate with each cooperative interval game sets of interval allocations with appealing properties provide a natural way to capture the uncertainty of coalition values into the players’ payoffs. In this paper, the relations between some set-valued solution concepts using interval payoffs, namely the interval core, the interval dominance core, the square interval dominance core and the interval stable sets for cooperative interval games, are studied. It is shown that the interval core is the unique stable set on the class of convex interval games.     

Independent mistakes in large games

Economic models usually assume that agents play precise best responses to others' actions. It is sometimes argued that this is a good approximation when there are many agents in the game, because if their mistakes are independent, aggregate uncertainty is small. We study a class of games in which players' payoffs depend solely on their individual actions and on the aggregate of all players' actions. We investigate whether their equilibria are affected by mistakes when the number of players becomes large. Indeed, in generic games with continuous payoff functions, independent mistakes wash out in the limit. This may not be the case if payoffs are discontinuous. As a counter-example we present the n players Nash bargaining game, as well as a large class of “free-rider games.” Received: November 1997/Final version: December 1999     

Monotonic games are spanning network games

Spanning network games, which are a generalization of minimum cost spanning tree games, were introduced by Granot and Maschler (1991), who showed that these games are always monotonic. In this paper a subclass of spanning network games is introduced, namely simplex games, and it is shown that every monotonic game is a simplex game. Hence, the class of spanning network games coincides with the class of monotonic games.     

A system-theoretic model for cooperation, interaction and allocation

A system-theoretic approach to cooperation, interaction and allocation is presented that simplifies, unifies and extends the results on classical cooperative games and their generalizations. In particular, a general Weber theory of linear values is obtained and a new theory for local cooperation and general interaction indices is established. The model is dynamic and based on the notion of states of cooperation that change under actions of agents. Careful distinction between “local” states of cooperation and general “system” states leads to a notion of entropy for arbitrary non-negative and efficient allocations and thus to a new information-theoretic criterion for fairness of allocation mechanisms. Shapley allocations, for instance, are exhibited as arising from random walks with maximal entropy. For a large class of cooperation systems, a characterization of game symmetries in terms of λ-values is given. A concept for cores and Weber sets is proposed and it is shown that a Weber set of a game with selection structure always contains the core.     

Monge extensions of cooperation and communication structures

Cooperation structures without any a priori assumptions on the combinatorial structure of feasible coalitions are studied and a general theory for marginal values, cores and convexity is established. The theory is based on the notion of a Monge extension of a general characteristic function, which is equivalent to the Lovász extension in the special situation of a classical cooperative game. It is shown that convexity of a cooperation structure is tantamount to the equality of the associated core and Weber set. Extending Myerson’s graph model for game theoretic communication, general communication structures are introduced and it is shown that a notion of supermodularity exists for this class that characterizes convexity and properly extends Shapley’s convexity model for classical cooperative games.     

Deposit games with reinvestment

In a deposit game coalitions are formed by players combining their capital. The proceeds of their investments then have to be divided among those players. The current model extends earlier work on capital deposits by allowing reinvestment of returns. Two specific subclasses of deposit games are introduced. These subclasses provide insight in two extreme cases. It is seen that each term dependent deposit game possesses a core element. Capital dependent deposit games are also shown to have a core element and even a population monotonic allocation scheme if the revenue function exhibits increasing returns to scale. Furthermore, it is shown that all superadditive games are deposit games if one allows for debt.     

不确定条件下n人非合作博弈均衡点集的通有稳定性

基于经典博弈模型的Nash均衡点集的通有稳定性和具有不确定参数的n人非合作博弈均衡点的概念,探讨了具有不确定参数博弈的均衡点集的通有稳定性.参照Nash均衡点集稳定性的统一模式,构造了不确定博弈的问题空间和解空间,并证明了问题空间是一个完备度量空间,解映射是上半连续的,且解集是紧集（即usco（upper semicontinuous and compact-valued）映射）,得到不确定参数博弈模型的解集通有稳定性的相关结论.     

Characterizations of perfect recall

This paper considers the condition of perfect recall for the class of arbitrarily large discrete extensive form games. The known definitions of perfect recall are shown to be equivalent even beyond finite games. Further, a qualitatively new characterization in terms of choices is obtained. In particular, an extensive form game satisfies perfect recall if and only if the set of choices, viewed as sets of ultimate outcomes, fulfill the “Trivial Intersection” property, that is, any two choices with nonempty intersection are ordered by set inclusion.     

On sums of graph games with last player losing

The purpose of this paper is to find the general class of graph games with last player losing which may be solved by an analogue ofBouton's [1901] solution. Moreover, it can be shown that this class contains all subtraction games, as well asLasker's [1931] nim and several other games. Games such asKayles andDawson's [1935] game with last player losing are not treated by the method of this paper and are still unsolved.     

Two-stage non-cooperative games with risk-averse players

This paper formally introduces and studies a non-cooperative multi-agent game under uncertainty. The well-known Nash equilibrium is employed as the solution concept of the game. While there are several formulations of a stochastic Nash equilibrium problem, we focus mainly on a two-stage setting of the game wherein each agent is risk-averse and solves a rival-parameterized stochastic program with quadratic recourse. In such a game, each agent takes deterministic actions in the first stage and recourse decisions in the second stage after the uncertainty is realized. Each agent’s overall objective consists of a deterministic first-stage component plus a second-stage mean-risk component defined by a coherent risk measure describing the agent’s risk aversion. We direct our analysis towards a broad class of quantile-based risk measures and linear-quadratic recourse functions. For this class of non-cooperative games under uncertainty, the agents’ objective functions can be shown to be convex in their own decision variables, provided that the deterministic component of these functions have the same convexity property. Nevertheless, due to the non-differentiability of the recourse functions, the agents’ objective functions are at best directionally differentiable. Such non-differentiability creates multiple challenges for the analysis and solution of the game, two principal ones being: (1) a stochastic multi-valued variational inequality is needed to characterize a Nash equilibrium, provided that the players’ optimization problems are convex; (2) one needs to be careful in the design of algorithms that require differentiability of the objectives. Moreover, the resulting (multi-valued) variational formulation cannot be expected to be of the monotone type in general. The main contributions of this paper are as follows: (a) Prior to addressing the main problem of the paper, we summarize several approaches that have existed in the literature to deal with uncertainty in a non-cooperative game. (b) We introduce a unified formulation of the two-stage SNEP with risk-averse players and convex quadratic recourse functions and highlight the technical challenges in dealing with this game. (c) To handle the lack of smoothness, we propose smoothing schemes and regularization that lead to differentiable approximations. (d) To deal with non-monotonicity, we impose a generalized diagonal dominance condition on the players’ smoothed objective functions that facilitates the application and ensures the convergence of an iterative best-response scheme. (e) To handle the expectation operator, we rely on known methods in stochastic programming that include sampling and approximation. (f) We provide convergence results for various versions of the best-response scheme, particularly for the case of private recourse functions. Overall, this paper lays the foundation for future research into the class of SNEPs that provides a constructive paradigm for modeling and solving competitive decision making problems with risk-averse players facing uncertainty; this paradigm is very much at an infancy stage of research and requires extensive treatment in order to meet its broad applications in many engineering and economics domains.     

The egalitarian solution and reduced game properties in convex games

The main purpose of this paper is to axiomatise the egalitarian solution of Dutta and Ray over the class of convex games. The main axioms used are the two reduced game properties due to Davis-Maschler and Hart-Mas Colell. The egalitarian solution is the only solution satisfying either of the two reduced game properties and agreeing with the egalitarian solution on two person games. Moreover, it is also shown that there is no solution satisfying symmetry, individual rationality and a monotonicity condition on two-person games and which simultaneously satisfies both the reduced game properties.     

Congestion network problems and related games

This paper analyzes network problems with congestion effects from a cooperative game theoretic perspective. It is shown that for network problems with convex congestion costs, the corresponding games have a non-empty core. If congestion costs are concave, then the corresponding game has not necessarily core elements, but it is derived that, contrary to the convex congestion situation, there always exist optimal tree networks. Extensions of these results to a class of relaxed network problems and associated games are derived.     

On a class of market games

It is shown that each game in a class of zero-monotonic games is a market game.     

A generalization of the Shapley–Ichiishi result

The Shapley–Ichiishi result states that a game is convex if and only if the convex hull of marginal vectors equals the core. In this paper, we generalize this result by distinguishing equivalence classes of balanced games that share the same core structure. We then associate a system of linear inequalities with each equivalence class, and we show that the system defines the class. Application of this general theorem to the class of convex games yields an alternative proof of the Shapley–Ichiishi result. Other applications range from computation of stable sets in non-cooperative game theory to determination of classes of TU games on which the core correspondence is additive (even linear). For the case of convex games we prove that the theorem provides the minimal defining system of linear inequalities. An example shows that this is not necessarily true for other equivalence classes of balanced games.     

Simplification of games in extensive form

Thevon Neumann-Morgenstern normal form of a game is conceptually and theoretically useful, but in practice leads to enormous matrix games. We discuss new methods of simplifying games in extensive form that should be useful for solving actual games. The first method is that of partially normalizing the game at an information set and, if dominations are found, making local “negative” decisions not to choose certain alternatives at the information set. Coupled with this idea is the reduction operation which eliminates parts of the game tree. These methods are shown to be powerful enough to eliminate all dominations in the strategy matrix, where we consider domination in three senses.     

Cooperative games under interval uncertainty: on the convexity of the interval undominated cores

Uncertainty is a daily presence in the real world. It affects our decision making and may have influence on cooperation. Often uncertainty is so severe that we can only predict some upper and lower bounds for the outcome of our actions, i.e., payoffs lie in some intervals. A suitable game theoretic model to support decision making in collaborative situations with interval data is that of cooperative interval games. Solution concepts that associate with each cooperative interval game sets of interval allocations with appealing properties provide a natural way to capture the uncertainty of coalition values into the players’ payoffs. This paper extends interval-type core solutions for cooperative interval games by discussing the set of undominated core solutions which consists of the interval nondominated core, the square interval dominance core, and the interval dominance core. The interval nondominated core is introduced and it is shown that it coincides with the interval core. A straightforward consequence of this result is the convexity of the interval nondominated core of any cooperative interval game. A necessary and sufficient condition for the convexity of the square interval dominance core of a cooperative interval game is also provided.     

Non-additive anonymous games

This paper introduces a class of non-additive anonymous games where agents are assumed to be uncertain (in the sense of Knight) about opponents’ strategies and about the initial distribution over players’ characteristics in the game. We model uncertainty by non-additive measures or capacities and prove the Cournot–Nash equilibrium existence theorem for this class of games. Equilibrium distribution can be symmetrized under milder conditions than in the case of additive games. In particular, it is not required for the space characteristics to be atomless under capacities. The set-valued map of the Cournot–Nash equilibria is upper-semicontinuous as a function of initial beliefs of the players for non-additive anonymous games.     

Informational aspects of a class of subjective games of incomplete information: Static case

Subjective games of incomplete information are formulated where some of the key assumptions of Bayesian games of incomplete information are relaxed. The issues arising because of the new formulation are studied in the context of a class of nonzero-sum, two-person games, where each player has a different model of the game. The static game is investigated in this note. It is shown that the properties of the static subjective game are different from those of the corresponding Bayesian game. Counterintuitive outcomes of the game can occur because of the different beliefs of the players. These outcomes may lead the players to realize the differences in their models.This work was sponsored by the Office of Naval Research under Contract No. N00014-84-C-0485.     

Link formation in cooperative situations

In this paper we study the endogenous formation of cooperation structures or communication graphs between players in a superadditive TU game. For each cooperation structure that is formed, the payoffs to the players are determined by an exogenously given solution. We model the process of cooperation structure formation as a game in strategic form. It is shown that several equilibrium refinements predict the formation of the complete cooperation structure or some structure which is payoff-equivalent to the complete structure. These results are obtained for a large class of solutions for cooperative games with cooperation structures. Received September 1995/Revised version I October 1996/Revised version II April 1997/Final version September 1997