Two fluid approximations for multi-server queues with abandonments

Insight is provided into a previously developed M/M/s/r+M(n) approximation for the M/GI/s/r+GI queueing model by establishing fluid and diffusion limits for the approximating model. Fluid approximations for the two models are compared in the many-server efficiency-driven (overloaded) regime. The two fluid approximations do not coincide, but they are close.     

A stability theorem for symmetrically rational counterplanning

In the absence of contrary information, it would seem prudent for a competitor to attribute to his opponents the same level of rationality that he himself employs. In the context of a general, linear-quadratic, nonzero-sum, two-person game, it is shown that a counterplanning procedure consistent with this principle of symmetrical rationality always converges to the unique Nash equilibrium for the game.The work of R. Kalaba and L. Tesfatsion was partially supported by the National Science Foundation under Grant No. ENG-77-28432 and by the National Institutes of Health under Grant No. GM-23732-03.     

A sequential technique for the control of traffic intensity in Markovian queues

A sequential parameter control technique previously introduced by the author is modified in this paper so as to make it simple in practice. The detailed procedure involving two phases, a warning phase with control limits and a testing phase using an appropriate test is illustrated for a queueing system with an embedded Markov chain. Operating characteristics of the procedure are also examined.     

Consolidating or non-consolidating queues: A game theoretic queueing model with holding costs

We consider a two-server queueing system in which the servers choose their service rate based on the demand and holding cost allocation scheme offered by the demand generating entity. We provide an optimal holding cost allocation scheme that leads to the maximum possible service rate for each of a pooled and a split system. Our results suggest that careful allocation of holding costs can create incentives that enable minimum turnaround times using a common queue.     

Simple bounds and monotonicity results for finite multi-server exponential tandem queues

Simple and computationally attractive lower and upper bounds are presented for the call congestion such as those representing multi-server loss or delay stations. Numerical computations indicate a potential usefulness of the bounds for quick engineering purposes. The bounds correspond to product-form modifications and are intuitively appealing. A formal proof of the bounds and related monotonicity results will be presented. The technique of this proof, which is based on Markov reward theory, is of interest in itself and seems promising for further application. The extension to the non-exponential case is discussed. For multiserver loss stations the bounds are argued to be insensitive.     

Large sample inference from single server queues

Problems of large sample estimation and tests for the parameters in a single server queue are discussed. The service time and the interarrivai time densities are assumed to belong to (positive) exponential families. The queueing system is observed over a continuous time interval (0,T] whereT is determined by a suitable stopping rule. The limit distributions of the estimates are obtained in a unified setting, and without imposing the ergodicity condition on the queue length process. Generalized linear models, in particular, log-linear models are considered when several independent queues are observed. The mean service times and the mean interarrival times after appropriate transformations are assumed to satisfy a linear model involving unknown parameters of interest, and known covariates. These models enhance the scope and the usefulness of the standard queueing systems.Partially supported by the U. S. Army Research Office through the Mathematical Sciences Institute of Cornell University.     

On normal approximation for maximum likelihood estimation from single server queues

This paper is concerned with the rate of convergence of the distribution of the maximum likelihood estimators of the arrival and the service rates in a GI/G/1 queueing system. This revised version was published online in June 2006 with corrections to the Cover Date.     

A simple proof for the constructions of optical priority queues

Constructions of optical queues by optical Switches and fiber Delay Lines (SDL) have received a lot of attention lately. In this short paper, we provide a simple proof for the construction of a priority queue with a switch and fiber delay lines in Sarwate and Anantharam (Queueing Syst. Theory Appl. 53, 115–125, 2006). Our proof not only gives the insights needed to understand why such a construction works, but also leads to a more general result that recovers the result in Sarwate and Anantharam (Queueing Syst. Theory Appl. 53, 115–125, 2006) as a special case. This research was supported in part by the National Science Council, Taiwan, ROC, under Contract NSC-93-2213-E-007-040, Contract NSC-93-2213-E-007-095, Contract NSC-94-2213-E-007-046, and the Program for Promoting Academic Excellence of Universities NSC 94-2752-E-007-002-PAE.     

