Improved Approximation Ratio for Strategyproof Facility Location on a Cycle
Authors: Krzysztof Rogowski, Marcin Dziubiński
IJCAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | To complement these theoretical results, we conducted numerical experiments to investigate which values of the approximation ratio are actually attained by the RD + PCD mechanism. The idea of the experiments is to compute the approximation ratio of the RD+PCD mechanism for a finite, computationally feasible, set of profiles, providing insight into the behavior of the mechanism for all possible profiles. |
| Researcher Affiliation | Academia | Krzysztof Rogowski , Marcin Dziubi nski University of Warsaw, Institute of Informatics EMAIL, |
| Pseudocode | No | The paper describes the mechanisms (Random Dictator, Proportional Circle Distance, and their mixture) using verbal descriptions and mathematical definitions, but it does not include explicitly labeled pseudocode or algorithm blocks. |
| Open Source Code | No | The paper mentions "Extended version of the paper is available at https://arxiv.org/abs/2505.12943" which points to the paper on arXiv, not source code. There is no other explicit statement about releasing source code or a link to a code repository. |
| Open Datasets | No | The paper discusses mechanisms for facility location on a cycle and conducts numerical experiments by simulating agent profiles on a cycle with varying parameters (number of agents, number of allowed points). It does not use any pre-existing or publicly available datasets. |
| Dataset Splits | No | The paper's experimental section describes numerical simulations of mechanism performance on generated profiles, not on external datasets. Therefore, there are no dataset splits mentioned. |
| Hardware Specification | No | The paper's 'Experiments' section describes the computational analysis of the RD+PCD mechanism but does not provide any specific details about the hardware (e.g., GPU/CPU models, memory) used for these computations. |
| Software Dependencies | No | The paper does not mention any specific software or library names with version numbers that were used to conduct the numerical experiments. |
| Experiment Setup | Yes | During the experiments, we considered the number of agents n in the range [2..60]. The second parameter to consider is the set of possible reports for each agent. ... For l N, let Gl denote the subset of l points on the cycle G (of length 1) that are equally spaced and include the point 0. During the experiments, we restricted agents reports to the set Gl for l [2..60]. ... In such cases, we restricted our analysis to profiles in which agents reported no more than 3 distinct points. |