Market Clearability

1 Introduction

Market mechanisms play a central role in AI for several reasons. First, they provide a tool for resource and task allocation in multiagent systems where the agents may be selfinterested. Second, AI techniques can be used to clear markets. For example, there has been a recent surge of research in the AI community on search algorithms [Sandholm, 1999; Fujishima et al., 1999; Sandholm and Suri, 2000] and specialcase polynomial algorithms [Tennenholtz, 2000] for clearing combinatorial auctions. Third, recent electronic commerce server prototypes such as eMediator [Sandholm, 2000] and AuctionBot [Wurman et al., 1998] from academic AI groups have led to the uncovering of a need for fast clearing algorithms for a vast space of market designs.

In this paper we analyze the inherent complexity of, and design algorithms for, clearing auctions and reverse auctions

A3 This work was funded by, and conducted at, CombineNet, Inc., 311 S. Craig St., Pittsburgh, PA 15213.

Subhash Suri

suri@cs.ucsb.edu Department of Computer Science University of California Santa Barbara, CA 93106

in the ubiquitous setting where there are multiple indistinguishable units of an item for sale.

In the largest securities markets where there are multiple units of each item (e.g., stock) for sale, there usually are liquidity providers (market makers on the NASDAQ and a specialist on the NYSE) that carry inventory, and guarantee that trades are possible at essentially any quantity. Therefore, direct matching between buyers and sellers is not absolutely necessary. However, we argue that if technically possible, it would be highly desirable to construct market clearing algorithms that directly match buyers and sellers, and do not rely on an external liquidity provider, for several reasons. First, most ecommerce marketplaces do not have external liquidity providers. Second, liquidity providers incur operating cost, and need to be compensated. This compensation tends to be paid (implicitly) by the market participants. Third, if the items that are being traded are not securities, the SEC does not impose or monitor rules on liquidity-provisioning parties. Finally, even in markets where the liquidity providers are regulated, they frequently violate the regulations (the most famous recent cases are from the NASDAQ).

We study the possibility of algorithms for accomplishing this in the context of price-quantity curves first, and pricequantity pairs second. We analyze markets with and without free disposal of units. We also uncover the complexity implications of non-discriminatory vs. discriminatory pricing.

2 Auctions with Demand Curve Bids

We consider the auction setting where each bidder submits a demand curve indicating the quantity D5B4D4B5 he will accept at each unit price D4. If his bid is cleared at price D4, he receives D5B4D4B5 units, for a total price of D4A1D5B4D4B5. Recently, several computational markets have been built that use piecewise linear [Sandholm, 2000] or step function [Lupien and Rickard, 1997; Sandholm, 2000] demand curves.

We focus mainly on piecewise linear curves because they can approximate any curve arbitrarily closely, and because their complexity (in the sense of measuring the length of the input) can be characterized systematically. In order to keep our discussion simple, we use a single parameter CZ to denote the complexity of the piecewise linear curves. That is, CZ is the largest number of pieces in any bidder's demand curve.

We begin with an elementary lemma, which will be used repeatedly in the following discussion. For now, in order to keep the discussion simple, let us assume that the seller has an infinite supply of units to sell. When the number of units available is finite, the solution follows as an easy corollary of Lemmata 2.1 and 2.2, as is discussed after those lemmata.

Lemma 2.1 Consider a linear demand curve D5 BP CPD4 B7 CQ subject to D4BN D5 AL BC.

• AF If CP AL BC, then an infinite revenue is achievable.
• AF If CP BO BC, then the revenue is maximized at price D4 A3 BP A0 CQ BECP . The corresponding quantity sold at this price is D5 A3 BP CQ BE , and the revenue is A0 CQ BE BGCP .

PROOF. If the slope is non-negative, the revenue is maximized by setting D4 A3 BP BD. The second case is more interesting. The revenue at price D4 equals D4B4CPD4 B7 CQB5 BP CPD4 BE B7 CQD4. Setting the first derivative with respect to D4 to zero, we get BECPD4 BP A0CQ, which yields D4 A3 BP A0 CQ BECP . The second derivative is negative (since CP BO BC), so the revenue is maximized at this D4. The values of D5 and D4 A1 D5 follow easily. BE

The demand curve could also have boundaries, meaning that the bidder expresses his preference by specifying the linear demand curve D5 BP CPD4 B7 CQ but with explicit bounds on the price. If the curve is restricted to the price range CJD4 BD BN D4 BE CL, where D4 BD BO D4 BE , we call it a bounded linear demand curve.

Lemma 2.2 Consider a bounded linear demand curve, D5 BP CPD4 B7 CQ, restricted to the price range CJD4 BD BN D4 BE CL.

