Discrete Mathematics and Optimization Seminar
Sept. 8, 2008
Competitive Auctions with Collusion
Kazuo Iwama
Kyoto University
It is widely understood that auction is vulnerable to collusion. For example, [Goldberg and Hartline SODA05] shows that (colluded) auction is truthful if and only if the prices from the auctioneer are completely independent of the bid vector, meaning any auction cannot be competitive. Thus collusion hurts a lot and the main source for this is obviously the fact that the collusion ring is secret. Then can we beat collusion if we do know the ring or the set of bids coming from the colluded people? This is our problem in this paper and our answer is mixed, namely, competitive algorithms now exist, but their competitive ratio is not that attractive. We show that there is an auction mechanism whose competitive ratio is at most lnm, where m is the number of people in the collusion ring. It turns out that this lnm is also a lower bound, i.e., any auction mechanism cannot do better essentially. We also study the case that the information of the collusion ring is not perfect or some error is included. Our model is basically the same as [Goldberg, Hartline and Wright SODA01]. This is a joint work with Takayuki Ichiba.