Publications by Type: Journal Article

In Press
Neyman A. Continuous-Time Stochastic Games. Revised version. Games and Economic Behavior. In Press. Paper
2017
Neyman A, Kohlberg E. Cooperative Strategic Games. The Federmann Center for the Study of Rationality, Hebrew University. 2017;DP 706.Abstract

 

We examine a solution concept, called the ``value," for n-person strategic games.

In applications, the value provides an a-priori assessment of the monetary worth of a player's position in a strategic game, comprising not only the player's contribution to the total payoff but also the player's ability to inflict losses on other players.  A salient feature is that the value takes account of the costs that ``spoilers" impose on themselves.

Our main result is an axiomatic characterization of the value.

For every subset, S, consider the zero-sum game played between S and its complement, where the players in each of these sets collaborate as a single player, and where the payoff is the difference between the sum of the payoffs to the players in S and the sum of payoffs to the players not in S.   We say that S has an effective threat if the minmax value of this game is positive. The first axiom is that if no subset of players has an effective threat then all players are allocated the same amount.

The second axiom is that if the overall payoff to the players in a game is the sum of their payoffs in two unrelated games then the overall value is the sum of the values in these two games.

The remaining axioms are the strategic-game analogs of the classical coalitional-games axioms for the Shapley value:  efficiency, symmetry, and null player.

 

Paper
2014
Neyman A, Bavly G. Online Concealed Correlation and Bounded Rationality. Games and Economic Behavior. 2014 : 71 - 89.Abstract

Correlation of players’ actions may evolve in the common course of the play of a repeated game with perfect monitoring (“online correlation”). In this paper we study the concealment of such correlation from a boundedly rational player. We show that “strong” players, i.e., players whose strategic complexity is less stringently bounded, can orchestrate the online correlation of the actions of “weak” players, where this correlation is concealed from an opponent of “intermediate” strength. The feasibility of such “online concealed correlation” is reflected in the individually rational payoff of the opponent and in the equilibrium payoffs of the repeated game. This result enables the derivation of a folk theorem that characterizes the set of equilibrium payoffs in a class of repeated games with boundedly rational players and a mechanism designer who sends public signals. The result is illustrated in two models, bounded recall strategies and finite automata.

Paper
2013
Neyman A. Stochastic Games with Short-Stage Duration. Dyn Games Appl. 2013;3 :236-278.Abstract

We introduce asymptotic analysis of stochastic games with short-stage duration. The play of stage k, $k\geq 0$, of a stochastic game $\Gamma_\delta$ with stage duration $\delta$ is interpreted as the play in time $k\delta\leq t<(k+1)\delta$, and therefore the average payoff of the $n$-stage play per unit of time is the sum of the payoffs in the first $n$ stages divided by $n\delta$, and the $\lambda$-discounted present value of a payoff $g$ in stage $k$ is $\lambda^{k\delta} g$. We define convergence, strong convergence, and exact convergence of the data of a family $(\Gamma_\delta)_{\delta>0}$ as the stage duration $\delta$ goes to $0$, and study the asymptotic behavior of the value, optimal strategies, and equilibrium. The asymptotic analogs of the discounted, limiting-average, and uniform equilibrium payoffs are defined. Convergence implies the existence of an asymptotic discounted equilibrium payoff, strong convergence implies the existence of an asymptotic limiting-average equilibrium payoff, and exact convergence implies the existence of an asymptotic uniform equilibrium payoff.

paper
Neyman A. The Maximal Variation of Martingales of Probabilities and Repeated Games with Incomplete Information. Journal of Theoretical Probability. 2013 :557-567.Abstract

