Heterogeneous Facility Location without Money

Hdl Handle:
http://hdl.handle.net/10149/607293
Title:
Heterogeneous Facility Location without Money
Authors:
Serafino, P. (Paolo); Ventre, C. (Carmine) ( 0000-0003-1464-1215 )
Affiliation:
Teesside University, Digital Futures Institute
Citation:
Serafino, P. & Ventre, C. (2016) 'Heterogeneous Facility Location without Money' Theoretical Computer Science; Available online 30 April 2016
Publisher:
Elsevier
Journal:
Theoretical Computer Science
Issue Date:
30-Apr-2016
URI:
http://hdl.handle.net/10149/607293
DOI:
10.1016/j.tcs.2016.04.033
Abstract:
The study of the facility location problem in the presence of self-interested agents has recently emerged as the benchmark problem in the research on mechanism design without money. In the setting studied in the literature so far, agents are single-parameter in that their type is a single number encoding their position on a real line. We here initiate a more realistic model for several real-life scenarios. Specifically, we propose and analyze heterogeneous facility location without money, a novel model wherein: (i) we have multiple heterogeneous (i.e., serving different purposes) facilities,(ii) agents’ locations are disclosed to the mechanism and (iii) agents bid for the set of facilities they are interested in (as opposed to bidding for their position on the network).We study the heterogeneous facility location problem under two different objective functions, namely: social cost (i.e., sum of all agents’ costs) and maximum cost. For either objective function, we study the approximation ratio of both deterministic and randomized truthful algorithms under the simplifying assumption that the underlying network topology is a line. For the social cost objective function, we devise an (n − 1)-approximate deterministic truthful mechanism and prove a constant approximation lower bound. Furthermore, we devise an optimal and truthful (in expectation) ran-domized algorithm. As regards the maximum cost objective function, we propose a 3-approximate deterministic strategyproof algorithm, and prove a 3/2 approximation lower bound for deterministic strategyproof mechanisms. Furthermore, we propose a 3/2-approximate randomized strategyproof algorithm and prove a 4/3 approximation lower bound for randomized strategyproof algorithms.
Type:
Article
Language:
en
ISSN:
0304-3975
Rights:
Author can archive post-print (ie final draft post-refereeing) after 12 month embargo from acceptance. For full details see http://www.sherpa.ac.uk/romeo/issn/0304-3975/ [Accessed 28/04/2016]

Full metadata record

DC FieldValue Language
dc.contributor.authorSerafino, P. (Paolo)en
dc.contributor.authorVentre, C. (Carmine)en
dc.date.accessioned2016-04-28T15:33:58Zen
dc.date.available2016-04-28T15:33:58Zen
dc.date.issued2016-04-30en
dc.identifier.citationTheoretical Computer Science; Available online 30 April 2016en
dc.identifier.issn0304-3975en
dc.identifier.doi10.1016/j.tcs.2016.04.033en
dc.identifier.urihttp://hdl.handle.net/10149/607293en
dc.description.abstractThe study of the facility location problem in the presence of self-interested agents has recently emerged as the benchmark problem in the research on mechanism design without money. In the setting studied in the literature so far, agents are single-parameter in that their type is a single number encoding their position on a real line. We here initiate a more realistic model for several real-life scenarios. Specifically, we propose and analyze heterogeneous facility location without money, a novel model wherein: (i) we have multiple heterogeneous (i.e., serving different purposes) facilities,(ii) agents’ locations are disclosed to the mechanism and (iii) agents bid for the set of facilities they are interested in (as opposed to bidding for their position on the network).We study the heterogeneous facility location problem under two different objective functions, namely: social cost (i.e., sum of all agents’ costs) and maximum cost. For either objective function, we study the approximation ratio of both deterministic and randomized truthful algorithms under the simplifying assumption that the underlying network topology is a line. For the social cost objective function, we devise an (n − 1)-approximate deterministic truthful mechanism and prove a constant approximation lower bound. Furthermore, we devise an optimal and truthful (in expectation) ran-domized algorithm. As regards the maximum cost objective function, we propose a 3-approximate deterministic strategyproof algorithm, and prove a 3/2 approximation lower bound for deterministic strategyproof mechanisms. Furthermore, we propose a 3/2-approximate randomized strategyproof algorithm and prove a 4/3 approximation lower bound for randomized strategyproof algorithms.en
dc.language.isoenen
dc.publisherElsevieren
dc.rightsAuthor can archive post-print (ie final draft post-refereeing) after 12 month embargo from acceptance. For full details see http://www.sherpa.ac.uk/romeo/issn/0304-3975/ [Accessed 28/04/2016]en
dc.titleHeterogeneous Facility Location without Moneyen
dc.typeArticleen
dc.contributor.departmentTeesside University, Digital Futures Instituteen
dc.identifier.journalTheoretical Computer Scienceen
or.citation.harvardSerafino, P. & Ventre, C. (2016) 'Heterogeneous Facility Location without Money' Theoretical Computer Science; Available online 30 April 2016en
dc.eprint.versionPost-printen
dc.embargo12 months-
dc.date.accepted2016-04-27en
All Items in TeesRep are protected by copyright, with all rights reserved, unless otherwise indicated.