Robust combinatorial auction protocol against false-name bids

This paper presents a new combinatorial auction protocol (LDS protocol) that is robust against false-name bids. Inter-net auctions have become an integral part of Electronic Com-merce (EC) and a promising field for applying agent and Ar-tificial Intelligence technologies. Although the Internet pro-vides an excellent infrastructure for combinatorial auctions, we must consider the possibility of a new type of cheating, i.e., an agent tries to profit from submitting several bids under fic-titious names (false-name bids). If there exists no false-name bid, the generalized Vickrey auction (GVA) satisfies individ-ual rationality, Pareto efficiency, and incentive compatibility. On the other hand, when false-name bids are possible, it is the-oretically impossible for a combinatorial auction protocol to simultaneously satisfy these three properties. The Leveled Division Set (LDS) protocol, which is a modi-fication of the GVA, utilizes reservation prices of auctioned goods for making decisions on whether to sell goods in a bun-dle or separately. The LDS protocol satisfies individual ratio-nality and incentive compatibility, although it is not guaran-teed to achieve a Pareto 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 a bundle