• AF If CP AL BC, then the revenue is maximized at price D4 A3 BP D4 BE .
• AF If CP BO BC, then the revenue is maximized either at D4 A3 BP A0 CQ BECP provided D4 BD AK A0 CQ BECP AK D4 BE , or at that endpoint of the range CJD4 BD BN D4 BE CL which is closer to A0 CQ BECP .

PROOF. Let us first consider the case of non-negative slope, CP AL BC. When CP AL BC, we have D5 BC BQ D5 BCBC whenever D4 BC BQ D4 BCBC , and so D4 BC D5 BC BQ D4 BCBC D5 BCBC . Thus, the maximum revenue is achieved at the highest permissible price, which is D4 BE .

When the demand curve has negative slope, Lemma 2.1 tells us that the optimal solution without price boundaries is D4 A3 BP A0CQBPBECP. If this optimal price is within the range CJD4 BD BN D4 BE CL, then it obviously maximizes the revenue, and we are done. So, let us now assume that D4 A3 BIBE CJD4 BD BN D4 BE CL.

Price

Figure 1: Revenue maximization for a linear demand curve with boundaries.

We consider the effect on revenue of changing the price by an amount AY from the unconstrained optimum D4 A3 BP A0CQBPBECP. (See Figure 1.) Let B4D4 BC BN D5 BC B5, where D5 BC BP D5B4D4B5, be an arbitrary point on the linear curve D5 BP CPD4B7CQ. Since CP is the slope of the demand curve, we note that D5 BC A0D5 A3 D4 BC A0D4 A3 BP CPBM Let AY BP D4 BC A0D4 A3 be the change in the price, and let Æ BP D5 BC A0 D5 A3 be the corresponding change in the quantity. Then, it follows that Æ BP CPAY. The revenue at point B4D4 BC BN D5 BC B5 is

In line 4 we used the fact that D4 A3 BP A0 CQ BECP and D5 A3 BP CQ BE . Since the demand curve slope CP is negative, this shows that a change of AY from the unconstrained optimal price D4 A3 BP A0 CQ BECP reduces the revenue by CYCPCYAY BE . Thus, if the price curve is bound to the range CJD4 BD BN D4 BE CL, and D4 A3 BIBE CJD4 BD BN D4 BE CL, the maximum revenue is achieved at either D4 BD or D4 BE , whichever is closer to D4 A3 . BE

In the preceding discussion, we assumed that the seller has an unlimited supply of units. When this supply is bounded by some quantity , the optimal solution can be derived easily, as follows. Of course, a feasible solution exists if and only if AL D1CXD2CUD5 BD BN D5 BE CV. When the slope is positive, the seller sells D1CXD2CUD5 BE BN CV units. When the slope is negative and AL CQBPBE, revenue is maximized at D5 A3 BP CQBPBE. But if BO CQBPBE, then the revenue is maximized at D5 A3 BP .

A piecewise linear demand curve consists of one or more bounded linear curves. We do not require the demand curve to be continuous (i.e., the quantity can "jump" between pieces). Given a single piecewise linear demand curve bid, we can use Lemma 2.2 on each linear piece separately to determine the revenue-maximizing allocation. To lay the groundwork for our auction-clearing algorithm, we next discuss the problem of aggregating the demand over multiple piecewise linear curves.

Demand Curve Aggregation: Consider a set of piecewise linear curves CU BD BN CU BE BN BM BM BM BN CU D2 . Their aggregate curve is a piecewise linear function CU BM CA B7 AXCA B7 such that CUB4D4B5 is the total demand at unit price D4. That is, CUB4D4B5 BP CU BD B4D4B5B7CU BE B4D4B5B7BM BM BMB7 CU D2 B4D4B5BN where CU CX B4D4B5 is the demand by curve CX at unit price D4. For instance, if the demand curves are linear functions D5 BP CP CX D4 B7 CQ CX , CX BP BDBN BEBN BM BM BM BN D2, then their aggregate curve is easily shown to be the linear function D5 BP B4  CX CP CX B5D4 B7  CX CQ CX .

Breakpoints of Aggregate Curve: The aggregate curve CU changes only when one of the component curve changes; that is, the breakpoints of CU are the union of the breakpoints of the component curves. Thus, given a set of D2 piecewise linear curves each of which has at most CZ pieces, their aggregate curve CU has at most D2CZ breakpoints.

Given D2 piecewise linear curves, we can compute their aggregate curve in time B4D2CZ D0D3CVB4D2CZB5B5, as follows, where CZ is maximum number of pieces in any curve. Let DE BD BN DE BE BN BM BM BM BN DE  , where  AK D2CZ, denote the breakpoints of all the component curves, in sorted order. We scan these breakpoints in right to left order (decreasing order of price), and determine the linear aggregate curve between two consecutive breakpoints.

