| Abstract |
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 [1]. For instance, Moab Workload Manager [2] and IBM Platform Computing Solutions [3] support AR. In both of these packages, an administrator can decide whether or not to enable AR and define an AR pricing scheme. 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. 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, PoC = 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 PoC = α/(α--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. |
