Search

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.

We consider the estimation of the characteristic exponent of the input to a Lévy-driven storage model. The input process is not directly observed, but rather the workload process is sampled on an equispaced grid. 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, the distribution of the estimation errors is asymptotically normal for a high frequency sampling scheme. A resampling scheme that uses the available information in a more efficient manner is suggested and studied via simulation experiments.

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.

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 focuses on hypothesis testing for the input of a L��vy-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.

This paper aims at semi-parametrically estimating the input process to a L��vy-driven queue by sampling the workload process at Poisson times. We construct a method-of-moments based estimator for the L��vy 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��vy 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��vy 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 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.