Initially, we compute the linear aggregate function in the range B4DE  BNBDB5, in B4D2B5 time. Next, as we move to the next breakpoint, at most one linear piece changes-one piece may end and another may begin. (If multiple curves begin or end at the same point, we can enforce an artificial order among those, and consider them one at a time.) We can update the linear aggregate by deleting the coefficients of the leaving curve and adding those of the entering curve, and so each update takes B4BDB5 time. Thus, the complete aggregate curve can be determined in time B4D2CZB5, after an initial sorting cost of B4D2CZ D0D3CVB4D2CZB5B5.

While the construction just described should be sufficiently fast for most practical applications, we can build the aggregate curve even faster if only part of the curve is needed.

Lemma 2.3 Given D2 piecewise linear demand curves, we can construct the D1 rightmost pieces of their aggregate curve in time B4D1 D0D3CV D2 B7 D2B5, where D1 BP B4D2CZB5, and each curve has at most CZ pieces.

PROOF. We maintain a priority queue that stores the "next" breakpoint (end, begin, or change) of each component curve. We process events in the order presented by the priority queue: when we delete a breakpoint from the queue, we insert the next linear piece (if any) of the same curve. We initially compute the rightmost piece of the aggregate curve in B4D2B5 time. After that the aggregate curve is updated at each event point in B4BDB5 time. Inserting or deleting an event from the priority queue takes B4D0D3CVD2B5 time, and so the total cost to construct D1 rightmost pieces of the aggregate curve is B4D1 D0D3CV D2 B7 D2B5. BE

2.1 Auctions with Non-Discriminatory Pricing

Say that the seller wants to auction off indistinguishable units of an item. Each of the D2 bidders submits a piecewise linear demand curve bid. In a non-discriminatory auction, the seller determines an optimal price D4 A3 to maximize his revenue, and every buyer pays the same unit price D4 A3 . (The number of items received by bidder CX is computed using his demand curve, evaluated at price D4 A3 .)

As Lemma 2.2 shows, if the seller wants to maximize his revenue, he might not sell all the units. We therefore consider the auction both with and without free disposal. With free disposal, the seller may choose to keep some units (because he can dispose of them for free), but without free disposal, he must sell all the units.

Theorem 2.4 Consider a single-item, multi-unit auction with D2 bidders, each with a piecewise linear demand curve. Under non-discriminatory pricing, the auction can be cleared so as to maximize the seller's revenue in time B4D2CZ D0D3CVB4D2CZB5B5 with or without free disposal, where CZ is the maximum number of pieces in any bidder's demand curve.

PROOF.

• AF [Without Free Disposal.] We construct the aggregate demand curve, incrementally from the right, as described in Lemma 2.3. For each linear piece of the aggregate curve, we check to see if it intersects the supply line D5 BP . If there is an intersection, then the intersection point is a feasible solution. Since the goal is to maximize seller's revenue, we want the rightmost (highest price) intersection. Thus, we can stop the algorithm as soon as we find an intersection. From this price we can determine the quantities sold to each bidder, using their demand curves. (The problem is clearly infeasible when there is no intersection between the line and the aggregate curve.)
• AF [With Free Disposal.] In this case, we compute the entire aggregate curve, since we cannot stop at the rightmost feasible solution. For each linear piece of the aggregate curve, we compute the maximum feasible revenue and keep track of the optimum found so far.
• If the piece lies entirely above the line D5 BP , no feasible solution exists for this piece.
• If the piece is entirely below the line, we take the solution given by Lemma 2.2. In other words, we compute the unconstrained optimum D4 A3 for this linear curve. If D4 A3 is within the price bounds of the piece, we take that solution; otherwise, we choose the endpoint of the linear piece whose price is closer to D4 A3 .
• If the piece intersects the line D5 BP , we compute the unconstrained optimum D5 A3 . If BQ D5 A3 , we take the unconstrained solution; otherwise, we sell units.

Each of the three cases takes constant time to evaluate. Thus the complexity is dominated by the time to build the aggregate curve, which is B4D2CZ D0D3CVB4D2CZB5B5. BE

2.2 Auctions with Discriminatory Pricing

In a discriminatory price auction, the seller determines for each buyer CY a distinct unit price D4 CY with the objective of maximizing his revenue  CY D4 CY D5 CY subject to the supply constraint  CY D5 CY AK . The quantity D5 CY sold to buyer CY is determined from CY's demand curve at price D4 CY . For a fixed set of demand curve bids, the seller's revenue in a discriminatory auction is generally higher (and never lower) than in a non-discriminatory auction, but the latter offers a stronger notion of fairness among bidders. Discriminatory price auctions however do offer a weak form of ex ante fairness: they are anonymous in the sense that had two players swapped their bids, their allocations would also have been swapped.

