An approach to detecting shill-biddable allocations in combinatorial auctions

This paper presents a method for discovering and detecting shill bids in combinatorial auctions. Combinatorial auctions have been studied very widely. The Generalized Vickrey Auction (GVA) is one of the most important combinatorial auctions because it can satisfy the strategy-proof property and Pareto efficiency. As Yokoo et al. pointed out, false-name bids and shill bids pose an emerging problem for auctions, since on the Internet it is easy to establish different e-mail addresses and accounts for auction sites. Yokoo et al. proved that GVA cannot satisfy the false-name-proof property. Moreover, they proved that there is no auction protocol that can satisfy all three of the above major properties. Their approach concentrates on designing new mechanisms. As a new approach against shill-bids, in this paper, we propose a method for finding shill bids with the GVA in order to avoid them. Our algorithm can judge whether there might be a shill bid from the results of the GVA's procedure. However, a straightforward way to detect shill bids requires an exponential amount of computing power because we need to check all possible combinations of bidders. Therefore, in this paper we propose an improved method for finding a shill bidder. The method is based on winning bidders, which can dramatically reduce the computational cost. The results demonstrate that the proposed method successfully reduces the computational cost needed to find shill bids. The contribution of our work is in the integration of the theory and detecting fraud in combinatorial auctions.