Publications by Type: Journal Articles

In Press
Hansen KA, Ibsen-Jensen R, Neyman A. The Big Match with a clock and a bit of memory. Mathematics of Operations Research. Accepted for publication. In Press.Abstract

The Big Match is a multi-stage two-player game. In each stage Player 1 hides one or two pebbles in his hand, and his opponent has to guess that number; Player 1 loses a point if Player 2 is correct, and otherwise he wins a point. As soon as Player 1 hides one pebble, the players cannot change their choices in any future stage.
The undiscounted Big Match has been much-studied. Blackwell and Ferguson (1968) give an epsilon-optimal
strategy for Player 1 that hides, in each stage, one pebble with a probability that depends on the entire past history. Any strategy that depends on just the clock or just a finite memory is worthless (i.e., cannot guarantee strictly more than the least reward). The long-standing natural open problem has been whether every strategy that depends on just the clock and a nite memory is worthless.
The present paper proves that there is such a strategy that is epsilon-optimal. In fact, we show that just two states of memory are sfficient.

accepted_version
Submitted
Hansen KA, Ibsen-Jensen R, Neyman A. Absorbing games with a clock and two bits of memory. Submitted.Abstract

 An absorbing game is a two-person zero-sum repeated game. Some of the entries are ``absorbing'' in the sense that, following the play of an absorbing entry, with positive probability all future payoffs are equal to that entry's payoff. The outcome of the game is the long-run average payoff.
 We prove that a two-person zero-sum absorbing game, with either finite or compact action sets, has, for each e>0, e-optimal strategies with finite memory. In fact, we show that there is an e-optimal strategy that depends on the clock and three states of memory.

submitted_paper_2020.pdf
Kohlberg E, Neyman A. Cooperative Strategic Games. Submitted. Paper. Revised.
2018
Kohlberg E, Neyman A. Games of Threats. Games and Economic Behavior [Internet]. 2018;108 :139--145. Publisher's VersionAbstract

A game of threats on a finite set of players, N, is a function d that assigns a real number to any coalition, S⊆N, such that d(S)=−d(N∖S). A game of threats is not necessarily a coalitional game as it may fail to satisfy the condition d(∅)=0. We show that analogs of the classic Shapley axioms for coalitional games determine a unique value for games of threats. This value assigns to each player an average of d(S) across all the coalitions that include the player. Games of threats arise naturally in value theory for strategic games, and may have applications in other branches of game theory.

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
Neyman A. Continuous-Time Stochastic Games. Games and Economic Behavior [Internet]. 2017;104 :92-130. Publisher's Version 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

Pages