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.     

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.     

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.     

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.     

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.     

On multivariate antagonistic marked point processes

This paper investigates two bivariate “antagonistic” processes in the framework of noncooperative games that find applications in economics, engineering, and warfare. These processes represent two players with entirely opposite interests. Hostile actions, associating with one of the components (such as deliberate sellout of stocks of the opponent), take place at random times having a random effect to various vital areas. A consequence of these actions is material damage (such as financial losses) which is associated with the second component. So, in general, each player has two (dependent) ways of striking, while his opponent can sustain multiple damages (of two kinds and interdependent) until his threshold of endurance is reached. Then, the player is ruined. One of the goals is to predict the ruin time of each player as well as the collateral damage to the loser and winner at the ruin time. Furthermore, it is also of vital interest to relate these random elements to the continuous time parameter processes referred to as time sensitive analysis. We succeed in these goals by arriving at closed form joint functionals of the named elements and processes.     

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.     

A model of a 2-player stopping game with priority and asynchronous observation

Various models of 2-player stopping games have been considered which assume that players simultaneously observe a sequence of objects. Nash equilibria for such games can be found by first solving the optimal stopping problems arising when one player remains and then defining by recursion the normal form of the game played at each stage when both players are still searching (a 2 × 2 matrix game). The model considered here assumes that Player 1 always observes an object before Player 2. If Player 1 accepts the object, then Player 2 does not see that object. If Player 1 rejects an object, then Player 2 observes it and may choose to accept or reject it. It is shown that such a game can be solved using recursion by solving appropriately defined subgames, which are played at each moment when both players are still searching. In these subgames Player 1 chooses a threshold, such that an object is accepted iff its value is above this threshold. The strategy of Player 2 in this subgame is a stopping rule to be used when Player 1 accepts this object, together with a threshold to be used when Player 1 rejects the object. Whenever the payoff of Player 1 does not depend on the value of the object taken by Player 2, such a game can be treated as two optimisation problems. Two examples are given to illustrate these approaches.     

Avoider-Enforcer: The rules of the game

An Avoider-Enforcer game is played by two players, called Avoider and Enforcer, on a hypergraph F⊆X². The players claim previously unoccupied elements of the board X in turns. Enforcer wins if Avoider claims all vertices of some element of F, otherwise Avoider wins. In a more general version of the game a bias b is introduced to level up the players' chances of winning; Avoider claims one element of the board in each of his moves, while Enforcer responds by claiming b elements. This traditional set of rules for Avoider-Enforcer games is known to have a shortcoming: it is not bias monotone.We relax the traditional rules in a rather natural way to obtain bias monotonicity. We analyze this new set of rules and compare it with the traditional ones to conclude some surprising results. In particular, we show that under the new rules the threshold bias for both the connectivity and Hamiltonicity games, played on the edge set of the complete graph Kn, is asymptotically equal to n/logn. This coincides with the asymptotic threshold bias of the same game played by two “random” players.     

Product rule wins a competitive game

We consider a game that can be viewed as a random graph process. The game has two players and begins with the empty graph on vertex set . During each turn a pair of random edges is generated and one of the players chooses one of these edges to be an edge in the graph. Thus the players guide the evolution of the graph as the game is played. One player controls the even rounds with the goal of creating a so-called giant component as quickly as possible. The other player controls the odd rounds and has the goal of keeping the giant from forming for as long as possible. We show that the product rule is an asymptotically optimal strategy for both players.

     

连续对策上的计策问题

限定一个连续对策不是平凡地无意义（例如对某个局中人绝对有利等），我们提出了连续对策上的计策的基本概念。最后得到结论，如果局中人1使用经典对策，那么他的赢得期望必不是赢得函数的最大值。如果局中人1使用计策成功（即使得局中人2中计），那么局中人1必取得赢得函数的最大值，局中人2也有对偶的结果。     

A single-shot game of multi-period inspection

This paper deals with an inspection game of Customs and a smuggler during some days. Customs has two options of patrolling or not. The smuggler can take two strategies of shipping its cargo of contraband or not. Two players have several opportunities to take an action during a limited number of days but they may discard some of the opportunities. When the smuggling coincides with the patrol, there occurs one of three events: the capture of the smuggler by Customs, a success of the smuggling and nothing new. If the smuggler is captured or no time remains to complete the game, the game ends. There have been many studies on the inspection game so far by the multi-stage game model, where both players at a stage know players’ strategies taken at the previous stage. In this paper, we consider a two-person zero-sum single-shot game, where the game proceeds through multiple periods but both players do not know any strategies taken by their opponents on the process of the game. We apply dynamic programming to the game to exhaust all equilibrium points on a strategy space of player. We also clarify the characteristics of optimal strategies of players by some numerical examples.     

Asymptotic random graph intuition for the biased connectivity game

