View in EDS

Winner-imposing strategyproof mechanisms for multiple Facility Location games

Saved in:
Bibliographic Details
Title: Winner-imposing strategyproof mechanisms for multiple Facility Location games
Authors: Fotakis, Dimitris1 fotakis@cs.ntua.gr, Tzamos, Christos2 tzamos@mit.edu
Source: Theoretical Computer Science. Feb2013, Vol. 472, p90-103. 14p.
Subjects: Facility location problems, Metric spaces, Approximation theory, Algorithms, Cost control, Computer networks, Artificial Intelligence (Book : Berlatsky), Proportional control systems
Abstract: Abstract: We study Facility Location games, where a number of facilities are placed in a metric space based on locations reported by strategic agents. A mechanism maps the agents’ locations to a set of facilities. The agents seek to minimize their connection cost, namely the distance of their true location to the nearest facility, and may even misreport their location. We are interested in mechanisms that are strategyproof, i.e., ensure that no agent can benefit from misreporting her location, do not resort to monetary transfers, and approximate the optimal social cost. We focus on the closely related problems of -Facility Location and Facility Location with a uniform facility opening cost, instead of a bound of on the number of facilities. In the former, the social cost is the agents’ total connection cost, while in the latter, the social cost is the sum of the total connection cost and the total facility opening cost. We mostly study mechanisms that are winner-imposing, in the sense that they allocate facilities to agents and require that each agent allocated a facility should connect to it. We prove that the winner-imposing version of the Proportional mechanism, proposed by Lu et al. (2010) [18], is stategyproof for the -Facility Location game, and achieves an approximation ratio of at most , for any . For the Facility Location game, we show that the winner-imposing version of the randomized online algorithm of Meyerson (2001) [21], which has an approximation ratio of , is strategyproof. Furthermore, we present a deterministic non-imposing group strategyproof -approximate mechanism for the Facility Location game on the line. We also consider oblivious winner-imposing mechanisms for location games on continuous metric spaces, and show that they are strategyproof iff they are locally strategyproof, i.e. no agent can benefit by reporting a location arbitrarily close to her true location. [Copyright &y& Elsevier]
Copyright of Theoretical Computer Science is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 85282365
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Winner-imposing strategyproof mechanisms for multiple Facility Location games
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Fotakis%2C+Dimitris%22">Fotakis, Dimitris</searchLink><relatesTo>1</relatesTo><i> fotakis@cs.ntua.gr</i><br /><searchLink fieldCode="AR" term="%22Tzamos%2C+Christos%22">Tzamos, Christos</searchLink><relatesTo>2</relatesTo><i> tzamos@mit.edu</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Theoretical+Computer+Science%22">Theoretical Computer Science</searchLink>. Feb2013, Vol. 472, p90-103. 14p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Facility+location+problems%22">Facility location problems</searchLink><br /><searchLink fieldCode="DE" term="%22Metric+spaces%22">Metric spaces</searchLink><br /><searchLink fieldCode="DE" term="%22Approximation+theory%22">Approximation theory</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Cost+control%22">Cost control</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+networks%22">Computer networks</searchLink><br /><searchLink fieldCode="DE" term="%22Artificial+Intelligence+%28Book+%3A+Berlatsky%29%22">Artificial Intelligence (Book : Berlatsky)</searchLink><br /><searchLink fieldCode="DE" term="%22Proportional+control+systems%22">Proportional control systems</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Abstract: We study Facility Location games, where a number of facilities are placed in a metric space based on locations reported by strategic agents. A mechanism maps the agents’ locations to a set of facilities. The agents seek to minimize their connection cost, namely the distance of their true location to the nearest facility, and may even misreport their location. We are interested in mechanisms that are strategyproof, i.e., ensure that no agent can benefit from misreporting her location, do not resort to monetary transfers, and approximate the optimal social cost. We focus on the closely related problems of -Facility Location and Facility Location with a uniform facility opening cost, instead of a bound of on the number of facilities. In the former, the social cost is the agents’ total connection cost, while in the latter, the social cost is the sum of the total connection cost and the total facility opening cost. We mostly study mechanisms that are winner-imposing, in the sense that they allocate facilities to agents and require that each agent allocated a facility should connect to it. We prove that the winner-imposing version of the Proportional mechanism, proposed by Lu et al. (2010) [18], is stategyproof for the -Facility Location game, and achieves an approximation ratio of at most , for any . For the Facility Location game, we show that the winner-imposing version of the randomized online algorithm of Meyerson (2001) [21], which has an approximation ratio of , is strategyproof. Furthermore, we present a deterministic non-imposing group strategyproof -approximate mechanism for the Facility Location game on the line. We also consider oblivious winner-imposing mechanisms for location games on continuous metric spaces, and show that they are strategyproof iff they are locally strategyproof, i.e. no agent can benefit by reporting a location arbitrarily close to her true location. [Copyright &y& Elsevier]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Theoretical Computer Science is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=85282365
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.tcs.2012.11.036
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 14
        StartPage: 90
    Subjects:
      – SubjectFull: Facility location problems
        Type: general
      – SubjectFull: Metric spaces
        Type: general
      – SubjectFull: Approximation theory
        Type: general
      – SubjectFull: Algorithms
        Type: general
      – SubjectFull: Cost control
        Type: general
      – SubjectFull: Computer networks
        Type: general
      – SubjectFull: Artificial Intelligence (Book : Berlatsky)
        Type: general
      – SubjectFull: Proportional control systems
        Type: general
    Titles:
      – TitleFull: Winner-imposing strategyproof mechanisms for multiple Facility Location games
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Fotakis, Dimitris
      – PersonEntity:
          Name:
            NameFull: Tzamos, Christos
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 11
              M: 02
              Text: Feb2013
              Type: published
              Y: 2013
          Identifiers:
            – Type: issn-print
              Value: 03043975
          Numbering:
            – Type: volume
              Value: 472
          Titles:
            – TitleFull: Theoretical Computer Science
              Type: main
ResultId 1