面向云计算动态资源配置的在线拍卖框架

Abstract—Auction mechanisms have recently attracted substantial attention as an efficient approach to pricing and allocating resources in cloud computing. This work, to the authors’ knowledge, represents the first online combinatorial auction designed for the cloud computing paradigm, which is general and expressive enough to both: 1) optimize system efficiency across the temporal domain instead of at an isolated time point; and 2) model dynamic provisioning of heterogeneous virtual machine (VM) types in practice. The final result is an online auction framework that is truthful, computationally efficient, and guarantees a competitive ratio in social welfare in typical scenarios. The framework consists of three main steps: 1) a tailored primal-dual algorithm that decomposes the long-term optimization into a series of independent one-shot optimization problems, with a small additive loss in competitive ratio; 2) a randomized subframework that applies primal-dual optimization for translating a centralized cooperative social welfare approximation algorithm into an auction mechanism, retaining the competitive ratio while adding truthfulness; and 3) a primal-dual algorithm for approximating the one shot optimization with a ratio close to . We also propose two extensions: 1) a binary search algorithm that improves the average-case performance; 2) an improvement to the online auction framework when a minimum budget spending fraction is guaranteed, which produces a better competitive ratio. The efficacy of the online auction framework is validated through theoretical analysis and trace-driven simulation studies. We are also in the hope that the framework can be instructive in auction design for other related problems.

Index Terms—Cloud computing, combinatorial auction, resource allocation, pricing, online algorithms, truthful mechanisms.

TABLE I. AMAZON EC2 VM INSTANCES

* EC2 compute units

puting paradigm that enables prompt and on-demand access to computing resources. As exemplified in Amazon EC2 [1] and Microsoft Azure [2], cloud providers invest substantially into their datacenter infrastructure, providing a virtually unlimited “sea” of CPU, RAM, and storage resources to cloud users, often assisted by virtualization technologies. The elastic and on-demand nature of cloud computing assists cloud users to meet their dynamic and fluctuating demands with minimal management overhead, while the cloud ecosystem as a whole achieves economies of scale through cost amortization.

Currently, most cloud providers adopt a fixed-price policy and charge users a fixed amount per-virtual-machine (VM) usage. For example, Table I shows the available VM types at Amazon EC2 and their hourly prices at different datacenters. Despite their apparent simplicity, fixed-price policies inher ently lack market agility and efficiency, failing to rapidly adapt to real-time demand–supply relation changes. Consequently, overpricing and underpricing routinely occur, which either dispel or undercharge the users, jeopardizing overall system social welfare as well as the providers’ revenue.

Toward effectively discovering the market value of VMs, auction mechanisms have been at the focal point of recent literature on cloud resource allocation and pricing [3], [4]. Spot Instance [5] is a first-step attempt to apply the auction mechanism on Amazon EC2, which was enhanced by sub sequent work [4], [6]. A series of recent work further study auction mechanism design in cloud markets from different perspectives [7]–[9]. Unfortunately, all existing designs either consider one-round auctions only or model VMs as type-obliv ious commodities and fail to account for the providers’ ability to dynamically assemble VMs.

Cloud Auctions Should Be Online: Real-world cloud resource transactions happen either when customer demands arrive or cloud resources become available, and hence are modeled more naturally by an online auction that incorporates the time dimen sion. Most cloud computing customers, enterprise or individual, are on a preallocated budget for a given time period (e.g., a year or a month like that in an ad-auction [10]). Thus, a customer’s purchase desire drastically declines over time, which needs to be considered for a practical auction mechanism. However, most existing cloud auctions focus on a single-round auction only and ignore such temporal correlation in decision making [8].

Manuscript received June 25, 2014; revised December 1, 2014, February 17, 2015, and May 12, 2015; accepted May 28, 2015; approved by the IEEE/ACM Transactions on Networking Editor U. Ayesta. Date of publication July 1, 2015; date of current version August 16, 2016. This work was supported in part by Hong Kong RGC grant HKU 718513 and NSERC Grant 10006298. DOI: 10.1109/TNET.2015.2444657.

Cloud Auctions Should Be Combinatorial: A cloud computing job in practice often demands a bundle of heterogeneous VM instances for its successful execution, and hence a cloud auction is naturally a combinatorial auction. For example, a social game application that consists of a front-end Web server layer, a load-balancing layer, and a back-end data storage layer is best served by a combination of VMs that are intended for communication-intensive, computation-intensive, and storage-intensive tasks, respectively. Such combinatorial VM auctions represent a dramatic departure of most existing VM auction designs that assume VMs are type-oblivious commodities, in that all VMs are essentially of the same type, and hence are substitutable or substitutable up to a simple multiplicative factor. Embracing heterogeneous VM types in the model further brings about the opportunity of considering dynamic resource provisioning: Decisions on VM assembling, which organizes the CPU, RAM, and Disk resource pools into typed VM instances, are no longer made randomly a priori [3], but made dynamically upon receiving user bids. Dynamic resource provisioning enables higher efficiency in cloud resource utilization, higher seller revenue for the provider, and higher social welfare for the entire cloud system.

This work generalizes and subsumes existing literature on cloud auctions by designing the first online combinatorial auction in which VMs of heterogeneous types are allocated in multiple consecutive time-slots. The final result is an online auction framework that simultaneously guarantees the following properties.

1) Truthfulness, the holy grail of auction mechanism design. It ensures that economically-motivated selfish buyers are automatically elicited to reveal their true valuations of the VMs they demand, in the bids submitted. This simplifies analysis of the resulting auction in theory and increases the predicability of auction outcomes in practice. 2) Combinatorial auctions, supporting heterogeneous VM types located at different datacenters. Besides hetero geneity in their types, another dimension of VM diversity may arise due to their geographical locations (assuming multiple datacenters). A combinatorial auction is hence necessary. 3) Dynamic resource provisioning. The number of instances of each VM type is not predefined, but dynamically ad justed as part of the auction mechanism, tailored to real time user demand. 4) Online auction: In commercial cloud platforms, auctions are executed repeatedly and the prices change termly. Each user is subject to a practical budget limitation for a given time period. Our online auction models a long-time auction over multiple rounds that are coupled together by customer budgets. A competitive ratio of is guaran teed in typical scenarios, i.e., our online auction achieves a long-term social welfare that is at least a 1/3.30 fraction of the offline optimum. Our proposed online auction framework consists of three main modules: A) translating online optimization into a series of one-round optimization problems; B) translating an approx imation algorithm for one-round optimization into a truthful auction; and C) designing an effective approximation algorithm

Our proposed online auction framework consists of three main modules: A) translating online optimization into a series of one-round optimization problems; B) translating an approx imation algorithm for one-round optimization into a truthful auction; and C) designing an effective approximation algorithm

