An inspection game: Taking account of fulfillment probabilities of players' aims

This paper deals with an inspection game of customs and a smuggler. The customs can take two options of assigning a patrol or not. The smuggler has two strategies of shipping its cargo of contraband or not. Two players have several opportunities to take actions during a limited number of days. When both players do, there are some possibilities that the customs captures the smuggler and, simultaneously, the smuggler possibly makes a success of the smuggling. If the smuggler is captured or there remain no days for playing the game, the game ends. In this paper, we formulate the problem into a multi‐stage two‐person zero‐sum stochastic game and investigate some characteristics of the equilibrium solution, some of which are given in a closed form in a special case. There have been some studies so far on the inspection game. However, some consider the case that the smuggler has only one opportunity of smuggling or the perfect‐capture case that the customs can certainly arrest the smuggler on patrol, and others think of a recursive game without the probabilities of fulfilling the players' purposes. In this paper, we consider the inspection game taking account of the fulfillment probabilities of the players' aims. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Decentralized admission control of a queueing system: A game‐theoretic model

Consider a distributed system where many gatekeepers share a single server. Customers arrive at each gatekeeper according to independent Poisson processes with different rates. Upon arrival of a new customer, the gatekeeper has to decide whether to admit the customer by sending it to the server, or to block it. Blocking costs nothing. The gatekeeper receives a reward after a customer completes the service, and incurs a cost if an admitted customer finds a busy server and therefore has to leave the system. Assuming an exponential service distribution, we formulate the problem as an n‐person non‐zero‐sum game in which each gatekeeper is interested in maximizing its own long‐run average reward. The key result is that each gatekeeper's optimal policy is that of a threshold type regardless what other gatekeepers do. We then derive Nash equilibria and discuss interesting insights. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 702–718, 2003.     

Generalized orienteering problem with resource dependent rewards

We introduce a generalized orienteering problem (OP) where, as usual, a vehicle is routed from a prescribed start node, through a directed network, to a prescribed destination node, collecting rewards at each node visited, to maximize the total reward along the path. In our generalization, transit on arcs in the network and reward collection at nodes both consume a variable amount of the same limited resource. We exploit this resource trade‐off through a specialized branch‐and‐bound algorithm that relies on partial path relaxation problems that often yield tight bounds and lead to substantial pruning in the enumeration tree. We present the smuggler search problem (SSP) as an important real‐world application of our generalized OP. Numerical results show that our algorithm applied to the SSP outperforms standard mixed‐integer nonlinear programming solvers for moderate to large problem instances. We demonstrate model enhancements that allow practitioners to represent realistic search planning scenarios by accounting for multiple heterogeneous searchers and complex smuggler motion. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

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     

Efficient distributions of arms‐control inspection effort

A rule that constrains decision‐makers is enforced by an inspector who is supplied with a fixed level of inspection resources—inspection personnel, equipment, or time. How should the inspector distribute its inspection resources over several independent inspectees? What minimum level of resources is required to deter all violations? Optimal enforcement problems occur in many contexts; the motivating application for this study is the role of the International Atomic Energy Agency in support of the Treaty on the Non‐Proliferation of Nuclear Weapons. Using game‐theoretic models, the resource level adequate for deterrence is characterized in a two‐inspectee problem with inspections that are imperfect in the sense that violations can be missed. Detection functions, or probabilities of detecting a violation, are assumed to be increasing in inspection resources, permitting optimal allocations over inspectees to be described both in general and in special cases. When detection functions are convex, inspection effort should be concentrated on one inspectee chosen at random, but when they are concave it should be spread deterministicly over the inspectees. Our analysis provides guidance for the design of arms‐control verification operations, and implies that a priori constraints on the distribution of inspection effort can result in significant inefficiencies. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

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     

Information security: Designing a stochastic‐network for throughput and reliability

Todas information and communication network requires a design that is secure to tampering. Traditional performance measures of reliability and throughput must be supplemented with measures of security. Recognition of an adversary who can inflict damage leads toward a game‐theoretic model. Through such a formulation, guidelines for network designs and improvements are derived. We opt for a design that is most robust to withstand both natural degradation and adversarial attacks. Extensive computational experience with such a model suggests that a Nash‐equilibrium design exists that can withstand the worst possible damage. Most important, the equilibrium is value‐free in that it is stable irrespective of the unit costs associated with reliability vs. capacity improvement and how one wishes to trade between throughput and reliability. This finding helps to pinpoint the most critical components in network design. From a policy standpoint, the model also allows the monetary value of information‐security to be imputed. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