A survey of Markov decision models for control of networks of queues

We review models for the optimal control of networks of queues. Our main emphasis is on models based on Markov decision theory and the characterization of the structure of optimal control policies.This research was partially supported by the National Science Foundation under Grant No. DDM-8719825. The Government has certain rights in this material. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation. The research was also partially supported by the C.I.E.S. (France), while the author was on leave at INRIA, Sophia-Antipolis, 1991–92.     

Some limit theorems for regenerative queues

We consider a single server queue with the interarrival times and the service times forming a regenerative sequence. This traffic class includes the standard models: iid, periodic, Markov modulated (e.g., BMAP model of Lucantoni [18]) and their superpositions. This class also includes the recently proposed traffic models in high speed networks, exhibiting long range dependence. Under minimal conditions we obtain the rates of convergence to stationary distributions, finiteness of stationary moments, various functional limit theorems and the continuity of stationary distributions and moments. We use the continuity results to obtain approximations for stationary distributions and moments of an MMPP/GI/1 queue where the modulating chain has a countable state space. We extend all our results to feed-forward networks where the external arrivals to each queue can be regenerative. In the end we show that the output process of a leaky bucket is regenerative if the input process is and hence our results extend to a queue with arrivals controlled by a leaky bucket. This revised version was published online in June 2006 with corrections to the Cover Date.     

Maximum likelihood estimation for single server queues from waiting time data

Maximum likelihood estimators for the parameters of a GI/G/1 queue are derived based on the information on waiting times {W _t },t=1,...,n, ofn successive customers. The consistency and asymptotic normality of the estimators are established. A simulation study of the M/M/1 and M/E _k /1 queues is presented.     

A model of a 2-player stopping game with priority and asynchronous observation

Various models of 2-player stopping games have been considered which assume that players simultaneously observe a sequence of objects. Nash equilibria for such games can be found by first solving the optimal stopping problems arising when one player remains and then defining by recursion the normal form of the game played at each stage when both players are still searching (a 2 × 2 matrix game). The model considered here assumes that Player 1 always observes an object before Player 2. If Player 1 accepts the object, then Player 2 does not see that object. If Player 1 rejects an object, then Player 2 observes it and may choose to accept or reject it. It is shown that such a game can be solved using recursion by solving appropriately defined subgames, which are played at each moment when both players are still searching. In these subgames Player 1 chooses a threshold, such that an object is accepted iff its value is above this threshold. The strategy of Player 2 in this subgame is a stopping rule to be used when Player 1 accepts this object, together with a threshold to be used when Player 1 rejects the object. Whenever the payoff of Player 1 does not depend on the value of the object taken by Player 2, such a game can be treated as two optimisation problems. Two examples are given to illustrate these approaches.     

A model of rational equilibrium in quota-regulated multiple-species fisheries

This paper derives rational ecological–economic equilibrium outcomes—capital and variable input allocations, harvests, discards, revenue, costs, and stock abundances—in a spatially heterogeneous, multispecies fishery that is regulated with individual fishing quotas (IFQs). The production setting is decentralized; a manager chooses species-specific, seasonal, and spatially nondelineated quotas. Industry controls all aspects of harvesting operations. We present a solution concept and computational algorithm to solve for equilibrium harvests, discards, and profits across species, space, and time (within the regulatory cycle). The rational equilibrium mapping that we derive, used recursively, can be used to implement management-preferred bioeconomic outcomes. The model offers an essential IFQ regulation-to-outcome mapping that enables more precise implementation of management goals in multiple-species and heterogeneous fishery settings. Recommendations for Resource Managers Knowing where and when individual tradeable fishing quotas will be utilized across heterogeneous space and time in multiple-species fisheries is essential for effective fisheries management. Ad hoc models, while simple, contribute to “implementation uncertainty” whereby predicted mortality, discards, cost, and rent outcomes across fish species, space, and time are poorly matched to the realized outcomes that are implemented by resource users. A model of rational equilibrium mortality, discards, costs, and rent across space and time offers and powerful tool to improve the management of quota-regulated fisheries.     

A differential game model of a market of substitutable products

