Truthful and Competitive Double Auctions

In this paper we consider the problem of designing a mechanism for double auctions where bidders each bid to buy or sell one unit of a single commodity. We assume that each bidder's utility value for the item is private to them and we focus on truthful mechanisms, ones were the bidders' optimal strategy is to bid their true utility. The profit of the auctioneer is the difference between the total payments from buyers and total to the sellers. We aim to maximize this profit. We extend the competitive analysis framework of basic auctions and give an upper bound on the profit of any truthful double auction. We then reduce the competitive double auction problem to basic auctions by showing that any competitive basic auction can be converted into a competitive double auction with a competitive ratio of twice that of the basic auction. In addition, we show that better competitive ratios can be obtained by directly adapting basic auction techniques to the double auction problem. This result provides insight into the design of profit maximizing mechanisms in general.

esa02-auctions.pdf
PDF file
esa02-auctions.ps
PostScript file

In  Proceedings of the 10th European Symposium on Algorithms (ESA '02)

Publisher  Springer-Verlag
All copyrights reserved by Springer 2002.

Details

TypeInproceedings
URLhttp://www.springer-ny.com/
> Publications > Truthful and Competitive Double Auctions