Securing a border under asymmetric information

We study a stochastic interdiction model of Morton et al. IIE Transactions, 39 (2007):3–14 that locates radiation sensors at border crossings to detect and prevent the smuggling of nuclear material. In this model, an interdictor places sensors at customs checkpoints to minimize a potential smuggler's maximum probability of crossing a border undetected. We focus on a model variant in which the interdictor has different, and likely more accurate, perceptions of the system's parameters than the smuggler does. We introduce a model that is tighter and uses fewer constraints than that of Morton et al. We also develop a class of valid inequalities along with a corresponding separation procedure that can be used within a cutting‐plane approach to reduce computational effort. Computational results demonstrate the effectiveness of our approach.Copyright © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 91–100, 2014     

Noncooperative cost spanning tree games with budget restrictions

We extend the noncooperative game associated with the cost spanning tree problem introduced by Bergantiños and Lorenzo (Math Method Oper Res 59(2004), 393–403) to situations where agents have budget restrictions. We study the Nash equilibria, subgame perfect Nash equilibria, and strong Nash equilibria of this game. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2008     

A search game on a cyclic graph

There is a finite cyclic graph. The hider chooses one of all nodes except the specified one, and he hides an (immobile) object there. At the beginning the seeker is at the specified node. After the seeker chooses an ordering of the nodes except the specified one, he examines each nodes in that order until he finds the object, traveling along edges. It costs an amount when he moves from a node to an adjacent one and also when he checks a node. While the hider wishes to maximize the sum of the traveling costs and the examination costs which are required to find the object, the seeker wishes to minimize it. The problem is modeled as a two‐person zero‐sum game. We solve the game when unit costs (traveling cost + examination cost) have geometrical relations depending on nodes. Then we give properties of optimal strategies of both players. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

Many‐server loss models with non‐poisson time‐varying arrivals

This article proposes an approximation for the blocking probability in a many‐server loss model with a non‐Poisson time‐varying arrival process and flexible staffing (number of servers) and shows that it can be used to set staffing levels to stabilize the time‐varying blocking probability at a target level. Because the blocking probabilities necessarily change dramatically after each staffing change, we randomize the time of each staffing change about the planned time. We apply simulation to show that (i) the blocking probabilities cannot be stabilized without some form of randomization, (ii) the new staffing algorithm with randomiation can stabilize blocking probabilities at target levels and (iii) the required staffing can be quite different when the Poisson assumption is dropped. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 177–202, 2017     

A sequential attribute sampling inspection game for item facilities

The routine inspection of facilities storing large numbers of identical items is modeled as a two‐person, sequential game. Timely detection of illegal activity is parameterized in terms of a critical time to detection, and equilibria are derived which provide inspection strategies. Necessary conditions for deterrence of illegal behavior are discussed. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 496–505, 2001     

Revisiting inspection game and inspector leadership through reaction networks

The inspection game is a two-player noncooperative game that models a situation where an inspector verifies whether the inspectee complies with the rules (on the assumption that the inspectee has the tendency to violate at least one of the rules). The usual approach in the analysis of this game seeks to find an optimal strategic inspection scheme for each of the two players yielding favorable payoffs. Recently, there have been some developments in the study of such games that use a mathematical structure known as reaction network involving a set of molecular species and the existing reactions among these species. In this paper, we use a reaction network to analyze the inspection game giving an alternative way of modeling the social situation. The molecular species play the role of the players' decision moves and their resulting gain or loss, while the reactions are the encounters of the decisions of the players which, as expected, yield payoffs. We reexamine the dynamics of the inspection game through the lens of reaction network theory and consider various situations that call for more detailed analyses such as equal or unequal reaction rates and inspection leadership. Conditions concerning reaction rates, initial population of decision species, benefits, and costs are determined in order to identify strategies that yield better payoffs both for the inspector and inspectee. These results illustrate practical insights rooted from the formulated simple game models.     

基于三方动态博弈模型的网络生存防御策略优化配置

