Mechanisms for Complement-Free ProcurementShahar Dobzinski∗Department of Computer ScienceCornell University, Ithaca NY [email protected] Papadimitriou†Computer Science DivisionUniversity of California at Berkeley, CA, [email protected] Singer‡Computer Science DivisionUniversity of California at Berkeley, CA, [email protected] study procurement auctions when the buyer has complement-free (subadditive) objectives in the budget feasibility model [18].For general subadditive functions we give a randomized uni-versally truthful mechanism which is an O(log2n) approxi-mation, and an O(log3n) deterministic truthful approxima-tion mechanism; both mechanisms are in the demand oraclemod el. For cut functions, an interesting case of nonincreas-ing objectives, we give both randomized and deterministictruthful and budget feasible approximation mechanisms thatachieve a constant approximation factor.Categories and Subject DescriptorsF.2.8 [Analysis of Algorithms and Problem complex-ity]: MiscellaneousGeneral TermsTheoryKeywordsProcurement Auctions, Incentive Compatibility, Truthful-ness, Budget Feasibility1. INTRODUCTIONWhen a principal wishes to buy items or services p rovidedby strategic agents, her goal is to maximize an objective thatassigns a valuation to any set of items. Since the agents may∗Supported by an Alfred P. Sloan Foundation Fellowshipand a Microsoft Research New Faculty Fellowship.†Supported in part by NSF grant ccf-0635319.‡Supported in part by a Microsoft Research graduate fellow-ship.Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.EC’11, June 5–9, 2011, San Jose, California, USA.Copyright 2011 ACM 978-1-4503-0261-6/11/06 ...$10.00.exaggerate their costs one is interested in designing truthfulmechanisms, in which the allocation and prices are set insuch a way so that it is provably in each agent’s interest toreveal her true cost.Such problems are extensively studied in the frameworkof frugality (see, for example, [1]), where the mechanismdesigner’s aim is to minimize payments. The frugality ap-proach deals with buyer objectives with 0-1 values (e.g., thebuyer wants the set of edges to be a spanning tree of a graph,and all spanning trees are equ ally desirable).1An alternative to frugality which encompasses much moregeneral objectives, is the budget feasibility framework intro-duced in [18] and subsequently studied in [6, 13, 10]. Inbudget feasibility, our goal is to optimize th e buyer’s objec-tive under a budget constraint.A budget feasibility setting is fully defined by the buyer’sobjective, a function mapping subsets of items to the re-als. The important question to ask here is, for which classobjectives one can obtain truthful mechanisms with reason-able approximation guarantees? A fi rst step in this directionwas taken recently in [18], where truthful mechanisms withconstant-factor approximation are developed for the impor-tant class of submodular objective functions. In this paper weextend this result to much more general classes of objectives.What are the limits of our ambition here? One first obser-vation is that even for very simple superadditive objectives(that is, objectives in which V (S ∪ T ) > V (S) + V (T ) forsome sets S, T ) mechanisms of the desired kind (truthful ofbounded approximation ratio) do not exist. Consider for ex-ample the objective in which there is a crucial item a∗andthe valuation V (S) is 1 if a∗∈ S and 0 otherwise. Then it iseasy to see that for this objective there can be n o approxi-mation guarantee, because the seller of the crucial item canalways ext ract the whole budget (pub licly known). In viewof this, we consider objectives that are complement-free, orsubadditive, valuations obeying V (S ∪ T ) ≤ V (S) + V (T ).This is a class that is a su bstantial generalization of sub-mod ular valuation functions. We seek truthful mechanismswith reasonable approximation guarantees for comp lement-free objectives. As the example ab ove shows, in procure-1It is problematic to extend the frugality framework beyond0-1 objectives, because that would bring us in the trickyrealm of multi-objective optimization. This reduces the prob-lem to budget feasibility: fixing the budget and maximizingthe objective function.ment auctions often desirable mechanisms are impossibleeven with unbounded computational resources. Therefore,we focus on the question of existence of a mechanism of thedesired kind, with less attention on computational efficiency(even though, as it happens, our algorithms are polynomialtime).1.1 Our ResultsFor complement-free (subadditive) objectives we first givea randomized O(log2n) ap proximation mechanism th at isuniversally truthful and budget feasible. We derandom-ize this mechanism and present a deterministic mechanismfor this domain with an O(log3n) approximation guarantee.Since subadditive functions may require representation thatis exponential in the number of agents, we assume we aregiven access to a demand oracle. Since the weaker valuequery oracles result in inapproximability as shown in [18], astronger oracle model such as the one used here is required.We also examine another class of objectives, namely cutfunctions: when agents represent vertices on a graph, a cutfunction is the cardinality of the cut procured. The op ti-mization problem is a variant of the celebrated MAX-CUTproblem, and the setting provides a nontrivial case valuationfunctions that can decrease in value as items are added. Forsuch functions we give a randomized constant factor approx -imation mechanism that is universally truthful and budgetfeasible, as well as a deterministic constant factor approxi-mation mechanism.The deterministic mechanisms, for both classes of objec-tives, are based on their randomized analogues. In bothcases derandomization in a man ner that preserves truthful-ness is nontrivial and requires constructing “monotone es-timators” that are crucial for obtaining bounded approxi-mation guarantees. Each construction uses a different tech-nique, though their underlying principle is similar. We dis-cuss