Search

In Naor's model [16], customers decide whether or not to join a queue after observing its length. We suppose that customers are heterogeneous in their service value (reward) $R$ from completed service and homogeneous in the cost of staying in the system per unit of time. It is assumed that the values of customers are independent random variables generated from a common parametric distribution. The manager observes the queue length process, but not the balking customers. Based on the queue length data, an MLE is constructed for the underlying parameters of $R$. We provide verifiable conditions for which the estimator is consistent and asymptotically normal. A dynamic pricing scheme is constructed that starts from some arbitrary price and iteratively updates the price using the estimated parameters. The performance of the estimator and the pricing algorithm are studied through a series of simulation experiments.

We study a multi-server queueing system with a periodic arrival rate and customers whose joining decision is based on their patience and a delay proxy. Specifically, each customer has a patience level sampled from a common distribution. Upon arrival, they receive an estimate of their delay before joining service and then join the system only if this delay is not more than their patience, otherwise they balk. The main objective is to estimate the parameters pertaining to the arrival rate and patience distribution. Here the complication factor is that this inference should be performed based on the observed process only, i.e., balking customers remain unobserved. We set up a likelihood function of the state dependent effective arrival process (i.e., corresponding to the customers who join), establish strong consistency of the MLE, and derive the asymptotic distribution of the estimation error. Due to the intrinsic non-stationarity of the Poisson arrival process, the proof techniques used in previous work become inapplicable. The novelty of the proving mechanism in this paper lies in the procedure of constructing i.i.d. objects from dependent samples by decomposing the sample path into i.i.d. regeneration cycles. The feasibility of the MLE-approach is discussed via a sequence of numerical experiments, for multiple choices of functions which provide delay estimates. In particular, it is observed that the arrival rate is best estimated at high service capacities, and the patience distribution is best estimated at lower service capacities., Comment: 39 pages, 34 figures

This work presents a non-parametric estimator for the cumulative distribution function (CDF) of the jump-size distribution for a storage system with compound Poisson input. The workload process is observed according to an independent Poisson sampling process. The nonparametric estimator is constructed by first estimating the characteristic function (CF) and then applying an inversion formula. The convergence rate of the CF estimator at $s$ is shown to be of the order of $s^2/n$, where $n$ is the sample size. This convergence rate is leveraged to explore the bias-variance tradeoff of the inversion estimator. It is demonstrated that within a certain class of continuous distributions, the risk, in terms of MSE, is uniformly bounded by $C n^{-\frac{\eta}{1+\eta}}$, where $C$ is a positive constant and the parameter $\eta>0$ depends on the smoothness of the underlying class of distributions. A heuristic method is further developed to address the case of an unknown rate of the compound Poisson input process.

Our goal is to estimate the characteristic exponent of the input to a L\'evy-driven storage system from a sample of equispaced workload observations. The estimator relies on an approximate moment equation associated with the Laplace-Stieltjes transform of the workload at exponentially distributed sampling times. The estimator is pointwise consistent for any observation grid. Moreover, a high frequency sampling scheme yields asymptotically normal estimation errors for a class of input processes. A resampling scheme that uses the available information in a more efficient manner is suggested and assessed via simulation experiments.

This note considers the problem of statistical inference of the parameters of the input process to a queue from periodic workload observations. The main focus is the open problem of constructing statistically efficient estimators for a given observation scheme, in the sense of minimizing the asymptotic variance of the estimation error.

A single server commences its service at time zero every day. A random number of customers decide when to arrive to the system so as to minimize the waiting time and tardiness costs. The costs are proportional to the waiting time and the tardiness with rates $\alpha$ and $\beta$, respectively. Each customer's optimal arrival time depends on the others' decisions, thus the resulting strategy is a Nash equilibrium. This work considers the estimation of the ratio $\displaystyle\theta\equiv \beta/(\alpha+\beta)$ from queue length data observed daily at discrete time points, given that customers use a Nash equilibrium arrival strategy. A method of moments estimator is constructed from the equilibrium conditions. Remarkably, the method does not require estimation of the Nash equilibrium arrival strategy itself, or even an accurate estimate of its support. The estimator is strongly consistent and the estimation error is asymptotically normal. Moreover, the asymptotic variance of the estimation error as a function of the queue length covariance matrix (at sampling times) is derived. The estimator performance is demonstrated through simulations, and is shown to be robust to the number of sampling instants each day., Comment: 31 pages, 10 figures, 3 tables

We suggest a novel stochastic-approximation algorithm to compute a symmetric Nash-equilibrium strategy in a general queueing game with a finite action space. The algorithm involves a single simulation of the queueing process with dynamic updating of the strategy at regeneration times. Under mild assumptions on the utility function and on the regenerative structure of the queueing process, the algorithm converges to a symmetric equilibrium strategy almost surely. This yields a powerful tool that can be used to approximate equilibrium strategies in a broad range of strategic queueing models in which direct analysis is impracticable.

