Article Preview
Top1. Introduction
The rapid growth of e-commerce in recent years can be attributed in large measure to the increasing popularity of online (i.e., iterative continuous) auctions, such as the eBay C2C auctions or B2B auction platforms like Ariba. But online auctions still remain confined to single items. When items are complementary in nature (Klemperer, 2004; Krishna 2002), i.e., if the value to the bidders of the items taken together exceeds the sum of the values of individual items, the complementarities among the items create an exposure problem (Klemperer, 2004). In such cases, allowing bids on packages (i.e., bundles) of items increases bidder satisfaction, and also yields higher revenue for the seller. The auctions which allow bidders to submit their bids after considering the complementarity (or substitutability) of the items are known as combinatorial auctions. Consider the Federal Communications Commission (FCC) spectrum auctions (Goeree et al., 2006; Kwasnica et al., 2005), in which the FCC offers licenses for sale to wireless telephone operators, giving them legal rights to operate in selected frequencies and geographical regions. A buyer is usually interested in acquiring a combination of licenses, and is willing to pay more for it than the sum of the prices of the individual licenses. Other examples can be cited from business domains such as logistics, transportation and travel, and supply chain management (Caplice & Sheffi, 2006; Greewald & Boyan, 2001; Ledyard et al., 2002; Rassenti et al., 1982, Walsh et al., 2000). If the authors could organize online combinatorial auctions efficiently, the monetary volume of business realized through e-commerce would grow far more sharply.
In a combinatorial auction, after the bidders submit their bids on their preferred packages, the auctioneer determines the set of feasible bids which maximizes the seller’s revenue. The revenue maximization problem is known as the Winner Determination Problem (WDP) (Sandholm, 2002). When the auction is online, where bidders must be permitted to join and leave the auction at any time, the WDP needs to be solved incrementally after each bid to provide useful information feedback to bidders. Specifically, bidders must be supplied the current valuations of packages to enable them to place meaningful bids during the auction. In addition, bidders must be provided a software agent that will help them keep track of the current state of an online auction. Therefore, it is infeasible to organize an online combinatorial auction without an agent based system.
To summarize, the agent based system should be able to address the following two issues:
- 1.
The seller must be able to solve the WDP fairly quickly after each bid, and also determine the provisional winning prices of the bundles. The seller can then provide bidders useful feedback on the current state of the auction, allowing them to place more meaningful bids with less effort.
- 2.
The participation and monitoring costs of the bidders must not be too high.
Recently, Adomavicius and Gupta (2005) have proposed a dynamic programming (DP) algorithm that makes use of more memory to reduce the time needed to solve the WDP. Their method involves keeping the information feedback parameters of all the possible packages in memory, and therefore, requires a memory table exponential in the number of items on auction. This imposes a limit on the number of items. However, in a C2C auction or even in the case of some B2B auctions, it is anticipated that the number of items will be large. The fact that it is impractical to run mathematical programming packages like CPLEX to solve WDP repeatedly and provide information feedback to bidders, further adds to the complexity of the problem.
Therefore, the challenge in conducting an online combinatorial auction is to design an agent based system which will reduce the costs of the bidders and provide relevant information feedback to bidders while accommodating a large number of items. None of the combinatorial auction schemes proposed so far (Cramton et al., 2005) is suitable for online adoption.