Kohlberg E, Neyman A. Cooperative Strategic Games. Submitted. Paper. Revised.
Kohlberg E, Neyman A. Games of Threats. Accepted manuscript. Games and Economic Behavior. Forthcoming. got_accepted_geb_paper.pdf
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.


Neyman A. Continuous-Time Stochastic Games. . Games and Economic Behavior [Internet]. 2017;104 :92-130. Publisher's Version ctsg_publised_copy.pdf
Neyman A, Kohlberg E. The Cooperative Solution of Stochastic Games. 2015.Abstract

Building on the work of Nash, Harsanyi, and Shapley, we define a cooperative solution for strategic games that takes account of both the competitive and the cooperative aspects of such games. We prove existence in the general (NTU) case and uniqueness in the TU case. Our main result is an extension of the definition and the existence and uniqueness theorems to stochastic games - discounted or undiscounted.

Neyman A, Levinsky R, ZELENY MIROSLAV. Should I Remember more than you?? – on the best response to factored based strategies. 2014.Abstract

In this paper we offer a new approach to modeling strategies of bounded complexity, the so-called factor-based strategies. In our model, the strategy of a player in the multi-stage game does not directly map the set of histories H to the set of her actions. Instead, the player’s perception of H is represented by a factor ϕ : H → X, where X reflects the “cognitive complexity” of the player. Formally, mapping ϕ sends each history to an element of a factor space X that represents its equivalence class. The play of the player can then be conditioned just on the elements of the set X. From the perspective of the original multi-stage game we say that a function ϕ from H to X is a factor of a strategy σ if there exists a function ω from X to the set of actions of the player such that σ = ω ◦ ϕ. In this case we say that the strategy σ is ϕ-factorbased. Stationary strategies and strategies played by finite automata and strategies with bounded recall are the most prominent examples of factor-based strategies. In the discounted infinitely repeated game with perfect monitoring, a best reply to a profile of ϕ-factor-based strategies need not be a ϕ-factor-based strategy. However, if the factor ϕ is recursive, namely, its value ϕ(a(1), . . . , a(t)) on a finite string of action profiles (a(1), . . . , a(t)) is a function of ϕ(a(1), . . . , a(t−1)) and at, then for every profile of factor-based strategies there is a best reply that is a pure factor-based strategy. We also study factor-based strategies in the more general case of stochastic games.

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.

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.

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.

Neyman A. Continuous-Time Stochastic Games. 2012.Abstract

Every continuous-time stochastic game with finitely many states and actions has a uniform and limiting-average equilibrium payoff.

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.

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.

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).

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.

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.

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

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.

Neyman A. Learning Effectiveness and Memory Size. Center for the Study of Rationality, Hebrew University. 2008;DP 476. Paper
Neyman A, Russo T. Public Goods and Budget Deficit. Center for the Study of Rationality, Hebrew University. 2006.Abstract

We examine incentive-compatible mechanisms for fair financing and efficient selection of a public budget (or public good). A mechanism selects the level of the public budget and imposes taxes on individuals. Individuals' preferences are quasilinear. Fairness is expressed as weak monotonicity (called scale monotonicity) of the tax imposed on an individual as a function of his benefit from an increased level of the public budget. Efficiency is expressed as selection of a Pareto-optimal level of the public budget. The budget deficit is the difference between the public budget and the total amount of taxes collected from the individuals. We show that any efficient scale-monotonic and incentive-compatible mechanism may generate a budget deficit. Moreover, it is impossible to collect taxes that always cover a fixed small fraction of the total cost.

Neyman A. Aumann Awarded Nobel Prize. Notices of the AMS. 2006;53 :44 - 46. aumann.pdf