We study biased Maker/Breaker games on the edges of the complete graph, as introduced by Chvátal and Erd?s. We show that Maker, occupying one edge in each of his turns, can build a spanning tree, even if Breaker occupies b ≤ (1 ? o(1)) · edges in each turn. This improves a result of Beck, and is asymptotically best possible as witnessed by the Breaker‐strategy of Chvátal and Erd?s. We also give a strategy for Maker to occupy a graph with minimum degree c (where c = c(n) is a slowly growing function of n) while playing against a Breaker who takes b ≤ (1 ? o(1)) · edges in each turn. This result improves earlier bounds by Krivelevich and Szabó. Both of our results support the surprising random graph intuition: the threshold bias is asymptotically the same for the game played by two “clever” players and the game played by two “random” players. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Random walk in mixed random environment without uniform ellipticity

We study a random walk in random environment on ?₊. The random environment is not homogeneous in law, but is a mixture of two kinds of site, one in asymptotically vanishing proportion. The two kinds of site are (i) points endowed with probabilities drawn from a symmetric distribution with heavy tails at 0 and 1, and (ii) “fast points” with a fixed systematic drift. Without these fast points, the model is related to the diffusion in heavy-tailed (“stable”) random potential studied by Schumacher and Singh; the fast points perturb that model. The two components compete to determine the behaviour of the random walk; we identify phase transitions in terms of the model parameters. We give conditions for recurrence and transience and prove almost sure bounds for the trajectories of the walk.     

Limiting distributions of the number of pure strategy Nash equilibria in n-person games

We study the number of pure strategy Nash equilibria in a “random” n-person non-cooperative game in which all players have a countable number of strategies. We consider both the cases where all players have strictly and weakly ordinal preferences over their outcomes. For both cases, we show that the distribution of the number of pure strategy Nash equilibria approaches the Poisson distribution with mean 1 as the numbers of strategies of two or more players go to infinity. We also find, for each case, the distribution of the number of pure strategy Nash equilibria when the number of strategies of one player goes to infinity, while those of the other players remain finite.     

Absolutely expedient algorithms for learning Nash equilibria

This paper considers a multi-person discrete game with random payoffs. The distribution of the random payoff is unknown to the players and further none of the players know the strategies or the actual moves of other players. A class of absolutely expedient learning algorithms for the game based on a decentralised team of Learning Automata is presented. These algorithms correspond, in some sense, to rational behaviour on the part of the players. All stable stationary points of the algorithm are shown to be Nash equilibria for the game. It is also shown that under some additional constraints on the game, the team will always converge to a Nash equilibrium. Dedicated to the memory of Professor K G Ramanathan     

Single-suit two-person card play

We consider a two-person constant sum perfect information game, which we call theEnd Play Game, which arises from an abstraction of simple end play positions in card games of the whist family, including bridge. This game was described in 1929 by Emanuel Lasker, the mathematician and world chess champion, who called itwhistette. The game uses a deck of cards that consists of a single totally ordered suit of 2n cards. To begin play the deck is divided into two handsA andB ofn cards each, held by players Left and Right, and one player is designated as having thelead. The player on lead chooses one of his cards, and the other player after seeing this card selects one of his own to play. The player with the higher card wins a “trick” and obtains the lead. The cards in the trick are removed from each hand, and play then continues until all cards are exhausted. Each player strives to maximize his trick total, and thevalue of the game to each player is the number of tricks he takes. Despite its simple appearance, this game is quite complicated, and finding an optimal strategy seems difficult. This paper derives basic properties of the game, gives some criteria under which one hand is guaranteed to be better than another, and determines the optimal strategies and value functions for the game in several special cases.     

Non-cooperative games with minmax objectives

We consider noncooperative games where each player minimizes the sum of a smooth function, which depends on the player, and of a possibly nonsmooth function that is the same for all players. For this class of games we consider two approaches: one based on an augmented game that is applicable only to a minmax game and another one derived by a smoothing procedure that is applicable more broadly. In both cases, centralized and, most importantly, distributed algorithms for the computation of Nash equilibria can be derived.     

Games of timing with resources of mixed type

The paper considers a game of timing which is closely related to the so-called duels. This is a game connected with the distribution of resources by two players. Each of the players is in possession of some amount of resource to be distributed by him in the time interval [0, 1]. In his behavior, Player 1 is restricted by the necessity of taking all of his resources at a single point, while Player 2 has no restrictions. For the payoff function, defined as for duels, the game is solved; explicit formulas on the value of the game and the optimal strategies for the players are found.     

连续对策的公平性和刺激性

本文用刺激性(感)来描述游戏一个零和对策的两个局中人的风险性和侥幸取胜性,游戏不同的零和对策可能有不同的刺激感,刺激性越大,对策结果的公平性越小;反之亦然,本文解决了如下问题;(1)刺激性和公平性的数学描述是什么?(2)局中人如何保证他们的一局对策的对策结果是最公平的或最有刺激感的?(3)如果两个局中人希望对策结果尽量公平或尽量有刺激感,他们最好从给定的连续对策中选择哪个?