Intractability under Piecewise Linear Demand Curves

In sharp contrast to a non-discriminatory auction, we show that clearing a discriminatory auction with piecewise linear demand curves is -Complete. In fact, this complexity jump occurs even for the simplest piecewise linear demand curve, a step function.

Step Function Demand Curve: A step function demand curve is defined by a tuple B4D4 CX BN D5 CX B5, indicating a buyer's willingness to buy D5 CX units at or below the unit price D4 CX ; the buyer is not willing to buy any units at price strictly greater than D4 CX .

Theorem 2.5 Consider a single-item, multi-unit auction with D2 bidders, each making a step function demand curve bid. Then the problem of determining a revenue-maximizing allocation using discriminatory pricing, is -Complete. This holds with or without free disposal.

PROOF.

• AF [With Free Disposal.]

We reduce the knapsack problem to our auction problem. Let CUB4D7 BD BN DA BD B5BN B4D7 BE BN DA BE B5BN BM BM BM BN B4D7 D2 BN DA D2 B5BN CV be an instance of the knapsack problem- is the knapsack capacity, D7 CX and DA CX , respectively, are the size and value of item CX. The goal is to choose a subset of items of maximum value with total size at most . We create an instance of the single-itemmulti-unit auction using step function demand curves, as follows. Bidder CX places a step function bid B4DA CX BPD7 CX BN D7 CX B5, meaning he is willing to buy D7 CX units at lot price DA CX (or maximum unit price DA CX BPD7 CX ), and no units for a higher price. The total number of units available is . Since we are using discriminatory pricing, the goal is to choose a subset of bids maximizing the total revenue subject to the total quantity constraint . Now, it is easy to see that any solution to the auction problem is a solution to the knapsack, and vice versa.

• AF [Without Free Disposal.]

We reduce the subset sum problem [Garey and Johnson, 1979] to the auction problem. In the subset sum problem, we are given a set of integers CG BP CUDC BD BN DC BE BN BM BM BM BN DC D2 CV, an integer , and the goal is to choose a subset of CG whose elements sum to exactly . We create D2 bids, where the bidder CX places a step function demand curve bid B4B0BDBN DC CX B5-that is, the buyer is willing to pay one dollar per unit for DC CX units, but does not accept any other quantity. (Actually, the price is immaterial in this transformation, so we use a default value of $1.) The total number of units available is . It is easy to see that the auction without free disposal has a feasible solution if and only if the original subset sum problem has a solution. BE

Thus, we conclude that even with step function demand curve bids, or more generally piecewise linear curve bids, the discriminatory auction becomes intractable.

Polynomial Algorithm for Linear Demand Curves

There is an important case of the discriminatory price auction for which we can clear the market in polynomial time. This is the case where all bids are downward sloping linear demand curves, that is, in the demand curve D5 BP CPD4B7CQ, we have CP BO BC and CQ AL BC. In other words, the buyer's demand decreases linearly as the price increases. We begin by describing the algorithm for auctions with free disposal. Let us suppose that the auctioneer has units of the item for sale. Then, the algorithm has the following steps.

1. Let CB BP CUBDBN BEBN BM BM BM BN D2CV denote the index set of bids.
2. Compute the unconstrainedoptimal solution for each bid independently: B4D4 CY BN D5 CY B5 BP AG A0CQ CY BECP CY BN CQ CY BE AH .
3. If  CYBECB D5 CY AK , then these unconstrained pricequantity pairs are the optimal solution.
4. Otherwise, let Æ BP D1CXD2 CYBECB CUD4 CY CV, and let CO be the index of the bid that achieves this minimum.
5. Set D4 BC CY BP D4 CY B7D4 CO , and D5 BC CY BP CP CY D4 BC CY B7CQ CY , for CY BE CB. That is, increase each bid's unit price by Æ, and determine the newquantity. (Note that D5 BC CY BO D5 CY because CP CY is negative.)
6. If  CYBECB D5 BC CY AK , then set D5 A3 CY BP D5 CY A0 CP CY BV, where BV BP B4  CYBECB CQ CY A0 BE B5BPB4BE  CYBECB CP CY B5, and stop. This is the optimal quantity sold to buyer CY, at the corresponding price D4 A3 CY BP D4 CY A0BV. (Note that both CP CY and BV are negative, and so D5 A3 CY BO D5 CY and D4 A3 CY BQ D4 CY .)
7. Otherwise, set CB BP CB A0 CUCOCV, and go to step 4.

