Publications

Working Paper
Kohlberg E. Demystifying the Math of the Coronavirus.; Working Paper.Abstract

We provide an elementary mathematical description of the spread of the coronavirus. We explain two fundamental relationships: How the rate of growth in new infections is determined by the “effective reproductive number”; and how the effective reproductive number is affected by social distancing. By making a key approximation, we are able to formulate these relationships very simply and thereby avoid complicated mathematics. The same approximation leads to an elementary method for estimating the effective eproductive
number.

05212020_demistyfying_the_math_of_the_coronavirus.pdf
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
2015
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.

Paper
2014
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.

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

Paper
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

Pages