首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
We present a new way to solve generalized Nash equilibrium problems. We assume the feasible set to be compact. Furthermore all functions are assumed to be polynomials. However we do not impose convexity on either the utility functions or the action sets. The key idea is to use Putinar’s Positivstellensatz, a representation result for positive polynomials, to replace each agent’s problem by a convex optimization problem. The Nash equilibria are then feasible solutions to a system of polynomial equations and inequalities. Our application is a model of the New Zealand electricity spot market with transmission losses based on a real dataset.  相似文献   

2.
Some projection-like methods for the generalized Nash equilibria   总被引:1,自引:0,他引:1  
A generalized Nash game is an m-person noncooperative game in which each player’s strategy depends on the rivals’ strategies. Based on a quasi-variational inequality formulation for the generalized Nash game, we present two projection-like methods for solving the generalized Nash equilibria in this paper. It is shown that under certain assumptions, these methods are globally convergent. Preliminary computational experience is also reported.  相似文献   

3.
In Pang and Fukushima (Comput Manage Sci 2:21–56, 2005), a sequential penalty approach was presented for a quasi-variational inequality (QVI) with particular application to the generalized Nash game. To test the computational performance of the penalty method, numerical results were reported with an example from a multi-leader-follower game in an electric power market. However, due to an inverted sign in the penalty term in the example and some missing terms in the derivatives of the firms’ Lagrangian functions, the reported numerical results in Pang and Fukushima (Comput Manage Sci 2:21–56, 2005) are incorrect. Since the numerical examples of this kind are scarce in the literature and this particular example may be useful in the future research, we report the corrected results. The online version of the original article can be found under doi:.  相似文献   

4.
The noncooperative multi-leader-follower game can be formulated as a generalized Nash equilibrium problem where each player solves a nonconvex mathematical program with equilibrium constraints. Two major deficiencies exist with such a formulation: One is that the resulting Nash equilibrium may not exist, due to the nonconvexity in each players problem; the other is that such a nonconvex Nash game is computationally intractable. In order to obtain a viable formulation that is amenable to practical solution, we introduce a class of remedial models for the multi-leader-follower game that can be formulated as generalized Nash games with convexified strategy sets. In turn, a game of the latter kind can be formulated as a quasi-variational inequality for whose solution we develop an iterative penalty method. We establish the convergence of the method, which involves solving a sequence of penalized variational inequalities, under a set of modest assumptions. We also discuss some oligopolistic competition models in electric power markets that lead to multi-leader-follower games.Jong-Shi Pang: The work of this authors research was partially supported by the National Science Foundation under grant CCR-0098013 and ECS-0080577 and by the Office of Naval Research under grant N00014-02-1-0286.Masao Fukushima: The work of this authors research was partially supported by a Grant-in-Aid for Scientific Research from the Ministry of Education, Science, Culture and Sports of Japan.  相似文献   

5.
This paper concentrates on the problem of the existence of equilibrium points for non-cooperative generalized N-person games, N-person games of normal form and their related inequalities. We utilize the K-K-M lemma to obtain a theorem and then use it to obtain a new Fan-type inequality and minimax theorems. Various new equilibrium point theorems are derived, with the necessary and sufficient conditions and with strategy spaces with no fixed point property. Examples are given to demonstrate that these existence theorems cover areas where other existence theorems break down.  相似文献   

6.
The aim of this paper is to prove an existence theorem for the Nash equilibria of a noncooperative generalized game with infinite-dimensional strategy spaces. The main peculiarity of this result is the absence of upper semicontinuity assumptions on the constraint multifunctions. Our result is in the same spirit of the paper Cubiotti (J Game Theory 26: 267–273, 1997), where only the case of finite-dimensional strategy spaces was considered.  相似文献   

7.
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.  相似文献   

8.
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.  相似文献   

9.
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  相似文献   

10.
11.
We study the problem of reaching a pure Nash equilibrium in multi-person games that are repeatedly played, under the assumption of uncoupledness: EVERY player knows only his own payoff function. We consider strategies that can be implemented by finite-state automata, and characterize the minimal number of states needed in order to guarantee that a pure Nash equilibrium is reached in every game where such an equilibrium exists.  相似文献   

