Strategy Proof Mechanisms for Facility Location with Capacity Limits
Authors: Toby Walsh
IJCAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | First, we prove a strong characterization theorem. For locating two identical facilities with capacity limits and no spare capacity, the INNERPOINT mechanism is the unique strategy proof mechanism that is both anonymous and Pareto optimal. Second, when there is spare capacity, we identify a more general class of strategy proof mechanisms that interpolates smoothly between INNERPOINT and ENDPOINT which are anonymous and Pareto optimal. Third, with two facilities of different capacities, we prove a strong impossibility theorem that no mechanism can be both anonymous and Pareto optimal except when the capacities differ by just a single agent. Fourth, with three or more facilities we prove a second impossibility theorem that no mechanism can be both anonymous and Pareto optimal even when facilities have equal capacity. Our characterization and impossibility results are all minimal as multiple mechanisms exist if we drop one property. |
| Researcher Affiliation | Academia | UNSW Sydney and CSIRO Data61 |
| Pseudocode | No | The paper does not contain structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. |
| Open Datasets | No | The paper does not provide concrete access information for a publicly available or open dataset, as it describes theoretical work. |
| Dataset Splits | No | The paper does not provide specific dataset split information, as it is theoretical research without empirical experiments. |
| Hardware Specification | No | The paper does not provide specific hardware details used for running its experiments, as it describes theoretical work. |
| Software Dependencies | No | The paper does not provide specific ancillary software details, as it describes theoretical work without empirical implementation. |
| Experiment Setup | No | The paper does not contain specific experimental setup details, as it describes theoretical work. |