Hdl Handle:
http://hdl.handle.net/10149/586887
Title:
Combinatorial Auctions without Money
Authors:
Fotakis, D. (Dimitris); Krysta, P. (Piotr); Ventre, C. (Carmine) ( 0000-0003-1464-1215 )
Affiliation:
Teesside University. Digital Futures Institute
Publisher:
Springer
Journal:
Algorithmica
Issue Date:
29-Dec-2015
URI:
http://hdl.handle.net/10149/586887
DOI:
10.1007/s00453-015-0105-8
Additional Links:
http://link.springer.com/article/10.1007/s00453-015-0105-8
Abstract:
Algorithmic Mechanism Design attempts to marry computation and incentives, mainly by leveraging monetary transfers between designer and selfish agents involved. This is principally because in absence of money, very little can be done to enforce truthfulness. However, in certain applications, money is unavailable, morally unacceptable or might simply be at odds with the objective of the mechanism. For example, in Combinatorial Auctions (CAs), the paradigmatic problem of the area, we aim at solutions of maximum social welfare but still charge the society to ensure truthfulness. Additionally, truthfulness of CAs is poorly understood already in the case in which bidders happen to be interested in only two different sets of goods. We focus on the design of incentive-compatible CAs without money in the general setting of k- minded bidders. We trade monetary transfers with the observation that the mechanism can detect certain lies of the bidders: i.e., we study truthful CAs with verification and without money. We prove a characterization of truthful mechanisms, which makes an interesting parallel with the well-understood case of CAs with money for single-minded bidders. We then give a host of upper bounds on the approximation ratio obtained by either deterministic or randomized truthful mechanisms when the sets and valuations are private knowledge of the bidders. (Most of these mechanisms run in polynomial time and return solutions with (nearly) best possible approximation guarantees.) We complement these positive results with a number of lower bounds (some of which are essentially tight) that hold in the easier case of public sets. We thus provide an almost complete picture of truthfully approximating CAs in this general setting with multi-dimensional bidders.
Type:
Article
Language:
en
ISSN:
0178-4617
Rights:
Following 12 month embargo author can archive post-print (ie final draft post-refereeing). For full details see http://www.sherpa.ac.uk/romeo [Accessed: 21/12/2015]

Full metadata record

DC FieldValue Language
dc.contributor.authorFotakis, D. (Dimitris)en
dc.contributor.authorKrysta, P. (Piotr)en
dc.contributor.authorVentre, C. (Carmine)en
dc.date.accessioned2015-12-21T13:22:15Zen
dc.date.available2015-12-21T13:22:15Zen
dc.date.issued2015-12-29en
dc.identifier.citationAlgorithmica; online first 29 Dec 2015en
dc.identifier.issn0178-4617en
dc.identifier.doi10.1007/s00453-015-0105-8en
dc.identifier.otherEPSRC grant EP/M018113/1en
dc.identifier.urihttp://hdl.handle.net/10149/586887en
dc.description.abstractAlgorithmic Mechanism Design attempts to marry computation and incentives, mainly by leveraging monetary transfers between designer and selfish agents involved. This is principally because in absence of money, very little can be done to enforce truthfulness. However, in certain applications, money is unavailable, morally unacceptable or might simply be at odds with the objective of the mechanism. For example, in Combinatorial Auctions (CAs), the paradigmatic problem of the area, we aim at solutions of maximum social welfare but still charge the society to ensure truthfulness. Additionally, truthfulness of CAs is poorly understood already in the case in which bidders happen to be interested in only two different sets of goods. We focus on the design of incentive-compatible CAs without money in the general setting of k- minded bidders. We trade monetary transfers with the observation that the mechanism can detect certain lies of the bidders: i.e., we study truthful CAs with verification and without money. We prove a characterization of truthful mechanisms, which makes an interesting parallel with the well-understood case of CAs with money for single-minded bidders. We then give a host of upper bounds on the approximation ratio obtained by either deterministic or randomized truthful mechanisms when the sets and valuations are private knowledge of the bidders. (Most of these mechanisms run in polynomial time and return solutions with (nearly) best possible approximation guarantees.) We complement these positive results with a number of lower bounds (some of which are essentially tight) that hold in the easier case of public sets. We thus provide an almost complete picture of truthfully approximating CAs in this general setting with multi-dimensional bidders.en
dc.language.isoenen
dc.publisherSpringeren
dc.relation.urlhttp://link.springer.com/article/10.1007/s00453-015-0105-8en
dc.rightsFollowing 12 month embargo author can archive post-print (ie final draft post-refereeing). For full details see http://www.sherpa.ac.uk/romeo [Accessed: 21/12/2015]en
dc.titleCombinatorial Auctions without Moneyen
dc.typeArticleen
dc.contributor.departmentTeesside University. Digital Futures Instituteen
dc.identifier.journalAlgorithmicaen
dc.eprint.versionAuthor accepted manuscripten
dc.eprint.versionAuthor accepted manuscripten
dc.embargo12 monthsen
dc.date.accepted2015-12-18en
All Items in TeesRep are protected by copyright, with all rights reserved, unless otherwise indicated.