A special day of lectures on topics in the intersection of queueing theory and game theory in

Sponsor

 

 

 

Organizers

Onno Boxma (o.j.boxma@tue.nl)

Liron Ravner (l.ravner@uva.nl)

 

Programme

09.15-09.45 –  Gathering

09.45-10.45 – Refael Hassin (Tel Aviv University)

10.45-11.00 –  Break

11.00-11.30 – Sara Ghazanfari (CWI and UvA)

11.30-12.00 – Binyamin Oz (Hebrew University of Jerusalem)

12.00-13.30 – Lunch (in the Eurandom lounge)

13:30-14.00 – Yutaka Sakuma (National Defense Academy of Japan)

14.00-14.30 – Liron Ravner (UvA and TUe)

14.30-14.45 – Break

14.45-15.15 – Yoav Kerner (Ben Gurion University of the Negev)

15.15-15.45 – Marco Slikker (TUe)

15.45-16.00 – Break

16.00-16.45 – Moshe Haviv (Hebrew University of Jerusalem)

 

Abstracts

Refael Hassin 

Introduction to Rational Queueing
The talk will introduce the subject of “Rational queueing” (or queueing games) dealing with queueing systems with multiple decision makers who strategically optimize their objectives.  The talk will mention central contributions in this area, with the emphasis on interesting qualitative insights that are unique to queueing systems.

 

Moshe Haviv 

Standby customers and marginal waiting in M/G/1 queues
Consider the M/G/1 queue under some work-conserving and non-anticipating service regime. We start with developing the LST of the waiting time of a standby customer which is regime independent. This leads to the LST of the waiting time in an M/G/1 queue under the preemptive random priority (PRP) regime. We then suggest two possible definitions for the marginal waiting a customer inflicts on others and conjecture that they coincide. This is exemplified in a number of commonly used regimes such as FCFS and LCFS-PR. Marginal waiting, as opposed to the waiting time of a standby customer, is regime dependent. We compare the two and show that they coincide in case of the PRP regime.
(joint work with Binyamin Oz)

 

Yoav Kerner 

Strategic behavior in an observable retrial queue
We consider a retrial queueing system, in which customers are not aware when the server becomes available and have to actively check it. Strategic customers decide when to check considering queue length and the age of their information. We use a Dynamic Programming approach to construct customers’ cost functions and obtain optimal and/or Nash Equilibrium strategies.

 

Sara Ghazanfari

A bottleneck with randomly distorted arrival times
We investigate the impact of random deviations in planned arrival times on user equilibrium in an extension of Vickrey’s celebrated bottleneck model. The model is motivated by the fact that in real life, users can not exactly plan the time at which they depart from home, nor the delay they experience before they join the congestion bottleneck under investigation. We investigate the existence of a user equilibrium and show that in general such an equilibrium can neither be a pure Nash equilibrium, nor a mixed equilibrium with a continuous density. Our results imply that when random distortions influence user decisions, the dynamics of standard bottleneck models are inadequate to describe such more complex situations. We illustrate with numerical analysis how the mechanics of a bottleneck with delayed arrivals are unstable for any continuous arrival strategy, thus shedding more light on the non-existence result.
(joint work with Daphne van Leeuwen, Liron Ravner, Sindo Núñez Queija)

 

Binyamin Oz

Strategic bidding in a discrete accumulating priority queue
We consider an unobservable M/G/1 accumulating priority queue where homogeneous customers choose one of a finite number of priority classes. We show that there are either one or two pure Nash equilibrium strategies. In the latter case they are two consecutive classes and there exists an equilibrium strategy mixing between these two classes. We find the best-response function and show that it is unimodal, with follow-the-crowd and avoid-the-crowd instances.
(joint work with Raneetha Abeywickrama, Moshe Haviv and Ilze Ziedins)

 

Liron Ravner

Fluid Queues with Synchronized Service
We consider two Lévy queues of which the output is synchronized as much as possible. That is, the output of the two queues is mixed into a final product according to fixed proportions and whatever cannot be mixed is sold on the open market for a lower price. The queues incur holding costs for work waiting to be processed and can choose the processing rate of work. We solve both the centralized and decentralized optimization problems. First we derive the jointly optimal processing rates that maximize the total profit of both queues together, followed by the Nash equilibrium solution when each queue sets its own rate selfishly. We find that in equilibrium the queues process work faster than desirable from a system point of view.
(joint work with Onno Boxma and Offer Kella)

 

Yutaka Sakuma

Equilibrium arrivals to a queue with heterogeneous service-time beliefs
We consider a discrete-time single-server queue with opening and closing times, no early arrivals allowed, and customers are served on a first-come first-served basis (FCFS). There is uncertainty regarding the service-time distribution and we assume there are two classes of customers that differ in their beliefs regarding this distribution. Customers choose their arrival-time slots with the goal of minimizing their expected waiting times. For this queueing game, we discuss the existence of Nash equilibrium arrival-time distributions for both classes, and construct a method for computing them. We further present a corresponding dynamic discrete choice model and study its properties by simulation.
(joint work with Liron Ravner)

 

Marco Slikker 

Stratified pooling versus full pooling: (non-)emptiness of the core
I will start with a short introduction to (cooperative) game theory related to operations management and then continue with a discussion of a working paper. In this paper we study several service providers that keep spare parts in stock to protect for downtime of their high-tech machines and that face different downtime costs per stock-out. Service providers can cooperate by forming a joint spare parts pool, and we study the allocation of the joint costs to the individual service providers by studying an associated cooperative game. In extant literature, the joint spare parts pool is typically controlled by a suboptimal full-pooling policy. A full-pooling policy may lead to an empty core of the associated cooperative game, and we show this result in our setting as well. We then focus on situations where service providers apply an optimal policy: a stratification that determines, depending on the real-time on-hand inventory, which service providers may take parts from the pool. We formulate the associated stratified pooling game by defining each coalitional value in terms of the minimal long-run average costs of a Markov decision process. We present a proof demonstrating that stratified pooling games always have a non-empty core. This five-step proof is of interest in itself because it may be more generally applicable for other cooperative games where coalitional values can be defined in terms of Markov decision processes.