Layers of noncooperative games

We model and analyze classes of antagonistic stochastic games of two players. The actions of the players are formalized by marked point processes recording the cumulative damage to the players at any moment of time. The processes evolve until one of the processes crosses its fixed preassigned threshold of tolerance. Once the threshold is reached or exceeded at some point of the time (exit time), the associated player is ruined. Both stochastic processes are being “observed” by a third party point stochastic process, over which the information regarding the status of both players is obtained. We succeed in these goals by arriving at closed form joint functionals of the named elements and processes. Furthermore, we also look into the game more closely by introducing an intermediate threshold (see a layer), which a losing player is to cross prior to his ruin, in order to analyze the game more scrupulously and see what makes the player lose the game.     

Tandem antagonistic games

We study an antagonistic sequential game of two players that undergoes two phases. Each phase is modeled by multi-dimensional random walk processes. During phase 1 (or game 1), the players exchange a series of random strikes of random magnitudes. Game 1 ends whenever one of the players sustains damages in excess of some lower threshold. However, the total damage does not exceed another upper threshold which allows the game to continue. Phase 2 (game 2) is run by another combination of random walk processes. At some point of phase 2, one of the players, after sustaining damages in excess of its third threshold, is ruined and he loses the entire game. We predict that moment, along with the total casualties to both players, and other critical information; all in terms of tractable functionals. The entire game is analyzed by tools of fluctuation theory.     

A BSDE approach to stochastic differential games with incomplete information

We consider a two-player zero-sum stochastic differential game in which one of the players has a private information on the game. Both players observe each other, so that the non-informed player can try to guess his missing information. Our aim is to quantify the amount of information the informed player has to reveal in order to play optimally: to do so, we show that the value function of this zero-sum game can be rewritten as a minimization problem over some martingale measures with a payoff given by the solution of a backward stochastic differential equation.     

A new rating system for duplicate bridge

We propose a new way to rate individual duplicate bridge players, which we believe is superior to the masterpoint system currently used by the American Contract Bridge League. This method measures only a player’s current skill level, and not how long or how frequently he has played. It is based on simple ideas from the theory of statistics and from linear algebra, and should be easy to implement.One particular issue which can occur within any system proposing to rate individual players using results earned by partnerships is what we call the “nonuniqueness problem”. This refers to the occasional inability for data to distinguish who is the “good player” and who is the “bad player” within particular partnerships. We prove that under our system this problem disappears if either (a) a certain “partnership graph” has no bipartite components, or if (b) every player is required to participate in at least one individual game.Finally, we present some data from a bridge club in Reno, NV. They show that even if (a) and (b) do not hold, our system will provide (unique) ratings for most players.     

On finite tetraprimary groups

A three-player game is considered in which the first and second players have dynamic superiority over the third player. Two fixed time points are specified. The game ends if either the first player captures the third player at the first time point, or the second player captures the third player at the second time point. We analyze a situation when the initial positions in the game are such that neither the first nor the second player alone can capture the third player at the specified points of time. We propose sufficient conditions on the parameters of the game under which, for given initial states of the players, the first and second players by applying some controls can guarantee that one of them will meet the third player at the prescribed moment. Simulation results for a model example are also presented.     

Random Walk Analysis in Antagonistic Stochastic Games

Abstract

This article deals with two “antagonistic random processes” that are intended to model classes of completely noncooperative games occurring in economics, engineering, natural sciences, and warfare. In terms of game theory, these processes can represent two players with opposite interests. The actions of the players are manifested by a series of strikes of random magnitudes imposed onto the opposite side and rendered at random times. Each of the assaults is aimed to inflict damage to vital areas. In contrast with some strictly antagonistic games where a game ends with one single successful hit, in the current setting, each side (player) can endure multiple strikes before perishing. Each player has a fixed cumulative threshold of tolerance which represents how much damage he can endure before succumbing. Each player will try to defeat the adversary at his earliest opportunity, and the time when one of them collapses is referred to as the “ruin time”. We predict the ruin time of each player, and the cumulative status of all related components for each player at ruin time. The actions of each player are formalized by a marked point process representing (an economic) status of each opponent at any given moment of time. Their marks are assumed to be weakly monotone, which means that each opposite side accumulates damages, but does not have the ability to recover. We render a time-sensitive analysis of a bivariate continuous time parameter process representing the status of each player at any given time and at the ruin time and obtain explicit formulas for related functionals.     

On noncooperative hybrid stochastic games