Modern industrial organization often classifies groups of differentiated products that are fairly good substitutes to belong to the same market. This paper develops a differential game model of a market of substitutable products. To avoid the problem of time-inconsistency, we solve a feedback Nash equilibrium solution for the game. A set of state-dependent equilibrium strategies is derived. Extensions of the model to a stochastic formulation and to an infinite time horizon specification are also provided.     

An equilibrium model for urban transit assignment based on game theory

The urban public transport system is portrayed as a special commodity market where passenger is consumer, transit operator is producer and the special goods is the service for passenger’s trip. The generalized Nash equilibrium game is applied to describe how passengers adjust their route choices and trip modes. We present a market equilibrium model for urban public transport system as a series of mathematical programmings and equations, which is to describe both the competitions among different transit operators and the interactive influences among passengers. The proposed model can simultaneously predict how passengers choose their optimal routes and trip modes. An algorithm is designed to obtain the equilibrium solution. Finally, a simple numerical example is given and some conclusions are drawn.     

A Penalty Approach for Generalized Nash Equilibrium Problem

The generalized Nash equilibrium problem (GNEP) is a generalization of the standard Nash equilibrium problem (NEP),in which both the utility function and the strategy space of each player depend on the strategies chosen by all other players.This problem has been used to model various problems in applications.However,the convergent solution algorithms are extremely scare in the literature.In this paper,we present an incremental penalty method for the GNEP,and show that a solution of the GNEP can be found by solving a sequence of smooth NEPs.We then apply the semismooth Newton method with Armijo line search to solve latter problems and provide some results of numerical experiments to illustrate the proposed approach.     

A simple method for computing state probabilities of theM/G/1 andGI/M/1 finite waiting space queues

This paper presents a simple method for computing steady state probabilities at arbitrary and departure epochs of theM/G/1/K queue. The method is recursive and works efficiently for all service time distributions. The only input required for exact evaluation of state probabilities is the Laplace transform of the probability density function of service time. Results for theGI/M/1/K –1 queue have also been obtained from those ofM/G/1/K queue.     

A procedure for finding Nash equilibria in bi-matrix games

In this paper we consider the computation of Nash equilibria for noncooperative bi-matrix games. The standard method for finding a Nash equilibrium in such a game is the Lemke-Howson method. That method operates by solving a related linear complementarity problem (LCP). However, the method may fail to reach certain equilibria because it can only start from a limited number of strategy vectors. The method we propose here finds an equilibrium by solving a related stationary point problem (SPP). Contrary to the Lemke-Howson method it can start from almost any strategy vector. Besides, the path of vectors along which the equilibrium is reached has an appealing game-theoretic interpretation. An important feature of the algorithm is that it finds a perfect equilibrium when at the start all actions are played with positive probability. Furthermore, we can in principle find all Nash equilibria by repeated application of the algorithm starting from different strategy vectors.This author is financially supported by the Co-operation Centre Tilburg and Eindhoven Universities, The Netherlands.     

A two-player competitive discrete location model with simultaneous decisions

In this paper we will describe and study a competitive discrete location problem in which two decision-makers (players) will have to decide where to locate their own facilities, and customers will be assigned to the closest open facilities. We will consider the situation in which the players must decide simultaneously, unsure about the decisions of one another, and we will present the problem in a franchising environment. Most problems described in the literature consider sequential rather than simultaneous decisions. In a competitive environment, most problems consider that there is a set of known and already located facilities, and new facilities will have to be located, competing with the existing ones. In the presence of more than one decision-maker, most problems found in the literature belong to the class of Stackelberg location problems, where one decision-maker, the leader, locates first and then the other decision-maker, the follower, locates second, knowing the decisions made by the first. These types of problems are sequential and differ significantly from the problem tackled in this paper, where we explicitly consider simultaneous, non-cooperative discrete location decisions. We describe the problem and its context, propose some mathematical formulations and present an algorithmic approach that was developed to find Nash equilibria. Some computational tests were performed that allowed us to better understand some of the features of the problem and the associated Nash equilibria. Among other results, we conclude that worsening the situation of a player tends to benefit the other player, and that the inefficiency of Nash equilibria tends to increase with the level of competition.