### 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

Abstract:

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.