大博弈中Nash均衡的存在性

研究了具有任意多个局中人的非合作博弈(大博弈)中Nash均衡的存在性.将1969年Ma的截口定理推广得到新的截口定理.用这个新的截口定理进一步证明了:1)大博弈中Nash均衡的存在性;2)纯策略集为紧度量空间而且支付函数为连续函数时,连续大博弈中混合策略Nash均衡的存在性.并且存在性定理推出了2010年Salonen的结果,即此研究结果较Salonen的结论更具普遍意义.     

Split equilibrium problems for related games and applications to economic theory

ABSTRACT

In this paper we introduce the concept of split Nash equilibrium problems associated with two related noncooperative strategic games. Then we apply the Fan-KKM theorem to prove the existence of solutions to split Nash equilibrium problems of related noncooperative strategic games, in which the strategy sets of the players are nonempty closed and convex subsets in Banach spaces. As an application of this existence to economics, an example is provided that studies the existence of split Nash equilibrium of utilities of two related economies. As applications, we study the existence of split Nash equilibrium in the dual (playing twice) extended Bertrand duopoly model of price competition.     

Two noncooperative games between a coalition and its surrounding in a class of n-person games with constant sum

A cooperative game engendered by a noncooperative n-person game (the master game) in which any subset of n players may form a coalition playing an antagonistic game against the residual players (the surrounding) that has a (Nash equilibrium) solution, is considered, along with another noncooperative game in which both a coalition and its surrounding try to maximize their gains that also possesses a Nash equilibrium solution. It is shown that if the master game is the one with constant sum, the sets of Nash equilibrium strategies in both above-mentioned noncooperative games (in which a coalition plays with (against) its surrounding) coincide.     

Network formation when players seek confirmation of information

We study network formation in a situation where the network allows players to obtain information (signals) about other players. This information is important for making a payoff relevant decision. However, not all information is reliable and so players may have an incentive to check it. By obtaining multiple messages about the same player through the network, a player learns whether his information is reliable for making the payoff relevant decision. We study the existence and architecture of strict Nash networks. We find that players who are involved in at least three links sponsor all links they are involved in. These players are similar to the central players in center sponsored stars. We show that strict Nash networks can be over-connected as well as under-connected as compared to efficient networks. Finally, we extend the basic model to study heterogeneous populations. In the first scenario, we allow for the co-existence of players who only value checked information and players who also value information with unknown reliability. In the second scenario, players who do not care about checking their information co-exist with players who do. Our results are robust to both types of heterogeneity, with one exception: the presence of a single player who cares only about checked information is enough to ensure that center sponsored stars are no longer stable.     

An improved two-step method for solving generalized Nash equilibrium problems

The generalized Nash equilibrium problem (GNEP) is a noncooperative game in which the strategy set of each player, as well as his payoff function, depend on the rival players strategies. As a generalization of the standard Nash equilibrium problem (NEP), the GNEP has recently drawn much attention due to its capability of modeling a number of interesting conflict situations in, for example, an electricity market and an international pollution control. In this paper, we propose an improved two-step (a prediction step and a correction step) method for solving the quasi-variational inequality (QVI) formulation of the GNEP. Per iteration, we first do a projection onto the feasible set defined by the current iterate (prediction) to get a trial point; then, we perform another projection step (correction) to obtain the new iterate. Under certain assumptions, we prove the global convergence of the new algorithm. We also present some numerical results to illustrate the ability of our method, which indicate that our method outperforms the most recent projection-like methods of Zhang et al. (2010).     

On solving generalized Nash equilibrium problems via optimization

This paper deals with the generalized Nash equilibrium problem (GNEP), i.e. a noncooperative game in which the strategy set of each player, as well as his payoff function, depends on the strategies of all players. We consider an equivalent optimization reformulation of GNEP using a regularized Nikaido–Isoda function so that solutions of GNEP coincide with global minima of the optimization problem. We then propose a derivative-free descent type method with inexact line search to solve the equivalent optimization problem and we prove that our algorithm is globally convergent. The convergence analysis is not based on conditions guaranteeing that every stationary point of the optimization problem is a solution of GNEP. Finally, we present the performance of our algorithm on some examples.     

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.     

Smoothing approach to Nash equilibrium formulations for a class of equilibrium problems with shared complementarity constraints

The equilibrium problem with equilibrium constraints (EPEC) can be looked on as a generalization of Nash equilibrium problem (NEP) and the mathematical program with equilibrium constraints (MPEC) whose constraints contain a parametric variational inequality or complementarity system. In this paper, we particularly consider a special class of EPECs where a common parametric P-matrix linear complementarity system is contained in all players?? strategy sets. After reformulating the EPEC as an equivalent nonsmooth NEP, we use a smoothing method to construct a sequence of smoothed NEPs that approximate the original problem. We consider two solution concepts, global Nash equilibrium and stationary Nash equilibrium, and establish some results about the convergence of approximate Nash equilibria. Moreover we show some illustrative numerical examples.     

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.     

