Yuko Sakurai, Makoto Yokoo, and Shigeo Matsubara
Electronic Commerce 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 collusion, 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 may be effective, i.e., the G.V.A. loses incentive compatibility under the possibility of false-name bids, when the marginal utility of an item increases or goods are complementary. Moreover, we prove that there exists no single-round sealed-bid auction protocol that simultaneously satisfies individual rationality, Pareto efficiency, and incentive compatibility in all cases if agents can submit false-name bids.