The variation of a martingale m[k] of k+1 probabilities p(0),...,p(k) on a finite (or countable) set X is the expectation of the sum of ||p(t)-p(t-1)|| (the L one norm of the martingale differences p(t)-p(t-1)), and is denoted V(m[k]). It is shown that V(m[k]) is less than or equal to the square root of 2kH(p(0)), where H(p) is the entropy function (the some over x in X of p(x)log p(x) and log stands for the natural logarithm. Therefore, if d is the number of elements of X, then V(m[k]) is less than or equal to the square root of 2k(log d). It is shown that the order of magnitude of this bound is tight for d less than or equal to 2 to the power k: there is C>0 such that for every k and d less than or equal to 2 to the power k there is a martingale m[k]=p(0),...,p(k) of probabilities on a set X with d elements, and with variation V(m[k]) that is greater or equal the square root of Ck(log d). It follows that the difference between the value of the k-stage repeated game with incomplete information on one side and with d states, denoted v(k), and the limit of v(k), as k goes to infinity, is bounded by the maximal absolute value of a stage payoff times the square root of 2(log d)/k, and it is shown that the order of magnitude of this bound is tight.

paper
2012
Neyman A. The Value of Two-Person Zero-Sum Repeated Games with Incomplete Information and Uncertain Duration. International Journal of Game Theory. 2012;41 :195-207.Abstract

It is known that the value of a zero-sum infinitely repeated game with incomplete information on both sides need not exist. It is proved that any number between the minmax and the maxmin of the zero-sum infinitely repeated game with incomplete information on both sides is the value of the long finitely repeated game where players' information about the uncertain number of repetitions is asymmetric.

Paper
2010
Neyman A. Singular Games in bv'NA. Journal of Mathematical Economics. 2010 :384 - 387.Abstract

Every simple game in bv'NA is a weighted majority game, and every game in bv'NA is a sume of a game in pNA and a convergent series of singular scalar measure games.

Paper
Neyman A, Spencer J. Complexity and Effective Prediction. Games and Economic Behavior. 2010 :165-168.Abstract

Let G = be a two-person zero-sum game. We examine the two-person zero-sum repeated game G(k,m) in which players 1 and 2 place down finite state automata with k,m states respectively and the payoff is the average per-stage payoff when the two automata face off. We are interested in the cases in which player 1 is “smart” in the sense that k is large but player 2 is “much smarter” in the sense that m>>k. Let S(g) be the value of G where the second player is clairvoyant, i.e., would know the player 1’s move in advance. The threshold for clairvoyance is shown to occur for m near min(|I|, | J |) to the power k. For m of roughly that size, in the exponential scale, the value is close to S(g). For m significantly smaller (for some stage payoffs g) the value does not approach S(g).

Paper
Neyman A, Sorin S. Repeated Games with Public Uncertain Duration Process. International Journal of Game Theory. 2010 :29-52.Abstract

We consider repeated games where the number of repetitions u is unknown. The information about the uncertain duration can change during the play of the game. This is described by an uncertain duration process U that defines the probability law of the signals that players receive at each stage about the duration. To each repeated game G and uncertain duration process U is associated the U-repeated game G(U). A public uncertain duration process is one where the uncertainty about the duration is the same for all players. We establish a recursive formula for the value V_U of a repeated two-person zero-sum game G(U) with a public uncertain duration process U. We study asymptotic properties of the normalized value v_U = V_U/E(u) as the expected duration E(u) goes to infinity. We extend and unify several asymptotic results on the existence of lim v_n and lim v_ë and their equality to lim v_U. This analysis applies in particular to stochastic games and repeated games of incomplete information.

Paper
2009
Neyman A, Mertens JF, Rosenberg D. Absorbing Games with Compact Action Spaces. Mathematics of Operations Research. 2009;34 :257-262.Abstract

We prove that games with absorbing states with compact action sets have a value.

Paper
Neyman A, Okada D. Growth of Strategy Sets, Entropy, and Nonstationary Bounded Recall. Games and Economic Behavior. 2009 :404-425.Abstract

The paper initiates the study of long term interactions where players’ bounded rationality varies over time. Time dependent bounded rationality, for player i, is reflected in part in the number ψi(t) of distinct strategies available to him in the first t-stages. We examine how the growth rate of ψi(t) affects equilibrium outcomes of repeated games. An upper bound on the individually rational payoff is derived for a class of two-player repeated games, and the derived bound is shown to be tight. As a special case we study the repeated games with nonstationary bounded recall and show that, a player can guarantee the minimax payoff of the stage game, even against a player with full recall, by remembering a vanishing fraction of the past. A version of the folk theorem is provided for this class of games

paper
2008
Neyman A. Existence of Optimal Strategies in Markov Games with Incomplete Information. International Journal of Game Theory. 2008 :581 - 596.Abstract

The existence of a value and optimal strategies is proved for the class of two-person repeated games where the state follows a Markov chain independently of players' actions and at the beginning of each stage only player one is informed about the state. The results apply to the case of standard signaling where players' stage actions are observable, as well as to the model with general signals provided that player one has a nonrevealing repeated game strategy. The proofs reduce the analysis of these repeated games to that of classical repeated games with incomplete information on one side.

Paper
2006
Neyman A. Aumann Awarded Nobel Prize. Notices of the AMS. 2006;53 :44 - 46. aumann.pdf
Neyman A, Gossner O, Hernandez P. Optimal Use of Communication Resources. Econometrica. 2006 :1603 - 1636.Abstract

We study a repeated game with asymmetric information about a dynamic state of nature. In the course of the game, the better informed player can communicate some or all of his information with the other. Our model covers costly and/or bounded communication. We characterize the set of equilibrium payoffs, and contrast these with the communication equilibrium payffs, which by definition entail no communication costs.

Paper
2004
Neyman A, Smordinsky R. Asymptotic Values of Vector Measure Games. Mathematics of Operations Research. 2004 :739 - 775.Abstract

The asymptotic value, introduced by Kannai in 1966, is an asymptotic approach to the notion of the Shapley value for games with infinitely many players. A vector measure game is a game v where the worth v(S) of a coalition S is a function f of u(S) where u is a vector measure. Special classes of vector measure games are the weighted majority games and the two-house weighted majority games, where a two-house weighted majority game is a game in which a coalition is winning if and only if it is winning in two given weighted majority games. All weighted majority games have an asymptotic value. However, not all two-house weighted majority games have an asymptotic value. In this paper, we prove that the existence of infinitely many atoms with sufficient variety suffice for the existence of the asymptotic value in a general class of nonsmooth vector measure games that includes in particular two-house weighted majority games.

Paper
Neyman A, Olivier G, Hernandez P. Dynamiques de Communication. Dynamiques de Communication. 2004;55 :509 - 516. revue.zip
2003
Neyman A, Mertens JF. A value on `AN. International Journal of Game Theory. 2003 : 109-120.Abstract

We prove here the existence of a value (of norm 1) on the spaces 'NA and even 'AN, the closure in the variation distance of the linear space spanned by all games f°µ, where µ is a non-atomic, non-negative finitely additive measure of mass 1 and f a real-valued function on [0,1] which satisfies a much weaker continuity at zero and one.

Paper
2001
Neyman A. Values of Non-Atomic Vector Measure Games. Israel Journal of Mathematics. 2001;124 :1-27.Abstract

Much of economic theory is concerned with the existence of prices. In particular, economists are interested in whether various outcomes defined by diverse postulates turn out to be actually generated by prices. Whenever this is the case, a theory of endogenous price formation is derived. In the present analysis, a well-known game-theoretic solution concept is considered: value. Nonatomic games are considered that are defined by finitely many nonnegative measures. Nonatomic vector measure games arise, for example, from production models and from finite-type markets. It is shown that the value of such a game need not be a linear combination of the nonatomic nonnegative measures. This is in contrast to all the values known to date. Moreover, this happens even for certain differentiable market games. In the economic models, this means that the value allocations are not necessarily produced by prices. All the examples presented are special cases of a new class of values.

Paper
2000
Neyman A, Okada D. Repeated games with bounded entropy. Games and Economic Behavior. 2000;30 :228--247.Abstract

We investigate the asymptotic behavior of the maxmin values of repeated two-person zero-sum games with a bound on the strategic entropy of the maximizer's strategies while the other player is unrestricted. We will show that if the bound (n), a function of the number of repetitions n, satisfies the condition (n)/n (n), then the maxmin value Wn ((n)) converges to (cavU)(), the concavification of the maxmin value of the stage game in which the maximizer's actions are restricted to those with entropy at most . A similar result is obtained for the infinitely repeated games.

Paper
Neyman A, Okada D. Two-person repeated games with finite automata. International Journal of Game Theory. 2000;29 :309--325.Abstract

We study two-person repeated games in which a player with a restricted set of strategies plays against an unrestricted player. An exogenously given bound on the complexity of strategies, which is measured by the size of the smallest automata that implement them, gives rise to a restriction on strategies available to a player. We examine the asymptotic behavior of the set of equilibrium payoffs as the bound on the strategic complexity of the restricted player tends to infinity, but sufficiently slowly. Results from the study of zero sum case provide the individually rational payoff levels.

Paper

Pages