Truthful mechanisms for exhibitions

George Christodoulou, Khaled Elbassioni, Mahmoud Fouz

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

10 Scopus citations

Abstract

We consider the following combinatorial auction: Given a range space , and m bidders interested in buying only ranges in , each bidder j declares her bid . We give a deterministic truthful mechanism, when the valuations are single-minded: when is a collection of fat objects (respectively, axis-aligned rectangles) in the plane, there is a truthful mechanism with a 1 + ε- (respectively, [logn])-approximation of the social welfare (where n is an upper bound on the maximum integral coordinate of each rectangle). We also consider the non-single-minded case, and design a randomized truthful-in-expectation mechanism with approximation guarantee O(1) (respectively, O(logm)).

Original languageBritish English
Title of host publicationInternet and Network Economics - 6th International Workshop, WINE 2010, Proceedings
Pages170-181
Number of pages12
DOIs
StatePublished - 2010
Event6th International Workshop on Internet and Network Economics, WINE 2010 - Stanford, CA, United States
Duration: 13 Dec 201017 Dec 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6484 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference6th International Workshop on Internet and Network Economics, WINE 2010
Country/TerritoryUnited States
CityStanford, CA
Period13/12/1017/12/10

Fingerprint

Dive into the research topics of 'Truthful mechanisms for exhibitions'. Together they form a unique fingerprint.

Cite this