Facility Location with Double-Peaked Preferences
Authors: Aris Filos-Ratsikas, Minming Li, Jie Zhang, Qiang Zhang
AAAI 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the problem of locating a single facility on a real line based on the reports of self-interested agents, when agents have double-peaked preferences, with the peaks being on opposite sides of their locations. We mainly focus on the case where peaks are equidistant from the agents locations and discuss how our results extend to more general settings. We show that most of the results for singlepeaked preferences do not directly apply to this setting; this makes the problem essentially more challenging. As our main contribution, we present a simple truthfulin-expectation mechanism that achieves an approximation ratio of 1+b/c for both the social and the maximum cost, where b is the distance of the agent from the peak and c is the minimum cost of an agent. For the latter case, we provide a 3/2 lower bound on the approximation ratio of any truthful-in-expectation mechanism. We also study deterministic mechanisms under some natural conditions, proving lower bounds and approximation guarantees. We prove that among a large class of reasonable mechanisms, there is no deterministic mechanism that outpeforms our truthful-in-expectation mechanism. |
| Researcher Affiliation | Academia | Aris Filos-Ratsikas Aarhus University, Denmark filosra@cs.au.dk Minming Li City University of Hong Kong, HK minming.li@cityu.edu.hk Jie Zhang University of Oxford, UK jie.zhang@cs.ox.ac.uk Qiang Zhang University of Warsaw, Poland qzhang@mimuw.edu.pl |
| Pseudocode | No | The paper describes 'Mechanism M1' and 'Mechanism M2' in prose, but does not provide them in a formally structured pseudocode or algorithm block. |
| Open Source Code | No | The paper does not provide any information about open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not involve the use of datasets for training. |
| Dataset Splits | No | The paper is theoretical and does not discuss dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not mention any hardware specifications used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup details such as hyperparameters or training configurations. |