Formulating an <Emphasis Type="Italic">n</Emphasis>-person noncooperative game as a tensor complementarity problem

In this paper, we consider a class of n-person noncooperative games, where the utility function of every player is given by a homogeneous polynomial defined by the payoff tensor of that player, which is a natural extension of the bimatrix game where the utility function of every player is given by a quadratic form defined by the payoff matrix of that player. We will call such a problem the multilinear game. We reformulate the multilinear game as a tensor complementarity problem, a generalization of the linear complementarity problem; and show that finding a Nash equilibrium point of the multilinear game is equivalent to finding a solution of the resulted tensor complementarity problem. Especially, we present an explicit relationship between the solutions of the multilinear game and the tensor complementarity problem, which builds a bridge between these two classes of problems. We also apply a smoothing-type algorithm to solve the resulted tensor complementarity problem and give some preliminary numerical results for solving the multilinear games.     

A Bidding Game with Heterogeneous Players

A one-sided limit order book is modeled as a noncooperative game for several players. Agents offer various quantities of an asset at different prices, competing to fulfill an incoming order, whose size is not known a priori. Players can have different payoff functions, reflecting different beliefs about the fundamental value of the asset and probability distribution of the random incoming order. In a previous paper, the existence of a Nash equilibrium was established by means of a fixed point argument. The main issue discussed in the present paper is whether this equilibrium can be obtained from the unique solution to a two-point boundary value problem, for a suitable system of discontinuous ordinary differential equations. Some additional assumptions are introduced, which yield a positive answer. In particular, this is true when there are exactly two players, or when all players assign the same exponential probability distribution to the incoming order. In both of these cases, we also prove that the Nash equilibrium is unique. A counterexample shows that these assumptions cannot be removed, in general.     

Neural nets in a group decision process

In recent years there has been some interest in applying Artificial Adaptive Agents (AAA) to the study of complex adaptive systems, especially economic systems. Neural networks are frequently employed as AAA. Artificial neural nets mimic certain aspects of the physical structure and information processing of the human brain and their most attractive characteristic is their ability to learn a pattern from a given set of examples. In this study, we investigated the ability of neural nets to model human behavior in a group decision process. The context was a market entry game with a linear payoff function and binary decisions. The players had to decide, for each trial, whether or not to enter a market whose capacity is public knowledge. Human behavior in this situation has been modeled and empirically validated by the Nash equilibrium for noncooperative n-person games. A simulation of the game was performed with neural nets instead of human subjects. The nets were trained using the results of the games in which they participated. The simulation with groups of neural nets exhibits phenomena very similar to those observed in groups of human players. Received February 2000     

On the Structural Stability of Values for Cooperative Games

It is generally assumed that any set of players can form a feasible coalition for classical cooperative games. But, in fact, some players may withdraw from the current game and form a union, if this makes them better paid than proposed. Based on the principle of coalition split, this paper presents an endogenous procedure of coalition formation by levels and bargaining for payoffs simultaneously, where the unions formed in the previous step continue to negotiate with others in the next step as “individuals,” looking for maximum share of surplus by organizing themselves as a partition. The structural stability of the induced payoff configuration is discussed, using two stability criteria of core notion for cooperative games and strong equilibrium notion for noncooperative games.

     

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.     

Stay-in-a-set games

There exists a Nash equilibrium (ε-Nash equilibrium) for every n-person stochastic game with a finite (countable) state space and finite action sets for the players if the payoff to each player i is one when the process of states remains in a given set of states G _i and is zero otherwise. Received: December 2000     

Negotiation-proof Nash equilibrium

This paper defines “negotiation-proof Nash equilibrium', a notion that applies to environments where players can negotiate openly and directly prior to the play of a noncooperative game. It recognizes the possibility that a group of self-interested players may choose, voluntarily and without binding agreement, to coordinate their choice of strategies and make joint objections; moreover, it takes the perfect foresight of rational players fully into account. The merit of the notion of negotiation-proof Nash equilibrium is twofold: (1) It offers a way to rectify the nestedness assumption and myopia embedded in the notion of coalition-proof Nash equilibrium. (2) The negotiation process is formalized by a “graph”, which serves as a natural extension to the approach that models preplay communication by an extensive game. Received: October 1998/Final version: May 2000     

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.     

A Characterization of Nash Equilibrium for the Games with Random Payoffs

We consider a two-player random bimatrix game where each player is interested in the payoffs which can be obtained with certain confidence. The payoff function of each player is defined using a chance constraint. We consider the case where the entries of the random payoff matrix of each player jointly follow a multivariate elliptically symmetric distribution. We show an equivalence between the Nash equilibrium problem and the global maximization of a certain mathematical program. The case where the entries of the payoff matrices are independent normal/Cauchy random variables is also considered. The case of independent normally distributed random payoffs can be viewed as a special case of a multivariate elliptically symmetric distributed random payoffs. As for Cauchy distribution, we show that the Nash equilibrium problem is equivalent to the global maximization of a certain quadratic program. Our theoretical results are illustrated by considering randomly generated instances of the game.     

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.