Network routing for insurgency: An adversarial risk analysis framework

Problems in counterterrorism and corporate competition have prompted research that attempts to combine statistical risk analysis with game theory in ways that support practical decision making. This article applies these methods of adversarial risk analysis to the problem of selecting a route through a network in which an opponent chooses vertices for ambush. The motivating application is convoy routing across a road network when there may be improvised explosive devices and imperfect intelligence about their locations. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

The discrete evasion game with three-move lag

The discrete evasion game with three-move lag, formulated over 30 years ago, was one of the earliest games with time-lag complications. This game remains unsolved even though it is well known that the game has a value. In this article we obtain an upper bound for the value by constructing a strategy which consists of 400 conditional probabilities for the minimizing player. This is believed to be the best upper bound known.     

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     

A continuous game of ambush

The article considers a two-person competitive problem in which a traveller wishes to choose a path across a rectangle from left to right in such a way as to avoid being ambushed by his adversary who has placed obstacles within the rectangle. Our results supplement those that have already been obtained by Ruckle and they indicate that, under certain conditions, the players need to adopt rather sophisticated strategies if they are to act optimally. This suggests that a complete solution to the problem could be difficult.     

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     

Game theoretic analysis of maximum cooperative purchasing situations

This article introduces maximum cooperative purchasing (MCP)‐situations, a new class of cooperative purchasing situations. Next, an explicit alternative mathematical characterization of the nucleolus of cooperative games is provided. The allocation of possible cost savings in MCP‐situations, in which the unit price depends on the largest order quantity within a group of players, is analyzed by defining corresponding cooperative MCP‐games. We show that a decreasing unit price is a sufficient condition for a nonempty core: there is a set of marginal vectors that belong to the core. The nucleolus of an MCP‐game can be derived in polynomial time from one of these marginal vectors. To show this result, we use the new mathematical characterization for the nucleolus for cooperative games. Using the decomposition of an MCP‐game into unanimity games, we find an explicit expression for the Shapley value. Finally, the behavior of the solution concepts is compared numerically. © 2013 Wiley Periodicals, Inc. Naval Research Logistics 60: 607–624, 2013     

The incentive effect of acceptance sampling plans in a supply chain with endogenous product quality

This article studies a firm that procures a product from a supplier. The quality of each product unit is measured by a continuous variable that follows a normal distribution and is correlated within a batch. The firm conducts an inspection and pays the supplier only if the product batch passes the inspection. The inspection not only serves the purpose of preventing a bad batch from reaching customers but also offers the supplier an incentive to improve product quality. The firm determines the acceptance sampling plan, and the supplier determines the quality effort level in either a simultaneous game or a Stackelberg leadership game, in which both parties share inspection cost and recall loss caused by low product quality. In the simultaneous game, we identify the Nash equilibrium form, provide sufficient conditions that guarantee the existence of a pure strategy Nash equilibrium, and find parameter settings under which the decentralized and centralized supply chains achieve the same outcome. By numerical experiments, we show that the firm's acceptance sampling plan and the supplier's quality effort level are sensitive to both the recall loss sharing ratio and the game format (i.e., the precommitment assumption of the inspection policy). © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

A continuous submarine versus submarine game

This paper analyzes, from a game-theoretic standpoint, the simultaneous choice of speeds by a transitor and by an SSK which patrols back and forth perpendicular to the transitor's course. Using idealized acoustic assumptions and a cookie-cutter detection model which ignores counterdetection, we are able to present the problem as a continuous game, and to determine an analytic solution. The results indicate that with these assumptions, there are conditions under which neither a “go fast” nor a “go slow” strategy is optimal. The game provides a good example of a continuous game with a nontrivial solution which can be solved effectively.     

A specially structured nonlinear integer resource allocation problem

We present an algorithm for solving a specially structured nonlinear integer resource allocation problem. This problem was motivated by a capacity planning study done at a large Health Maintenance Organization in Texas. Specifically, we focus on a class of nonlinear resource allocation problems that involve the minimization of a convex function over one general convex constraint, a set of block diagonal convex constraints, and bounds on the integer variables. The continuous variable problem is also considered. The continuous problem is solved by taking advantage of the structure of the Karush‐Kuhn‐Tucker (KKT) conditions. This method for solving the continuous problem is then incorporated in a branch and bound algorithm to solve the integer problem. Various reoptimization results, multiplier bounding results, and heuristics are used to improve the efficiency of the algorithms. We show how the algorithms can be extended to obtain a globally optimal solution to the nonconvex version of the problem. We further show that the methods can be applied to problems in production planning and financial optimization. Extensive computational testing of the algorithms is reported for a variety of applications on continuous problems with up to 1,000,000 variables and integer problems with up to 1000 variables. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 770–792, 2003.     

