False-Name-Proof Locations of Two Facilities: Economic and Algorithmic Approaches

Authors

  • Akihisa Sonoda Kyushu University
  • Taiki Todo Kyushu University
  • Makoto Yokoo Kyushu University

DOI:

https://doi.org/10.1609/aaai.v30i1.10029

Keywords:

facility location problem, mechanism design, false-name-proofness, strategy-proofness, approximation analysis

Abstract

This paper considers a mechanism design problem for locating two identical facilities on an interval, in which an agent can pretend to be multiple agents. A mechanism selects a pair of locations on the interval according to the declared single-peaked preferences of agents. An agent's utility is determined by the location of the better one (typically the closer to her ideal point). This model can represent various application domains. For example, assume a company is going to release two models of its product line and performs a questionnaire survey in an online forum to determine their detailed specs. Typically, a customer will buy only one model, but she can answer multiple times by logging onto the forum under several email accounts. We first characterize possible outcomes of mechanisms that satisfy false-name-proofness, as well as some mild conditions. By extending the result, we completely characterize the class of false-name-proof mechanisms when locating two facilities on a circle. We then clarify the approximation ratios of the false-name-proof mechanisms on a line metric for the social and maximum costs.

Downloads

Published

2016-02-21

How to Cite

Sonoda, A., Todo, T., & Yokoo, M. (2016). False-Name-Proof Locations of Two Facilities: Economic and Algorithmic Approaches. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1). https://doi.org/10.1609/aaai.v30i1.10029

Issue

Section

Technical Papers: Game Theory and Economic Paradigms