Experimenting with Proxy Agents in Online Combinatorial Auctions

Experimenting with Proxy Agents in Online Combinatorial Auctions

Soumyakanti Chakraborty, Anup Kumar Sen, Amitava Bagchi
Copyright: © 2014 |Pages: 20
DOI: 10.4018/ijiit.2014040104
(Individual Articles)
No Current Special Offers


To promote online eBay-like combinatorial auctions, the authors experiment with a distributive agent based mechanism PRACA which attempts to address two research issues. First, the scheme uses an algorithm CompDL to incrementally solve the Winner Determination Problem under limited memory for any package that the bidder may be interested to bid at any time. This helps the bidder to bid effectively knowing the current state of the auction. CompDL thereby allows a large number of items to be put on auction. Second, PRACA supplies an autonomous proxy agent to each bidder who logs in to an ongoing auction; this agent bids on the bidder's behalf and relays data on requested packages to the bidder. Therefore, PRACA helps in reducing operational overheads of seller and bidder in online combinatorial auctions. Both schemes have been implemented and the efficacy of the approach is demonstrated by experiments.
Article Preview

1. 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.

Complete Article List

Search this Journal:
Volume 20: 1 Issue (2024)
Volume 19: 1 Issue (2023)
Volume 18: 4 Issues (2022): 3 Released, 1 Forthcoming
Volume 17: 4 Issues (2021)
Volume 16: 4 Issues (2020)
Volume 15: 4 Issues (2019)
Volume 14: 4 Issues (2018)
Volume 13: 4 Issues (2017)
Volume 12: 4 Issues (2016)
Volume 11: 4 Issues (2015)
Volume 10: 4 Issues (2014)
Volume 9: 4 Issues (2013)
Volume 8: 4 Issues (2012)
Volume 7: 4 Issues (2011)
Volume 6: 4 Issues (2010)
Volume 5: 4 Issues (2009)
Volume 4: 4 Issues (2008)
Volume 3: 4 Issues (2007)
Volume 2: 4 Issues (2006)
Volume 1: 4 Issues (2005)
View Complete Journal Contents Listing