Some games of search on a lattice

In this article we shall deal with some two-person games on a lattice. These are games of search and ambush where the set of strategies of one of the players is determined by functions on the lattice. We give a general method to obtain a solution of these games and we apply it to three particular games. © 1993 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     

A cooperative game in search theory

Search theory originates from the military research efforts of WWII. Most researchers of that period modeled their search games in noncooperative games, where players are enemies or compete against each other. In this article, we deal with a cooperative search game, where multiple searchers behave cooperatively. First we describe several search problems and discuss the possibility of a coalition or cooperation among searchers. For the cooperative search game, we define a function named quasi‐characteristic function, which gives us a criterion similar to the so‐called characteristic function in the general coalition game with transferable utility. The search operation includes a kind of randomness with respect to whether the searchers can detect a target and get the value of the target. We also propose a methodology to divide the obtained target value among members of the coalition taking account of the randomness. As a concrete problem of the cooperative search game, we take the so‐called search allocation game, where searchers distribute their searching resources to detect a target in a cooperative way and the target moves in a search space to evade the searchers. Lastly, we discuss the core of the cooperative search allocation game. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

Capacity games for partially complementary products under multivariate random demands

In this study, we consider n firms, each of which produces and sells a different product. The n firms face a common demand stream which requests all their products as a complete set. In addition to the common demand stream, each firm also faces a dedicated demand stream which requires only its own product. The common and dedicated demands are uncertain and follow a general, joint, continuous distribution. Before the demands are realized, each firm needs to determine its capacity or production quantity to maximize its own expected profit. We formulate the problem as a noncooperative game. The sales price per unit for the common demand could be higher or lower than the unit price for the dedicated demand, which affects the firm's inventory rationing policy. Hence, the outcome of the game varies. All of the prices are first assumed to be exogenous. We characterize Nash equilibrium(s) of the game. At the end of the article, we also provide some results for the endogenous pricing. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 59: 146–159, 2012     

Inventory competition with yield reliability improvement

This article studies the inventory competition under yield uncertainty. Two firms with random yield compete for substitutable demand: If one firm suffers a stockout, which can be caused by yield failure, its unsatisfied customers may switch to its competitor. We first study the case in which two competing firms decide order quantities based on the exogenous reliability levels. The results from the traditional inventory competition are generalized to the case with yield uncertainty and we find that quantity and reliability can be complementary instruments in the competition. Furthermore, we allow the firms to endogenously improve their yield reliability before competing in quantity. We show that the reliability game is submodular under some assumptions. The results indicate that the competition in quantity can discourage the reliability improvement. With an extensive numerical study, we also demonstrate the robustness of our analytical results in more general settings. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 107–126, 2015     

Technical note: Characterization of binomial semivalues through delegation games

Semivalues are allocation rules for cooperative games that assign to each player in a given game a weighted sum of his marginal contributions to all coalitions he belongs to, where the weighting coefficients depend only on the coalition size. Binomial semivalues are a special class of semivalues whose weighting coefficients are obtained by means of a unique parameter. In particular, the Banzhaf value is a binomial semivalue. In this article, we provide an axiomatic characterization for each binomial semivalue. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

The solution to an open problem for a caching game

In a caching game introduced by Alpern et al. (Alpern et al., Lecture notes in computer science (2010) 220–233) a Hider who can dig to a total fixed depth normalized to 1 buries a fixed number of objects among n discrete locations. A Searcher who can dig to a total depth of h searches the locations with the aim of finding all of the hidden objects. If he does so, he wins, otherwise the Hider wins. This zero‐sum game is complicated to analyze even for small values of its parameters, and for the case of 2 hidden objects has been completely solved only when the game is played in up to 3 locations. For some values of h the solution of the game with 2 objects hidden in 4 locations is known, but the solution in the remaining cases was an open question recently highlighted by Fokkink et al. (Fokkink et al., Search theory: A game theoretic perspective (2014) 85–104). Here we solve the remaining cases of the game with 2 objects hidden in 4 locations. We also give some more general results for the game, in particular using a geometrical argument to show that when there are 2 objects hidden in n locations and n→∞, the value of the game is asymptotically equal to h/n for h≥n/2. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 23–31, 2016     