The present article models and analyzes a noncooperative hybrid stochastic game of two players. The main phase (prime hybrid mode) of the game is preceded by “unprovoked” hostile actions by one of the players (during antecedent hybrid mode) that at some time transforms into a large scale conflict between two players. The game lasts until one of the players gets ruined. The latter occurs when the cumulative damage to the losing player exceeds a fixed threshold. Both hybrid modes are formalized by marked point stochastic processes and the theory of fluctuations is utilized as one of the chief techniques to arrive at a closed form functional describing the status of both players at the ruin time.     

Asymptotic results for time-changed Lévy processes sampled at hitting times

We provide asymptotic results for time-changed Lévy processes sampled at random instants. The sampling times are given by the first hitting times of symmetric barriers, whose distance with respect to the starting point is equal to ε. For a wide class of Lévy processes, we introduce a renormalization depending on ε, under which the Lévy process converges in law to an α-stable process as ε goes to 0. The convergence is extended to moments of hitting times and overshoots. These results can be used to build high frequency statistical procedures. As examples, we construct consistent estimators of the time change and, in the case of the CGMY process, of the Blumenthal-Getoor index. Convergence rates and a central limit theorem for suitable functionals of the increments of the observed process are established under additional assumptions.     

Average-discounted equilibria in stochastic games

In stochastic games with finite state and action spaces, we examine existence of equilibria where player 1 uses the limiting average reward and player 2 a discounted reward for the evaluations of the respective payoff sequences. By the nature of these rewards, the far future determines player 1's reward, while player 2 is rather interested in the near future. This gives rise to a natural cooperation between the players along the course of the play. First we show the existence of stationary ε-equilibria, for all ε>0, in these games. However, besides these stationary ε-equilibria, there also exist ε-equilibria, in terms of only slightly more complex ultimately stationary strategies, which are rather in the spirit of these games because, after a large stage when the discounted game is not interesting any longer, the players cooperate to guarantee the highest feasible reward to player 1. Moreover, we analyze an interesting example demonstrating that 0-equilibria do not necessarily exist in these games, not even in terms of history dependent strategies. Finally, we examine special classes of stochastic games with specific conditions on the transition and payoff structures. Several examples are given to clarify all these issues.     

Van der waerden and ramsey type games

Let us consider the following 2-player game, calledvan der Waerden game. The players alternately pick previously unpicked integers of the interval {1, 2, ...,N}. The first player wins if he has selected all members of ann-term arithmetic progression. LetW*(n) be the least integerN so that the first player has a winning strategy. By theRamsey game on k-tuples we shall mean a 2-player game where the players alternately pick previously unpicked elements of the completek-uniform hypergraph ofN verticesK _N ^k , and the first player wins if he has selected allk-tuples of ann-set. LetR _k*(n) be the least integerN so that the first player has a winning strategy. We prove (W* (n))¹/n → 2,R ₂*(n)<(2+ε) ⁿ andR _k ^* n<2 ^nk / ^k! fork ≧3.     

The Liar Game Over an Arbitrary Channel

We introduce and analyze a liar game in which t-ary questions are asked and the responder may lie at most k times. As an additional constraint, there is an arbitrary but prescribed list (the channel) of permissible types of lies. For any fixed t, k, and channel, we determine the exact asymptotics of the solution when the number of queries goes to infinity.     

Zero-sum constrained stochastic games with independent state processes

We consider a zero-sum stochastic game with side constraints for both players with a special structure. There are two independent controlled Markov chains, one for each player. The transition probabilities of the chain associated with a player as well as the related side constraints depend only on the actions of the corresponding player; the side constraints also depend on the player’s controlled chain. The global cost that player 1 wishes to minimize and that player 2 wishes to maximize, depend however on the actions and Markov chains of both players. We obtain a linear programming formulations that allows to compute the value and saddle point policies for this problem. We illustrate the theoretical results through a zero-sum stochastic game in wireless networks in which each player has power constraints     

Static search games played over graphs and general metric spaces

We define a general game which forms a basis for modelling situations of static search and concealment over regions with spatial structure. The game involves two players, the searching player and the concealing player, and is played over a metric space. Each player simultaneously chooses to deploy at a point in the space; the searching player receiving a payoff of 1 if his opponent lies within a predetermined radius r of his position, the concealing player receiving a payoff of 1 otherwise. The concepts of dominance and equivalence of strategies are examined in the context of this game, before focusing on the more specific case of the game played over a graph. Methods are presented to simplify the analysis of such games, both by means of the iterated elimination of dominated strategies and through consideration of automorphisms of the graph. Lower and upper bounds on the value of the game are presented and optimal mixed strategies are calculated for games played over a particular family of graphs.     