First, we formulate a linear integer program that characterizes the long-term social welfare optimization problem in the cloud market for VMs and formulate the dual LP of its LP relaxation (without the integer constraints). A tailored primal-dual algorithm iteratively adjusts a dual variable corresponding to each customer’s budget, acting as a shadow price that signals how “tight” the latter is. A series of one-round combinatorial VM auctions are then executed under a fixed shadow price vector. Such primal-dual decoupling of the auction rounds admits a rather intuitive interpretation: The algorithm strikes to avoid prematurely depleting a user’s budget, and gives higher priority to cloud customers with low budget pressures during each auction round. As a result, we prove that the decomposition intro duces an additive loss to the competitive ratio bounded by .

Second, for each one-round combinatorial auction problem, we employ a randomized auction subframework, which ex ploits the underlying packing property of one-round social welfare maximization and translates any centralized cooper ative approximation algorithm into an auction, inheriting the same approximation ratio while adding truthfulness. At the core of this translation is a primal-dual optimization-based decomposition technique that decomposes an optimal fractional solution to one-round social welfare maximization into a convex combination of integral solutions, recently developed in the literature of theoretical computer science [11] and suc cessfully applied in the literature of computer networking [12]. We also propose a new binary search-based technique to find the minimum feasible scale-down ratio in the fractional so lution decomposition and thereby improve the average-case performance of the online auction algorithm.

Third, we design a specific approximation algorithm for one round VM allocation by applying iterative primal-dual solution updates followed by dual fitting. The resulting algorithm is poly nomial-time computable and guarantees an approximation ratio that approaches in practical scenarios. Combining all three modules together, the overall competitive ratio of the resulting online auction framework is bounded by in typ ical scenarios. We hope that the online auction framework pro posed in this work, as well as its three components, may shed light to the design of auction mechanisms in related problem settings.

What’s more, we further propose an improvement to the online auction framework in the case that a minimum budget spending fraction is guaranteed. The improved online auction algorithm uses a new method to adjust the dual variables corresponding to users’ budgets over time and achieves a better competitive ratio.

The rest of the paper is organized as follows: We discuss related work in Section II, define the problem model in Section III, present the online algorithm framework and the auction algorithm in Sections IV and V, discuss an improvement of the online auction framework in Section VI, present simulations in Section VII, and conclude the paper in Section VIII.

Auctions have been extensively studied for resource alloca tion in computing and network systems, which simultaneously target bidding truthfulness and economic efficiency. Classic apareas, such as network bandwidth allocation [13], wireless spec trum allocation [12], and wireless crowdsourcing [14].

The celebrated VCG mechanism [15] is a well-known type of auction. It is essentially the only type of auction that simul taneously guarantees both truthfulness and absolute economic efficiency (social welfare maximization), through calculating the optimal allocation and a carefully designed pricing rule. However, when the underlying allocation problem is NP-hard, which is common for combinatorial auctions [16], VCG be comes computationally infeasible. When polynomial-time ap proximation algorithms are applied to solving the underlying allocation problem, VCG loses its truthfulness property [17]. One usually needs to custom design a payment rule to work in concert with the approximation algorithm at hand to achieve truthfulness; for example, this can be done by exploiting the concept of critical bids [18]. Another relatively new alternative is to resort to the LP decomposition technique [11], as done in this work, which is universally applicable to problems with a packing or covering structure.

Recently, a series of auction mechanisms are designed for VM allocation in cloud computing. Wang et al. [6] apply the critical value method, and derive a mechanism that is collusion resistant, an important property in practice. Yet their work, like many others, considers only one-round auctions; and their algorithm has a competitive ratio , where is the number of VM instances. Mashayekhy et al. [19] propose an online mech anism for resource allocation in clouds, also based on the crit ical value method, but omit a theoretical performance analysis. Shanmuganathan et al. [20] introduce the concept of bundles in VM allocation. Zhang et al. [8] are among the first to study dynamic VM provisioning and design a truthful single-round auction using the LP decomposition method. However, our work is more advanced than theirs in two aspects: 1) We consider the problem over a period of time, instead of just one round, and serve cloud users in an online manner. Our mechanism more closely resembles a real-world cloud market in practice. 2) We not only apply but also propose improvements to the decom posing method, which can improve the performance of the online auction in practice.

Extending single-round truthful auctions into online auctions in a straightforward way usually breaks the truthfulness prop erty [21]. The lack of future information brings a key challenge in pursuing truthfulness. For example, the VCG auction does not directly work in the online setting since the optimal allocation for the future cannot be calculated, even given unlimited computational resources. A known technique for achieving truth fulness in online auctions is based on the concept of a supply curve [22], as applied by Zhang et al. [4] in their design of an online cloud auction algorithm. The bidding language and the user characteristic proposed in their work are novel and cap ture the heterogeneous demands in cloud market. However, they only consider a single type of VM, significantly simplifying the underlying social welfare maximization. In absence of multiple VM types, their model naturally ignores the dynamic provisioning problem. Wang et al. propose an online auction for cloud markets [9], and their model also focuses on one type of VM only.

Many resource allocation algorithms have been pro posed in cloud computing scenarios with different focuses. VMs in a distributed cloud system. Maguluri et al. [24] tackle the randomness of arriving workloads and solve optimization problems for load balancing and VM scheduling. Xu et al. [25] summarize the recent attempts in managing performance over head in clouds. Lin et al. [26], [27] study the energy efficiency in VM provisioning. VM migration overhead [28] and energy consumption [29] are also important practical issues in VM provisioning. In addition, data traffic commonly exists between VMs. Guo et al. [30] focus on traffic variation issues in the underlying datacenter networks and solve the VM placement problem with traffic awareness. These aspects are not fully covered in the current paper, and will be investigated in our future work.

We consider a cloud spanning geographically distributed datacenters, each with a pool of types of resources including CPU, RAM, and disk storage that can be dynamically assem bled into different types of VMs for lease to cloud users. Let denote the integer set . Each VM of type is constituted by units of type resource, for all There are users of the cloud system, which request VMs of different types to execute their jobs. The cloud provider acts as the auctioneer and leases VMs to the users through auctions.

The system runs in a time-slotted fashion within a span of , where is a potentially large number. We sup pose the available amounts of resources at each datacenter are time-varying, i.e., there are units of type resource in datacenter at time , whose value may change from one time-slot to another.1 In each time-slot, one round of the auctions is carried out, where the cloud provider decides the VM allocation for the current time-slot based on user bids. The terms time-slot and round are used interchangeably.

The cloud users are bidders in the auctions, each sub mitting a bid containing optional bundles in each round. A bundle consists of a list of desired quantities of VMs of dif ferent types, as well as the bidder’s valuation for the bundle. Specifically, let denote the number of type- VMs in datacenter that user specifies in its th bundle in time-slot , and be its valuation for this th bundle in . The th bundle in the bid of user in the auction at is described by a -tuple of elements , and . The cases where a user may join and leave (intermittent bidding) or may bid a smaller number of bundles than are all subsumed by our bid model by allowing empty bundles in the bids.