Interchange fee rate,merchant discount rate,and retail price in a credit card network: A game‐theoretic analysis

We consider two game‐theoretic settings to determine the optimal values of an issuer's interchange fee rate, an acquirer's merchant discount rate, and a merchant's retail price in a credit card network. In the first setting, we investigate a two‐stage game problem in which the issuer and the acquirer first negotiate the interchange fee rate, and the acquirer and the retailer then determine their merchant discount rate and retail price, respectively. In the second setting, motivated by the recent US bill “H.R. 2695,” we develop a three‐player cooperative game in which the issuer, the acquirer, and the merchant form a grand coalition and bargain over the interchange fee rate and the merchant discount rate. Following the cooperative game, the retailer makes its retail pricing decision. We derive both the Shapley value‐ and the nucleolus‐characterized, and globally‐optimal unique rates for the grand coalition. Comparing the two game settings, we find that the participation of the merchant in the negotiation process can result in the reduction of both rates. Moreover, the stability of the grand coalition in the cooperative game setting may require that the merchant should delegate the credit card business only to the issuer and the acquirer with sufficiently low operation costs. We also show that the grand coalition is more likely to be stable and the U.S. bill “H.R. 2695” is thus more effective, if the degree of division of labor in the credit card network is higher as the merchant, acquirer, and issuer are more specialized in the retailing, acquiring, and issuing operations, respectively. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

Modified fictitious play

We describe a modification of Brown's fictitious play method for solving matrix (zero-sum two-person) games and apply it to both symmetric and general games. If the original game is not symmetric, the basic idea is to transform the given matrix game into an equivalent symmetric game (a game with a skew-symmetric matrix) and use the solution properties of symmetric games (the game value is zero and both players have the same optimal strategies). The fictitious play method is then applied to the enlarged skew-symmetric matrix with a modification that calls for the periodic restarting of the process. At restart, both players' strategies are made equal based on the following considerations: Select the maximizing or minimizing player's strategy that has a game value closest to zero. We show for both symmetric and general games, and for problems of varying sizes, that the modified fictitious play (MFP) procedure approximates the value of the game and optimal strategies in a greatly reduced number of iterations and in less computational time when compared to Brown's regular fictitious play (RFP) method. For example, for a randomly generated 50% dense skew-symmetric 100 × 100 matrix (symmetric game), with coefficients |a_ij| ≤ 100, it took RFP 2,652,227 iterations to reach a gap of 0.03118 between the lower and upper bounds for the game value in 70.71 s, whereas it took MFP 50,000 iterations to reach a gap of 0.03116 in 1.70 s. Improved results were also obtained for general games in which the MFP solves a much larger equivalent symmetric game. © 1996 John Wiley & Sons, Inc.     

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     

Purchase and retrieval competition for seasonal produce

We study the competition problem of purchase and multiretrieval of perishable seasonal produce, where wholesalers purchase and stock their products in the first period, and then retrieve and sell them in subsequent periods. We first consider the duopoly case and assume that the prices are exogenous and fluctuate. In each period, after the price realization, the wholesalers retrieve some stock from their warehouses to satisfy their demands. One wholesaler's unsatisfied customers can switch to another and be satisfied by its left retrieved products. Any unsold retrieved stock has no salvage value and any unsatisfied demand is lost. The unretrieved stock is carried to the next period at a perishable rate. The wholesalers compete for the substitute demand by determining their own purchase and retrieval quantities. We show the existence and uniqueness of a pure-strategy Nash equilibrium, and that the Nash equilibrium strategy has the simple “sell-down-to” structure. We also consider the general N-person game and show the existence of the Nash equilibrium, and characterize the structure of the equilibrium strategy for the symmetric case. In addition, we consider the case with endogenous prices, and show that the problem reduces to a repeated newsvendor game with price and inventory competition. We derive the conditions under which a unique Nash equilibrium exists and characterize the equilibrium strategy. Finally, we conduct numerical studies to examine the impacts of the model parameters on the equilibrium outcomes and to generate managerial insights.