A further enhancement of Vickrey-Clarke-Groves (VCG) algorithm applied in an online combinatorial auction

ABSTRACT: Auction is a common name for several types of sales where the price is neither set nor arrived at by negotiation, but is discovered through the process of competitive and open bidding. An auction has well-defined rules that enforce an agreement between the auctioneer and the winning bidder. One of the best-known auction algorithm is the Vickrey-Clarke-Groves Algorithm, named after William Vickrey, Edward H. Clarke, and Theodore Groves for their papers that successively generalized the idea. It is an auction algorithm that can be used for combinatorial auctions in which multiple items/goods are sold simultaneously. It has been exposed for many years that the idea and the algorithm itself can never be changed. Despite that, enhancements would still be much considered. First are the odds that the auctioneer will get a low revenue. It was eliminated by adding a process in which succeeding bids for the same bidder will be compared. Second is the occurrence of false-name bids which revokes the algorithms incentive compatibility. Last is the algorithms susceptibility to bidders collusion which affects its efficiency and undermines the auction severely. In order to preserve the algorithm’s incentive compatibility and its efficiency, it has been made false-named-proof, and collusion-resistant. With that said, a more reliable auction algorithm used in an online combinatorial auction was achieved by modifying the existing Vickrey-Clarke-Groves Algorithm.

Filipiniana