DIMACS Theoretical Computer Science Seminar

Title: Competitive Auctions with Collusion

Speaker: Kazuo Iwama, Kyoto University

Date: Wednesday, September 10, 2008 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ


It is widely understood that auctions are vulnerable to collusion. For example, [Goldberg and Hartline SODA05] shows that a (colluded) auction is truthful if and only if the prices from the auctioneer are completely independent of the bid vector, meaning that 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 in which 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 joint work with Takayuki Ichiba.