The correctness of the algorithm depends on three facts: B4CPB5 if the unconstrained solution is quantity-infeasible, then one must increase the unit price uniformly for all bids, until either the solution becomes feasible or the price becomes infeasible for some bid, B4CQB5 when the price becomes infeasible for some bid, that bid receives zero units in the optimal solution, and B4CRB5 in the price-interval where the set of feasible bids remains constant, the formula of line (6) gives the optimal solution. Due to lack of space, we omit the proofs of these claims. Instead, we briefly discuss the time complexity of the algorithm. Step (4) repeatedly chooses a bid with the next smallest unconstrained optimal price D4 CY . In order to facilitate this choice, we initially sort the bids in increasing order of D4 CY 's. The key step is to determine whether  CYBECB D5 BC CY AK . However, it is easy to see that  CYBECB D5 BC CY BP  CYBECB D5 CY B7B4  CYBECB CP CY B5D4 D0 . Thus, we can calculate  CYBECB D5 BC CY in B4BDB5 time, by simply keeping track of the sums  CYBECB CP CY and  CYBECB D5 CY . These sums only change when a bid is removed from CB, and can be maintained in B4BDB5 time per update to CB. In summary, once the bids have been sorted, the total cost of running the algorithm is B4D2B5. We summarize this result in the following theorem.

Theorem 2.6 Consider a single-item, multi-unit auction with D2 bidders, each making a downward sloping linear demand curve bid. Under discriminatory pricing, the auction can be cleared so as to maximize revenue in B4D2 D0D3CV D2B5 time, with or without free disposal. BD

Remark. For completeness, we now discuss the complexity of clearing absurd types of linear demand curves. If all the demand curves are upward sloping (the higher the unit price, the more the bidder will buy), then the optimal solution is easily obtained (with or without free disposal) by selling all units to the bidder whose demand line intersects the constant line D5 BP at the highest unit price. This can be determined in B4D2B5 time by calculating the intersection point for every demand line. Next we consider the case where all demand curves are constant (CP BP BC), i.e., the bidders do not care about price. With free disposal, the seller's revenue can be maximized in B4D2B5 time by choosing any bidder (whose quantity is positive, i.e., CQ BQ BC), and charging an infinite price. Without free disposal, finding a feasible solution (finding a combination of the constant curves whose quantities sum up to exactly ) is -Complete because that is equivalent to the subset sum problem. If a feasible solution is found, the seller can charge an infinite price.

3 Reverse Auctions with Supply Curve Bids

In this section, we consider reverse (or, buyer-based) auctions using an analog of demand curve bidding. These types of auctions are frequently used for Requests for Proposals (RFPs) and Requests for Quotes (RFQs). The buyer posts the items (goods, services, etc.) she wants to purchase, and sellers compete for the business by bidding to sell the items. We assume that a buyer wishes to acquire indistinguishable units of a certain item, and each seller submits a supply curve bid.

We start by establishing simple properties of linear supply curves. As in auctions, we consider two settings: free disposal and no free disposal. Under free disposal, the buyer is willing to accept more than the desired units if it leads to lower cost (at worst he can dispose of the extra units for free). Without free disposal, the buyer wants exactly units (or none if the solution is infeasible).

BD When free disposal is not allowed, the only change to the algorithm is this: if the initial unconstrained optimal solution is quantityfeasible, meaning  CYBECB D5 CY AK , instead of stopping, we decrease the price uniformly over all bids, until either the total demand reaches , or some bid becomes infeasible (its price reaches zero). When a bid becomes infeasible, we remove it from CB and continue.

Lemma 3.1 Consider a linear supply curve D5 BP CPD4 B7 CQ subject to D4BN D5 AL BC. Suppose that the buyer wishes to acquire units of the item.

• AF If CP AK BC, then there is a feasible solution if and only if AK CQ. If AK CQ, the cost to the buyer is BC with free disposal, and B4 A0 CQB5BPCP without free disposal.
• AF If CP BQ BC, then the cost of acquiring the items is D1CPDCCUBCBN B4 A0 CQB5BPCPCVBM

PROOF. When the supply curve has non-positive slope, the maximum number of items that can be purchased is CQ. Thus, the trade is feasible if and only if AK CQ. If free disposal is allowed, the buyer buys CQ units at price BC; without free disposal, the buyer pays B4 A0 CQB5BPCP per unit.

If the supply curve has positive slope, the price per unit is increasing with the number of units. If CQ BQ , then the buyer can buy units at zero cost. Otherwise, the buyer purchases exactly units at the unit cost of B4 A0 CQB5BPCP. BE

Lemma 3.2 Consider a bounded linear supply curve, D5 BP CPD4 B7 CQ, restricted to the price range CJD4 BD BN D4 BE CL, where D4 BD BO D4 BE . Suppose the buyer wishes to acquire units of the item.