Stein’s method for invariant measures of diffusions via Malliavin calculus

Given a random variable F$F$ regular enough in the sense of the Malliavin calculus, we are able to measure the distance between its law and any probability measure with a density function which is continuous, bounded, strictly positive on an interval in the real line and admits finite variance. The bounds are given in terms of the Malliavin derivative of F$F$. Our approach is based on the theory of Itô diffusions and the stochastic calculus of variations. Several examples are considered in order to illustrate our general results.     

On the Besov regularity of periodic Lévy noises

In this paper, we study the Besov regularity of Lévy white noises on the d-dimensional torus. Due to their rough sample paths, the white noises that we consider are defined as generalized stochastic fields. We, initially, obtain regularity results for general Lévy white noises. Then, we focus on two subclasses of noises: compound Poisson and symmetric-α-stable (including Gaussian), for which we make more precise statements. Before measuring regularity, we show that the question is well-posed; we prove that Besov spaces are in the cylindrical σ-field of the space of generalized functions. These results pave the way to the characterization of the n-term wavelet approximation properties of stochastic processes.     

A dynamic solution in N-person cooperative game theory

We formulate a cooperative game as an extended form game in which each player in turn proposes payoffs to a coalition over M steps. Payoffs at time t are discounted by a penalty function f(t). If all players in a coalition agree to their payoffs, they receive them. Under a convergence hypothesis verified by computer for three players in many cases, we compute the payoffs resulting from a coalition pattern and give necessary conditions for particular patterns. The resulting solution is related to the Nash bargaining solution and the competitive solution.     

Multilayers in a modulated stochastic game

We are concerned with an antagonistic stochastic game between two players A and B which finds applications in economics and warfare. The actions of the players are manifested by a series of strikes of random magnitudes at random times exerted by each player against his opponent. Each of the assaults inflicts a random damage to enemy's vital areas. In contrast with traditional games, in our setting, each player can endure multiple strikes before perishing. Predicting the ruin time (exit) of player A, along with the total amount of casualties to both players at the exit is a main objective of this work. In contrast to the time sensitive analysis (earlier developed to refine the information on the game) we insert auxiliary control levels, which both players will cross in due game before the ruin of A. This gives A (and also B) an additional opportunity to reevaluate his strategy and change the course of the game. We formalize such a game and also allow the real time information about the game to be randomly delayed. The delayed exit time, cumulative casualties to both players, and prior crossings are all obtained in a closed-form joint functional.     

The contiguity of probability measures and asymptotic inference in continuous time stationary diffusions and Gaussian processes with known covariance

We establish contiguity of families of probability measures indexed by T, as T → ∞, for classes of continuous time stochastic processes which are either stationary diffusions or Gaussian processes with known covariance. In most cases, and in all the examples we consider in Section 4, the covariance is completely determined by observing the process continuously over any finite interval of time. Many important consequences pertaining to properties of tests and estimators, outlined in Section 5, will then apply.     

Quasi-stationary distributions and Yaglom limits of self-similar Markov processes

We discuss the existence and characterization of quasi-stationary distributions and Yaglom limits of self-similar Markov processes that reach 0 in finite time. By Yaglom limit, we mean the existence of a deterministic function g$g$ and a non-trivial probability measure ν$\nu$ such that the process rescaled by g$g$ and conditioned on non-extinction converges in distribution towards ν$\nu$. We will see that a Yaglom limit exists if and only if the extinction time at 0$0$ of the process is in the domain of attraction of an extreme law and we will then treat separately three cases, according to whether the extinction time is in the domain of attraction of a Gumbel, Weibull or Fréchet law. In each of these cases, necessary and sufficient conditions on the parameters of the underlying Lévy process are given for the extinction time to be in the required domain of attraction. The limit of the process conditioned to be positive is then characterized by a multiplicative equation which is connected to a factorization of the exponential distribution in the Gumbel case, a factorization of a Beta distribution in the Weibull case and a factorization of a Pareto distribution in the Fréchet case.     

Stopping for two-dimensional stochastic processes

The aim of this paper is to introduce some techniques that can be used in the study of stochastic processes which have as parameter set the positive quadrant of the plane R²₊. We define stopping lines and derive an interesting property of measurability for them. The notion of predictability is developed, and we show the connection between predictable processes, fields associated with stopping lines, and predictable stopping lines. We also give a theorem of section for predictable sets. Extension to processes indexed by any partially ordered set with some regularity assumptions can be carried out quite easily with the same techniques.