In each round, upon receiving users’ bids, the cloud provider computes its resource allocation and produces the auction results, , where if user wins bundle and 0 otherwise, as well as its payment for acquiring VMs in its winning bundle. We assume that a user can win at most one bundle among its optional bundles in each round of the auctions (given that any need for combining two or more bun dles can be expressed as a separate bundle already). In addition, the VM demands in each bundle cannot be supplied partially, i.e., the cloud provider either provides all the required VMs in a bundle to the bidder or rejects the bundle.

Let denote the utility function of user in time-slot , which is decided by its valuations of the bundles and its payment at . We will present the concrete form of the utility function in Section V. We assume user has a total budget , which is a bound of its overall payment in the auctions throughout the system span under consideration, e.g., a preallocated budget for VM rental over a month or a year, which is assumed to be public information. A user’s valuations in its bids are independent from its current budget level, while its current budget level will be taken into consideration at the cloud provider when al locating resources.

TABLE II. NOTATION

We aim to design an online auction mechanism to be carried out by the cloud provider, which guides resource allocation in the cloud system in a round-by-round fashion through multiple consecutive rounds. The auction design targets the following properties.

1) Truthfulness (Definition 1): Bidding true valuations is a dominant strategy at the users, and consequently, both bid ding strategies and auction design are simplified. 2) Individual rationality: Each bidder obtains a nonnegative utility by participating in the auction in any time-slot, i.e., . 3) Social welfare maximization: The social welfare in our system is the sum of the cloud provider’s revenue, , and all the users’ utility gain, , which equals truthful bidding), . Users’ payment and the provider’s revenue cancel out each other.

Definition 1 (Truthfulness): The auction mechanism is truthful if for any user at any time , declaring a bid that truthfully reveals its requirements of VM quantities, , and its valuations of bundles , al ways maximizes its expected utility, regardless of other users’ bids.

We first formulate an offline social welfare optimization problem that provides the “ideal” optimal allocation strate gies for the cloud provider to address users’ VM demands in the entire system lifespan , assuming bids are truthful. Let be the amount of type resource at datacenter required in user ’s th bundle maximize (1) s.t. Constraint (1a) specifies that each user can win at most one bundle each round. Constraint (1b) is the budget constraint at each user. Constraint (1c) limits the overall demand for each type of resource in the winning bundles by the amount available.

Introducing dual variable vectors , and to constraints (1a), (1b), and (1c) respectively, and ignoring the binary variable constraint (1d) temporarily, we can formulate the dual of the resulting linear program to be used in the primal-dual algorithm design in Section IV (2) s.t. (2a) (2b)

To derive an optimal solution to (1), complete knowledge about the system over its entire lifespan is needed, which is apparently not practical. In a dynamic cloud system, the provider should allocate resources on the fly, based on the cur rent amount of available resources, ’s, and users’ bidding bundles including resource demands ’s and valuations ’s, which are not known a priori. We seek to design an online auction mechanism for real-time resource allocation, which also guarantees truthful bidding. We achieve the goals in two steps. First, in Section IV, we assume that a truthful auction mechanism to be carried out in each time-slot is known and guarantees an approximation ratio , and we propose an online algorithm framework that produces a competitive ratio

We design an online algorithm framework as shown in Algorithm 1, which solves the offline optimization problem (1) and its dual (2), using a subroutine running at each time-slot. We next discuss the one-round resource allocation problem to be solved by , as well as the design rationale of the online algorithm framework.

Assuming truthful bids are known, the one-round social wel fare maximization problem at time is as follows, which in cludes the constraints from the offline optimization problem (1) related to the current time-slot, and excludes the user budget constraints (dealt with in the online algorithm framework in stead). , a reduced valuation of user for bundle from the actual valuation adjusted according to the level of its remaining budget, is used in the objective function. The ratio nale will be detailed in Section IV-B. Given , the cloud provider’s current resource supplies ’s, and users’ resource demands ’s, the one-round optimization problem decides the optimal resource allocation at

maximize (3) s.t. (3a) (3b) (3c) Adopting the same dual variables as in the dual of (1) and omitting constraint (3c), we formulate the dual of LP (3) minimize (4) s.t. (4b)

The primal problem (3) is a special case of the multidimen sional multiple-choice 0–1 knapsack problem [31], which is both NP-hard and, more strongly, has no fully polynomial-time approximation schemes unless [32]. What we will pursue in is an auction mechanism, which not only guar antees individual rationality and truthfulness, but also employs a primal-dual approximation algorithm that solves problems (3) and (4) to decide resource allocation in polynomial time with a small approximation ratio. We delay the discussion of the auction mechanism to Section V, but first utilize its properties when analyzing our online algorithm framework. We will show that given a competitive ratio achieved by the one-round auction mechanism, our online algorithm framework achieves a good competitive ratio.

When a good approximation algorithm for one-round resource allocation is in place, the difficulty of designing an online algorithm lies in achieving a good competitive ratio, defined as the maximum ratio between the offline optimal social welfare derived by solving (1) exactly and the social welfare produced by the online algorithm. The budget limits the bundles a user can acquire over the rounds of auctions, leading to different amounts of overall social welfare when the budget is spent in different rounds. The intuition we follow in designing the online algorithm is that inefficiency in social welfare may appear when a user’s budget runs out at an early stage since its future bids become invalid after its budget depletion, narrowing down possible future allocation decisions at the provider, prohibiting larger social welfare. The ideal scenario is that each user’s budget can last for all the rounds of auctions, making it possible for the cloud provider to explore the best resource allocation strategies over the entire span to approach the best overall social welfare.

Under this intuition, we should be cautious when winning a bundle suddenly exhausts a user’s remaining budget. Our main idea in the online algorithm in Algorithm 1 is to associate the resource allocation in each round with the users’ remaining budgets. We introduce an auxiliary variable for each user

, whose value starts at 0, increases with the decrease of the remaining budget of the user, and reaches 1 when the budget is exhausted. Instead of the actual valuation of each bundle, is used in the one-round resource allocation as in (3), such that the bid from a user with a smaller remaining budget will be evaluated less at the cloud provider, leading to a lower chance of ac quiring a bundle. A user’s budget lasts for a longer period of time as a result. is updated after each round of resource allocation in Algorithm 1, where . , which is the maximum ratio between the valuation of any bundle and the corresponding user’s budget. We consider , given that users typically do not put a large proportion of their total budget on one bundle in one round. The increment of is carefully computed (see proof of Theorem 1), such that the budget constraint (1b) is guaranteed over the rounds of online auctions. We set dual variable in the offline dual problem variable after rounds . In this way, the adjustment of in each round can be understood as the adjustment of the dual variable toward an optimal solution to the offline dual problem (2).

The performance of our online algorithm in Algorithm 1 is stated in Theorem 1, with a detailed proof in Appendix A.

Theorem 1: If an auction mechanism in each round produces feasible solutions for (3) and (4) and guarantees the stated one-round competitive ratio, then the online algorithm framework is competitive for optimization problem (1).

We note that when , the competitive ratio ap proaches , i.e., the long-term online optimization framework incurs only an additive loss of in competitive ratio, as compared to the one-round allocation algorithm.