12.
We prove the existence of a mixed strategy Nash equilibrium in normal form games when the space of mixed strategies consists of finitely additive probability measures. It is then proved that from this result an existence result for epsilon equilibria with countably additive mixed strategies can be obtained. These results are applied to the classic Cournot game.  相似文献   

13.
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.  相似文献   

14.
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.  相似文献   

15.
We consider the problem of routing a number of communication requests in WDM (wavelength division multiplexing) all-optical networks from the standpoint of game theory. If we view each routing request (pair of source-target nodes) as a player, then a strategy consists of a path from the source to the target and a frequency (color). To reflect the restriction that two requests must not use the same frequency on the same edge, conflicting strategies are assigned a prohibitively high cost.Under this formulation, we consider several natural cost functions, each one reflecting a different aspect of restriction in the available bandwidth. For each cost function we examine the problem of the existence of pure Nash equilibria, the complexity of recognizing and computing them and finally, the problem in which we are given a Nash equilibrium and we are asked to find a better one in the sense that the total bandwidth used is less. As it turns out some of these problems are tractable and others are NP-hard.  相似文献   

16.
We consider Nash equilibria in 2‐player random games and analyze a simple Las Vegas algorithm for finding an equilibrium. The algorithm is combinatorial and always finds a Nash equilibrium; on m × n payoff matrices, it runs in time O(m2nloglog n + n2mloglog m) with high probability. Our result follows from showing that a 2‐player random game has a Nash equilibrium with supports of size two with high probability, at least 1 − O(1/log n). Our main tool is a polytope formulation of equilibria. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007  相似文献   

17.
We propose and analyze a primal-dual, infinitesimal method for locating Nash equilibria of constrained, non-cooperative games. The main object is a family of nonstandard Lagrangian functions, one for each player. With respect to these functions the algorithm yields separately, in differential form, directions of steepest-descent in all decision variables and steepest-ascent in all multipliers. For convergence we need marginal costs to be monotone and constraints to be convex inequalities. The method is largely decomposed and amenable for parallel computing. Other noteworthy features are: non-smooth data can be accommodated; no projection or optimization is needed as subroutines; multipliers converge monotonically upward; and, finally, the implementation amounts, in essence, only to numerical integration.  相似文献   

18.
Pairwise-stability and Nash equilibria in network formation   总被引:1,自引:0,他引:1  
Suppose that individual payoffs depend on the network connecting them. Consider the following simultaneous move game of network formation: players announce independently the links they wish to form, and links are formed only under mutual consent. We provide necessary and sufficient conditions on the network link marginal payoffs such that the set of pairwise stable, pairwise-Nash and proper equilibrium networks coincide, where pairwise stable networks are robust to one-link deviations, while pairwise-Nash networks are robust to one-link creation but multi-link severance. Under these conditions, proper equilibria in pure strategies are fully characterized by one-link deviation checks. We thank William Thomson, an associate editor and two anonymous referees for their suggestions that led to substantial improvements. We also thank Sjaak Hurkens, Bettina Klaus, Jordi Massó and Giovanni Neglia for helpful conversations. The first author gratefully acknowledges the financial support from the Spanish Ministry of Education and FEDER through grant SEJ2005-01481/ECON, the Fundación BBVA and the Barcelona Economics Program of XREA. The second author is grateful to the Netherlands Organization for Scientific Research (NWO) for its support under grant VIDI-452-06-013.  相似文献   

19.
This paper considers two-person non-zero-sum games on the unit square with payoff functions having a new property called poor convexity. This property describes “something between” the classical convexity and quasi-convexity. It is proved that various types of such games have Nash equilibria with a very simple structure, consisting of the players’ mixed strategies with at most two-element supports. Since poor convexity is a basic notion in the paper, also a theory of poorly convex functions is also developed.  相似文献   

20.
以往关于广义博弈Nash平衡的稳定性的研究,均利用可行策略映射之间的一致度量.现考虑在更弱的度量下,利用可行策略映射图像之间的Hausdorff距离定义度量.在此弱图像拓扑下,证明了广义博弈空间的完备性,以及Nash平衡映射的上半连续性和紧性,进而得到广义博弈Nash平衡的通有稳定性.即在Baire分类的意义下,大多数的广义博弈都是本质的.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号