Optimal betting strategies for favorable games

We examine the problem of a gambler interested in maximizing the expected value of a convex utility function of his fortune after n plays of a game. We allow any probability distribution to rule the outcome of each play, and this distribution may change from play to play according to a Markov process. We present results regarding the existence of an optimal policy and its structural dependence on the gambler's fortune. The well-known results of Bellman and Kalaba for exponential and logarithmic utility functions and coin-tossing games are generalized. We also examine the situation of general stale spaces and show that the same structural results hold.     

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     

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     

An infiltration game with time dependent payoff

The problem of assigning patrol boats, subject to resource constraints, to capture or delay an infiltrator with perishable contraband attempting escape across a long, narrow strait is formulated as a two-sided time sequential game. Optimal mixed strategies are derived for the situation of one patrol boat against one smuggler. Procedures for obtaining numerical solutions for R > 1 patrol boats are discussed.     

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.     

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     

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     

Discrete search allocation game with false contacts

This paper deals with a two‐person zero‐sum game called a search allocation game, where a searcher and a target participate, taking account of false contacts. The searcher distributes his search effort in a search space in order to detect the target. On the other hand, the target moves to avoid the searcher. As a payoff of the game, we take the cumulative amount of search effort weighted by the target distribution, which can be derived as an approximation of the detection probability of the target. The searcher's strategy is a plan of distributing search effort and the target's is a movement represented by a path or transition probability across the search space. In the search, there are false contacts caused by environmental noises, signal processing noises, or real objects resembling true targets. If they happen, the searcher must take some time for their investigation, which interrupts the search for a while. There have been few researches dealing with search games with false contacts. In this paper, we formulate the game into a mathematical programming problem to obtain its equilibrium point. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

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.     

On the core and competitive equilibria of a market with indivisible goods

We consider a generalization of the assignment game of Shapley and Shubik [4]. In the market which we consider, s kinds of indivisible goods are exchanged for money. The market consists of buyers and sellers. Each buyer wants to buy at most one unit of the goods, and each seller may sell more than one unit. First, we show that the set of all competitive imputations is given by the solutions of a certain linear programing problem dual to the optimal problem. Second, we show that the core of the market coincides with the set of all competitive imputations under some condition, and consider the core of the market where s=1 and the condition does not hold.     

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.     

Optimal ordering policies for a product that perishes in two periods subject to stochastic demand

This paper considers the problem of computing optimal ordering policies for a product that has a life of exactly two periods when demand is random. Initially costs are charged against runouts (stockouts) and outdating (perishing). By charging outdating costs according to the expected amount of outdating one period into the future, a feasible one period model is constructed. The central theorem deals with the n-stage dynamic problem and demonstrates the appropriate cost functions are convex in the decision variable and also provides bounds on certain derivatives. The model is then generalized to include ordering and holding costs. The paper is concluded with a discussion of the infinite horizon problem.     

Solving partially observable agent‐intruder games with an application to border security problems

In this paper, we introduce partially observable agent‐intruder games (POAIGs). These games model dynamic search games on graphs between security forces (an agent) and an intruder given possible (border) entry points and high value assets that require protection. The agent faces situations with dynamically changing, partially observable information about the state of the intruder and vice versa. The agent may place sensors at selected locations, while the intruder may recruit partners to observe the agent's movement. We formulate the problem as a two‐person zero‐sum game, and develop efficient algorithms to compute each player's optimal strategy. The solution to the game will help the agent choose sensor locations and design patrol routes that can handle imperfect information. First, we prove the existence of ?‐optimal strategies for POAIGs with an infinite time horizon. Second, we introduce a Bayesian approximation algorithm to identify these ?‐optimal strategies using belief functions that incorporate the imperfect information that becomes available during the game. For the solutions of large POAIGs with a finite time horizon, we use a solution method common to extensive form games, namely, the sequence form representation. To illustrate the POAIGs, we present several examples and numerical results.     

Detection of a Markovian target with optimization of the search efforts under generalized linear constraints

This paper deals with search for a target following a Markovian movement or a conditionally deterministic motion. The problem is to allocate the search efforts, when search resources renew with generalized linear constraints. The model obtained is extended to resource mixing management. New optimality equations of de Guenin's style are obtained. Practically, the problem is solved by using an algorithm derived from the FAB method. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 117–142, 2002; DOI 10.1002/nav.10009     

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.     

Revenue sharing contracts in a supply chain with uncontractible actions