We now present a randomized auction mechanism that efficiently allocates resources according to users’ bids in each time-slot and guarantees individual rationality and truthfulness. The auction mechanism in each round allocates resources according to the one-round resource allocation problem in (3) and decides the payments from the winning bidders. The classic Vickrey–Clarke–Groves (VCG) mecha nism [15] is a potential candidate for our auction design, which assigns items (VM bundles in our case) to bidders in a socially optimal manner by solving a corresponding resource allocation problem, charges each winner the externality it exerts on other bidders, and ensures that the optimal strategy for a bidder is to bid its true valuations. However, our allocation problem in (3) is NP-hard, and hence a VCG mechanism becomes computa tionally infeasible. We therefore resort to a fractional version of the VCG auction for achieving both computational efficiency (polynomial-time complexity) and economic efficiency [social welfare maximization in (3)], by applying the VCG mechanism to the LP relaxation of the integer program (3). The fractional VCG mechanism produces fractional bundle allocation results, which are not practically applicable. We further employ a primal-dual optimization-based decomposition technique that decomposes such an optimal fractional solution into a convex combination of integral solutions, and then design a random ized auction that randomly picks one from the integral solutions as the bundle allocation result in each round and retains the nice properties of a fractional VCG auction. We detail the fractional VCG auction, the decomposition technique, and the randomized auction design in Sections V-A–V-C.

The classic Vickrey–Clarke–Groves (VCG) mecha nism [15] is a potential candidate for our auction design, which assigns items (VM bundles in our case) to bidders in a socially optimal manner by solving a corresponding resource allocation problem, charges each winner the externality it exerts on other bidders, and ensures that the optimal strategy for a bidder is to bid its true valuations. However, our allocation problem in (3) is NP-hard, and hence a VCG mechanism becomes computa tionally infeasible. We therefore resort to a fractional version of the VCG auction for achieving both computational efficiency (polynomial-time complexity) and economic efficiency [social welfare maximization in (3)], by applying the VCG mechanism to the LP relaxation of the integer program (3). The fractional VCG mechanism produces fractional bundle allocation results, which are not practically applicable. We further employ a primal-dual optimization-based decomposition technique that decomposes such an optimal fractional solution into a convex combination of integral solutions, and then design a random ized auction that randomly picks one from the integral solutions as the bundle allocation result in each round and retains the nice properties of a fractional VCG auction. We detail the fractional VCG auction, the decomposition technique, and the randomized auction design in Sections V-A–V-C.

In the fractional VCG auction, the auctioneer solves the LP relaxation of (3) by relaxing constraint (3c) to , to decide the bundle allocation in . Let denote the resulting optimal VCG payment from a winner, the auctioneer solves the LP relaxation again with the winner excluded from the allocation. Let denote the social welfare achieved when winner is excluded. The payment of winner , is: .

The utility function of bidder in a VCG auction is typ ically defined as the difference between its valuation and its payment. In our online auction framework, a user’s utility in each round should be related not only to its valuation and pay ment, but also to its remaining budget: Intuitively, smaller utility gain is appreciated if a user won a bundle when its remaining budget is small, and larger otherwise. We characterize this prop erty using a utility function (5) This utility function is consistent with the social welfare calcu lation in the one-round allocation problem (3). Thus, a user’s budget can potentially last longer, enabling later acquirement of better bundles with the same consumption of budget (i.e., the same payment), contributing to social welfare efficiency over all rounds of auctions.

We show in Theorem 2 that under this utility function, bid ding true valuations is the best strategy for each user in the fractional VCG auction. A nonnegative utility is guaranteed for each bidder, based on VCG auction theory [15].

Theorem 2: The fractional VCG auction that produces fractional allocation and payments is truthful and individually rational.

Since fractional VM bundles are impractical in real-world cloud systems, we next decompose the fractional solution into a combination of integer solutions, which will be used by our randomized auction mechanism. We apply the LP duality-based decomposition technique [11]. The goal of the decomposition is to find and a set of integer solutions ( is an index set), to the one-round resource allocation problem (3), such that , and . The randomized auction in each round can choose the integer solution with probability , achieving a good competitive ratio in social welfare in expectation, as compared to that achieved by the optimal integer solution to (3). However, there in fact does not exist a convex combination of integer solutions, , that equals the fraction solution , because otherwise the expected social welfare achieved by these integer solutions equals that achieved by the fractional solution, which apparently contradicts with the fact that the fractional solution achieves a higher social welfare than any integer solution. Therefore, to achieve a feasible decomposition, we need to scale down the optimal fractional solution by a certain factor. According to [11], if there exists an approximation algorithm that solves the one-round allocation problem (3) with an approximation ratio of and guarantees (where and are the objective function values of the

the scaling factor, and rest assured that a feasible solution to the following decomposition problem exists: minimize (6) s.t. (6a) (6b) (6c)

We give a simple numerical example to illustrate the decom position. Suppose there are two users and two types of VMs. The fractional solution is (0.3, 0.7, 1, 0.7), representing that the first (second) user receives 0.3 (1) unit of VM 1 and 0.7 (0.7) unit of VM 2, respectively. It can be decomposed into two in teger solutions: (1, 0, 1, 0) and (0, 1, 1, 1), with corresponding probabilities 0.3 and 0.7. However, in fact we cannot find any combination of integer solutions satisfying the one-round constraints in (3) (i.e., the integer solutions are not feasible) since the optimal fractional solution should be better than any feasible integer solution. Therefore, we have to divide the fractional so lution by a factor before decomposing it.

We next present a primal-dual algorithm that solves (3) with an approximation ratio , and then discuss how to solve the decomposition problem (6) to obtain and .

1) Primal-Dual Algorithm for One-Round Resource Alloca tion: Algorithm 2 is our primal-dual approximation algorithm to the NP-hard allocation problem (3). is the maximum amount of type resource at datacenter re quired by any bundle in . is the minimum ratio between the total amount of available resource of a type and the amount of the resource required by one bundle. In practice, the resource pool is substantially larger than a single user’s demand, and hence . The main idea of the algorithm is to introduce an auxiliary variable for each type of resource [which is the dual variable associated with constraint (3b)], acting as the unit price in allocation decision. The unit price is updated according to the remaining amount of this type of resource. The algorithm evaluates each bundle acand always chooses the user with a higher bid on a lower valued bundle as the winner.

Theorem 3: Algorithm 2 computes feasible primal and dual solutions for (3) and (4) and guarantees the approximation bound stated in the theorem.

