ABSTRACT

Queueing systems are everywhere: in transportation networks, service centers, communication systems, clinics, manufacturing systems, etc. In this dissertation, we contribute to the theory of queueing in two aspects. In the first part, we dilate the interplay between retrials and strategic arrival behavior in single class queueing networks. Specifically, we study a variation of the ‘Network Concert Queueing Game,’ wherein a fixed but large number of strategic users arrive at a network of queues where they can be routed to other queues in the network following a fixed routing matrix, or potentially feedback to the end of the queue they arrive at. Working in a non- atomic setting, we prove the existence of Nash equilibrium arrival and routing profiles in three simple, but non- trivial, network topologies/architectures. In two of them, we also prove the uniqueness of the equilibrium. Our results prove that Nash equilibrium decisions on when to arrive and which queue to join in a network are substantially impacted by routing, inducing ‘herding’ behavior under certain conditions on the network architecture. Our theory raises important design implications for capacity-sharing in systems with strategic users, such as ride-sharing and crowdsourcing platforms.

In the second part, we develop a new method of data-driven model calibration or estimation for queueing models. Statistical and theoretical analyses of traffic traces show that the doubly stochastic Poisson processes are appropriate models of high intensity traffic arriving at an array of service systems. On the other hand, the statistical estimation of the underlying latent stochastic intensity process driving the traffic model involves a rather complicated nonlinear filtering problem. In this thesis we use deep neural networks to ‘parameterize’ the path measures induced by the stochastic intensity process, and solve this nonlinear filtering problem by maximizing a tight surrogate objective called the evidence lower bound (ELBO). This framework is flexible in the sense that we can also estimate other stochastic processes (e.g., the queue length process) and their related parameters (e.g., the service time distribution). We demonstrate the effectiveness of our results through extensive simulations. We also provide approximation guarantees for the estimation/calibration problem. Working with the Markov chain induced by the Euler-Maruyama discretization of the latent diffusion, we show that (1) there exists a sequence of approximate data generating distributions that converges to the “ground truth” distribution in total variation distance; (2) the variational gap is strictly positive for the optimal solution to the ELBO. For an arbitrary (known) posterior, we identify the variational gap minimizing approximate posterior and further, prove a lower bound on the optimal ELBO. Recent theoretical results on optimizing the ELBO for related (but ultimately different) models show that when the data generating distribution equals the ground truth distribution and the variational gap is zero, the probability measures that achieve these conditions also maximize the ELBO. Our results show that this may not be true in all problem settings.