Accumulation Games,Part 1: Noisy Search

In an accumulation game, a hider places objects at locations, and a seeker examines these locations. If the seeker discovers an object, the seeker confiscates it. The goal of the hider is to accumulate a certain number of objects before a given time, and the goal of the seeker is to prevent this. In this paper, we first classify various possible variations on the accumulation game. Next, we discuss the so-called noisy accumulation game in which the hider can observe each action of the seeker. We present the solution of this game for all but some marginal cases and illustrate it with computational examples.     

Continuous Accumulation Games in Continuous Regions

In a continuous accumulation game on a continuous region, a Hider distributes material over a continuous region at each instant of discrete time, and a Seeker examines the region. If the Seeker locates any of the material hidden, the Seeker confiscates it. The goal of the Hider is to accumulate a certain amount of material before a given time, and the goal of the Seeker is to prevent this. In previous works, we have studied accumulation games involving discrete objects and continuous material over discrete locations. The issues raised when the region is continuous are substantially different. In this paper, we study accumulation of continuous material over two types of continuous regions: the interval and the circle.     

Stochastic Differential Games with Multiple Modes and a Small Parameter

Abstract

Two persons stochastic differential games with multiple modes where the system is driven by a wideband noise is considered. The state of the system at time t is given by a pair (x ^ε(t), θ^ε(t)), where θ^ε(t) takes values in S = {1, 2,…, N} and ε is a small parameter. The discrete component θ^ε(t) describes various modes of the system. The continuous component x ^ε(t) is governed by a “controlled process” with drift vector which depends on the discrete component θ^ε (t). Thus, the state of the system, x ^ε(t), switches from one random path to another at random times as the mode θ^ε(t) changes. The discrete component θ^ε (t) is a “controlled Markov chain” with transition rate matrix depending on the continuous component. Both zero-sum and nonzero-sum games will be considered. In a zero-sum game, player I is trying to maximize certain expected payoff over his/her admissible strategies, where as player II is trying to minimize the same over his/her admissible strategies. This kind of game typically occurs in a pursuit-evation problem where an interceptor tries to destroy a specific target. Due to swift manuaring of the evador and the corresponding reaction by the interceptor, the trajectory keep switching rapidly at random times. We will show that the process (x ^ε(t), θ^ε(t)) converges to a process whose evolution is given by a “controlled diffusion process” with switching random paths. We will also establish the existence of randomized δ -optimal strategies for both players.     

Two Person Zero-Sum Semi-Markov Games with Unknown Holding Times Distribution on One Side: A Discounted Payoff Criterion

This paper deals with two person zero-sum semi-Markov games with a possibly unbounded payoff function, under a discounted payoff criterion. Assuming that the distribution of the holding times H is unknown for one of the players, we combine suitable methods of statistical estimation of H with control procedures to construct an asymptotically discount optimal pair of strategies. Work supported partially by Consejo Nacional de Ciencia y Tecnología (CONACyT) under Grant 46633-F.     

Zero-Sum Ergodic Semi-Markov Games with Weakly Continuous Transition Probabilities

Zero-sum ergodic semi-Markov games with weakly continuous transition probabilities and lower semicontinuous, possibly unbounded, payoff functions are studied. Two payoff criteria are considered: the ratio average and the time average. The main result concerns the existence of a lower semicontinuous solution to the optimality equation and its proof is based on a fixed-point argument. Moreover, it is shown that the ratio average as well as the time average payoff stochastic games have the same value. In addition, one player possesses an ε-optimal stationary strategy (ε>0), whereas the other has an optimal stationary strategy. A. Jaśkiewicz is on leave from Institute of Mathematics and Computer Science, Wrocław University of Technology. This work is supported by MNiSW Grant 1 P03A 01030.     

Products of Capacities Derived from Additive Measures

One of the unanswered questions in non-additive measure theory is how to define product of non-additive measures. Most of the approaches that have already been presented only work for discrete measures. In this paper a new approach is presented for not necessarily discrete non-additive measures that are in a certain relation with additive measures, usually this means that they are somehow derived from the additive measures.     

A differential game with jump process observations

