Treffer: Computationally-feasible truthful auctions for convex bundles

In many economic settings, convex figures on the plane are for sale. For exam-ple, one might want to sell advertising space on a newspaper page. Selfish agents must be motivated to report their true values for the figures as well as to reportthe true figures. Moreover, an approximation algorithm should be used for guaranteeing a reasonable solution for the underlying NP-complete problem. We presenttruthful mechanisms that guarantee a certain fraction of the social welfare, as a function of a measure on the geometric diversity of the shapes. We give the firstapproximation algorithm for packing arbitrary weighted compact convex figures. We use this algorithm, and variants of existing algorithms, to create polynomial-time truthful mechanisms that approximate the social welfare. We show that each mechanism achieves the best approximation over all the mechanisms of its kind.We also study different models of information and a discrete model, where players bid for sets of predefined building blocks. 1 Introduction The intersection between Micro-Economic theory and Computer-Science theory raisesmany new questions. These questions were studied recently by researchers from both disciplines (see, e.g., the surveys in [13, 6]). A leading example for a problem in thisintersection is the Combinatorial Auction problem. In a combinatorial auction, a finite set of heterogenous items is for sale, and each selfish agent has a valuation for everysubset of these items. As the auction designers, we try to find an allocation of the items among the agents that maximizes the "social welfare " (i.e., a set of disjoint packagesthat maximizes the sum of valuations) or at least to find a good approximation. In this paper, we study a variant of combinatorial auctions: e.g., a newspaper wantsto sell an advertising space on a newspaper page. Agents might have different preferences about their desired space: the size of the ad, its location on the page, whether its