Communications of the ACM

Communications of the ACM

Software Frameworks For Advanced Procurement Auction Markets

By Martin Bichler, Jayant R. Kalagnanam
Communications of the ACM, December 2006, Vol. 49 No. 12, Pages 104-108
10.1145/1183236.1183239
Comments

Traditional auctions such as the English and first-price sealed-bid auctions have been adopted as another tool for procurement negotiations. The competitive process of auctions serves to aggregate the scattered information about a bidder's valuation and to dynamically set the prices of a trade. As a result, support for auctions and competitive bidding has recently become an integral part of most software packages for electronic sourcing and procurement. Throughout the past decade many new auction formats have been developed, which support more general negotiation and resource allocation tasks. Information systems supporting these types of auctions promise high economic efficiency even in the case of complex preferences, but require special design considerations.

The typical bidding process implemented by the sourcing auction software consists of these steps: bid submission, bid evaluation (also known as winner determination, market clearing, matching, or resource allocation), and the calculation of settlement prices, followed by some feedback to the bidders in an iterative, or open-cry auction (see Figure 1). The auctions close either at a fixed point in time or after a certain closing criterion is met (such as a certain time lapse).

A fundamental shortcoming of auction tools today is their inability to allow for the creation of complex bidding events and request for quotes (RFQ), which allow for a variety of bid structures that exploit complementarities and economies of scale in cost structures of suppliers. As many organizations have begun to realize the efficacy of auctions, interest has emerged to extend basic auction types to support negotiations beyond price, and communicate bids with a more complex set of preferences. For example, procurement of direct inputs is usually very large (in total quantity and dollar value) and requires the use of special price negotiation schemes that incorporate appropriate business practices. Typically, bids in these settings have the following properties:

• Transaction volume tends to be large and suppliers often provide volume discounts;
• Suppliers often provide all-or-nothing bids on a set of items with a special discounted price; and
• Items may have multiple, non-price attributes to be traded off against price attributes.

Volume discount auctions facilitate negotiations on large quantities of a good [6]; combinatorial auctions allow bids on bundles of goods [4]; and multi-attribute auctions facilitate negotiation on multiple attributes of an auction [1]. These multidimensional auction formats have performed well in the lab, and also in a number of real-world implementations in the field [2, 4]. Similar concepts have been described as expressive commerce [11].

After receiving such complex bids in a procurement auction, the buyer needs to identify the set of bids that minimizes total procurement cost subject to allocation constraints such as:

• The number of winning suppliers should be greater than a certain number (to avoid depending too heavily on just a few suppliers), but smaller than a certain number (to avoid too much administrative overhead);
• The maximum amount purchased from each supplier is bounded to a certain limit;
• At least one supplier from a target group (such as a minority group) needs to be chosen; and
• If there are multiple winning bid sets, then one needs to pick the set that arrived first.

Identifying the cost-minimizing bid set subject to these allocation constraints is a difficult optimization problem and difficult to do by hand. Therefore, automated winner determination is central to such complex auction applications.

The many economic and computational aspects that must be considered make the design of auction software a challenging task and have attracted considerable academic attention from the areas of artificial intelligence, economics, operations research, and theoretical computer science [6]. A number of companies have started to address this market, providing commercial, off-the-shelf advanced auction format software for sourcing applications. Examples include CombineNet, DigitalUnion, Emptoris, NetExchange, and TradeExtensions.

The design of software platforms to support respective auctions must address many economic and computational issues in addition to the ones found in traditional information systems design or auction software. We will discuss the main economic aspects important to designing respective auction software. This framework has guided the design of MAP, a software solution developed at IBM's T.J. Watson Research Center, which is used with a number of electronic procurement platforms, as well as marketdesigner.org, an experimental software suite for combinatorial auctions developed at Munich Technical University.

Back to Top

Auction Design Considerations

Auctions can be described as decentralized resource allocation mechanisms, for environments where there are multiple bidders with private utility functions for various resources. The task for the auctioneer is to use an economic mechanism that allocates these resources in an optimal way. The auctioneer has no direct control over the bidding strategy of bidders except through the mechanism. A measure for optimality used in economic theory is allocative efficiency, in which the auction mechanism implements a solution that maximizes the total payoff across all agents. Another goal is payoff maximization, in which the auction achieves a solution that maximizes the payoff to a particular participant (in the sourcing context this agent is the buyer). Auction design can be described as a set of rules, which implements a desired optimal outcome. Different designs have different implications on the strategic behaviors of the bidders. Software implementations of these rules must allow the choice of different rule sets that implement specific desired outcomes. Overall, three types of auction rules exist (see [12] for an overview of auction design parameters):