We introduce a stochastic differential game with jump process observations. Both players obtain common, noisy information of the state of the system only at random time instants. The solutions to this game and its continuous observations in noise counterpart are obtained. Some earlier results dealing with the effect of changes in system parameters on the optimal cost for the continuous observations case are extended to the game with jump process observations.This work was supported by a 1978 Summer Faculty Fellowship from the University of Maryland, Baltimore County.     

Repeated Games with Bonuses

This paper deals with 2-player zero-sum repeated games in which player 1 receives a bonus at stage t if he repeats the action he played at stage t−1. We investigate the optimality of simple strategies for player 1. A simple strategy for player 1 consists of playing the same mixed action at every stage, irrespective of past play. Furthermore, for games in which player 1 has a simple optimal strategy, we characterize the set of stationary optimal strategies for player 2.     

Zero-sum stochastic games with unbounded costs: Discounted and average cost cases

Zero-sum stochastic games with countable state space and with finitely many moves available to each player in a given state are treated. As a function of the current state and the moves chosen, player I incurs a nonnegative cost and player II receives this as a reward. For both the discounted and average cost cases, assumptions are given for the game to have a finite value and for the existence of an optimal randomized stationary strategy pair. In the average cost case, the assumptions generalize those given in Sennott (1993) for the case of a Markov decision chain. Theorems of Hoffman and Karp (1966) and Nowak (1992) are obtained as corollaries. Sufficient conditions are given for the assumptions to hold. A flow control example illustrates the results.     

Static and Dynamic Equilibria in Games With Continuum of Players

This paper is a study of a general class of deterministic dynamic games with an atomless measure space of players and an arbitrary time space. The payoffs of the players depend on their own strategy, a trajectory of the system and a function with values being finite dimensional statistics of static profiles. The players' available decisions depend on trajectories of the system.The paper deals with relations between static and dynamic open-loop equilibria as well as their existence. An equivalence theorem is proven and theorems on the existence of a dynamic equilibrium are shown as consequences.     

具有模糊目标的多目标双矩阵对策集结与求解

针对不确定性多冲突环境,建立了多个具有模糊目标的多目标双矩阵对策的综合集结模型.在假定局中人各模糊目标的隶属函数为线性函数的情形下,基于总体模糊目标的可达度,给出了纳什均衡解的定义,并应用粒子群优化算法对集结模型求解.最后,给出一个军事例子说明了模型的实用有效性和粒子群优化算法求解的高效性.     

A game locating a needle in a circular haystack

A complete solution of the following Hider-Seeker zero-sum game is obtained. The hider hides a needle of lengtha, 0<a2, in the closed unit dise, and the seeker tries to locate it by shooting in a straight line across the disc. The payoff to the seeker is 1 if he hits the needle and 0 otherwise.     

Zero-sum games with incompletely defined payoff

It is shown that a saddle-point solution exists in a two-person, zero-sum game whose payoff is given by a matrix which is not completely defined. On the other hand, we show that such games do not always have a value, so that a saddle-point solution is not necessarily an optimal solution.This work was supported by the Centre d'Etudes Atomiques, Saclay, France.     

A game locating a needle in a square haystack

The following hider-seeker zero-sum game is considered. The hider hides a needle of length , in the closed unit square, and the seeker tries to locate it by shooting in a straight line across the square. The payoff to the seeker is 1 if he hits the needle and 0 otherwise.A solution of the game is obtained when or whena lies in either of the intervals and ; in addition, it is shown that, whenn is a positive integer anda=1/n, the value of the game is 1/2n. The properties of the solutions are in marked contrast to those for the analogous game over the closed unit disc, which the authors solved in a previous paper, and suggest that a complete solution may well be difficult. It is also shown that every member of a whole class of haystack games has a value.     

On the Tikhonov Well-Posedness of Concave Games and Cournot Oligopoly Games

