Solving the winner determination problem in a divisible-object auction.(Author abstract)

INTRODUCTION

Auctions can be used to allocate one or multiple objects to a set of winning bidders and determine the prices they pay. Depending on the auctioneer's objective, the auction goal may be to maximize the total utility of the agents (welfare maximization) or to maximize the revenue from the allocation. In the former case, when an auction maximizes an aggregate measure of the utility, the allocation is said to be efficient (for more detailed discussion, see Ausubel, 2004; Ausubel and Cramton, 1996; Krishna, 2002; Milgrom, 2004). The auction design should also establish the allocation, payment rules, and bidding dynamics; that is, who gets what, how much the winners pay for the awarded objects, and whether the auction has one or several bidding rounds, respectively.

When only one (indivisible) object is auctioned, the so-called Vickrey (1961) auction can maximize the joint utility of the agents and yield an efficient allocation. In contrast, if multiple identical (indivisible) objects are to be auctioned, a dynamic auction ensures allocation efficiency (Ausubel, 2004) and may also increase the revenue when compared to that of the uniform or discriminatory auctions. If, however, the objects are nonidentical, the auctioneer can use a combinatorial auction. The auctioneer's problem in such auctions (which is overviewed extensively by de Vries and Vohra, 2003) is known to be NP-complete (Rothkopf et al., 1998). To address this issue, Park and Rothkopf (2003) propose a dynamic combinatorial or package-bidding auction.

Sometimes auctioneers seek to allocate an amount of an indivisible commodity in a way that bidders can ask for fractions or shares. For example, in treasury bond auctions, the object to be auctioned, public debt, is considered perfectly divisible. Wilson (1979), who refers to them as share auctions, provides evidence that such auctions generate less revenue than the auctioning of whole objects.

In divisible-object auctions, the bidders' preferences are expressed as individual demand functions, which are assumed to be stepwise and nonincreasing (Krishna, 2002; Ausubel, 2001), meaning that the bidder is willing to pay less (or the same price) for each additional unit. In this case, the objects are perceived by the bidders as substitutes because the marginal value of winning subsequent objects decreases. However, even if the objects are identical, they may appear to the bidders as either substitutes or complements depending on bidder preferences. If perceived as complements, the marginal value of winning subsequent objects increases (Krishna, 2002; Milgrom, 2004).

When shares of a divisible object are to be auctioned, if all bidders have nonincreasing demands, the optimal allocation can be found by arranging the bids in decreasing order and assigning the asked shares until the amount to be auctioned is exhausted. Such a procedure is essentially a greedy-based algorithm. Nevertheless, if at least one bidder's demand exhibits some degree of complementarity, the greedy algorithm may fail to produce an allocation that maximizes the auctioneer's revenue. Such complementarity !s expressed by the fact that over some quantity interval the demand function is nondecreasing.

The implicit assumption in the traditional use of a greedy algorithm in divisible-object auctions is that bidders submit nonincreasing demand functions. However, such demand function cannot capture the preference of a bidder that requires a target share, for which a smaller or larger allocation has little or no value. As an illustration, consider the case of treasury bond auctions. In these auctions, the bidders are usually called primary dealers. The regulation of central banks requires that a primary dealer achieves a targeted amount of such securities if it is to hold its primary dealer status. Therefore, if a primary dealer needs to achieve a given target, that is, a given amount of purchased debt, its demand should indicate a strong preference for the target and less preference for other quantities. The latter is an indication of the need such bidder has for expressing …