X hits on this document

PDF document

google-cluster-auctions.pdf - page 4 / 8





4 / 8

User 1 Proxy

x (t)


User 2 Proxy

x (t)



User 3 Proxy

. . .

x (t)


x (t)




User U Proxy

Price Clock


Fig. 1.


of price

update loop in ascending




auctioneer collects the demands and/or supplies from each bidder proxy as a function of the current price. If demand exceeds supply, then the price clock

is increased and the process repeats.

without significant “post processing” (see [10] for a more detailed discussion).

Instead, we propose using an ascending clock auction in- spired by the “Simultaneous Clock Auction” from [11] and the updated, more advanced “Clock-Proxy Auction” from [12]. In both of these, the current price for each resource is represented by a “clock” that all participants can see. At each time slot, users name the quantities of each resource desired / offered at the given price. If the excess demand vector, u xu, has all nonpositive components, then the auction ends. Otherwise, the auctioneer increases the prices for those items which have positive excess demand, and again solicits bids. Hence, the auction allows users to “discover” prices in real time and ends with a “fair” allocation in which all users pay / receive payment in proportion to uniform resource prices.

This “clock” approach has many desirable properties (de- tailed later) but requires feedback from the users over mul- tiple rounds. We can adapt the algorithm to our single- round environment, however, by introducing bidder proxies that automatically adjust their demands on behalf of the real bidders. Although these proxies can be extremely sophisticated in practice, for our purposes here we model them as functions, Gu(p) qu, mapping the current prices into the “best” bundle from each Qu set. In particular, we have



where qˆu


u T i f qˆ p πu



a r g m i n q T u p



Given this proxy framework, we can time index the system state and then run a simulated, multi-round clock auction, as described below and shown in Figure 1.

1) Algorithm: From the discussion above, we have the following settlement algorithm:

Algorithm 1 Ascending Clock Auction

1: Given: U users, R resources, starting prices p˜, update

increment function g : (x, p) RR 2: Set t = 0, p(0) = p˜ 3: loop


Update prices: p(t + 1) = p(t) + g(x(t), p(t))


t t+1


end if

4: 5: 6: 7: 8:


Collect bids: xu(t) = Gu(p(t)) u u C a l c u l a t e e x c e s s d e m a n d : z ( t ) =

if z(t) 0 then

Break else

12: end loop

2) Parameters: As formulated above, the clock auction requires two input parameters: (1) p˜, a set of starting prices, and (2) g(x, p), a function for setting the price increment. The first should be set well below the expected settling prices (to ensure positive excess demand). On the other hand, setting these too low may unnecessarily prolong the auction. If there exist “reserve” prices that serve as lower bounds on all bids, then these are a reasonable choice. See Section IV below for one possible method of setting the former.

The g(·) function, on the other hand, maps the current sys- tem state into an R-dimensional vector of nonnegative, additive price updates. The simplest choice is g(x, p) = αz(t)+ where α is some small positive scalar, z(t) is the excess demand defined above, and the notation x+ is equivalent to max(x, 0), taken componentwise. In practice, however, this often causes the prices to move too quickly in the early rounds of the auction and then too slowly in the later ones. A more effective choice is to construct g such that no price changes by more than some fixed fraction, say δ:

g(x, p) = min(αz(t)+, δe)


where e is the R-dimensional vector of all 1’s and the latter minimization is taken componentwise.

Another adjustment to consider for g(·) is a normalization for differences in the base resource prices. If some resource (e.g. disk) is much cheaper per unit than the others (e.g., CPU and RAM), then it may be helpful to reduce its increment rate. Otherwise, the final prices may be out of proportion from their expected relative sizes.

3) Convergence: Even if there exists a solution to SYS- TEM, there may exist price directions along which excess demand is never eliminated. Hence, it is plausible that the clock auction may not converge even though its prices increase monotonically from round to round. We note, however, that such convergence is guaranteed if all participants are either “pure buyers” or “pure sellers,” i.e. each element of Qu is either all nonnegative or all nonpositive for each user. The reasoning behind this is that, for each “pure buyer” there exists some price threshold at which this user “drops out” and no

Document info
Document views26
Page views26
Page last viewedThu Jan 19 12:01:10 UTC 2017