2) Decomposition With LP Duality-Based Technique: To solve the decomposition problem (6), we can first find all the possible integer solutions to (3) using some exhaustive search method, and then directly solve (6) to derive the decomposition coefficients ’s. However, this method has an exponential-time complexity since there are an exponential number of possible integer solutions , and hence an ex ponential number of variables in LP (6). We therefore resort to its dual, formulated in (7), where dual variables and associate with primal constraints (6a) and (6b), respectively maximize (7) s.t. (7a) (7b) Even though the dual (7) has an exponential number of constraints, the ellipsoid method can be applied to solve it in poly nomial time. The ellipsoid method obtains an optimal dual so lution using a polynomial number of separating hyperplanes. Algorithm 2 acts as a key component of a separation oracle for generating these separating hyperplanes, and a feasible integer solution to (3) can be derived each time a separating hyperplane is generated [11]. Hence, a polynomial number of candidate in teger solutions ’s are produced through the process of the ellipsoid method, and the primal problem (6) can be reduced to a linear program with a polynomial number of variables ( ’s) corresponding to these integer solutions. Then, we can solve the reduced primal problem in polynomial time. The correctness of the above decomposition method is given in Lemma 1, with detailed proof and the construction of the separation oracle in Appendix D. Lemma 1: The decomposition method correctly obtains a polynomial number of integer solutions to the one round allocation problem (3) and the probabilities , which solve (6), in polynomial time. C. Randomized Auction Algorithm 3 gives our randomized auction to be carried out in each round of the online algorithm in Algorithm 1. It selects an integer solution produced by the decomposition method with probability . The payment from a winning bidder sat isfies two conditions: 1) The expectation of the payment should be equal to the scale-down fractional payment,

Lemma 1: The decomposition method correctly obtains a polynomial number of integer solutions to the one-round allocation problem (3) and the probabilities, which solve (6), in polynomial time.

C. Randomized Auction. Algorithm 3 gives our randomized auction to be carried out in each round of the online algorithm in Algorithm 1. It selects an integer solution produced by the decomposition method with probability. The payment from a winning bidder satisfies two conditions: the expectation of the payment equals the scale-down fractional payment to preserve truthfulness, and the payment is no larger than the bidder’s valuation of the winning bundle to guarantee individual rationality.

In the fractional VCG auction, the auctioneer solves the LP relaxation of (3) by relaxing constraint (3c) to , to decide the bundle allocation in . Let denote the resulting optimal VCG payment from a winner, the auctioneer solves the LP relaxation again with the winner excluded from the allocation. Let denote the social welfare achieved when winner is excluded. The payment of winner , is:

Theorems 4–5: The one-round randomized auction runs in polynomial time, is truthful and individually rational, and is λ(1+B_max)-competitive. Combined with Algorithm 1, it yields a truthful, individually rational online auction with the competitive ratio stated in Theorem 5.

We have decomposed the fractional solution in Section V-B after scaling it down by the approximation ratio of the one-round allocation Algorithm 2, such that a feasible solution to the decomposition problem (6) is guaranteed. According to Theorem 5, the scale-down factor is closely related to the competitive ratio of our online auction, such that a smaller scale-down factor leads to a better competitive ratio. However, a scale-down factor smaller than may not guarantee a feasible decomposition. We therefore design a binary search algorithm in Algorithm 4 to compute the smallest scale-down factor that enables feasible decomposition.

The algorithm is designed based on a property of the scale down factor, as given in Theorem 6 (proof in Appendix G). With its monotonicity, we can find the smallest, feasible scale down factor using binary search (with arbitrary small error). We should note that this trial-and-error method may improve the performance of our online auction algorithm on average in

Theorem 6: If the fractional allocation can be decom posed under scale-down factor , then it can also be decom posed under any factor .

Theorem 6: If the fractional allocation can be decomposed under scale-down factor λ₁, it can also be decomposed under any factor λ₂>λ₁.

In this section, we propose an improvement of the online algorithm framework when additional information on users’ budget spending is available [10]. Suppose that each user’s total spending over rounds is at least a fraction of its budget. Specifically, user is going to use at least an amount of its overall budget, where . When this minimum budget spending guarantee is in place, we design an improved online algorithm framework , as given in Algorithm 5. We show that this improved online algorithm can achieve a better worst-case competitive ratio , where is the minimum budget spending fraction among all users, as compared to the competitive ratio of the original online auction given in Theorem 5. For example, in the case that , the additive loss in the competitive ratio brought by , as compared to the one-round auction , is ; if we know that all users are going to spend at least % of their respective budget, the additive loss brought by the

The main idea of improving to is as follows. If user spends a large fraction of its overall budget over time, the value of will be close to 1 upon termination of the online algorithm. In the original online algorithm in Algorithm 1, the value of is exponentially increased from 0 to 1 with the in crease of budget consumption since we can prove that no matter what the final value of is, updating exponentially guaran tees a good performance of the online algorithm. Now we know that will at least reach a value (computed according to the minimum budget expenditure based on the update formula of in Algorithm 1), and we can increase the value of linearly with the increase of budget consumption before it reaches , and then increase in the original way (as in Algorithm 1) afterwards. In this way, we can prove that a better competitive ratio can be achieved.

Theorem 7: The improved online framework in Algorithm 5 combined with Algorithm 3 constitutes a truthful, individually rational, competitive online auction.

We evaluate our online auction design using trace-driven simulations. We investigate 23 types of VMs distributed in (default value 9) datacenters, assembled from three types of resources (CPU, RAM, and Disk capacity, ). Users’ resource demands are extracted from Google cluster-usage data [33], which record jobs submitted to the Google cluster with information on their resource demands (CPU, RAM, Disk). We translate each job request in the Google data into a bidding bundle as follows: We generate a set of VMs in

(default value 9) datacenters, assembled from three types of resources (CPU, RAM, and Disk capacity, ). Users’ resource demands are extracted from Google cluster-usage data [33], which record jobs submitted to the Google cluster with information on their resource demands (CPU, RAM, Disk). We translate each job request in the Google data into a bidding bundle as follows: We generate a set of VMs in Table I randomly that altogether can make up the resource demands in the job request; the valuation in the bidding bundle is calculated as the product of the total cost to acquire these VMs according to the VM charges in Table I and a random coefficient in the range of [0.5, 2]. In this way, we obtain a pool of bidding bundles from the Google data. In each round of the online auctions, each user randomly picks (default 3) bundles in the pool, tags each VM in each bundle with a data center randomly selected from the datacenters, and bids the bundles. A user ’s total budget is decided by multiplying the sum of valuations in all the bundles the user may bid in the

rounds of auctions by a random coefficient in the range of [0.5, 1]. We also compute the total amount of resource of each type needed by all the bid bundles of users in each round, scale it down using a random factor in [0, 1], and distribute the overall amount of type resource to datacenters evenly, to obtain the amount of available resource, , for each type of resource in each datacenter at each time. Note that we run random bundle selection for each user over rounds first to estimate users’ budgets ’s and available resources in the datacenters, ’s, before running the experiments to evaluate our online auction with the obtained ’s and ’s. We suppose the maximum ratio between the overall demands for any type of resource in any two bundles in a user’s bid in each time-slot , i.e., , is no larger than 2.5, by picking up bundles with similar resource demands for each user in the auctions, which we believe to reflect the reality better. We also suppose

We compare the performance of four algorithms:

• Alloc, a pure online resource allocation algorithm, with the one-round resource allocation algorithm Algorithm 2 serving in the place of in in Algorithm 1; • Auc, our online auction algorithm presented in Section V-C, i.e., combined with in Algorithm 3; • AucBS, the online auction algorithm with the improved scale-down factor, i.e., adding the binary search in Algorithm 4 to the auction algorithm in ; • AucExt, the improved online auction algorithm with the improved scale-down factor, i.e., adding the binary search in Algorithm 4 to in the improved online auction algorithm in Algorithm 5.

We compare these algorithms in different settings, based on the ratio between the offline optimal social welfare derived by solving (1) exactly and the overall social welfare produced by each online algorithm over rounds, which we refer to as the offline/online ratio. In each scenario, we repeat each experiment for 10 times to derive the average ratios. We first compare the algorithms through varying the number of cloud users from 300 to 3000, while fixing the number of rounds , as illustrated in Fig. 1(a). The offline/online ratio of Auc declines when is large , which is consistent with our theoretical analysis in Theorem 3: The larger the scale of the cloud system, the larger the value of , and consequently the better offline/online ratio results. When users’ truthful resource demands and valuations are as sumed available for free, the pure online resource allocation al gorithm, Alloc, achieves an offline/online ratio close to 1, which shows that our online algorithm framework together with the one-round resource allocation algorithm performs closely to the offline optimum in social welfare, if all the cloud users are coop erative. AucBS achieves a better offline/online ratio as compared to Auc, revealing the usefulness of our improved scale-down factor based on the binary-search Algorithm 4 in decomposing the fractional solution into better integer solutions in practical scenarios. AucExt only slightly outperforms AucBs in this av erage-case ratio since its improvement mainly lies in the theo retical worst-case competitive ratio.

Figure 1. Performance of Alloc, Auc, AucBS, and AucExt (a) under different numbers of users, (b) under different numbers of rounds, (c) with different numbers of bundles, and (d) with different numbers of datacenters.

We next vary the total number of rounds our system is running for while fixing the number of users to 500. Suppose each round is 1 h. We observe in Fig. 1(b) that the offline/online ratio of each algorithm always remains at similar levels, demonstrating the stable performance of our online algorithms regardless of the total number of rounds they are applied into.

We further evaluate the performance of AucBS when the number of bundles each user bids for in each round, , and the number of datacenters, , vary. Fig. 1(c) shows that in general the performance of the improved online auction is better when the number of bundles is smaller. This can be explained as follows: The competitive ratio of our online auction (given in Theorem 5) is related to , the approximation ratio of the one-round resource allocation algorithm in Algorithm 2, which is further closely related to . When is smaller, is potentially smaller, and thus is smaller, leading to a lower competitive ratio of the online auction. In a practical cloud system, the bundles that a user bids are typically different time-slot, e.g., different bundles may specify different numbers of different types of VMs requested from different datacenters, which add up to a similar amount of each type of resource across different bundles, to serve the user’s need in . Therefore, we do not expect a large value of at any time. When the value of is capped (e.g., to 2.5 in our simulation settings), the competitive ratio is bounded even when takes larger values, as shown by the similar offline/online ratios obtained when , or 5, respectively, in Fig. 1(c).

Fig. 1(d) shows that when the total number of datacenters in the cloud system increases, the performance of our online auction degrades slightly because the approximation ratio of Algorithm 2 is larger when is larger. Nevertheless, we do not expect more than a few tens of datacenters in a real-world cloud system, and the offline/online ratio is still acceptable around 2.80 when is 10.

We note that the performance ratios obtained in our simu lations are much smaller than the theoretical ratios computed based on Theorem 5, in the range of 6–7 under the same settings as used in our simulations. This promises the good performance of our online auction algorithm in practice.

Now we compare our online auction algorithm AucBS to an other auction algorithm MUCA [6]. The settings in MUCA are the most similar in the existing literature, which however is a one-round multi-unit combinatorial auction, where each user only demands one resource bundle . The main idea of MUCA is to calculate a virtual price for each bundle based on the amount of resource consumed by a bundle and a randomly assigned unit resource price, and to choose the winning bundle as the one with the highest cost efficiency, i.e., the highest val uation with the lowest virtual price. The competitive ratio of VM instances. In order to do a fair comparison between MUCA and our online algorithm, we run MUCA as a subroutine in stead of in the same online algorithm framework in Algorithm 1; for multiple bundles submitted by one user, the MUCA subroutine greedily chooses the most cost-efficient available bundle.

Fig. 2(a) compares AucBS and MUCA to different numbers of datacenters, . The performance of AucBS is always better than MUCA. With more datacenters, the offline/online ratio of AucBS increases slower than MUCA, exhibiting that our algorithm handles multiple datacenters better. The reason is that the competitive ratio of our algorithm mainly depends on , which increases with very slowly , while the compet itive ratio of MUCA is close to , which increases signif icantly with . Fig. 2(b) compares the performance of both algorithms when they run for different overall time. We observe that the perfor mance of AucBS is again better and the ratios of both algorithms are quite stable with different time lengths.

Finally, we compare our algorithm AucBS to another online auction algorithm, COCA [4]. The main idea of COCA is to calculate an estimated payment for user’s requested resources based on a pricing curve and accept users with positive utility as winners. The original COCA model focuses on one type of resource; for fair comparison, we extend this method to multiple types of resources and multiple resource bundles, create a pricing curve for each type of resource with a coefficient as signed following the unit price of the respective resource in real-world cloud services [34], and always choose the bundle with the largest utility for each user. Note that we simply follow the underlying pricing curve method of COCA, and assign coef ficients in an intuitive fashion. In this way, the extended COCA algorithm retains similar characteristics (such as truthfulness), guaranteed. Before presenting the simulation comparison, we compare the extended COCA algorithm and our AucBS from a theoretical perspective: the theoretical performance of COCA depends on the ratio between the highest and lowest unit valuations, while AucBS is not influenced by the distribution of user valuations. However, the performance of AucBS is negatively affected when is small (e.g., when ) since be comes larger, while the performance of COCA is the same for any values of .

Figure 2. Performance comparison between AucBS, MUCA, and COCA (a) under different numbers of datacenters, (b) under different numbers of rounds, (c) under different numbers of datacenters, and (d) under different numbers of bundles.

guaranteed. Before presenting the simulation comparison, we compare the extended COCA algorithm and our AucBS from a theoretical perspective: the theoretical performance of COCA depends on the ratio between the highest and lowest unit valuations, while AucBS is not influenced by the distribution of user valuations. However, the performance of AucBS is negatively affected when is small (e.g., when ) since be comes larger, while the performance of COCA is the same for any values of .

We compare the offline/online ratio achieved by the two algorithms by taking the average over 10 times of run of each exper iment. Fig. 2(c) shows that the advantage of AucBS is clearer at larger values of . This is because more datacenters result in more types of resources (CPU/RAM/disk at different data centers are treated as different types of resources), and COCA handles multiple types of resources in a simple intuitive fashion, which becomes less efficient when the number of types becomes larger. Fig. 2(d) reveals that the performance of AucBS is again consistently better under different numbers of bundles, .