• AF Without free disposal, a feasible solution exists iff D5 BD AL AL D5 BE , and if feasible, the solution has cost B4 A0 CQB5BPCP.
• AF With free disposal and CP AK BC, a feasible solution exists iff AK D5 BD . Set D5 BC BE BP D1CPDCCUD5 BE BN CV. If feasible, the solution has cost D1CXD2CUD4 BD D5 BD BN D4 BC BE D5 BC BE CV, where D4 BC BE is the price corresponding to D5 BC BE .
• AF With free disposal and CP BQ BC, a feasible solution exists iff AK D5 BE , and in that case the solution has cost D1CPDCCUD4 BD D5 BD BN B4 A0 CQB5BPCPCV.

PROOF. See Figure 2 for illustration. The first case follows easily, since the boundaries of the supply curve dictate that the quantity supplied is in the range CJD5 BD BN D5 BE CL. If lies in this range, the cost equals B4 A0 CQB5BPCP.

In the second case, since the slope is negative, the maximum quantity supplied is D5 BD , and so for feasibility, we must have AK D5 BD . Since the buyer admits free disposal, we can purchase any quantity between and D5 BD , in order to minimize the cost. We define D5 BC BE BP D1CPDCCUD5 BE BN CV so that the feasible range of quantity is CJD5 BD BN D5 BC BE CL. We now invoke the algebra of Lemma 2.2 to observe that quantity D4 A1 D5B4D4B5 decreases the farther the price deviates from D4 A3 BP A0 CQ BECP . (Recall that we have CP AK BC in this case.) Thus, the cost of acquiring at least units in the range CJD5 BD BN D5 BC BE CL is minimized at one of the endpoints of the range. So, we take the smaller of the two values.

Finally, in the third case, the largest quantity supplied by the curve is D5 BE , so the feasibility condition checks whether AK D5 BE . If AK D5 BE , then we can set D5 BC BD BP D1CPDCCU BN D5 BD CV, and our cost is D4 BC BD D5 BC BD , where D4 BC BD is the price corresponding to D5 BC BD . BE

3.1 Reverse Auctions with Non-Discriminatory Pricing

Consider a reverse auction where a buyer wants units of an item. Each of the D2 sellers submits a piecewise linear supply curve. In a non-discriminatory reverse auction, the buyer determines an optimum price D4 A3 to minimize his cost, and sellers supply their share of units at price D4 A3 . (The number of items purchased from seller CX is computed using his supply curve, evaluated at price D4 A3 .) The proof of the following theorem is similar to the proof of Theorem 2.4.

Theorem 3.3 Consider a single-item, multi-unit reverse auctions with D2 bidders, each making a CZ-piece supply curve bid. Under non-discriminatory pricing, the auction can be solved so as to minimize cost in time B4D2CZ D0D3CVB4D2CZB5B5 with or without free disposal.

3.2 Reverse Auctions with Discriminatory Pricing

In a discriminatory reverse auction, the buyer determines for each seller CY a distinct price D4 CY with the objective of minimizing the total cost  CY D4 CY D5 CY subject to the supply constraint  CY D5 CY AL . (Without free disposal, the quantity constraint is an equality.) The problem of clearing such an auction with piecewise linear supply curves again turns out to be - Complete.

Theorem 3.4 A single-item, multi-unit reverse auction with discriminatory pricing and piecewise linear (specifically step function) supply curve bids is -Complete to clear so as to minimize cost (with or without free disposal).

PROOF. The proof without free disposal is the same as in Theorem 2.5. The details of the free disposal case are different, so we discuss that here. We reduce the knapsack problem to the reverse auction, but since knapsack is a value-maximization problem, while the reverse auction is a cost-minimization problem, we need a minor transformation in between.

Let CUB4D7 BD BN DA BD B5BN B4D7 BE BN DA BE B5BN BM BM BM BN B4D7 D2 BN DA D2 B5BN CV be an instance of the knapsack problem-the knapsack has capacity , and item CX has size D7 CX and value DA CX . Let us create an instance of the single-itemmulti-unit reverse auction, as follows.

Bidder CX places a step function bid B4DA CX BN D7 CX B5, meaning he is willing to supply D7 CX units at lot price DA CX (or at any price higher than DA CX ), and no units for a price less than DA CX . Let CC BP  CX D7 CX be the total number of units in all the bids. We set up the auction so that the buyer wishes to purchase at least CC A0 units, at minimum possible price. Let CB BC be the set of bids that are winning bids in the reverse auction. Then, we claim that the remaining bids (those not in CB BC ) form a solution to the knapsack problem. First, since the bids in CB BC have a total of at least CC A0 units, the remaining units are at most , and so the solution is knapsack feasible. Second, since the bids in CB BC provide CC A0 units at least possible price, the total price of the remaining bids is largest possible subject to the knapsack constraint. Thus, the auction problem is -Complete. BE