针对网络攻防环境中防御方以提高系统生存能力为目的所进行的最优生存防御策略的选取问题,提出了一种基于完全信息动态博弈理论的生存防御策略优化配置算法。将恶意攻击方、故障意外事件及防御方作为博弈的参与人,提出了一种混合战略模式下的三方动态博弈模型,对博弈的主要信息要素进行了说明,以混合战略纳什均衡理论为基础,将原纳什均衡条件式的表达式转化为可计算数值结果的表达式,并据此增加了近似的概念,最后,将提出的模型和近似纳什均衡求解算法应用到一个网络实例中,结果证明了模型和算法的可行性和有效性。     

A multi‐objective model for bank ATM networks

In this paper we present an application of the core solution concepts for multi‐objective games to a bank ATM network model. In these games, the worth of a coalition is given by a subset of vectors of the k‐dimensional space rather than by a scalar. The paper investigates how an ATM network model based on multi‐objective cooperative game theory could be used as an alternative way of setting interchange fees paid by the customer's bank to the one that owns the ATM. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Timely exposure of a secret project: Which activities to monitor?

A defender wants to detect as quickly as possible whether some attacker is secretly conducting a project that could harm the defender. Security services, for example, need to expose a terrorist plot in time to prevent it. The attacker, in turn, schedules his activities so as to remain undiscovered as long as possible. One pressing question for the defender is: which of the project's activities to focus intelligence efforts on? We model the situation as a zero‐sum game, establish that a late‐start schedule defines a dominant attacker strategy, and describe a dynamic program that yields a Nash equilibrium for the zero‐sum game. Through an innovative use of cooperative game theory, we measure the harm reduction thanks to each activity's intelligence effort, obtain insight into what makes intelligence effort more effective, and show how to identify opportunities for further harm reduction. We use a detailed example of a nuclear weapons development project to demonstrate how a careful trade‐off between time and ease of detection can reduce the harm significantly.     

Capacity allocation with traditional and Internet channels

In this paper we study a capacity allocation problem for two firms, each of which has a local store and an online store. Customers may shift among the stores upon encountering a stockout. One question facing each firm is how to allocate its finite capacity (i.e., inventory) between its local and online stores. One firm's allocation affects the decision of the rival, thereby creating a strategic interaction. We consider two scenarios of a single‐product single‐period model and derive corresponding existence and stability conditions for a Nash equilibrium. We then conduct sensitivity analysis of the equilibrium solution with respect to price and cost parameters. We also prove the existence of a Nash equilibrium for a generalized model in which each firm has multiple local stores and a single online store. Finally, we extend the results to a multi‐period model in which each firm decides its total capacity and allocates this capacity between its local and online stores. A myopic solution is derived and shown to be a Nash equilibrium solution of a corresponding “sequential game.” © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

A search game with a protector

A classic problem in Search Theory is one in which a searcher allocates resources to the points of the integer interval [1, n] in an attempt to find an object which has been hidden in them using a known probability function. In this paper we consider a modification of this problem in which there is a protector who can also allocate resources to the points; allocating these resources makes it more difficult for the searcher to find an object. We model the situation as a two‐person non‐zero‐sum game so that we can take into account the fact that using resources can be costly. It is shown that this game has a unique Nash equilibrium when the searcher's probability of finding an object located at point i is of the form (1 − exp (−λ_ix_i)) exp (−μ_iy_i) when the searcher and protector allocate resources x_i and y_i respectively to point i. An algorithm to find this Nash equilibrium is given. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47:85–96, 2000     

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     

Bullwhip and reverse bullwhip effects under the rationing game

When an unreliable supplier serves multiple retailers, the retailers may compete with each other by inflating their order quantities in order to obtain their desired allocation from the supplier, a behavior known as the rationing game. We introduce capacity information sharing and a capacity reservation mechanism in the rationing game and show that a Nash equilibrium always exists. Moreover, we provide conditions guaranteeing the existence of the reverse bullwhip effect upstream, a consequence of the disruption caused by the supplier. In contrast, we also provide conditions under which the bullwhip effect does not exist. In addition, we show that a smaller unit reservation payment leads to more bullwhip and reverse bullwhip effects, while a large unit underage cost results in a more severe bullwhip effect. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 203–216, 2017