Robust Combinatorial Auction Protocol against False-Name Bids

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 17

Agents

This paper presents a new combinatorial auction protocol (LDS 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, we must consider the possibility of a new type 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 (G.V.A.) 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. The LDS protocol, which is a modification of the G.V.A., 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, although it is not guaranteed 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.