Consider a population of customers each of which needs to decide independently when to arrive to a facility that provides a service during a fixed period of time, say a day. This is a common scenario in many service systems such as a bank, lunch at a cafeteria, music concert, flight check-in and many others. High demand for service at a specific time leads to congestion that comes at a cost, e.g., for waiting, earliness or tardiness. Queueing Theory provides tools for the analysis of the waiting times and associated costs. If customers have the option of deciding when to join the queue, they will face a decision dilemma of when to arrive. The level of congestion one suffers from depends on others behavior and not only that of the individual under consideration. This fact leads customers to make strategic decisions regarding their time of arrival. In addition, multiple decision makers that affect each other's expected congestion, call for non-cooperative game theoretic analysis of this strategic interaction. This common daily scenario has prompted a research stream pioneered by the ?/M/1 model of Glazer and Hassin (GH1983) that first characterized an arrival process to a queue as a Nash equilibrium solution of a game. This survey provides an overview of the main results and developments in the literature on queueing systems with strategic timing of arrivals. Another issue is that of social optimality, namely the strategy profile used by customers that optimizes their aggregate utility. In particular, we review results concerning the price of anarchy (PoA), which is the ratio between the socially optimal and the equilibrium utilities.

This paper studies a service system in which arriving customers are provided with information about the delay they will experience. Based on this information they decide to wait for service or to leave the system. Specifically, every customer has a patience threshold and they balk if the observed delay is above the threshold. The main objective is to estimate the parameters of the customers' patience-level distribution and the corresponding potential arrival rate, using knowledge of the actual queue-length process only. The main complication, and distinguishing feature of our setup, lies in the fact that customers who decide not to join are not observed, remarkably, we manage to devise a procedure to estimate the underlying patience and arrival rate parameters. The model is a multi-server queue with a Poisson stream of customers, enabling evaluation of the corresponding likelihood function of the state-dependent effective arrival process. We establish strong consistency of the MLE and derive the asymptotic distribution of the estimation error. Several applications and extensions of the method are discussed. The performance is further assessed through a series of numerical experiments. By fitting parameters of hyperexponential and generalized-hyperexponential distributions our method provides a robust estimation framework for any continuous patience-level distribution.

This paper focuses on hypothesis testing for the input of a L\'evy-driven storage system by sampling of the storage level. As the likelihood is not explicit we propose two tests that rely on transformation of the data. The first approach uses i.i.d. `quasi-busy-periods' between observations of zero workload. The distribution of the duration of quasi-busy-periods is determined. The second method is a conditional likelihood ratio test based on the Bernoulli events of observing a zero or positive workload, conditional on the previous workload. Performance analysis is presented for both tests along with speed-of-convergence results, that are of independent interest.

We study the problem of strategic choice of arrival time to a single-server queue with opening and closing times when there is uncertainty regarding service speed. A Poisson population of customers choose their arrival time with the goal of minimizing their expected waiting times and are served on a first-come first-served basis. There are two types of customers that differ in their beliefs regarding the service time distribution. The inconsistent beliefs may arise from randomness in the server state along with noisy signals that customers observe. Customers are aware of the two types of populations with differing beliefs. We characterize the Nash equilibrium dynamics for exponentially distributed service times and show how they substantially differ from the model with homogeneous customers. We further provide an explicit solution for a fluid approximation of the game. For general service time distributions we provide an algorithm for computing the equilibrium in a discrete time setting. We find that in equilibrium customers with different beliefs arrive during different (and often disjoint) time intervals. Numerical analysis further shows that the mean waiting time increases with the coefficient of variation of the service time. Furthermore, we present a learning agent based model (ABM) in which customers make joining decisions based solely on their signals and past experience. We numerically compare the long-term average outcome of the ABM with that of the equilibrium and find that the arrival distributions are quite close if we assume (for the equilibrium solution) that customers are fully rational and have knowledge of the system parameters, while they may greatly differ if customers have limited information or computing abilities.

This paper aims at semi-parametrically estimating the input process to a L\'evy-driven queue by sampling the workload process at Poisson times. We construct a method-of-moments based estimator for the L\'evy process' characteristic exponent. This method exploits the known distribution of the workload sampled at an exponential time, thus taking into account the dependence between subsequent samples. Verifiable conditions for consistency and asymptotic normality are provided, along with explicit expressions for the asymptotic variance. The method requires an intermediate estimation step of estimating a constant (related to both the input distribution and the sampling rate); this constant also features in the asymptotic analysis. For subordinator L\'evy input, a partial MLE is constructed for the intermediate step and we show that it satisfies the consistency and asymptotic normality conditions. For general spectrally-positive L\'evy input a biased estimator is proposed that only uses workload observations above some threshold; the bias can be made arbitrarily small by appropriately choosing the threshold.

