Yuko Sakurai, Makoto Yokoo, and Shigeo Matsubara, NTT Communication Science Laboratories
Electronic Commerce (EC) has rapidly grown with the expansion of the Internet. Among these activities, auctions have recently achieved huge popularity, and have become a promising field for applying agent and Artificial Intelligence technologies. Although the Internet provides an infrastructure for much cheaper auctioning with many more sellers and buyers, we must consider the possibility of a new type of cheating, i.e., an agent tries to get some profit by submitting several bids under fictitious names (false-name bids). Although false-name bids are easier to execute than forming coalitions, the vulnerability of auction protocols to false-name bids has not been discussed before. In this paper, we examine the robustness of the generalized Vickrey auction (G.V.A.) against false-name bids. The G.V.A. has the best theoretical background among various auction mechanisms, i.e., it has proved to be incentive compatible and be able to achieve a Pareto efficient allocation. We show that false-name bids can be effective, i.e., the G.V.A. is no longer incentive compatible under the possibilities of false-name bids, when the marginal utility of an item increases or goods are complements. Moreover, we prove that under these conditions, there exists no single-round sealed-bid auction protocol that simultaneously satisfies individual rationality, Pareto efficiency, and incentive compatibility.