
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.