We consider a game of decentralized timing of jobs to a single server (machine) with a penalty for deviation from a due date, and no delay costs. The jobs' sizes are homogeneous and deterministic. Each job belongs to a single decision maker, a customer, who aims to arrive at a time that minimizes his deviation penalty. If multiple customers arrive at the same time then their order of service is determined by a uniform random draw. We show that if the cost function has a weighted absolute deviation form then any Nash equilibrium is pure and symmetric, that is, all customers arrive together. Furthermore, we show that there exist multiple, in fact a continuum, of equilibrium arrival times, and provide necessary and sufficient conditions for the socially optimal arrival time to be an equilibrium. The base model is solved explicitly, but the prevalence of a pure symmetric equilibrium is shown to be robust to several relaxations of the assumptions: restricted server availability, inclusion of small waiting costs, stochastic job sizes, randomly sized population, heterogeneous due dates, and non-linear deviation penalties.

We consider a service system with an infinite number of exponential servers sharing a finite service capacity. The servers are ordered according to their speed, and arriving customers join the fastest idle server. A capacity allocation is an infinite sequence of service rates. We study the probabilistic properties of this system by considering overflows from sub-systems with a finite number of servers. Several stability measures are suggested and analysed. The tail of the series of service rates that minimizes the average expected delay (service time) is shown to be approximately geometrically decreasing. We use this property in order to approximate the optimal allocation of service rates by constructing an appropriate dynamic program.

This paper presents a new method for deriving the waiting time distribution of the lowest class in an accumulating priority (AP) queue with positive L\'evy input. The priority of a non-atomic customer (particle) is a function of their class and waiting time in the system, and the particles with the highest AP are the next to be processed. The method relies on the construction of a workload overtaking process and solving a first-passage time problem using an appropriate stopping time.

We study the strategic purchasing of priorities in a time-dependent accumulating priority M/G/$1$ queue. We formulate a non-cooperative game in which customers purchase priority coefficients with the goal of reducing waiting costs in exchange. The priority of each customer in the queue is a linear function of the individual waiting time, with the purchased coefficient being the slope. The unique pure Nash equilibrium is solved explicitly for the case with homogeneous customers. A general characterisation of the Nash equilibrium is provided for the heterogeneous case. It is shown that both avoid the crowd and follow the crowd behaviours are prevalent, within class types and between them. We further present a pricing mechanism that ensures the order of the accumulating priority rates in equilibrium follows a $C\mu$ type rule and improves overall efficiency.

We consider a discrete population of users with homogeneous service demand who need to decide when to arrive to a system in which the service rate deteriorates linearly with the number of users in the system. The users have heterogeneous desired departure times from the system, and their goal is to minimize a weighted sum of the travel time and square deviation from the desired departure times. Users join the system sequentially, according to the order of their desired departure times. We model this scenario as a non-cooperative game in which each user selects his actual arrival time. We present explicit equilibria solutions for a two-user example, namely the subgame perfect and Nash equilibria and show that multiple equilibria may exist. We further explain why a general solution for any number of users is computationally challenging. The difficulty lies in the fact that the objective functions are piecewise convex, i.e., non-smooth and non-convex. As a result, the minimization of the costs relies on checking all arrival and departure order permutations, which is exponentially large with respect to the population size. Instead we propose an iterated best-response algorithm which can be efficiently studied numerically. Finally, we compare the equilibrium arrival profiles to a socially optimal solution and discuss the implications.

We consider the problem of scheduling arrivals to a congestion system with a finite number of users having identical deterministic demand sizes. The congestion is of the processor sharing type in the sense that all users in the system at any given time are served simultaneously. However, in contrast to classical processor sharing congestion models, the processing slowdown is proportional to the number of users in the system at any time. That is, the rate of service experienced by all users is linearly decreasing with the number of users. For each user there is an ideal departure time (due date). A centralized scheduling goal is then to select arrival times so as to minimize the total penalty due to deviations from ideal times weighted with sojourn times. Each deviation is assumed quadratic, or more generally convex. But due to the dynamics of the system, the scheduling objective function is non-convex. Specifically, the system objective function is a non-smooth piecewise convex function. Nevertheless, we are able to leverage the structure of the problem to derive an algorithm that finds the global optimum in a (large but) finite number of steps, each involving the solution of a constrained convex program. Further, we put forward several heuristics. The first is the traversal of neighbouring constrained convex programming problems, that is guaranteed to reach a local minimum of the centralized problem. This is a form of a "local search", where we use the problem structure in a novel manner. The second is a one-coordinate "global search", used in coordinate pivot iteration. We then merge these two heuristics into a unified "local-global" heuristic, and numerically illustrate the effectiveness of this heuristic.

Suppose customers need to choose when to arrive to a congested queue with some desired service at the end, provided by a single server that operates only during a certain time interval. We study a model where the customers incur not only congestion (waiting) costs but also penalties for their index of arrival. Arriving before other customers is desirable when the value of service decreases with every admitted customer. This may be the case for example when arriving at a concert or a bus with unmarked seats or going to lunch in a busy cafeteria. We provide game theoretic analysis of such queueing systems with a given number of customers, specifically we characterize the arrival process which constitutes a symmetric Nash equilibrium.