This work presents the first online combinatorial auction for the VM market in cloud computing. It advances the state-of-the-art of cloud auction design in that all previous VM auction mechanisms are either one-round only or simplify VMs into type-oblivious good (and hence circumvent the challenge imposed by combinatorial auctions). Our online auction com prises three components. First, we design an intuition-driven primal-dual algorithm for translating the online social welfare optimization problem into a series of one-round optimizations, incurring only a small additive penalty in competitive ratio. Second, we apply a randomized auction subframework that can translate a cooperative approximation algorithm to the one-round optimization into an auction. Third, we apply a greedy primal-dual algorithm that approximates the one-round social welfare optimization. We also propose two extensions to the basic online auction framework to further improve the competitive ratio. Our overall online VM auction guarantees a theoretical competitive ratio close to 3.30 in typical scenarios, and its design may shed light on similar auction problems in related settings.

Finally, we briefly discuss practical implementation concerns of dynamic VM provisioning in real-world cloud systems. Latencies for resource partitioning are incurred for VM provi sioning, which are a common issue in IaaS cloud provisioning. To realistically reduce such latencies before a VM can be ready to run, a practical solution is to maintain pools of pre assembled VMs with typical resource configurations (e.g., summarized according to historical user demands) and do hot plug of CPU/RAM/disk [35] upon user’s requests to produce customized VMs. Hotplug of CPU and RAM is highly efficient, while the preparation for the hard disk requires longer time. Nevertheless, users’ demands for disk capacity are typically more uniform than those for CPU and RAM, which allows the cloud provider to prepare some “standard” sizes of virtual disks in advance (e.g., 256 GB, 512 GB, etc.). In this way, the latency for dynamic VM provisioning can be reduced to as low as a few seconds, which is ignorable compared to the hours of VM rental periods. In addition, our work does not deal with

decisions on switching servers on or off are typically made at much larger time intervals than VM provisioning, e.g., once per month or so in Amazon EC2 cloud according to discussions with Amazon employees. We plan to pursue auction mecha nism design for two-time-scale decision making and resource allocation in our future work.

We prove the correctness and competitiveness of $\mathcal{A}_{\mathrm{online}}$ by proving three claims: (1) at the end of the algorithm it produces a feasible solution for dual (2); (2) if $P^{(t)}$ is the objective value of (1) after iteration $t$, $\Delta P^{(t)}=P^{(t)}-P^{(t-1)}$, and $\Delta D^{(t)}$ is defined similarly for dual (2), then the following holds at any round; (3) the output $y_{n,k}^{(t)}$ is almost feasible for primal (1): it satisfies (1a), (1c), (1d), while for (1b) it satisfies the weaker bound below for all $n\in[N]$.

Proof of (1): Since $w_{n,k}^{(t)}\ge b_{n,k}^{(t)}(1-x_n^{(t-1)})$ whether $x_n^{(t-1)}<1$ or $\ge1$, constraint (4a) guarantees the inequality below. Also, $x_n^{(t)}$ is nondecreasing in $t$, so (2a) holds.

Proof of (2): At time $t$, $\Delta P^{(t)}=\sum_{n\in\mathcal{N}}b_{n,k_n}^{(t)}(1-x_n^{(t-1)})p$. Substitute $\sum_{n\in\mathcal{N}}b_{n,k_n}^{(t)}(1-x_n^{(t-1)})$ for $p$ to obtain claim (2).

Proof of (3): Constraints (1a), (1c), and (1d) follow from (3). For (1b), prove by induction the following relation. It holds for $t'=0$. Suppose it holds for $t'-1$. If $n\notin\mathcal{N}$, both sides retain their values from $t'-1$. If $n\in\mathcal{N}$, the update is as shown.

Comparing this with (8), it suffices to show $1+b/B_n\ge\gamma^{b/B_n}$. We use $\ln(1+x)/x\ge\ln(1+y)/y$ for $0\le x\le y\le1$; since $b_{n,k}^{(t)}/B_n\le B_{\max}$, (8) follows.