We consider a supplier–customer relationship where the customer faces a typical Newsvendor problem of determining perishable capacity to meet uncertain demand. The customer outsources a critical, demand‐enhancing service to an outside supplier, who receives a fixed share of the revenue from the customer. Given such a linear sharing contract, the customer chooses capacity and the service supplier chooses service effort level before demand is realized. We consider the two cases when these decisions are made simultaneously (simultaneous game) or sequentially (sequential game). For each game, we analyze how the equilibrium solutions vary with the parameters of the problem. We show that in the equilibrium, it is possible that either the customer's capacity increases or the service supplier's effort level decreases when the supplier receives a larger share of the revenue. We also show that given the same sharing contract, the sequential game always induces a higher capacity and more effort. For the case of additive effort effect and uniform demand distribution, we consider the customer's problem of designing the optimal contract with or without a fixed payment in the contract, and obtain sensitivity results on how the optimal contract depends on the problem parameters. For the case of fixed payment, it is optimal to allocate more revenue to the supplier to induce more service effort when the profit margin is higher, the cost of effort is lower, effort is more effective in stimulating demand, the variability of demand is smaller or the supplier makes the first move in the sequential game. For the case of no fixed payment, however, it is optimal to allocate more revenue to the supplier when the variability of demand is larger or its mean is smaller. Numerical examples are analyzed to validate the sensitivity results for the case of normal demand distribution and to provide more managerial insights. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Contractual agreements for coordination and vendor‐managed delivery under explicit transportation considerations

We consider the coordination problem between a vendor and a buyer operating under generalized replenishment costs that include fixed costs as well as stepwise freight costs. We study the stochastic demand, single‐period setting where the buyer must decide on the order quantity to satisfy random demand for a single item with a short product life cycle. The full order for the cycle is placed before the cycle begins and no additional orders are accepted by the vendor. Due to the nonrecurring nature of the problem, the vendor's replenishment quantity is determined by the buyer's order quantity. Consequently, by using an appropriate pricing schedule to influence the buyer's ordering behavior, there is an opportunity for the vendor to achieve substantial savings from transportation expenses, which are represented in the generalized replenishment cost function. For the problem of interest, we prove that the vendor's expected profit is not increasing in buyer's order quantity. Therefore, unlike the earlier work in the area, it is not necessarily profitable for the vendor to encourage larger order quantities. Using this nontraditional result, we demonstrate that the concept of economies of scale may or may not work by identifying the cases where the vendor can increase his/her profits either by increasing or decreasing the buyer's order quantity. We prove useful properties of the expected profit functions in the centralized and decentralized models of the problem, and we utilize these properties to develop alternative incentive schemes for win–win solutions. Our analysis allows us to quantify the value of coordination and, hence, to identify additional opportunities for the vendor to improve his/her profits by potentially turning a nonprofitable transaction into a profitable one through the use of an appropriate tariff schedule or a vendor‐managed delivery contract. We demonstrate that financial gain associated with these opportunities is truly tangible under a vendor‐managed delivery arrangement that potentially improves the centralized solution. Although we take the viewpoint of supply chain coordination and our goal is to provide insights about the effect of transportation considerations on the channel coordination objective and contractual agreements, the paper also contributes to the literature by analyzing and developing efficient approaches for solving the centralized problem with stepwise freight costs in the single‐period setting. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Optimal replacement under additive damage in randomly varying environments

A system is subject to a sequence of randomly occurring shocks. Each shock causes a random amount of damage which accumulates additively. Any of the shocks might cause the system to fail. The shock process is in some sense related to an environmental process in order to describe randomly varying external factors of an economical and/or technical nature as well as internal factors of a statistical nature. A discrete time formulation of the problem is given. Sufficient conditions are found for optimality of a generalized control-limit rule with respect to the total cost criterion: Whenever the accumulated damage s is not less than a specified critical number t(i), depending on the environmental state i, replace the system by a new one; otherwise do not replace it. Moreover, bounds are given for these critical numbers.     

Technical note: Find a hidden “treasure”

This paper deals with a two searchers game and it investigates the problem of how the possibility of finding a hidden object simultaneously by players influences their behavior. Namely, we consider the following two‐sided allocation non‐zero‐sum game on an integer interval [1,n]. Two teams (Player 1 and 2) want to find an immobile object (say, a treasure) hidden at one of n points. Each point i ∈ [1,n] is characterized by a detection parameter λ_i (μ_i) for Player 1 (Player 2) such that p_i(1 ? exp(?λ_ix_i)) (p_i(1 ? exp(?μ_iy_i))) is the probability that Player 1 (Player 2) discovers the hidden object with amount of search effort x_i (y_i) applied at point i where p_i ∈ (0,1) is the probability that the object is hidden at point i. Player 1 (Player 2) undertakes the search by allocating the total amount of effort X(Y). The payoff for Player 1 (Player 2) is 1 if he detects the object but his opponent does not. If both players detect the object they can share it proportionally and even can pay some share to an umpire who takes care that the players do not cheat each other, namely Player 1 gets q₁ and Player 2 gets q₂ where q₁ + q₂ ≤ 1. The Nash equilibrium of this game is found and numerical examples are given. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

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