Truthful Mechanisms without Money for Non-Utilitarian Heterogeneous Facility Location
Authors: Paolo Serafino, Carmine Ventre
AAAI 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we consider the facility location problem under a novel model recently proposed in the literature, which combines the no-money constraint (i.e. the impossibility to employ monetary transfers between the mechanism and the agents) with the presence of heterogeneous facilities, i.e. facilities serving different purposes. Agents thus have a significantly different cost model w.r.t. the classical model with homogeneous facilities studied in literature. We initiate the study of non-utilitarian optimization functions under this novel model. In particular, we consider the case where the optimization goal consists of minimizing the maximum connection cost of the agents. In this setting, we investigate both deterministic and randomized algorithms and derive both lower and upper bounds regarding the approximability of strategyproof mechanisms. ... We study both deterministic and randomized algorithms, and prove that in both cases the optimal allocation does not preserve truthfulness. We prove a lower bound of 3/2 on the approximation guarantee of deterministic SP mechanisms. |
| Researcher Affiliation | Academia | Paolo Serafino School of Computing Teesside University p.serafino@tees.ac.uk Carmine Ventre School of Computing Teesside University c.ventre@tees.ac.uk |
| Pseudocode | Yes | Algorithm 1: TWOEXTREMES Algorithm 2: RANDAVG |
| Open Source Code | No | The paper does not provide any statement or link indicating the availability of open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not involve the use of datasets for training or evaluation. Therefore, it does not provide information about publicly available datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with data splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe any computational experiments that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific software or libraries with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an empirical experimental setup with hyperparameters or training configurations. |