Finite statistical games and linear programming

The dual linear programs associated with finite statistical games are investigated and their optimal solutions are interpreted. The usual statistical game is generalized to a two-sided (inference) game and its possible application as a tactical model is discussed.     

An attack-defense game with matrix strategies

This paper presents the results and the method of analysis for an attack-defense game involving allocation of resources. Each player is assumed to have several different types of resources to be divided in optimal fashion among a fixed set of targets. The payoff function of the game is convex. The “No Soft-Spot” principle of M. Dresher, and the concept of the generalized inverse of a matrix are used to determine optimal strategies for each player and the value of the game.     

Adaptive competitive decision in repeated play of a matrix game with uncertain entries

This study is concerned with a game model involving repeated play of a matrix game with unknown entries; it is a two-person, zero-sum, infinite game of perfect recall. The entries of the matrix ((pij)) are selected according to a joint probability distribution known by both players and this unknown matrix is played repeatedly. If the pure strategy pair (i, j) is employed on day k, k = 1, 2, …, the maximizing player receives a discounted income of β^{k - 1} X_ij, where β is a constant, 0 ≤ β ? 1, and X_ij assumes the value one with probability p_ij or the value zero with probability 1 - p_ij. After each trial, the players are informed of the triple (i, j, X_ij) and retain this knowledge. The payoff to the maximizing player is the expected total discounted income. It is shown that a solution exists, the value being characterized as the unique solution of a functional equation and optimal strategies consisting of locally optimal play in an auxiliary matrix determined by the past history. A definition of an ?-learning strategy pair is formulated and a theorem obtained exhibiting ?-optimal strategies which are ?-learning. The asymptotic behavior of the value is obtained as the discount tends to one.     

一种基于博弈论的无线网状网络路由与信道分配联合优化算法

无线网络中的路由与信道分配可极大地影响网络的性能.为了解决无线网状网络中的路由与信道分配问题,提出并研究了一种称为CRAG(基于博弈论的无线网状网络路由与信道分配联合优化)的方法.CRAG采用协同博弈的方式将网络中的每个节点模型化为一个弈者,每个弈者的策略为与其相关的路由与信道分配方案,收益函数为给定流量需求矩阵下的成功传输流量.弈者通过协同博弈来优化收益函数以最大化网络的吞吐量.基于NS3的仿真结果表明,CRAG在收敛性、时延、丢包率和吞吐量方面优于其他当前的算法,从而证明了协同博弈的方法可以用于无线网状网络的路由与信道分配联合优化,并有效地改进网络性能.     

New results on a Ruckle problem in discrete games of ambush

This article deals with a two‐person zero‐sum game in which player I chooses in integer interval [1, N] two integer intervals consisting of p and q points where p + q < N, and player II chooses an integer point in [1, N]. The payoff to player I equals 1 if the point chosen by player II is at least in one of the intervals chosen by player II and 0 otherwise. This paper complements the results obtained by Ruckle, Baston and Bostock, Lee, Garnaev, and Zoroa, Zoroa and Fernández‐Sáez. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 98–106, 2001     

Estimation of strategies in a markov game

In this paper a two-person Markov game, in discrete time, and with perfect state information, is considered from the point of view of a single player (player A) only. It is assumed that A's opponent (player B) uses the same strategy every time the game is played. It is shown that A can obtain a consistent estimate of B's strategy on the basis of his past experience of playing the game with B. Two methods of deriving such an estimate are given. Further, it is shown that using one of these estimates A can construct a strategy for himself which is asymptotically optimal. A simple example of a game in which the above method may be useful is given.     

Continuous accumulation games on discrete locations

In an accumulation game, a HIDER attempts to accumulate a certain number of objects or a certain quantity of material before a certain time, and a SEEKER attempts to prevent this. In a continuous accumulation game the HIDER can pile material either at locations $1, 2, …, n, or over a region in space. The HIDER will win (payoff 1) it if accumulates N units of material before a given time, and the goal of the SEEKER will win (payoff 0) otherwise. We assume the HIDER can place continuous material such as fuel at discrete locations i = 1, 2, …, n, and the game is played in discrete time. At each time k > 0 the HIDER acquires h units of material and can distribute it among all of the locations. At the same time, k, the SEEKER can search a certain number s < n of the locations, and will confiscate (or destroy) all material found. After explicitly describing what we mean by a continuous accumulation game on discrete locations, we prove a theorem that gives a condition under which the HIDER can always win by using a uniform distribution at each stage of the game. When this condition does not hold, special cases and examples show that the resulting game becomes complicated even when played only for a single stage. We reduce the single stage game to an optimization problem, and also obtain some partial results on its solution. We also consider accumulation games where the locations are arranged in either a circle or in a line segment and the SEEKER must search a series of adjacent locations. © 2002 John Wiley & Sons, Inc. Naval Research Logistics, 49: 60–77, 2002; DOI 10.1002/nav.1048     

Characterization of the nucleolus for a class of n-person games

An inductive procedure is given for finding the nucleolus of an n-person game in which all coalitions with less than n-1 players are totally defeated. It is shown that, for such a game, one of three things may occur: (a) all players receive the same amount; (b) each player receives his quota, plus a certain constant (which may be positive, nerative, or zero); (c) the weakest player receives one half his quota, and the other players divide the remaining profit according to the nucleolus of a similar (n-1)-person game. It is also shown that the nucleolus of such a game yields directly the nucleolus of each derived game. An example is worked out in detail.     

Analytic solution for the nucleolus of a three‐player cooperative game