In fact, the reverse auction without free disposal is - Complete even with linear downward sloping supply curves, unlike the seller auction with linear demand curves which is polytime solvable (except in the absurd case of constant demand lines and no free disposal), cf. Theorem 2.6.

Theorem 3.5 A single-item, multi-unit reverse auction with discriminatory pricing and no free disposal is -Complete to clear so as to minimize cost with downward sloping linear supply curve bids.

PROOF. Consider an instance of the subset sum problem: set of non-negative integers CG BP CUDC BD BN DC BE BN BM BM BM BN DC D2 CV, and an integer . Corresponding to DC CX , we create a linear supply curve D5 BP A0D4 B7 DC CX . The subset sum problem has a solution if and only if the reverse auction without free disposal has a solution for quantity and cost 0. BE

Remark. In the preceding theorem, the price zero is only for convenience. We can easily truncate the supply curves, for example at D4 BP BD, to enforce a minimum unit price of one. In that case, the subset sum has solution if and only if the buyer can acquire exactly  units at total price .

Remark. With free disposal and downward sloping or constant supply lines (that start at D4 BP BC), the optimal solution is obtained in B4D2B5 time by accepting all supply lines at D4 BP BC. If the aggregate quantity is at least , then the solution is feasible and optimal. Otherwise, no solution is feasible.

Remark. With constant supply lines and no free disposal, finding a feasible solution to the reverse auction is - Complete because that corresponds to the subset sum problem. If a feasible solution exists, and the lines start at D4 BP BC, then the optimal solution has zero cost (accept at D4 BP BC each one of the lines that are part of the feasible solution).

Remark. In reverse auctions, downward sloping supply corresponds to quantity discounts. A more common case would be upward sloping supply, i.e., the higher the price, the more the supplier is willing to sell. We analyze upward sloping supply lines in another paper [Sandholm and Suri, 2001], showing clearing complexity of B4D2 D0D3CV D2B5-the same complexity as auctions with downward sloping demand lines.

4 Price-Quantity Pair Bids

In this section we consider auctions where the auctioneer has multiple indistinguishable units of one item to sell, and bidders express their preferences via price-quantity pairs.

Definition 1 In a price-quantity pair bid B4D4BN D5B5, the bidder states a price D4 BE CI B7 that he is willing to pay for D5 BE CI B7 units. BE The bid is atomic, meaning it must be accepted as a whole or rejected-it cannot be accepted fractionally.

Theorem 4.1 (Known) If the seller has units, and each buyer submits one price-quantity bid, then the problem of maximizing revenue is equivalent to the -Complete knapsack problem. It is solvable in pseudo-polynomial time B4D2 BE CE B5 [Garey and Johnson, 1979], where D2 is the number of bids and CE is the maximum price of any bid. It is approximable within a B4BD A0 AYB5 factor of the optimum in polynomial time B4D2 D0D3CV BD AY B7 BD AY BG B5 [Lawler, 1976].

BE In this section we consider the case where D4 is the price for the entire lot D5. If a unit price is stated instead, it can be trivially converted to a lot price by multiplying by D5.

If there is free disposal, the auctioneer can always sell fewer than units because, at worst, he can dispose of the extra units for free. On the other hand, for many real goods there is no free disposal.

Theorem 4.2 If the seller has to sell exactly units (or none if the instance is infeasible), and each buyer submits one price-quantity bid, then even finding a feasible solution is -Complete. The problem of maximizing revenue can be solved optimally in pseudo-polynomial time.

PROOF. Finding a feasible solution is -Complete because the special case where D4 CX BP D5 CX for all CX is equivalent to the subset sum problem, which is -Complete. The problem can be solved in pseudo-polynomial time using a straightforward dynamic program. We omit it due to limited space. BE

In many settings, a bidder could accept alternative quantities at different prices. This can be enabled by allowing each bidder to submit multiple price-quantity bids which are combined with DCD3D6.

Theorem 4.3 If a seller can sell at most units, and each buyer submits a set of alternative price-quantity bids (i.e., DCD3D6 bids), then the problem is -Complete. It can be solved in pseudo-polynomial time B4D2 BE CE B5, where D2 is the number of bidders,  is the maximum number of alternative bids by any buyer, and CE is the maximum price of any bid. The problem can also be approximated within a B4BD A0 AYB5 factor of the optimum in B4D2 D0D3CV BD AY B7 BD AY BG B5 time.

PROOF. -Completeness follows from Theorem 4.1 since each bidder might only submit one price-quantity pair.

