PhD Student and teaching assistant, Tel Aviv University
Games played by agents who operate in a service system, according to an economic choice model.
Avoiding congestion is a task we are faced with on a daily basis, e.g., in traffic, cellular and Wi-Fi networks, waiting lines and shared resource accessing in general. Among the reasons we wish to avoid congestion are saving time, improving the quality of service and reducing expenses. In this particular research area we wish to investigate processes of interaction between customers and service providers in a system affected by congestion, when participants are granted the freedom of choice. A natural way to model problems of congestion is using the tools of Queueing Theory, which provides the mathematical framework of analyzing congested systems. This however is not enough, since we assume customers utilize their freedom to benefit their own interest. The combination of a Game Theoretic approach together with the tools of Queueing Theory, a framework we call "Rational Queueing", allows us to analyze congested systems where customers and servers behave strategically.
The models that we analyze draws inspiration from the behavior of users of sharing-economy platforms, such as Uber, Airbnb or TaskRabbit, as well as from other more traditional platforms such as stock exchanges and call centers. In this kind of interactions customers and service provider ought to make several decisions such whether to join the platform or use some outside option, how much money to offer/ask for the service, and more, depending on the choice model.
Of particular interest in the Game Theoretic approach is the notion of Nash Equilibrium, i.e., an economic situation where no single participant can increase his/her own benefit by changing his/her own decision. Smith's famous principle of "invisible hand" maintains that individuals' efforts to pursue their own interest may frequently benefit society more than if their actions were directly intending to benefit society. Nonetheless, in Rational Queueing models, equilibrium is typically not optimal in the sense of social welfare. Among the questions we attempt to resolve in the research are what kind of participants' behavior induces equilibrium in the market, and is the equilibrium behavior indeed consolidates with the socially-optimal behavior? If not, than what managerial actions can be taken to reduce the discrepancy? Studying these matters is our main goal, but also addressing other issues of importance that arise upon exploration.
Abstract: The intuition while observing the economy of queueing systems, is that one’s motivation to join the system, decreases with its level of congestion. Here we present a queueing model where sometimes the opposite is the case. The point of departure is the standard first-come first-served single server queue with Poisson arrivals. Customers commence service immediately if upon their arrival the server is idle. Otherwise, they are informed if the queue is empty or not. Then, they have to decide whether to join or not. We assume that the customers are homogeneous and when they consider whether to join or not, they assess their queueing costs against their reward due to service completion. As the whereabouts of customers interact, we look for the (possibly mixed) join/do not join Nash equilibrium strategy, a strategy that if adopted by all, then under the resulting steady-state conditions, no one has any incentive not to follow it oneself. We show that when the queue is empty then depending on the service distribution, both ‘avoid the crowd’ (ATC) and ‘follow the crowd’ (FTC) scenarios (as well as none-of-the-above) are possible. When the queue is not empty, the situation is always that of ATC. Also, we show that under Nash equilibrium it is possible (depending on the service distribution) that the joining probability when the queue is empty is smaller than it is when the queue is not empty.
Pub.: 01 May '07, Pinned: 30 Jul '17
Abstract: We introduce a rate balance principle for general (not necessarily Markovian) stochastic processes. Special attention is given to processes with birth and death like transitions, for which it is shown that for any state $i$, the rate of two consecutive transitions from $i-1$ to $i+1$, coincides with the corresponding rate from $i+1$ to $i-1$. This observation appears to be useful in deriving well-known, as well as new, results for the Mn/Gn/1 and G/Mn/1 queueing systems, such as a recursion on the conditional distributions of the residual service times (in the former model) and of the residual inter-arrival times (in the latter one), given the queue length.
Pub.: 09 Oct '15, Pinned: 30 Jul '17
Abstract: 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 behaviors 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.
Pub.: 20 Feb '16, Pinned: 30 Jul '17
Abstract: A subgame perfection refinement of Nash equilibrium is suggested for games of the following type: each of an infinite number of identical players selects an action using his private information on the system's state; any symmetric strategy results in a discrete Markov chain over such states; the player's payoff is a function of the state, the selected action, and the common strategy selected by the other players. The distinction between equilibria which are subgame perfect and those which are not, is made apparent due to the possibility that some states are transient. We illustrate the concept by considering several queueing models in which the number of customers in the system constitutes the state of the system.
Pub.: 01 Jul '02, Pinned: 30 Jul '17
Abstract: Consider two servers of equal service capacity, one serving in a first-come first-served order (FCFS), and the other serving its queue in random order. Customers arrive as a Poisson process and each arriving customer observes the length of the two queues and then chooses to join the queue that minimizes its expected queueing time. Assuming exponentially distributed service times, we numerically compute a Nash equilibrium in this system, and investigate the question of which server attracts the greater share of customers. If customers who arrive to find both queues empty independently choose to join each queue with probability 0.5, then we show that the server with FCFS discipline obtains a slightly greater share of the market. However, if such customers always join the same queue (say of the server with FCFS discipline) then that server attracts the greater share of customers.
Pub.: 21 Jul '09, Pinned: 30 Jul '17
Abstract: We consider a service system with an infinite number of exponential servers sharing a finite service capacity. The servers are ordered from the fastest to the slowest, and arriving customers join the fastest idle server. A capacity allocation is an infinite decreasing series 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.
Pub.: 09 Aug '16, Pinned: 30 Jul '17
Abstract: We consider a game of decentralized timing of jobs to a single server (machine) with a penalty for deviation from some 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 is determined by a uniform random draw. 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: inclusion of small waiting costs, stochastic job sizes, random sized population, heterogeneous due dates and non-linear deviation penalties.
Pub.: 17 Jan '17, Pinned: 30 Jul '17
Abstract: We derive the waiting time distribution of the lowest class in an accumulating priority (AP) queue with positive Lévy input. The priority of an infinitesimal 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. To this end we introduce a new method that relies on the construction of a workload overtaking process and solving a first-passage problem using an appropriate stopping time.
Pub.: 01 Dec '16, Pinned: 30 Jul '17