Strategyproof approximation of the minimax on networks

Noga Alon, Michal Feldman, Ariel D. Procaccia, Moshe Tennenholtz

Research output: Contribution to journalArticlepeer-review

76 Scopus citations

Abstract

We consider the problem of locating a facility on a network represented by a graph. A set of strategic agents have different ideal locations for the facility; the cost of an agent is the distance between its ideal location and the facility. A mechanism maps the locations reported by the agents to the location of the facility. We wish to design mechanisms that are strategyproof (SP) in the sense that agents can never benefit by lying and, at the same time, provide a small approximation ratio with respect to the minimax measure. We design a novel "hybrid" strategyproof randomized mechanism that provides a tight approximation ratio of 3/2 when the network is a circle (known as a ring in the case of computer networks). Furthermore, we show that no randomized SP mechanism can provide an approximation ratio better than 2?o(1), even when the network is a tree, thereby matching a trivial upper bound of two.

Original languageEnglish (US)
Pages (from-to)513-526
Number of pages14
JournalMathematics of Operations Research
Volume35
Issue number3
DOIs
StatePublished - Aug 2010
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)
  • Computer Science Applications
  • Management Science and Operations Research

Keywords

  • Approximation
  • Facility location
  • Mechanism design
  • Minimax

Fingerprint

Dive into the research topics of 'Strategyproof approximation of the minimax on networks'. Together they form a unique fingerprint.

Cite this