We now devise a pseudo-polynomial algorithm. We label the bidders (arbitrarily), BD through D2. Observe that D2CE is an upper bound on the revenue. Let BTB4CXBN DAB5 denote the smallest number of units that can be sold to bidders in the set CUBDBN BEBN BM BM BM BN CXCV with total revenue exactly DA.

1. [Initialize:] Let the alternative price-quantity bids of buyer 1 be B4D5 BD BN D4 BD B5 DCD3D6 B4D5 BE BN D4 BE B5 DCD3D6 BM BM BM B4D5 CY BN D4 CY B5. Set
2. AF BTB4BDBN D4 D8 B5 BP D5 D8 , for D8 BP BDBN BEBN BM BM BM BN CY.
3. AF BTB4BDBN DAB5 BP BD, for all other values of DA.

This algorithm computes a solution in B4D2 BE CE B5 time. This pseudo-polynomial algorithm can be converted to an AYapproximation algorithm with running time B4D2 D0D3CV BD AY B7 BD AY BG B5 using the scheme of Lawler [Lawler, 1976]. BE

While DCD3D6 bids are fully expressive in the sense that they allow a bidder to express any valuation (mapping from the number of units to a price), in many cases, a more compact (and never less compact) representation of the same valuation can be obtained using the D3D6-of-DCD3D6s bidding language BF . An D3D6-of-DCD3D6s bid is a bid where multiple DCD3D6 price-quantity bids are offered and any number of these can be accepted (subject to honoring the overall quantity ):

BF DCD3D6 bids and D3D6-of-DCD3D6s bids were originally introduced for combinatorial auctions where there are multiple distinguish-

CJB4D5 BD BN D4 BD B5 DCD3D6 B4D5 BE BN D4 BE B5 DCD3D6 BM BM BM B4D5 CX BN D4 CX B5CL D3D6

CJB4D5 CZ BN D4 CZ B5 DCD3D6 B4D5 CZB7BD BN D4 CZB7BD B5 DCD3D6 BM BM BM B4D5 D0 BN D4 D0 B5CLBM

Theorem 4.4 If the auctioneer can sell at most units, and each bidder submits an D3D6-of-DCD3D6s bid, then the problem can be solved and approximated with the time complexities stated in Theorem 4.3, where D2 now is the number of DCD3D6disjuncts submitted overall, and  is the maximum number of bids within any DCD3D6-disjunct.

PROOF. We can treat different DCD3D6 bids from the same bidder as coming from different bidders. Since each bidder can be awarded any number of D3D6 bids, this transformation is sound. We can thus assume that each bidder has submitted only one DCD3D6 bid, and solve the problem using the algorithm described in the proof of Theorem 4.3. BE

Now, consider XOR bids and D3D6-of-DCD3D6s bids in settings where the auctioneer has to sell exactly units. It follows from Theorem 4.2 that finding a feasible solution (and therefore also approximation) is -Complete (unlike in the free disposal setting). The problem can be solved in pseudopolynomial time using a dynamic program akin to the ones above where the auctioneer can keep any of the units (we omit these due to limited space).

5 Conclusions

Market mechanisms play a central role in AI as a coordination tool in multiagent systems, and as an application area for algorithm design. Market mechanisms where buyers are directly cleared with sellers, and thus do not require an external liquidity provider, are highly desirable for electronic marketplaces for several reasons. In this paper we studied the inherent complexity of, and designed algorithms for, clearing auctions and reverse auctions with multiple indistinguishable units for sale.

Table 1 summarizes our results on market clearability under demand/supply curves. Note that in non-discriminatory settings, even when each bidder's curve is linear, the aggregate curve might not be linear but piecewise linear (because the bidder's curves have to be ignored below zero quantity).

able items for sale, and bids can be submitted on combinations of items [Sandholm, 1999; 2000]

In addition to the results summarized in the table, we believe that one of the most surprising result of our paper is the following property of discriminatory auctions: at the unconstrained optimum, each bidder generally gets a different price, but interestingly, to accommodate the constraint of limited supply, each bidder's price is incremented equally from the unconstrained optimum.

When bidders express their preferences with price-quantity pairs, the market clearing problem is essentially equivalent to the knapsack problem, and therefore -Complete but solvable in pseudo-polynomial time. With free disposal, the problem admits a polynomial-time approximation scheme, but no such approximation scheme is possible without free disposal. We also describe pseudo-polynomial algorithms for XOR bids and D3D6-of-DCD3D6s bids, and their polynomial approximability when free disposal is allowed.

Our -completeness results carry over to exchanges (where the objective is to maximize surplus, i.e., sum of accepted bids minus sum of accepted asks) directly since auctions and reverse auctions are special cases of exchanges.

Our algorithms help pave the way toward automated electronic markets without external liquidity providers, but at the same time, our -Completeness results curtail the space of automated market designs that are computationally tractable.