共查询到20条相似文献,搜索用时 15 毫秒
1.
Eleftherios Couzoudis Philipp Renner 《Mathematical Methods of Operations Research》2013,77(3):459-472
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.
Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games 总被引:1,自引:0,他引:1
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.
Shiow-Yu Chang 《Nonlinear Analysis: Theory, Methods & Applications》2010,73(9):2933-2940
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.
Yakov Babichenko 《International Journal of Game Theory》2010,39(3):483-502
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.
Massimo Marinacci 《International Journal of Game Theory》1997,26(3):315-333
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.
Charles Horvath 《Journal of Fixed Point Theory and Applications》2012,11(2):315-332
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.
George F. Georgakopoulos 《Discrete Mathematics》2009,309(13):4332-379
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.
Sjur Didrik Flåm 《Applied Mathematics and Optimization》1993,27(3):275-289
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.
Tadeusz Radzik 《International Journal of Game Theory》2014,43(1):169-192
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. 相似文献