17 research outputs found
Equilibrium and learning in queues with advance reservations.
No full textConsider a multi-class preemptive-resume M/D/1 queueing system that supports advance reservations (AR). In this system, strategic customers must decide whether to reserve a server in advance (thereby gaining higher priority) or avoid AR. Reserving a server in advance bears a cost. In this paper, we conduct a game-theoretic analysis of this system, characterizing the equilibrium strategies. Specifically, we show that the game has two types of equilibria. In one type, none of the customers makes reservation. In the other type, only customers that realize early enough that they will need service make reservations. We show that the types and number of equilibria depend on the parameters of the queue and on the reservation cost. Specifically, we prove that the equilibrium
is unique if the server utilization is below 1/2. Otherwise, there may be multiple equilibria depending on the reservation cost. Next, we assume that the reservation cost is a fee set by the provider. In that case, we show that the revenue maximizing fee leads to a unique equilibrium if the utilization is below 2/3, but multiple equilibria if the utilization exceeds 2/3.
Finally, we study a dynamic version of the game, where users learn and adapt their strategies based on observations of past actions or strategies of other users. Depending on the type of learning (i.e., action learning vs. strategy learning), we show that the game converges to an equilibrium in some cases, while it cycles in other cases.First author draf
Advance reservations and information sharing in queues with strategic customers
No full textIn many branches of the economy, including transportation, lodging, and more recently cloud computing, users can reserve resources in advance. Although advance reservations are gaining popularity, little is known about the strategic behavior of customers facing the decision whether to reserve a resource in advance or not.
Making an advance reservation can reduce the waiting time or the probability of not getting service, but it is usually associated with an additional cost. To evaluate this trade-off, we develop a game-theoretic framework, called advance reservation games, that helps in reasoning about the strategic behavior of customers in systems that allow advance reservations. Using this framework, we analyze several advance reservation models, in the context of slotted loss queues and waiting queues. The analysis of the economic equilibria, from the provider perspective, yields several key insights, including: (i) If customers have no a-priori information about the availability of servers, then only customers granted service should be charged a reservation fee; (ii) Informing customers about the exact number of available servers is less profitable than only informing them that servers are available; (iii) In many cases, the reservation fee that leads to the equilibrium with maximum possible profit leads to other equilibria, including one resulting with no profit; (iv) If the game repeats many times and customers update their strategy after observing actions of other customers at previous stage, then the system converges to an equilibrium where no one makes an advance reservation, if such an equilibrium exists. Else, the system cycles and yields positive profit to the provider
Finally, we study the impact of information sharing in M/M/1 queues with strategic customers. We analyze the intuitive policy of sharing the queue length with customers when it is small and hiding it when it is large. We prove that, from the provider perspective, such a policy is never optimal. That is, either always sharing the queue length or always hiding it maximizes the average number of customers joining the queue
Advance reservation games and the price of conservatism,” in
No full textABSTRACT Advance reservation (AR) services form a pillar of many branches of the economy, e.g., transportation, lodging, dining, and health care. There has also been increased interest in applying AR in cloud computing systems In most systems supporting AR, customers can choose whether making AR or not. Since the payoff of each customer is affected by decisions of other customers, it is natural to analyze the behavior of such systems as strategic games. In this work, we study a strategic non-cooperative game, referred to as an advance reservation game. In this game, players (customers) can reserve future resources in advance for a fixed reservation fee C. We consider a slotted loss system with N servers where customers are not flexible, i.e., they leave the system if they cannot be served at their desired time slots. Customers are not informed of the state of the system (i.e., the number of unreserved servers) prior to attempting a reservation. Thus, a customer opting not to make a reservation lowers its chance of finding a server available at the desired time. The number of customers in each slot is an i.i.d. Poisson random variable with parameter λ [4]. Customers have different lead times, where the lead time of a customer is defined as the time elapsing between its arrival and the slot starting time. Each customer only knows its own lead time. However, all lead times are derived from the same continuous distribution known by both the provider and the customers. In [5], we derive the equilibria structure of AR games. We show that for any C > 0, only two types of equilibria are possible. In the first type, none of the customers, regardless of their lead times, makes AR (non-make-AR equilibrium). In the second type, only customers with lead time greater than some threshold make AR (threshold equilibrium). Furthermore, we establish the existence of three different ranges of fees, such that if C falls in the first range only threshold equilibria exist, in the second range both threshold equilibria and a none-make-AR equilibrium exist, and in the third range only a none-make-AR equilibrium exists. In many cases, the fee C that maximizes the provider's profit lies in the second range. However, setting up a fee in that range carries also the risk of zero profit for the provider. Copyright is held by author/owner(s). Therefore, in order to properly set the AR fee, the provider should consider both the fee yielding the maximum possible profit and the fee yielding the maximum guaranteed profit. A guaranteed profit can be only achieved using fees falling within the first range. In this work, we introduce the concept of price of conservatism (PoC), which corresponds to the ratio of the maximum possible profit to the maximum guaranteed profit, and analyze it in different regimes. A greater PoC indicates greater potential profit loss if the provider opts to be conservative. First, we analyze a single-server regime, where we prove that for any fee the equilibrium is unique (the second range collapses in that case). Hence, P oC = 1 and the provider experiences no loss. Next, we analyze a many-server regime where λ = αN and N → ∞. We distinguish between the cases of overloaded and underloaded systems (i.e., α > 1 and α < 1 respectively). For the overloaded case, we show that P oC = α/(α−1). Hence, the price of conservatism increases in an unbounded fashion as α approaches one from above. Finally, for the underloaded case, we show that both the maximum and guaranteed profits converge to zero
Advance reservation games
No full textAdvance reservation (AR) services form a pillar of several branches of the economy, including transportation,
lodging, dining, and, more recently, cloud computing. In this work, we use game theory to analyze a slotted
AR system in which customers differ in their lead times. For each given time slot, the number of customers
requesting service is a random variable following a general probability distribution. Based on statistical
information, the customers decide whether or not to make an advance reservation of server resources in
future slots for a fee. We prove that only two types of equilibria are possible: either none of the customers
makes AR or only customers with lead time greater than some threshold make AR. Our analysis further
shows that the fee that maximizes the provider’s profit may lead to other equilibria, one of which yields zero
profit. In order to prevent ending up with no profit, the provider can elect to advertise a lower fee yielding
a guaranteed but smaller profit. We refer to the ratio of the maximum possible profit to the maximum
guaranteed profit as the price of conservatism. When the number of customers is a Poisson random variable, we prove that the price of conservatism is one in the single-server case, but can be arbitrarily high in a many-server system.CNS-1117160 - National Science Foundationhttp://people.bu.edu/staro/ACM_ToMPECS_AR.pdfAccepted manuscrip
On the Impact of Sharing Information in Advance Reservation Systems
No full textServices that allow advance reservations (AR) over the In-ternet differ in the information provided to customers about future availability of servers. In some services, customers ob-serve the exact number of currently available servers prior to making decisions. In other services, customers are only alerted when a few servers remain available, while there are also services in which no information whatsoever is shared about the availability of servers. Examples for the first case can be found in entertainment services, where customers are allowed to choose their seats and observe the exact number of available seats. Examples for the second case can be found in lodging reservations websites, such as Booking.com, that alert potential customers only when a few available rooms are left. Booking of airline tickets is an example of the thir
Workload characterization of the shared/buy-in computing cluster at Boston University
No full textComputing clusters provide a complete environment
for computational research, including bio-informatics, machine
learning, and image processing. The Shared Computing Cluster
(SCC) at Boston University is based on a shared/buy-in architecture
that combines shared computers, which are free to be
used by all users, and buy-in computers, which are computers
purchased by users for semi-exclusive use. Although there exists
significant work on characterizing the performance of computing
clusters, little is known about shared/buy-in architectures. Using
data traces, we statistically analyze the performance of the SCC.
Our results show that the average waiting time of a buy-in job
is 16.1% shorter than that of a shared job. Furthermore, we
identify parameters that have a major impact on the performance
experienced by shared and buy-in jobs. These parameters include
the type of parallel environment and the run time limit (i.e., the
maximum time during which a job can use a resource). Finally,
we show that the semi-exclusive paradigm, which allows any SCC
user to use idle buy-in resources for a limited time, increases
the utilization of buy-in resources by 17.4%, thus significantly
improving the performance of the system as a whole.http://people.bu.edu/staro/MIT_Conference_Yoni.pdfAccepted manuscrip
