共查询到20条相似文献,搜索用时 610 毫秒
1.
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. 相似文献
2.
Consider a family of zero-sum games indexed by a parameter that determines each player’s payoff function and feasible strategies.
Our first main result characterizes continuity assumptions on the payoffs and the constraint correspondence such that the
equilibrium value and strategies depend continuously and upper hemicontinuously (respectively) on the parameter. This characterization
uses two topologies in order to overcome a topological tension that arises when players’ strategy sets are infinite-dimensional.
Our second main result is an application to Bayesian zero-sum games in which each player’s information is viewed as a parameter.
We model each player’s information as a sub-σ-field, so that it determines her feasible strategies: those that are measurable with respect to the player’s information.
We thereby characterize conditions under which the equilibrium value and strategies depend continuously and upper hemicontinuously
(respectively) on each player’s information. 相似文献
3.
Koichi Nabetani Paul Tseng Masao Fukushima 《Computational Optimization and Applications》2011,48(3):423-452
We consider the generalized Nash equilibrium problem (GNEP), in which each player’s strategy set may depend on the rivals’
strategies through shared constraints. A practical approach to solving this problem that has received increasing attention
lately entails solving a related variational inequality (VI). From the viewpoint of game theory, it is important to find as
many GNEs as possible, if not all of them. We propose two types of parametrized VIs related to the GNEP, one price-directed
and the other resource-directed. We show that these parametrized VIs inherit the monotonicity properties of the original VI
and, under mild constraint qualifications, their solutions yield all GNEs. We propose strategies to sample in the parameter
spaces and show, through numerical experiments on benchmark examples, that the GNEs found by the parametrized VI approaches
are widely distributed over the GNE set. 相似文献
4.
Masao Fukushima 《Computational Management Science》2011,8(3):201-218
The generalized Nash equilibrium problem (GNEP) is a generalization of the standard Nash equilibrium problem, in which each
player’s strategy set may depend on the rival players’ strategies. The GNEP has recently drawn much attention because of its
capability of modeling a number of interesting conflict situations in, for example, an electricity market and an international
pollution control. However, a GNEP usually has multiple or even infinitely many solutions, and it is not a trivial matter
to choose a meaningful solution from those equilibria. The purpose of this paper is two-fold. First we present an incremental
penalty method for the broad class of GNEPs and show that it can find a GNE under suitable conditions. Next, we formally define
the restricted GNE for the GNEPs with shared constraints and propose a controlled penalty method, which includes the incremental
penalty method as a subprocedure, to compute a restricted GNE. Numerical examples are provided to illustrate the proposed
approach. 相似文献
5.
Roman Kozhan 《International Journal of Game Theory》2011,40(2):215-230
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. 相似文献
6.
Guimei Luo 《Applications of Mathematics》2012,57(5):503-520
In this paper, we investigate the bimatrix game using the robust optimization approach, in which each player may neither exactly estimate his opponent’s strategies nor evaluate his own cost matrix accurately while he may estimate a bounded uncertain set. We obtain computationally tractable robust formulations which turn to be linear programming problems and then solving a robust optimization equilibrium can be converted to solving a mixed complementarity problem under the l 1 ∩ l ∞-norm. Some numerical results are presented to illustrate the behavior of the robust optimization equilibrium. 相似文献
7.
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. 相似文献
8.
Andrés Perea 《International Journal of Game Theory》2006,34(4):529-559
In this paper we develop an epistemic model for dynamic games in which players may revise their beliefs about the opponents’ utility functions as the game proceeds. Within this framework, we propose a rationalizability concept that is based upon the following three principles: (1) at every instance of the game, a player should believe that his opponents are carrying out optimal strategies, (2) a player, at information set h, should not change his belief about an opponent’s relative ranking of two strategies s and s′ if both s and s′ could have led to h, and (3) the players’ initial beliefs about the opponents’ utility functions should agree on a given profile u of utility functions. Common belief in these events leads to the concept of persistent rationalizability for the profile u of utility functions. It is shown that for a given game tree with observable deviators and a given profile u of utility functions, every properly point-rationalizable strategy is a persistently rationalizable strategy for u. This result implies that persistently rationalizable strategies always exist for all game trees with observable deviators and all profiles of utility functions. We provide an algorithm that can be used to compute the set of persistently rationalizable strategies for a given profile u of utility functions. For generic games with perfect information, persistent rationalizability uniquely selects the backward induction strategy for every player. 相似文献
9.
This paper provides an overview of the various shapes the best-reply multifunctions can take in 2×2×2 trimatrix games. It
is shown that, unlike in 2×2 bimatrix games, the best replies to the opponents’ pure strategies do not completely determine
the structure of the Nash equilibrium set.
相似文献
10.
Vianney Perchet 《Journal of Optimization Theory and Applications》2011,149(3):665-677
We provide a necessary and sufficient condition under which a convex set is approachable in a game with partial monitoring,
i.e. where players do not observe their opponents’ moves but receive random signals. This condition is an extension of Blackwell’s
Criterion in the full monitoring framework, where players observe at least their payoffs. When our condition is fulfilled,
we construct explicitly an approachability strategy, derived from a strategy satisfying some internal consistency property in an auxiliary game. 相似文献
11.
Two kinds of vertical cooperative advertising program are considered in a distribution channel constituted by a manufacturer and a retailer, where the manufacturer pays part of
the retailer’s advertising costs. In the first participation scheme, the manufacturer chooses his/her advertising participation
rate in the retailer’s advertising effort and then each player determines the advertising effort that maximizes his/her profit.
In the second scheme, the retailer chooses the manufacturer’s participation rate and then the manufacturer determines the
advertising efforts of both players with the objective of maximizing the manufacturer’s profit. Each participation scheme
corresponds to a special Stackelberg game: the manufacturer is the leader of the first, while the retailer is the leader of
the second. The Stackelberg equilibrium advertising efforts and participation rate in both games are provided. Then the equilibrium
strategies of the two players in the analyzed scenarios are compared with the Nash equilibrium in the competitive framework.
Finally, the conditions which suggest a special kind of agreement to a player are analyzed.
This work was supported by the Italian Ministry of University and Research and the University of Padua. 相似文献
12.
Eitan Altman Konstantin Avrachenkov Richard Marquez Gregory Miller 《Mathematical Methods of Operations Research》2005,62(3):375-386
We consider a zero-sum stochastic game with side constraints for both players with a special structure. There are two independent
controlled Markov chains, one for each player. The transition probabilities of the chain associated with a player as well
as the related side constraints depend only on the actions of the corresponding player; the side constraints also depend on
the player’s controlled chain. The global cost that player 1 wishes to minimize and that player 2 wishes to maximize, depend
however on the actions and Markov chains of both players. We obtain a linear programming formulations that allows to compute
the value and saddle point policies for this problem. We illustrate the theoretical results through a zero-sum stochastic
game in wireless networks in which each player has power constraints 相似文献
13.
We consider the generalized Nash equilibrium problem which, in contrast to the standard Nash equilibrium problem, allows joint
constraints of all players involved in the game. Using a regularized Nikaido-Isoda-function, we then present three optimization
problems related to the generalized Nash equilibrium problem. The first optimization problem is a complete reformulation of
the generalized Nash game in the sense that the global minima are precisely the solutions of the game. However, this reformulation
is nonsmooth. We then modify this approach and obtain a smooth constrained optimization problem whose global minima correspond
to so-called normalized Nash equilibria. The third approach uses the difference of two regularized Nikaido-Isoda-functions
in order to get a smooth unconstrained optimization problem whose global minima are, once again, precisely the normalized
Nash equilibria. Conditions for stationary points to be global minima of the two smooth optimization problems are also given.
Some numerical results illustrate the behaviour of our approaches. 相似文献
14.
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. 相似文献
15.
Pricing and Advertising of Private and National Brands in a Dynamic Marketing Channel 总被引:1,自引:0,他引:1
N. Amrouche G. Martín-Herrán G. Zaccour 《Journal of Optimization Theory and Applications》2008,137(3):465-483
We consider a marketing channel where a retailer sells, along the manufacturer’s brand, its own store brand. We assume that
each player invests in advertising in order to build the brand’s goodwill. One distinctive feature of this paper is the introduction
of the negative effect of own advertising on other player’s goodwill stock evolution. We characterize feedback-Nash pricing
and advertising strategies and assess the impact of the store brand and national brand’s goodwill stocks on these strategies
in different settings. The main findings suggest first that investing in building up some equity for each brand reduces the
price competition between them and propels the market power for both. Second, the retailer will pass to consumer an increase
in its purchasing cost of the national brand in all situations as no coordination is taken into account to counter the double
marginalization problem. Finally, the higher the brand equity of the store brand, the more the retailer invests in advertising. 相似文献
16.
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. 相似文献
17.
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. 相似文献
18.
We present a distribution-free model of incomplete-information games, both with and without private information, in which
the players use a robust optimization approach to contend with payoff uncertainty. Our ``robust game' model relaxes the assumptions
of Harsanyi's Bayesian game model, and provides an alternative distribution-free equilibrium concept, which we call ``robust-optimization
equilibrium,' to that of the ex post equilibrium. We prove that the robust-optimization equilibria of an incomplete-information game subsume the ex post equilibria of the game and are, unlike the latter, guaranteed to exist when the game is finite and has bounded payoff uncertainty
set. For arbitrary robust finite games with bounded polyhedral payoff uncertainty sets, we show that we can compute a robust-optimization
equilibrium by methods analogous to those for identifying a Nash equilibrium of a finite game with complete information. In
addition, we present computational results.
The research of the author was partially supported by a National Science Foundation Graduate Research Fellowship and by the
Singapore-MIT Alliance.
The research of the author was partially supported by the Singapore-MIT Alliance. 相似文献
19.
Francesca Busetto Giulio Codognato Sayantan Ghosal 《International Journal of Game Theory》2008,37(3):371-386
In this paper, we investigate the problem of the strategic foundation of the Cournot–Walras equilibrium approach. To this
end, we respecify à la Cournot–Walras the mixed version of a model of simultaneous, noncooperative exchange, originally proposed
by Lloyd S. Shapley. We show, through an example, that the set of the Cournot–Walras equilibrium allocations of this respecification
does not coincide with the set of the Cournot–Nash equilibrium allocations of the mixed version of the original Shapley’s
model. As the nonequivalence, in a one-stage setting, can be explained by the intrinsic two-stage nature of the Cournot–Walras
equilibrium concept, we are led to consider a further reformulation of the Shapley’s model as a two-stage game, where the
atoms move in the first stage and the atomless sector moves in the second stage. Our main result shows that the set of the
Cournot–Walras equilibrium allocations coincides with a specific set of subgame perfect equilibrium allocations of this two-stage
game, which we call the set of the Pseudo–Markov perfect equilibrium allocations.
We would like to thank Pierpaolo Battigalli, Marcellino Gaudenzi, and an anonymous referee for their comments and suggestions. 相似文献
20.
《Journal of Computational and Applied Mathematics》2005,175(1):113-136
Nash equilibrium constitutes a central solution concept in game theory. The task of detecting the Nash equilibria of a finite strategic game remains a challenging problem up-to-date. This paper investigates the effectiveness of three computational intelligence techniques, namely, covariance matrix adaptation evolution strategies, particle swarm optimization, as well as, differential evolution, to compute Nash equilibria of finite strategic games, as global minima of a real-valued, nonnegative function. An issue of particular interest is to detect more than one Nash equilibria of a game. The performance of the considered computational intelligence methods on this problem is investigated using multistart and deflection. 相似文献