For a user $n$, let $t'$ be the first time cumulative winning bids reach $B_n$, i.e. $\sum_{t=1}^{t'}\sum_k b_{n,k}^{(t)}y_{n,k}^{(t)}\ge B_n$. By (8), $x_n^{(t')}\ge1$. The algorithm gives no new bundle after $x_n\ge1$, since its weight in $\mathcal{A}_{\mathrm{round}}$ is set to 0. Thus, the first budget crossing is the only overspend; this proves the stated bound in claim (3).

Since each valuation increment is the minimum of the user's valuation and remaining budget, total social welfare is at least $P^{(T)}/(1+B_{\max})$. With $P^{(0)}=D^{(0)}=0$, claim (2) gives $D^{(T)}\le(\nu+1/(\gamma-1))P^{(T)}$. Thus welfare is at least $D^{(T)}/[(1+B_{\max})(\nu+1/(\gamma-1))]$. By duality, the approximation ratio of $\mathcal{A}_{\mathrm{online}}$ is $(1+B_{\max})(\nu+1/(\gamma-1))$.

Suppose user $n$ bids $b_{n,k}^{(t)}$; $w_{n,k}^{(t)}$ is calculated by definition. Omitting that calculation, assume this user submits $w_{n,k}^{(t)}$ and each other user $n'\ne n$ submits $w_{n',k}^{(t)}$. By payment rule $\Pi_n^{(t)}$,

$y^{(t)F}$ maximizes $\sum_{n,k}y_{n,k}^{(t)}w_{n,k}^{(t)}$, the total social welfare. Its value exceeds $\widetilde V_n^{(t)}$, the maximum welfare with the same resources and one fewer user. Thus $u_n^{(t)}\ge0$. If $n$ bids falsely $\widetilde w_{n,k}^{(t)}$, the fractional allocation becomes $\widetilde y_{n,k}^{(t)F}$ and utility is

Again, $y^{(t)F}$ maximizes social welfare, so truthful bidding gives at least the welfare under a false bid.

Constraints (3a) and (3c) are never violated. For (3b), suppose $w_{n^*,k(n^*)}$ is the first bid at iteration $\tau$ that would violate it. Then for some $q\in[Q],r\in[R]$,

Since $C_{q,r}\ge c_{n^*,k(n^*),r,q}$, the accumulated consumption is at least $A_{q,r}-C_{q,r}$. Thus $\frac{\sum_{n\in\mathcal{N}}c_{n,k(n),r,q}}{A_{q,r}-C_{q,r}}\ge1$, and $A_{q,r}z_{q,r}^{\tau-1}\ge z_{\mathrm{base}}$, where $z_{q,r}^{\tau-1}$ is its value before iteration $\tau$. Hence (3b) is not violated.

Lemma 2: If $(s_n^{\tau-1},z_{q,r}^{\tau-1})$ is the dual solution before iteration $\tau$, then $(s_n^{\tau-1},\varepsilon f(z,n^*,k(n^*))z_{q,r}^{\tau-1})$ is feasible for dual (4), where $f(z,n,k)=\frac{w_{n,k}}{\sum_{q\in[Q]}\sum_{r\in[R]}c_{n,k,r,q}z_{q,r}}$; $z$ is the set of current $z_{q,r}^{\tau-1}$ and $n^*$ is the selected user. The proof uses the fact that the selected bundle maximizes this ratio, giving the following feasibility inequality.

For Theorem 3, let $d_1^\tau=\sum_{n\in[N]}s_n$, $d_2^\tau=\sum_{q\in[Q]}\sum_{r\in[R]}A_{q,r}z_{q,r}^\tau$, let $d^*$ be optimal for dual (4), and let $(n^\tau,k^\tau)$ be the bundle selected at iteration $\tau$. There are $\omega$ iterations. Case 1: the algorithm stops with $\mathcal{N}=[N]$ and $d_2^\omega<z_{\mathrm{base}}$; the solution is optimal. Case 2: it stops with $d_2^\omega\ge z_{\mathrm{base}}$ and some $\tau\le\omega$ has $\lambda\ge d^*/d_1^{\tau-1}$; since $d_1^{\tau-1}=p^{\tau-1}$ and is nondecreasing, the solution is a $\lambda$-approximation. Case 3: it stops with $d_2^\omega\ge z_{\mathrm{base}}$ and $\lambda<d^*/d_1^{\tau-1}$ for every $\tau\le\omega$. Define

Using $(1+a)^x\le1+ax$ for $x\in[0,1]$, let $\Delta=\max_{q,r}\frac{A_{q,r}\delta_{q,r}}{A_{q,r}-C_{q,r}}$. The ratio in this maximum is nonincreasing in $A_{q,r}/C_{q,r}$, so its maximum occurs at $A_{q,r}/C_{q,r}=C_{\min}$. Hence $d_2^\tau\le d_2^{\tau-1}+\Delta\sum_{q,r}c_{n^\tau,k^\tau,r,q}z_{q,r}^{\tau-1}$. By the definition of $f$, the sum equals $w_{n^\tau,k^\tau}/f(z,n^\tau,k^\tau)$; the text then invokes a corollary of Lemma 2 and $1+x\le e^x$ to iterate this bound. Since $d_2^0=QR$ and $d_2^\omega\ge z_{\mathrm{base}}$, it concludes the stated $\lambda$-approximation using weak duality.

In each ellipsoid-method iteration, a candidate $\{v_{n,k}^{(t)}\},\tau$ is passed to the separation oracle (Algorithm 6), which tests feasibility. If infeasible, it returns a conflicting set $y_{n,k}^{(t)\ell}$ and uses the following separation plane. If the objective exceeds 1, it suffices to find an allocation with $\sum_{n,k}y_{n,k}^{(t)\ell}v_{n,k}^{(t)}\ge1-\tau$; since the input has $\frac1\lambda\sum_{n,k}y_{n,k}^{(t)F}v_{n,k}^{(t)}\ge1-\tau$, it suffices to find one satisfying the next inequality.

Algorithm 6 — Separation Oracle. Require input $v_{n,k}^{(t)},\tau$. (1) If $\frac1\lambda\sum_n\sum_k y_{n,k}^{(t)F}v_{n,k}^{(t)}+\tau=1$, return “YES”. (2) If it is $<1$, return “NO” with separation plane $\frac1\lambda\sum_n\sum_k y_{n,k}^{(t)F}v_{n,k}^{(t)}+\tau\ge1$. (3) If it is $>1$: (4) set $\widetilde v_{n,k}^{(t)}=\max\{0,v_{n,k}^{(t)}\}$; (5) run $\mathcal{A}_{\mathrm{round}}$ on $\widetilde v,c_{n,k,r,q},A_{q,r}^{(t)}$ to obtain $\widetilde y_{n,k}^{(t)\ell}$, and set $y_{n,k}^{(t)\ell}=\widetilde y_{n,k}^{(t)\ell}$ if $v_{n,k}^{(t)}\ge0$, and 0 otherwise; (6) return “NO” and $\sum_n\sum_k y_{n,k}^{(t)\ell}v_{n,k}^{(t)}+\tau\le1$; (7) end if.

To prove Lemma 1, for any $\{v_{n,k}^{(t)}\}$ find in polynomial time a feasible integer allocation satisfying $\sum_{n,k}y_{n,k}^{(t)\ell}v_{n,k}^{(t)}\ge\frac1\lambda\sum_{n,k}y_{n,k}^{(t)F}v_{n,k}^{(t)}$. Values $v$ can be negative, so do not call $\mathcal{A}_{\mathrm{round}}$ directly: clip them to $\widetilde v=\max\{0,v\}$, run the rounding algorithm, then zero out allocations at negative-value coordinates. The resulting integer allocation preserves the required lower bound.

The optimum of (7), and hence (6), is exactly 1. A feasible value-1 point is $\tau=1,v_{n,k}^{(t)}=0$, so the optimum is at least 1. If it exceeded 1, the preceding method would produce an integer allocation with $\sum_{n,k}y_{n,k}^{(t)\ell}v_{n,k}^{(t)}+\tau>1$, contradicting (7a). Thus the optimum is at most 1. The oracle's cases at objective equal to or below 1 are immediate; above 1 it generates $\widetilde v$ and calls $\mathcal{A}_{\mathrm{round}}$, so the oracle solves (7) as required.

A false bid cannot increase utility, so the scaled-down auction is truthful. Fractional VCG social welfare is $W_F=\sum_{n\in[N]}\min\{\sum_k b_{n,k}^{(t)}y_{n,k}^{(t)F},B_n\}$. The randomized auction's expected welfare is at least $W_F/[\lambda(1+B_{\max})]$, proving the competitive ratio because the optimal fractional welfare is at least the integer optimum. For individual rationality, the definition gives $\sum_{\ell\in L}\beta_\ell\Pi_n^{(t)\ell}=\Pi_n^{(t)F}/\lambda$. Under random choice $\ell$, the paper writes user utility as the next expression; it suffices to show the fractional payment is at most the fractional value.

The only difference between Theorems 5 and 1 is the introduction of randomness. In Theorem 1, only claim (2) is affected. We analyze expected primal and dual increments. At time $t$,

This finishes the proof.

Suppose under scale-down ratio $\lambda_1$, $y_{n,k}^{(t)F}$ is decomposed into integer allocations $y_{n,k}^{(t)\ell}$ with probabilities $\beta_\ell$. To obtain ratio $\lambda_2$, add a “zero” allocation $y_{n,k}^{(t)\ell^*}=0$ and adjust probabilities as follows. The zero allocation has probability $1-\sum_{\ell\in L}\beta'_\ell$. The new probabilities give the decomposition for ratio $\lambda_2$.

First prove $x_n^{(T)}\ge x_n^s$. The total valuation is $\sum_{t\in[T]}b_{n,k_n}^{(t)}=g_nB_n$, and $x_n^{(T)}=x_n^s$. The first two claims follow as in Appendix A. For the third, induct on the following relation, where user $n$ has spent fraction $g_n'$ of its budget. The first case follows by monotonicity; the second by induction as in Appendix A.