III.

PRICING ALGORITHM

A.

Design Goals

Given the auction setup above, we now seek some algorithm that maps the bids described previously into both resource prices and allocations. The former are important for two reasons. First, these determine how much each winning user pays for its awarded resources. Second, and perhaps more importantly, though, these final prices act as signals to both the operator and the users. If demand exceeds supply for some resource pool, for instance, then this should be reflected by a significant price increase. This increase, in turn, indicates to losing bidders that they should increase their bids in future auctions. Moreover, it indicates to the system operator that there may be a shortage in the corresponding pool; the operator should address this shortage by increasing the supply of resources appropriately.

Any pricing algorithm, therefore, should satisfy the follow- ing criteria:

1)

Clear Signaling: As discussed above, one of the primary goals of a grid-system resource auction is to provide clear signals about supply and demand to the participants. This is easiest to achieve when the final prices are uniform and linear. In other words, all winners within a given resource pool pay exactly the same “price per unit.” These unit prices are clearly announced at the end of the auction so that losing bidders can adjust their behavior in future auctions.

2)

Fair Outcomes: Winners should be those who have “bid enough” and losers those who have bid “too little” given the final auction prices. In this sense, allocations are determined completely by the prices and bids, not by, “unfair,” exogenously provided operator preferences.

3)

Computational Tractability: In a large grid computing environment, any pricing and allocation method has to scale well in the size of the system (i.e., number of resource pools and users). Procedures that require solving NP-hard optimizations are probably not a good choice.

B.

Mathematical Description

We now describe the problem in more formal, mathe- matical terms. Let the final auction prices be given by the R-component vector p and let x_{1}, x_{2}, . . . , x_{U }represent the corresponding user allocations. Furthermore, let W and L represent, respectively, the sets of “winning” and “losing” bidders. Our algorithm design problem can then be expressed as

# SYSTEM:

max_{x,p }subject to:

f (x, p)

x_{u } π u u x x_{u }T u p π_{u }p

∈

{0 ∪ Q_{u}}

≤0 ≥ x T = min < min ≥0 u p q∈Q_{u }q∈Q_{u }

q T p q T p

∀u

∀u ∈ W ∀u ∈ W ∀u ∈ L

We refer to the above optimization as SYSTEM in the sequel.

There are many possible forms for the objective function, f(x, p), and the “best” choice from these varies significantly from application to application. Some possibilities include using (1) the total surplus, i.e. the total difference between what users are willing to pay minus what they actually pay or (2) the total value of trade, i.e. the net value of all resources that change hands. Optimizing over these and then comparing the relative costs and benefits of the outcomes produced are rich areas for future research. In this paper we focus on a tractable solution for satisfying the constraints. Note that these have the following interpretations:

(1) x_{u }∈ {0 ∪ Q_{u}} ∀u: Users either get one of their desired

bundles or nothing at all. Thus, no scaling is allowed. (2) _{u }x_{u }≤ 0: The final allocation leads to a net surplus

of resources. There are no shortages created by awarding resources which are not available for distribution. ( 3 ) π u ≥ x T u p ∀ u ∈ W : A l l w i n n e r s h a v e p r o v i d e d v a l u e s

that are “high enough” given final prices. ( 4 ) x T u p = m i n q ∈ Q u q T p ∀ u ∈ W : W i n n e r s a t t a i n t h e

“cheapest” bundles in their indifference sets. (5) π_{u }< min_{q∈Qu }q^{T}p ∀u ∈ L: All losers have bid “too low”

given the final prices. (6) p ≥ 0: Prices must be non-negative.

Alternatively, one can tighten the second constraint to _{u }x_{u }= 0, i.e. eliminate all “left over,” surplus resources, at the expense of violating the first one. Note that, in practice, it is usually impossible to have the market perfectly clear without scaling some user; supplies and demands will rarely “align” to the necessary extent.

Another possible modification is to replace the last con- straint by p ≥ p_{min}, p ≤ p_{max }where p_{min }and p_{max }are reasonable lower and upper bounds, respectively, on system prices. Doing so can keep the system away from “weird” or “unfair” values. On the downside, though, these additional constraints reduce the size of the feasible region and increase the possibility that no solution exists. In the remainder of this document, we assume for simplicity that p is only constrained to be nonnegative. Replacing this with upper and lower bounds does not significantly change the analysis or our results.

Finally, one might want to relax the win / loss constraints in the case of ties. For instance, if there is one unit of supply, and two users are both willing to pay up to $1.00 for this unit, then the only feasible, “fair” outcome is that both lose and the resource remains unallocated. As this seems wasteful, it may be desirable in this case to break the “fairness” constraints by allowing one to lose and the other to win. This is less of a worry in large systems, though, because the probability of having an exact tie is extremely low.

# C. Ascending Clock Auction

The requirements above rule out the most commonly applied combinatorial auction algorithms (e.g., the Vickrey-Clarke- Groves (VCG) mechanism), as these are generally not com- putationally tractable and do not produce fair, uniform prices