Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Computationally-feasible truthful auctions for convex bundles

Moshe Babaioff and Liad Blumrosen

Abstract

In many economic settings, like spectrum and real-estate auctions, geometric figures on the plane are for sale. Each bidder bids for his desired figure, and the auctioneer has to choose a set of disjoint figures that maximizes the social welfare. In this work, we design mechanisms that are both incentive compatible and computationally feasible for these environments. Since the underlying algorithmic problem is computationally hard, these mechanisms cannot always achieve the optimal welfare; Nevertheless, they do guarantee a fraction of the optimal solution. We differentiate between two information models - when both the desired figures and their values are unknown to the auctioneer or when only the agents’ values are private data. We guarantee different fractions of the optimal welfare for each information model and for different families of figures (e.g., arbitrary convex figures or axis-aligned rectangles). We suggest using a measure on the geometric diversity of the figures for expressing the quality of the approximations that our mechanisms provide.

Details

Publication typeArticle
Published inGames and Economic Behavior (GEB)
URLhttp://ideas.repec.org/a/eee/gamebe/v63y2008i2p588-620.html
Pages588-620
Volume63
Number2
PublisherElsevier
> Publications > Computationally-feasible truthful auctions for convex bundles