• The auction protocol, which involves the sequence, syntax, and semantics of messages exchanged by the participants throughout the auction.

• The allocation rules, which include the overall objective of the allocation (efficiency vs. payoff maximization), as well as allocation constraints.

• The payment rules, which determine the payment from or to the winners.

All these auction rules impact the economic as well as computational properties of the respective auction mechanism (see Figure 2). In addition, in iterative auction mechanisms, the auctioneer provides some kind of information feedback to the bidders (such as ask prices) to help them decide how they can improve their bids. We will begin with a discussion of some desirable auction properties, followed by a discussion of the auction rules that lead to these auction properties.

Auction properties. Most of the desirable economic properties of auctions have been analyzed in the context of mechanism design theory [9]. Payoff maximization and allocative efficiency, as defined in the previous section, are two natural design goals in the application of mechanism design to auctions and markets. For example, in a reverse auction a payoff maximizing auction would minimize the buyer's cost in an expected sense. Individual rationality provides that there is a non-negative expected utility for an auction participant and budget-balance assures that there is no net payment made from the auctioneer to the bidders. Speed of convergence refers to the speed with which the auction arrives at a solution.

The auction protocol (including the information feedback to the bidders) and the payment rules impact the bidders' strategies and the strategic complexity of an auction. Strategy-proof mechanisms are designs in which truthful bidding is a dominant strategy for bidders. The second-price sealed-bid (Vickrey) auction is such a strategy-proof mechanism. In a Vickrey auction, the payment of the winning bidder is the bid of the second-best bidder. Note, however, that design without a single dominant strategy for bidders requires bidders to solve a strategy selection problem based on their available information on the other agents. The strategy selection problem is a hard computational problem in most circumstances. Computational complexity has not been a major concern in traditional price-only auctions. The set of allocation problems that occur in multidimensional auctions, however, typically belong to the class of NP-hard problems and require efficient software solutions.

Auction rules. Auction design determines the rules of an auction, which are tailored to the type of resources traded, as well as a set of potential participants.

• Resources: A resource could be a single item (such as a good or service) or multiple heterogeneous items, with single or multiple units of each item. An additional consideration common in real settings is the type of the item; for example, whether it is a standard commodity or a multi-attribute commodity. In the case of multi-attribute items, the bidders might need to specify the non-price attributes and some function describing their utility for different attribute combinations.
• Participants (Market Structure): An auction supports trade negotiations between different numbers of buyers and sellers. In forward auctions a single seller is selling resources to multiple buyers. Alternately, in reverse auctions, a single buyer is sourcing resources from multiple suppliers, as it is common in procurement. Auctions with multiple buyers and sellers are called double auctions or exchanges, and these are commonly used for trading securities and financial instruments, but sometimes also within the supply chain.

The auction rules specify the auction protocol, the allocation rules, as well as the payment to the bidders (see Figure 2). In other words, they specify how the negotiation is conducted. The auction protocol defines rules about the sequence and the contents of messages exchanged throughout an auction. One aspect of an auction protocol is whether it is direct or indirect. The Vickrey auction is a simple form of a direct protocol, where bidders are asked to submit their true valuation directly without receiving feedback from the auction. In an indirect mechanism, such as an open-cry English auction, bidders can adjust bids in response to information feedback from the auction. Information feedback rules determine how much information is released to the bidders during the auction. This information can specify all the bid information (including the identity of competing bidders), only their ranking, only the information about winning bids, or no information at all, as it is the case with sealed bid auctions. A specific form of information feedback in procurement auctions are ask prices. In iterative combinatorial auctions, not only the allocation itself, but also the calculation of ask prices can lead to computational problems [4].

The bid control can be manual by the bidders, or automated by the auctioneer, such as it is the case in a Dutch or Japanese auction. The protocol also specifies whether the auction is ascending or descending, and a minimum bid increment. In addition, activity rules encourage bidders to stay active in multi-round auctions. Finally, closing rules determine the conditions under which an auction is terminated, for example whether at a prespecified date and time, or after a certain time elapsed without new bids.

