Facility Location with Minimax Envy
Authors: Qingpeng Cai, Aris Filos-Ratsikas, Pingzhong Tang
IJCAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | First, for the problem of locating the facility on a real line, we propose a class of truthful-in-expectation mechanisms that generalize the well-known LRM mechanism [Procaccia and Tennenholtz, 2009; Alon et al., 2009], the best of which has performance arbitrarily close to the social optimum. Then, we restrict the possible locations of the facility to a real interval and consider two cases; when the interval is determined relatively to the agents reports and when the interval is fixed in advance. For the former case, we prove that for any choice of such an interval, there is a mechanism in the aforementioned class with additive approximation arbitrarily close to the best approximation achieved by any truthful-in-expectation mechanism. For the latter case, we prove that the approximation of the best truthful-in-expectation mechanism is between 1/3 and 1/2. |
| Researcher Affiliation | Academia | Qingpeng Cai Tsinghua University, China cqp14@mails.tsinghua.edu.cn Aris Filos-Ratsikas University of Oxford, UK Aris.Filos-Ratsikas@cs.ox.ac.uk Pingzhong Tang Tsinghua University, China kenshinping@gmail.com |
| Pseudocode | Yes | Mechanism -LRM. For any location profile x, let L (x) = 1 4 L(x). Place the facility at mid(x) with probability 1 2 , at lm(x) L (x) with probability , and at rm(x) + L (x) with probability . |
| Open Source Code | No | The paper does not contain any statements or links indicating that open-source code for the described methodology is provided. |
| Open Datasets | No | The paper is theoretical and uses abstract 'location profiles' (x1, ..., xn) rather than specific public datasets for empirical evaluation. Therefore, there is no mention of dataset availability. |
| Dataset Splits | No | This paper is theoretical and does not involve empirical experiments on datasets, thus there are no training, validation, or test splits mentioned. |
| Hardware Specification | No | The paper focuses on theoretical analysis and does not describe any computational experiments that would require hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not describe any computational experiments with specific software dependencies or version numbers. |
| Experiment Setup | No | This paper presents theoretical work and does not include details on experimental setup such as hyperparameters or system-level training settings. |