共查询到20条相似文献,搜索用时 31 毫秒
1.
Dinah Rosenberg Eilon Solan Nicolas Vieille 《International Journal of Game Theory》2003,32(1):133-150
We study finite zero-sum stochastic games in which players do not observe the actions of their opponent. Rather, at each stage, each player observes a stochastic signal that may depend on the current state and on the pair of actions chosen by the players. We assume that each player observes the state and his/her own action. We prove that the uniform max-min value always exists. Moreover, the uniform max-min value is independent of the information structure of player 2. Symmetric results hold for the uniform min-max value.
We deeply thank E. Lehrer, J.-F. Mertens, A. Neyman and S. Sorin. The discussions we had, and the suggestions they provided, were extremely useful. We acknowledge the financial support of the Arc-en-Ciel/Keshet program for 2001/2002. The research of the second author was supported by the Israel Science Foundation (grant No. 69/01-1). 相似文献
2.
We introduce a new class of games, congestion games with failures (CGFs), which allows for resource failures in congestion games. In a CGF, players share a common set of resources (service providers), where each service provider (SP) may fail with some known probability (that may be constant or depend on the congestion on the resource). For reliability reasons, a player may choose a subset of the SPs in order to try and perform his task. The cost of a player for utilizing any SP is a function of the total number of players using this SP. A main feature of this setting is that the cost for a player for successful completion of his task is the minimum of the costs of his successful attempts. We show that although CGFs do not, in general, admit a (generalized ordinal) potential function and the finite improvement property (and thus are not isomorphic to congestion games), they always possess a pure strategy Nash equilibrium. Moreover, every best reply dynamics converges to an equilibrium in any given CGF, and the SPs’ congestion experienced in different equilibria is (almost) unique. Furthermore, we provide an efficient procedure for computing a pure strategy equilibrium in CGFs and show that every best equilibrium (one minimizing the sum of the players’ disutilities) is semi-strong. Finally, for the subclass of symmetric CGFs we give a constructive characterization of best and worst equilibria. 相似文献
3.
An absorbing game is a repeated game where some action combinations are absorbing, in the sense that whenever they are played,
there is a positive probability that the game terminates, and the players receive some terminal payoff at every future stage.
We prove that every multi-player absorbing game admits a correlated equilibrium payoff. In other words, for every ε>0 there
exists a probability distribution p
ε over the space of pure strategy profiles that satisfies the following. With probability at least 1−ε, if a pure strategy
profile is chosen according to p
ε and each player is informed of his pure strategy, no player can profit more than ε in any sufficiently long game by deviating
from the recommended strategy.
Received: April 2001/Revised: June 4, 2002 相似文献
4.
The Nash equilibrium in pure strategies represents an important solution concept in nonzero sum matrix games. Existence of
Nash equilibria in games with known and with randomly selected payoff entries have been studied extensively. In many real
games, however, a player may know his own payoff entries but not the payoff entries of the other player. In this paper, we
consider nonzero sum matrix games where the payoff entries of one player are known, but the payoff entries of the other player
are assumed to be randomly selected. We are interested in determining the probabilities of existence of pure Nash equilibria
in such games. We characterize these probabilities by first determining the finite space of ordinal matrix games that corresponds
to the infinite space of matrix games with random entries for only one player. We then partition this space into mutually
exclusive spaces that correspond to games with no Nash equilibria and with r Nash equilibria. In order to effectively compute the sizes of these spaces, we introduce the concept of top-rated preferences
minimal ordinal games. We then present a theorem which provides a mechanism for computing the number of games in each of these
mutually exclusive spaces, which then can be used to determine the probabilities. Finally, we summarize the results by deriving
the probabilities of existence of unique, nonunique, and no Nash equilibria, and we present an illustrative example. 相似文献
5.
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. 相似文献
6.
Wojciech Połowczuk Piotr Więcek Tadeusz Radzik 《Mathematical Methods of Operations Research》2007,65(1):141-152
This paper gives wide characterization of n-person non-coalitional games with finite players’ strategy spaces and payoff functions having some concavity or convexity
properties. The characterization is done in terms of the existence of two-point-strategy Nash equilibria, that is equilibria
consisting only of mixed strategies with supports being one or two-point sets of players’ pure strategy spaces. The structure
of such simple equilibria is discussed in different cases. The results obtained in the paper can be seen as a discrete counterpart
of Glicksberg’s theorem and other known results about the existence of pure (or “almost pure”) Nash equilibria in continuous
concave (convex) games with compact convex spaces of players’ pure strategies. 相似文献
7.
Shuige Liu 《Operations Research Letters》2018,46(3):273-277
This paper considers the directed graphical structure of a game, called influence structure, where a directed edge from player to player indicates that player may be able to affect ’s payoff via his unilateral change of strategies. We give a necessary and sufficient condition for the existence of pure-strategy Nash equilibrium of games having a directed graph in terms of the structure of that graph. We also discuss the relationship between the structure of graphs and potential games. 相似文献
8.
We examine n-player stochastic games. These are dynamic games where a play evolves in stages along a finite set of states; at each stage players independently have to choose actions in the present state and these choices determine a stage payoff to each player as well as a transition to a new state where actions have to be chosen at the next stage. For each player the infinite sequence of his stage payoffs is evaluated by taking the limiting average. Normally stochastic games are examined under the condition of full monitoring, i.e. at any stage each player observes the present state and the actions chosen by all players. This paper is a first attempt towards understanding under what circumstances equilibria could exist in n-player stochastic games without full monitoring. We demonstrate the non-existence of -equilibria in n-player stochastic games, with respect to the average reward, when at each stage each player is able to observe the present state, his own action, his own payoff, and the payoffs of the other players, but is unable to observe the actions of them. For this purpose, we present and examine a counterexample with 3 players. If we further drop the assumption that the players can observe the payoffs of the others, then counterexamples already exist in games with only 2 players. 相似文献
9.
一种n人静态博弈纯策略纳什均衡存在性判别法 总被引:6,自引:0,他引:6
本首先给出了n人静态博弈纯策略纳什均衡存在的充要条件。然后给出n人静态博弈纯策略纳什均衡存在性的一种判别方法。最后在判别纯策略纳什均衡存在的条件下,给出判定该静态博弈存在多少纯策略纳什均衡以及哪些纯策略组合是纯策略纳什均衡(解)的方法。 相似文献
10.
Gadi Moran 《Israel Journal of Mathematics》1973,14(4):418-441
Variants of two basic infinite games of perfect information are studied. A notion of continuous strategy for the playerS (Size) is shown to be related to a notion of convergence norm for sequences of reals. With each such norm, a variant of each
of the basic games is associated in which the size player has to see that each play obeys the norm. Restriction to choose
only rational numbers is also imposed onS. Some games are completely solved, and in this caseS has a winning strategy iff his set includes a perfect subset, andD has a winning strategy iffS's set is at most denumerable. Some other games, in whichS has to choose only rationals and obey a norm, induce a hierarchy structure on the class of nowhere dense perfect sets, that
is embedded cofinally in the lattice of infinite sequences of integers modulo finite differences. 相似文献
11.
12.
Quitting games are multi-player sequential games in which, at every stage, each player has the choice between continuing and quitting. The game ends as soon as at least one player chooses to quit; each player i then receives a payoff r
S
i, which depends on the set S of players that did choose to quit. If the game never ends, the payoff to each player is zero.? We exhibit a four-player
quitting game, where the “simplest” equilibrium is periodic with period two. We argue that this implies that all known methods
to prove existence of an equilibrium payoff in multi-player stochastic games are therefore bound to fail in general, and provide
some geometric intuition for this phenomenon.
Received: October 2001 相似文献
13.
Professor A. Kats 《International Journal of Game Theory》1974,3(4):251-260
A class of non-cooperative games is discussed in which one player (“the monopolist”) by choosing his strategy restricts the other players to subsets of their strategy sets. Examples of such games in various fields are given. In particular it is shown that some very important economic situations fall within this class of games. A solution concept is defined and sufficient conditions for its existence are derived. The question of the advantages a player derives from being a monopolist is raised and conditions are derived for him to benefit from being a monopolist. 相似文献
14.
Guilherme Carmona 《International Journal of Game Theory》2005,33(2):181-187
We study whether we can weaken the conditions given in Reny [4] and still obtain existence of pure strategy Nash equilibria in quasiconcave normal form games, or, at least, existence of pure strategy ɛ-equilibria for all ɛ>0. We show by examples that there are:1. quasiconcave, payoff secure games without pure strategy ɛ-equilibria for small enough ɛ>0 (and hence, without pure strategy Nash equilibria),2. quasiconcave, reciprocally upper semicontinuous games without pure strategy ɛ-equilibria for small enough ɛ>0, and3. payoff secure games whose mixed extension is not payoff secure.The last example, due to Sion and Wolfe [6], also shows that non-quasiconcave games that are payoff secure and reciprocally upper semicontinuous may fail to have mixed strategy equilibria.I wish to thank the editor, an associate editor and an anonymous referee for very helpful comments. I thank also John Huffstot for editorial assistance. Any remaining error is, of course, mine 相似文献
15.
《Optimization》2012,61(5):805-811
This paper treats of non-zero-sum discontinuous games with compact Hausdorff strategy spaces. It is assumed that the payoff function of each player in the game is bounded, Borel measurable and is upper semicontinuous on his strategy space, for all fixed actions of the remaining players. It is shown that for each ε>0, such games possess weakly correlated ε-epuilibria introduced by Moulin and Vial as extension of correlated equilibria in the sense of Aumann. An upper semicontinuous came having weakly correlated equilibria and no correlated equilibria is discussed in details. 相似文献
16.
Leeat Yariv 《International Journal of Game Theory》1997,26(2):229-234
We show that even when the information structure is independent of the state of nature, the value of then-stage zero-sum game with incomplete information is not necessarily monotonie with respect to the length of the game. More precisely, we give an example of such ann-stage game in whichV
1 >V
2 <V
3.I am very grateful to Ehud Lehrer who introduced this question to me. 相似文献
17.
《Operations Research Letters》2021,49(2):260-264
We consider two-player normal form games where each player has the same finite strategy set. The payoffs of each player are assumed to be i.i.d. random variables with a continuous distribution. We show that, with high probability, the better-response dynamics converges to pure Nash equilibrium whenever there is one, whereas best-response dynamics fails to converge, as it is trapped. 相似文献
18.
In a recent paper (Ref. 1), Papavassilopoulos obtained results on the probability of the existence of pure equilibrium solutions in stochastic matrix games. We report a similar result, but where the payoffs are drawn from a finite set of numbers N. In the limiting case, as N tends to infinity, our result and that of Papavassilopoulos are identical. We also cite similar results obtained independently by others, some of which were already independently brought to the notice of Papavassilopoulos by Li Calzi as reported in Papavassilopoulos (Ref. 2). We cite a much earlier result obtained by Goldman (Ref. 3). We also cite our related work (Ref. 4), in which we derive the conditions for the existence of mixed strategy equilibria in two-person zero-sum games. 相似文献
19.
We prove the existence of a subgame-perfect ε-equilibrium, for every ε > 0, in a class of multi-player games with perfect information, which we call free transition games. The novelty is that a non-trivial class of perfect information games is solved for subgame-perfection, with multiple non-terminating actions, in which the payoff structure is generally not (upper or lower) semi-continuous. Due to the lack of semi-continuity, there is no general rule of comparison between the payoffs that a player can obtain by deviating a large but finite number of times or, respectively, infinitely many times. We introduce new techniques to overcome this difficulty. 相似文献
20.
In this paper, we generalize the exitence result for pure strategy Nash equilibria in anonymous nonatomic games. By working directly on integrals of pure strategies, we also generalize, for the same class of games, the existence result for undominated pure strategy Nash equilibria even though, in general, the set of pure strategy Nash equilibria may fail to be weakly compact.
Received August 2001 相似文献