Traditionally, the types of bids exchanged throughout an auction were simple price quotes. In multidimensional auctions the bidding language has become a fundamental topic [4]. The bidding language specifies the semantics used to express bidders' preferences, their resource requirements, as well as their capabilities. For a single unit, single item commodity, the required bids are simple statements of willingness to pay/accept. For a multi-unit identical item setting, bids need to specify price and quantity. Already this introduces the possibility for allowing volume discounts, where a bid defines the price as a function of the quantity. With multiple items, bids may specify all-or-nothing bids with a price on a bundle of items. In addition, bidders might wish to provide several alternative bids but restrict the choice of bids. The preferences define a bidder's utility for different outcomes. For example, when negotiating over multiple units bidders might indicate a decreasing marginal utility for additional units. A buyer's preference structure is also important when negotiating over attributes for an item.

The allocation rules specify how the auction is matching supply to demand. They include allocation goals, as well as additional allocation constraints. Allocation goals, such as allocative efficiency can impact the objective function of the winner determination problem. Allocation constraints are of high practical relevance and arise out of domain requirements. They are typically defined on:

• The number of winning bidders;
• The quality of the negotiated goods and services;
• The budget spent per supplier or supplier group.

Payments for the winning bidders are typically determined in a separate step. In multi-unit auctions one distinguishes between discriminative auctions, where every winner pays the bid price, and non-discriminative auctions, where the bidders pay the price of the first losing bid. Overall, the set of possible auction rules that must be considered for advanced procurement markets is extensive and influences the software framework design and the required hot spots.

Back to Top

Computational Tasks

While this framework would largely fit traditional auction software, computational aspects have typically not been an issue in this domain. The Internet now enables the exchange of complex preference profiles—such as bidding languages that allowed for completely new auction designs—but also leads to computationally complex allocations problems. Problems range the entire spectrum from simple sorting problems to NP-hard optimization problems.

Combinatorial auctions are used here to illustrate some of the aspects mentioned here, since they have already found application in industrial procurement, transportation, the allocation of spectrum licenses, and airspace system resources [4]. They provide a possibility of achieving efficient allocations in situations where bidders are allowed to place bids on combinations of possibly heterogeneous goods or services. For example, in procurement situations, it can be advantageous to aggregate demand over several locations and plants since this leads to a larger transaction. An additional advantage is that suppliers can provide a discounted bid on a bundle. However, the discounted bid price is valid only if the entire bid is accepted.

The example in the table here shows there is a reverse auction for packaging in three different packaging formats and bids from four suppliers. Each supplier has provided a bundled "all-or-nothing" bid and a price for the bundle represented by the seller column. Notice that each supplier is usually allowed more than one bid and as the number of items increases the number of bids can get quite large. The winner determination problem in such combinatorial reverse auctions can be modeled as an instance of the Weighted Set Covering Problem, which is known to be NP-hard [7]. Similar computational problems can be found in volume discount auctions [6] or multi-attribute auctions [3]. In iterative combinatorial auctions, auctioneers must provide ask prices or other types of information feedback to the bidders, in order to help them improve their bid. Determining linear or non-linear ask prices has been shown to be a central problem in the design of these types of auctions and can be a hard problem in itself [4, 8, 10].

An additional aspect of these types of auctions is the allocation constraints, which can impact the runtime further. For example, in a reverse auction, buyers want to make sure that the entire supply is not sourced from too few suppliers, since this creates a high exposure if some of them are not able to deliver on their promise. Another common constraint is volume-based budget limits, which are often placed as an upper limit on the total volume of the transaction with a particular supplier. In a reverse auction, these limits could either be on the total spend or on the total quantity that is sourced to a supplier. Algorithmic approaches to solve computational problems of this sort with realistic problem sizes are fundamental for applications in the field.

Back to Top

Software Solutions

Throughout the past few years, many new and versatile auction formats have been developed, which allow more flexibility in specifying demand and supply, and ultimately lead to more efficient outcomes in complex negotiation situations. Multidimensional, in particular combinatorial auction designs have been subject of an intense theoretical discussion among economists and computer scientists, and they provide much potential for procurement and sourcing. Although a considerable amount of academic literature has been published on related topics, the experience with these advanced multidimensional auction types in the field is limited. Much progress in this field can be expected from the availability of respective software platforms, allowing for further experimentation, but also for lower barriers to application of these new concepts in the field.

Back to Top

Back to Top

Back to Top

Back to Top

Back to top

The Digital Library is published by the Association for Computing Machinery. Copyright © 2006 ACM, Inc.

---

No entries found