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.     

A class of Bayes-optimal two-stage screens

Items are characterized by a set of attributes (T) and a collection of covariates (X) associated with those attributes. We wish to screen for acceptable items (T ∈ C_T), but T is expensive to measure. We envisage a two-stage screen in which observation of X_ is used as a filter at the first stage to sentence most items. The second stage involves the observation of T for those items for which the first stage is indecisive. We adopt a Bayes decision-theoretic approach to the development of optimal two-stage screens within a general framework for costs and stochastic structure. We also consider the important question of how much screens need to be modified in the light of resource limitations that bound the proportion of items that can be passed to the second stage. © 1996 John Wiley & Sons, Inc.     

Linear search with bounded resources

A point is placed at random on the real line according to some known distribution F, and a search is made for this point, beginning at some starting points s on the line, and moving along the line according to some function x(t). The objective of this article is to maximize the probability of finding the point while traveling at most d units. Characterizations of simple optimal searches are found for arbitrary distributions, for continuous distributions with continuous density everywhere (e.g., normal, Cauchy, triangular), and for continuous distributions with density which is continuous on its support (e.g., exponential, uniform). These optimal searches are also shown to be optimal for maximization of the expected number of points found if the points are placed on the line independently from a known distribution F.     

A periodic maintenance model with used equipment and random minimal repair

The maintenance strategy considered in this article is in the class of block replacement policies. The working unit is replaced by new ones at instants T,2T,3T,… independently of the age and state of the unit. If a failure occurs between these instants, the random repair cost is evaluated. If it is smaller than a predetermined control limit then a minimal repair is carried out. Otherwise the unit is replaced by a used unit. The performance of this maintenance strategy is evaluated in terms of average total cost per time unit over an infinite time span. The mathematical model is defined and several analytical results are obtained. A computer program has been written, which solves the mathematical problem, and some examples are given for the cases where the underlying life distribution is gamma, Weibull or truncated normal.     

Optimal layered search

This article investigates the problem of planning an optimal layered search for a stationary target. A search is layered if it assigns each point in the search space an integer number of glimpses or looks. General necessary and sufficient conditions and an existence theorem are obtained. The special case in which the initial target distribution is bivariate normal is considered in detail.     

Interrelationships between performance measures for the machine-repairman problem

The machine-repairman problem with heterogeneous machines and multiple repairmen is considered. It is assumed that machine up times and repair times have general distributions, and a work-conserving service discipline is employed. Under these general assumptions, steady-state relationships between performance measures are examined for the individual machines. Also, various performance measures are defined for the aggregate system and interrelationships between these measures are established.     

Interactive multicriteria linear programming: An extension of the method of Zionts and Wallenius

This article presents an extension of the interactive multicriteria linear-programming method of Zionts and Wallenius [see Management Science, 29 (5) (1983)]. The decision maker's underlying utility function is assumed to be pseudoconcave, and his preference structure is assessed through pairwise comparison questions. In the method of Zionts and Wallenius, the decision maker's preference structure is represented as constraints on the weights on the objectives derived from his responses. This representation is only a linear approximation to the underlying nonlinear utility function. Accordingly, inconsistency among the constraints on the weights arises while solving the problem. Therefore, some of the constraints have to be dropped, resulting in a loss of information on the preference structure, and hence an increase in the total number of questions. In this article we develop a hybrid representation scheme to avoid this problem. The proposed scheme is implemented within the algorithmic framework of the method of Zionts and Wallenius, and its underlying theory is developed. Computational results show that the number of questions required by the Zionts and Wallenius method can be sinificantly reduced using the proposed scheme.     

Facility location on a grid with a diagonal line

This article extends the traditional median problem on a grid to include a diagonal line (e.g., a street). In contrast to the traditional median problem, this generalized problem is nonconvex and nonseparable, invalidating some of the properties on which well-known median-seeking algorithms are based. This work presents an algorithm for finding the median on this generalized grid and discusses the relationship between it and the traditional median.     

Gittins-index heuristics for research planning

The classical work of Gittins, which resulted in the celebrated index result, had applications to research planning as an important part of its motivation. However, research planning problems often have features that are not accommodated within Gittins's original framework. These include precedence constraints on the task set, influence between tasks, stopping or investment options and routes to success in which some tasks do not feature. We consider three classes of Markovian decision models for research planning, each of which has all of these features. Gittins-index heuristics are proposed and are assessed both analytically and computationally. They perform impressively. © 1995 John Wiley & Sons, Inc.     

Optimal cutoff strategies in capacity expansion problems

Capacity expansion refers to the process of adding facilities or manpower to meet increasing demand. Typical capacity expansion decisions are characterized by uncertain demand forecasts and uncertainty in the eventual cost of expansion projects. This article models capacity expansion within the framework of piecewise deterministic Markov processes and investigates the problem of controlling investment in a succession of same type projects in order to meet increasing demand with minimum cost. In particular, we investigate the optimality of a class of investment strategies called cutoff strategies. These strategies have the property that there exists some undercapacity level M such that the strategy invests at the maximum available rate at all levels above M and does not invest at any level below M. Cutoff strategies are appealing because they are straightforward to implement. We determine conditions on the undercapacity penalty function that ensure the existence of optimal cutoff strategies when the cost of completing a project is exponentially distributed. A by-product of the proof is an algorithm for determining the optimal strategy and its cost. © 1995 John Wiley & Sons, Inc.