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.     

Cumulative search-evasion games

Cumulative search-evasion games (CSEGs) are two-person zero-sum search-evasion games where play proceeds throughout some specified period without interim feedback to either of the two players. Each player moves according to a preselected plan. If (X_t, Y_t,) are the positions of the two players at time t, then the game's payoff is the sum over t from 1 to T of A(X_t, Y_t, t). Additionally, all paths must be “connected.” That is, the finite set of positions available for a player in any time period depends on the position selected by that player in the previous time period. One player attempts to select a mixed strategy over the feasible T-time period paths to maximize the expected payoff. The other minimizes. Two solution procedures are given. One uses the Brown-Robinson method of fictitious play and the other linear programming. An example problem is solved using both procedures.     

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.     

Localization of optimal strategies in certain games

Assume the payoffs of a matrix game are concave in the index of the maximizing player. That player is shown to have an optimal strategy which uses at most two consecutive pure strategies, identifiable through approximate solution of a related continuous game. Generalizations are given, and the results are applied to a motivating hidden-target model due to Shapley. © 1994 John Wiley & Sons, Inc.     

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     

An algorithm for the discrete bilevel programming problem

The bilevel programming problem (BLPP) is an example of a two-stage, noncooperative game in which the first player can influence but not control the actions of the second. This article addresses the linear formulation and presents a new algorithm for solving the zero-one case. We begin by converting the leader's objective function into a parameterized constraint, and then attempt to solve the resultant problem. This produces a candidate solution that is used to find a point in the BLPP feasible reagion. Incremental improvements are sought, which ultimately lead to a global optimum. An example is presented to highlight the computations and to demonstrate some basic characteristics of the solution. Computational experience indicates that the algorithm is capable of solving problems with up to 50 variables in a reasonable amount of time.     

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.     

Finding saddle points on polyhedra: Solving certain continuous minimax problems

This article reviews procedures for computing saddle points of certain continuous concave-convex functions defined on polyhedra and investigates how certain parameters and payoff functions influence equilibrium solutions. The discussion centers on two widely studied applications: missile defense and market-share attraction games. In both settings, each player allocates a limited resource, called effort, among a finite number of alternatives. Equilibrium solutions to these two-person games are particularly easy to compute under a proportional effectiveness hypothesis, either in closed form or in a finite number of steps. One of the more interesting qualitative properties we establish is the identification of conditions under which the maximizing player can ignore the values of the alternatives in determining allocation decisions. © 1996 John Wiley & Sons, Inc.     

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     

Search for an infiltrator

We have solved a discrete search game on an array of n ordered cells for n ⩽ 9, with two players: infiltrator (hider) and searcher, who have opposite goals. The infiltrator wishes to reach the last cell number n (in finite time) and the searcher has to defend that cell. The payoff (to the hider) is the probability that the hider wins, that is, reaches the last cell without getting captured. © 1995 John Wiley & Sons, Inc.     

海军兵棋演习系统研究

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