Robust Combinatorial Auction Protocol Against False-Name Bids

Abstract

This paper presents a new combinatorial auction protocol that is robust against false-name bids. Internet auctions have become an integral part of Electronic Commerce (EC) and a promising field for applying agent and Artificial Intelligence technologies. Although the Internet provides an excellent infrastructure for combinatorial auctions, wemust consider the possibilityofanewtype of cheating, i.e., an agent tries to profit from submitting several bids under fictitious names (false-name bids). If there exists no false-name bid, the Generalized Vickrey Auction protocol (GVA) satisfies individual rationality,Pareto efficiency, and incentive compatibility. On the other hand, when false-name bids are possible, it is theoretically impossible for a combinatorial auction protocol to simultaneously satisfy these three properties. Our newly developed Leveled Division Set (LDS) protocol, which is a modification of the GVA, utilizes reservation prices of auctioned goods for making decisions on whether to sell goods in a bundle or separately. The LDS protocol satisfies individual rationality and incentive compatibility even if agents can submit false-name bids, although it is not guaranteed to achieveaPareto efficient social surplus. Simulation results show that the LDS protocol can achieve a better social surplus than that for a protocol that always sells goods in one bundle. Key words: Mechanism Design, Auction, Game Theory, Electronic Commerce 3 Corresponding author. Email addresses: [email protected] (Makoto Yokoo), [email protected] (Yuko Sakurai), [email protected] (Shigeo Matsubara). URLs: http://www.kecl.ntt.co.jp/csl/ccrg/members/yokoo (Makoto Yokoo), http://www.kecl.ntt.co.jp/csl/ccrg/members/yuko (Yuko Sakurai), http://www.kecl.ntt.co.j...