The purpose of this paper is to investigate whether theorems known to guarantee the existence and uniqueness of Nash equilibria, provide also sufficient conditions for the Tikhonov well-posedness (T-wp). We consider several hypotheses that ensure the existence and uniqueness of a Nash equilibrium (NE), such as strong positivity of the Jacobian of the utility function derivatives (Ref. 1), pseudoconcavity, and strict diagonal dominance of the Jacobian of the best reply functions in implicit form (Ref. 2). The aforesaid assumptions imply the existence and uniqueness of NE. We show that the hypotheses in Ref. 2 guarantee also the T-wp property of the Nash equilibrium.As far as the hypotheses in Ref. 1 are concerned, the result is true for quadratic games and zero-sum games. A standard way to prove the T-wp property is to show that the sets of -equilibria are compact. This last approach is used to demonstrate directly the T-wp property for the Cournot oligopoly model given in Ref. 3. The compactness of -equilibria is related also to the condition that the best reply surfaces do not approach each other near infinity.     

Polytope Games

Starting from the definition of a bimatrix game, we restrict the pair of strategy sets jointly, not independently. Thus, we have a set , which is the set of all feasible strategy pairs. We pose the question of whether a Nash equilibrium exists, in that no player can obtain a higher payoff by deviating. We answer this question affirmatively for a very general case, imposing a minimum of conditions on the restricted sets and the payoff. Next, we concentrate on a special class of restricted games, the polytope bimatrix game, where the restrictions are linear and the payoff functions are bilinear. Further, we show how the polytope bimatrix game is a generalization of the bimatrix game. We give an algorithm for solving such a polytope bimatrix game; finally, we discuss refinements to the equilibrium point concept where we generalize results from the theory of bimatrix games.     

一般化两人零和模糊对策

定义一般化两人零和模糊对策,分别对具有纯策略和混合策略的一般化两人零和模糊对策进行研究,得到相应的最小最大值定理,以及一些与经典矩阵对策相类似的结果。     

凸对策核仁的非空性及合成凸对策核仁的单调性

本文给出了核仁与核及最小核心之间的关系 ,且证明了凸对策核仁的存在性和唯一性 ,证明了凸对策的合成对策仍是凸对策 .最后 ,我们讨论了合成凸对策的核仁不满足单调性 .     

Effort Games and the Price of Myopia

We consider Effort Games, a game‐theoretic model of cooperation in open environments, which is a variant of the principal‐agent problem from economic theory. In our multiagent domain, a common project depends on various tasks; carrying out certain subsets of the tasks completes the project successfully, while carrying out other subsets does not. The probability of carrying out a task is higher when the agent in charge of it exerts effort, at a certain cost for that agent. A central authority, called the principal, attempts to incentivize agents to exert effort, but can only reward agents based on the success of the entire project. We model this domain as a normal form game, where the payoffs for each strategy profile are defined based on the different probabilities of carrying out each task and on the boolean function that defines which task subsets complete the project, and which do not. We view this boolean function as a simple coalitional game, and call this game the underlying coalitional game. We suggest the Price of Myopia (PoM) as a measure of the influence the model of rationality has on the minimal payments the principal has to make in order to motivate the agents in such a domain to exert effort. We consider the computational complexity of testing whether exerting effort is a dominant strategy for an agent, and of finding a reward strategy for this domain, using either a dominant strategy equilibrium or using iterated elimination of dominated strategies. We show these problems are generally #P‐hard, and that they are at least as computationally hard as calculating the Banzhaf power index in the underlying coalitional game. We also show that in a certain restricted domain, where the underlying coalitional game is a weighted voting game with certain properties, it is possible to solve all of the above problems in polynomial time. We give bounds on PoM in weighted voting effort games, and provide simulation results regarding PoM in another restricted class of effort games, namely effort games played over Series‐Parallel Graphs (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Take-and-guess games

This paper studies two classes of two-person zero-sum games in which the strategies of both players are of a special type. Each strategy can be split into two parts, a taking and a guessing part. In these games two types of asymmetry between the players can occur. In the first place, the number of objects available for taking does not need to be the same for both players. In the second place, the players can be guessing sequentially instead of simultaneously; the result is asymmetric information. The paper studies the value and equilibria of these games, for all possible numbers of objects available to the players, for the case with simultaneous guessing as well as for the variant with sequential guessing.