The nucleolus solution for cooperative games in characteristic function form is usually computed numerically by solving a sequence of linear programing (LP) problems, or by solving a single, but very large‐scale, LP problem. This article proposes an algebraic method to compute the nucleolus solution analytically (i.e., in closed‐form) for a three‐player cooperative game in characteristic function form. We first consider cooperative games with empty core and derive a formula to compute the nucleolus solution. Next, we examine cooperative games with nonempty core and calculate the nucleolus solution analytically for five possible cases arising from the relationship among the value functions of different coalitions. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Maximal nash subsets for bimatrix games

In this work maximal Nash subsets are studied in order to show that the set of equilibrium points of a bimatrix game is the finite union of all such subsets. In addition, the extreme points of maximal Nash subsets are characterized in terms of square submatrices of the payoff matrices and dimension relations are derived.     

A price leadership method for solving the inspector's non-constant-sum game

An inspector's game is a non-constant-sum two-person game in which one player has promised to perform a certain duty and the other player is allowed to inspect and verify occasionally that the duty has indeed been performed. A solution to a variant of such a game is given in this paper, based on the assumption that the inspector can announce his mixed strategy in advance, if he so wishes, whereas the other player, who has already given his promise, cannot threaten by explicitly saying that he will not keep his word.     

Inspection games with local and global allocation bounds

This article discusses a two‐player noncooperative nonzero‐sum inspection game. There are multiple sites that are subject to potential inspection by the first player (an inspector). The second player (potentially a violator) has to choose a vector of violation probabilities over the sites, so that the sum of these probabilities do not exceed one. An efficient method is introduced to compute all Nash equilibria parametrically in the amount of resource that is available to the inspector. Sensitivity analysis reveals nonmonotonicity of the equilibrium utility of the inspector, considered as a function of the amount of resource that is available to it; a phenomenon which is a variant of the well‐known Braess paradox. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

Application of the fundamental theorem of games to an example concerning antiballistic missile defense

This paper considers a two sided resource allocation game in which both players initially have fixed resources which may be distributed over various targets. Their effectiveness depends on the manner of distribution and also on the strategy of the opponent, a natural payoff function for such a situation being used. The complete solution to the game is derived and a numerical example given.     

More on the search for an infiltrator

We have asymptotically solved a discrete search game on an array of n ordered cells with two players: infiltrator (hider) and searcher, when the probability of survival approaches 1. The infiltrator wishes to reach the last cell in finite time, and the searcher has to defend that cell. When the players occupy the same cell, the searcher captures the infiltrator with probability 1 ? z. The payoff to the hider is the probability that the hider reaches the last cell without getting captured. © 2002 John Wiley & Sons, Inc. Naval Research Logistics, 49: 1–14, 2002; DOI 10.1002/nav.1047     

海军兵棋演习系统研究

兵棋演习系统是我军未来开展模拟训练的重要手段，针对国内外对兵棋推演系统现状及技术发展趋势进行研究，提出海军兵棋演习系统的发展方向和设计方法，并结合海军兵棋推演的研究内容重点，给出作战规则建模、指挥关系建模等主要关键技术的解决方法，为我国海军未来兵棋推演系统设计、研究和发展提供技术支撑。     

To catch an intruder: Part A—uncluttered scenario

We analyze an interdiction scenario where an interceptor attempts to catch an intruder as the intruder moves through the area of interest. A motivating example is the detection and interdiction of drug smuggling vessels in the Eastern Pacific and Caribbean. We study two models in this article. The first considers a nonstrategic target that moves through the area without taking evasive action to avoid the interdictor. We determine the optimal location the interceptor should position itself to best respond when a target arrives. The second model analyzes the strategic interaction between the interceptor and intruder using a Blotto approach. The intruder chooses a route to travel on and the interceptor chooses a route to patrol. We model the interaction as a two‐player game with a bilinear payoff function. We compute the optimal strategy for both players and examine several extensions. © 2017 Wiley Periodicals, Inc. Naval Research Logistics, 64: 29–40, 2017     

A family of games on 1,∞)2 with payoff a function of y/x

A two-parameter class of games on 1,∞)² is studied. The games may be regarded as analogs of Silverman games, having continuous payoff function in place of a step function of y/x. This change is motivated by a desire to move toward a model for competitive situations where the penalty for overspending increases with the amount of overspending. There are some similarities to games with bell-shaped kernel. For most of the region considered in the plane of the two parameters there are solutions of finite type, which are obtained explicitly. There are, however, pockets in this plane where no optimal strategies have been found and possibly where none of finite type exist.     

On a ruckle problem in discrete games of ambush

The following zero-sum game is considered. Red chooses in integer interval [1, n] two integer intervals consisting of k and m points where k + m < n, and Blue chooses an integer point in [1, n]. The payoff to Red equals 1 if the point chosen by Blue is at least in one of the intervals chosen by Red, and 0 otherwise. This work complements the results obtained by Ruckle, Baston and Bostock, and Lee. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 353–364, 1997     

The matrix game derived from the many-against-many battle

The many-against-many battle, which is a variant of the Friedman's one-against-many battle, is formulated as a two-person constant-sum game. It is shown that the matrix which expresses this game has a saddle point. Some cases are presented in which the payoff matrix of the game can be reduced. Finally, some parametrically special cases are analyzed.     

改进的遗传算法在导弹火力分配中的应用

弹道导弹系统是一个非常复杂的系统,有其自身的特点,其造价昂贵,数量有限,发射点也很分散.因此,火力分配问题在弹道导弹射击中具有极为重要的地位.尤其对于常规战术弹道导弹,火力分配的合理与否将直接影响作战效果与战斗力的发挥.根据地地战术导弹的作战运用特点,建立了导弹火力分配的优化模型;详细介绍了一种改进的遗传算法,将其应用于火力分配优化模型的求解,通过算例比较,证明该改进算法更能有效快速地找到最优解.