Facility location with Minimax envyReportar como inadecuado

Facility location with Minimax envy - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Reference: Cai, Q, Filos-Ratsikas, A and Tang, P, (2016). Facility location with Minimax envy.Citable link to this page:


Facility location with Minimax envy

Abstract: We study the problem of locating a public facilityon a real line or an interval, when agents’ costsare their (expected) distances from the location ofthe facility. Our goal is to minimize the maximumenvy over all agents, which we will refer to as theminimax envy objective, while at the same time ensuringthat agents will report their most preferredlocations truthfully. First, for the problem of locatingthe facility on a real line, we propose a classof truthful-in-expectation mechanisms that generalizethe well-known LRM mechanism [Procacciaand Tennenholtz, 2009; Alon et al., 2009], the bestof which has performance arbitrarily close to thesocial optimum. Then, we restrict the possible locationsof the facility to a real interval and considertwo cases; when the interval is determined relativelyto the agents’ reports and when the interval isfixed in advance. For the former case, we prove thatfor any choice of such an interval, there is a mechanismin the aforementioned class with additive approximationarbitrarily close to the best approximationachieved by any truthful-in-expectation mechanism.For the latter case, we prove that the approximationof the best truthful-in-expectation mechanismis between 1/3 and 1/2.

Publication status:PublishedPeer Review status:Peer reviewedVersion:Accepted ManuscriptDate of acceptance:04 May 2016Notes:Copyright © 2016, IJCAI. This is the accepted manuscript version of the article. The final version is available online from IJCAI at: http://www.ijcai.org/Abstract/16/027

Bibliographic Details

Publisher: AAAI Press / International Joint Conferences on Artificial Intelligence

Publisher Website: http://www.ijcai.org/

Host: Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI-16)see more from them

Publication Website: http://www.ijcai.org/proceedings/2016

Extent: 137-143

Issue Date: 09 July 2016


Uuid: uuid:3504369b-6817-4500-8563-232c3e256766

Urn: uri:3504369b-6817-4500-8563-232c3e256766

Pubs-id: pubs:648530

Isbn: 978-1-57735-770-4 Item Description

Type: conference-proceeding;

Version: Accepted Manuscript


Autor: Cai, Q - - - Filos-Ratsikas, A - Oxford, MPLS, Computer Science fundingEuropean Research Council grantNumberAdvanced Grant 321171

Fuente: https://ora.ox.ac.uk/objects/uuid:3504369b-6817-4500-8563-232c3e256766


Documentos relacionados