View Full Document

Mechanisms for Complement-Free Procurement



View the full content.
View Full Document
View Full Document

5 views

Unformatted text preview:

Mechanisms for Complement Free Procurement Shahar Dobzinski Christos Papadimitriou Department of Computer Science Cornell University Ithaca NY 14853 Computer Science Division University of California at Berkeley CA 94720 shahar cs cornell edu christos cs berkeley edu Yaron Singer Computer Science Division University of California at Berkeley CA 94720 yaron cs berkeley edu ABSTRACT We study procurement auctions when the buyer has complementfree subadditive objectives in the budget feasibility model 18 For general subadditive functions we give a randomized universally truthful mechanism which is an O log 2 n approximation and an O log3 n deterministic truthful approximation mechanism both mechanisms are in the demand oracle model For cut functions an interesting case of nonincreasing objectives we give both randomized and deterministic truthful and budget feasible approximation mechanisms that achieve a constant approximation factor Categories and Subject Descriptors F 2 8 Analysis of Algorithms and Problem complexity Miscellaneous General Terms Theory Keywords Procurement Auctions Incentive Compatibility Truthfulness Budget Feasibility 1 INTRODUCTION When a principal wishes to buy items or services provided by strategic agents her goal is to maximize an objective that assigns a valuation to any set of items Since the agents may Supported by an Alfred P Sloan Foundation Fellowship and a Microsoft Research New Faculty Fellowship Supported in part by NSF grant ccf 0635319 Supported in part by a Microsoft Research graduate fellowship Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page To copy otherwise to republish to post on servers or to redistribute to lists requires prior specific permission and or a fee EC 11 June 5 9 2011 San Jose California



Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Mechanisms for Complement-Free Procurement and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Mechanisms for Complement-Free Procurement and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?