共查询到20条相似文献,搜索用时 62 毫秒
1.
Heike Sperber 《Mathematical Methods of Operations Research》2010,71(2):245-265
We study the complexity of finding extreme pure Nash equilibria in symmetric network congestion games and analyse how it is
influenced by the graph topology and the number of users. In our context best and worst equilibria are those with minimum
or maximum total latency, respectively. We establish that both problems can be solved by a Greedy type algorithm equipped
with a suitable tie breaking rule on extension-parallel graphs. On series-parallel graphs finding a worst Nash equilibrium
is NP-hard for two or more users while finding a best one is solvable in polynomial time for two users and NP-hard for three or more. additionally we establish NP-hardness in the strong sense for the problem of finding a worst Nash equilibrium on a general acyclic graph. 相似文献
2.
Vitaly Pruzhansky 《International Journal of Game Theory》2011,40(2):351-365
Since the seminal paper of Nash (1950) game theoretic literature has focused mostly on equilibrium and not on maximin (minimax)
strategies. We study the properties of these strategies in non-zero-sum strategic games that possess (completely) mixed Nash
equilibria. We find that under certain conditions maximin strategies have several interesting properties, some of which extend
beyond 2-person strategic games. In particular, for n-person games we specify necessary and sufficient conditions for maximin strategies to yield the same expected payoffs as
Nash equilibrium strategies. We also show how maximin strategies may facilitate payoff comparison across Nash equilibria as
well as refine some Nash equilibrium strategies. 相似文献
3.
Ryusuke Shinohara 《International Journal of Game Theory》2010,39(4):603-615
We examine the coalition-proof equilibria of a participation game in the provision of a (pure) public good. We study which
Nash equilibria are achieved through cooperation, and we investigate coalition-proof equilibria under strict and weak domination.
We show that under some incentive condition, (i) a profile of strategies is a coalition-proof equilibrium under strict domination if and only if it is a Nash equilibrium that is not strictly Pareto-dominated by any other Nash equilibrium and (ii) every
strict Nash equilibrium for non-participants is a coalition-proof equilibrium under weak domination. 相似文献
4.
Cyclic Markov equilibria in stochastic games 总被引:1,自引:0,他引:1
We examine a three-person stochastic game where the only existing equilibria consist of cyclic Markov strategies. Unlike in two-person games of a similar type, stationary ε-equilibria (ε > 0) do not exist for this game. Besides we characterize the set of feasible equilibrium rewards. 相似文献
5.
This paper attempts to study two-person nonzero-sum games for denumerable continuous-time Markov chains determined by transition rates,with an expected average criterion.The transition rates are allowed to be unbounded,and the payoff functions may be unbounded from above and from below.We give suitable conditions under which the existence of a Nash equilibrium is ensured.More precisely,using the socalled "vanishing discount" approach,a Nash equilibrium for the average criterion is obtained as a limit point of a sequence of equilibrium strategies for the discounted criterion as the discount factors tend to zero.Our results are illustrated with a birth-and-death game. 相似文献
6.
Ryoichi Nishimura Shunsuke Hayashi Masao Fukushima 《Journal of Global Optimization》2012,53(1):107-120
Consider the N-person non-cooperative game in which each player’s cost function and the opponents’ strategies are uncertain. For such an
incomplete information game, the new solution concept called a robust Nash equilibrium has attracted much attention over the
past several years. The robust Nash equilibrium results from each player’s decision-making based on the robust optimization
policy. In this paper, we focus on the robust Nash equilibrium problem in which each player’s cost function is quadratic,
and the uncertainty sets for the opponents’ strategies and the cost matrices are represented by means of Euclidean and Frobenius
norms, respectively. Then, we show that the robust Nash equilibrium problem can be reformulated as a semidefinite complementarity
problem (SDCP), by utilizing the semidefinite programming (SDP) reformulation technique in robust optimization. We also give
some numerical example to illustrate the behavior of robust Nash equilibria. 相似文献
7.
Elżbieta Z. Ferenstein 《Mathematical Methods of Operations Research》2007,66(3):531-544
We study nonzero-sum stopping games with randomized stopping strategies. The existence of Nash equilibrium and ɛ-equilibrium
strategies are discussed under various assumptions on players random payoffs and utility functions dependent on the observed
discrete time Markov process. Then we will present a model of a market game in which randomized stopping times are involved.
The model is a mixture of a stochastic game and stopping game.
Research supported by grant PBZ-KBN-016/P03/99. 相似文献
8.
Axel Dreves 《Journal of Optimization Theory and Applications》2018,178(3):973-997
We propose a new solution concept for generalized Nash equilibrium problems. This concept leads, under suitable assumptions, to unique solutions, which are generalized Nash equilibria and the result of a mathematical procedure modeling the process of finding a compromise. We first compute the favorite strategy for each player, if he could dictate the game, and use the best response on the others’ favorite strategies as starting point. Then, we perform a tracing procedure, where we solve parametrized generalized Nash equilibrium problems, in which the players reduce the weight on the best possible and increase the weight on the current strategies of the others. Finally, we define the limiting points of this tracing procedure as solutions. Under our assumptions, the new concept selects one reasonable out of typically infinitely many generalized Nash equilibria. 相似文献
9.
Andrzej S. Nowak 《Mathematical Methods of Operations Research》1999,50(1):65-76
We consider stochastic games with countable state spaces and unbounded immediate payoff functions. Our assumptions on the transition structure of the game are based on a recent work by Meyn and Tweedie [19] on computable bounds for geometric convergence rates of Markov chains. The main results in this paper concern the existence of sensitive optimal strategies in some classes of zero-sum stochastic games. By sensitive optimality we mean overtaking or 1-optimality. We also provide a new Nash equilibrium theorem for a class of ergodic nonzero-sum stochastic games with denumerable state spaces. 相似文献
10.
The generalized Nash equilibrium problem (GNEP) is a generalization of the standard Nash equilibrium problem (NEP),in which both the utility function and the strategy space of each player depend on the strategies chosen by all other players.This problem has been used to model various problems in applications.However,the convergent solution algorithms are extremely scare in the literature.In this paper,we present an incremental penalty method for the GNEP,and show that a solution of the GNEP can be found by solving a sequence of smooth NEPs.We then apply the semismooth Newton method with Armijo line search to solve latter problems and provide some results of numerical experiments to illustrate the proposed approach. 相似文献
11.
This paper deals with an extension of the concept of correlated strategies to Markov stopping games. The Nash equilibrium approach to solving nonzero-sum stopping games may give multiple solutions. An arbitrator can suggest to each player the decision to be applied at each stage based on a joint distribution over the players’ decisions according to some optimality criterion. This is a form of equilibrium selection. Examples of correlated equilibria in nonzero-sum games related to the best choice problem are given. Several concepts of criteria for selecting a correlated equilibrium are used. 相似文献
12.
This paper deals with a new optimality criterion consisting of the usual three average criteria and the canonical triplet (totally so-called strong average-canonical optimality criterion) and introduces the concept of a strong average-canonical policy for nonstationary Markov decision processes, which is an extension of the canonical policies of Herna′ndez-Lerma and Lasserre [16] (pages: 77) for the stationary Markov controlled processes. For the case of possibly non-uniformly bounded rewards and denumerable state space, we first construct, under some conditions, a solution to the optimality equations (OEs), and then prove that the Markov policies obtained from the OEs are not only optimal for the three average criteria but also optimal for all finite horizon criteria with a sequence of additional functions as their terminal rewards (i.e. strong average-canonical optimal). Also, some properties of optimal policies and optimal average value convergence are discussed. Moreover, the error bound in average reward between a rolling horizon policy and a strong average-canonical optimal policy is provided, and then a rolling horizon algorithm for computing strong average ε(>0)-optimal Markov policies is given. 相似文献
13.
Games with frequency-dependent stage payoffs (FD-games), are infinitely repeated non-cooperative games played at discrete moments in time called stages. The stage payoffs depend on the action pair actually chosen, and on the relative frequencies with which all actions were chosen before.
We assume that players wish to maximize their expected (limiting) average rewards over the entire time-horizon. We prove an analogy to, as well as an extension of the (perfect) Folk Theorem. Each pair of rewards in the convex hull of all individually-rational jointly-convergent pure-strategy rewards can be supported by an equilibrium. Moreover, each pair of rewards in same set giving each player strictly more than the threat-point-reward, can be supported by a subgame-perfect equilibrium. Under a pair of jointly-convergent strategies, the relative frequency of each action pair converges in the long run.
Received: March 2002/Revised: January 2003 相似文献
14.
Piotr Więcek 《Mathematical Methods of Operations Research》2009,69(1):59-79
We present a discrete model of two-person constant-sum dynamic strategic market game. We show that for every value of discount
factor the game with discounted rewards possesses a pure stationary strategy equilibrium. Optimal strategies have some useful
properties, such as Lipschitz property and symmetry. We also show value of the game to be nondecreasing both in state and
discount factor. Further, for some values of discount factor, exact form of optimal strategies is found. For β less than , there is an equilibrium such that players make large bids. For β close to 1, there is an equilibrium with small bids. Similar result is obtained for the long run average reward game. 相似文献
15.
16.
We consider a class of generalized Ky Fan inequalities (quasi-variational inequalities) in which the involved multi-valued
mapping is lower semi-continuous. We present a relaxed version of the generalized Nash equilibrium problem involving strategy
maps, which are only lower semi-continuous. This relaxed version may have no exact Nash equilibrium, but we prove that it
has an ε-Nash equilibrium for every ε > 0. Easy examples of such problems show no existence of exact solutions, but existence of ε-solutions for every ε > 0. We give positive answers to two questions (in the compact case) raised in a recent paper of Cubiotti and Yao. 相似文献
17.
Do we detect and exploit mixed strategy play by opponents? 总被引:1,自引:0,他引:1
We conducted an experiment in which each subject repeatedly played a game with a unique Nash equilibrium in mixed strategies against some computer-implemented mixed strategy. The results indicate subjects are successful at detecting and exploiting deviations from Nash equilibrium. However, there is heterogeneity in subject behavior and performance. We present a one variable model of dynamic random belief formation which rationalizes observed heterogeneity and other features of the data.The minimax and Nash equilibrium solutions coincide in this setting, and we could proceed only referring to the minimax solution and strategies. However, we proceed using the Nash equilibrium framework because we wish to focus on the concept of best response. 相似文献
18.
Alberto A. Pinto Fernanda A. Ferreira Miguel Ferreira Bruno M.P.M. Oliveira 《PAMM》2007,7(1):1041303-1041304
We present a new deterministic dynamical model on the market size of Cournot competitions, based on Nash equilibria of R&D investment strategies to increase the size of the market of the firms at every period of the game. We compute the unique Nash equilibrium for the second subgame and the profit functions for both firms. Adding uncertainty to the R&D investment strategies, we get a new stochastic dynamical model and we analyse the importance of the uncertainty to reverse the initial advantage of one firm with respect to the other. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) 相似文献
19.
《佛山科学技术学院》2014,6(3):299-314
In this paper, we investigate Nash equilibrium strategy of two-person zero-sum games with fuzzy payoffs. Based on fuzzy max order, Maeda and Cunlin constructed several models in symmetric triangular and asymmetric triangular fuzzy environment, respectively. We extended their models in trapezoidal fuzzy environment and proposed the existence of equilibrium strategies for these models. We also established the relation between Pareto Nash equilibrium strategy and parametric bi-matrix game. In addition, numerical examples are presented to find Pareto Nash equilibrium strategy and weak Pareto Nash equilibrium strategy from bi-matrix game. 相似文献
20.
Asymptotic Analysis of Linear Feedback Nash Equilibria in Nonzero-Sum Linear-Quadratic Differential Games 总被引:2,自引:0,他引:2
A. J. T. M. Weeren J. M. Schumacher J. C. Engwerda 《Journal of Optimization Theory and Applications》1999,101(3):693-722
In this paper, we discuss nonzero-sum linear-quadratic differential games. For this kind of games, the Nash equilibria for different kinds of information structures were first studied by Starr and Ho. Most of the literature on the topic of nonzero-sum linear-quadratic differential games is concerned with games of fixed, finite duration; i.e., games are studied over a finite time horizon t
f. In this paper, we study the behavior of feedback Nash equilibria for t
f.In the case of memoryless perfect-state information, we study the so-called feedback Nash equilibrium. Contrary to the open-loop case, we note that the coupled Riccati equations for the feedback Nash equilibrium are inherently nonlinear. Therefore, we limit the dynamic analysis to the scalar case. For the special case that all parameters are scalar, a detailed dynamical analysis is given for the quadratic system of coupled Riccati equations. We show that the asymptotic behavior of the solutions of the Riccati equations depends strongly on the specified terminal values. Finally, we show that, although the feedback Nash equilibrium over any fixed finite horizon is generically unique, there can exist several different feedback Nash equilibria in stationary strategies for the infinite-horizon problem, even when we restrict our attention to Nash equilibria that are stable in the dynamical sense. 相似文献