Facility Location Games With Fractional Preferences
Authors: Chi Kit Ken Fong, Minming Li, Pinyan Lu, Taiki Todo, Makoto Yokoo
AAAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we propose a fractional preference model for the facility location game with two facilities that serve the similar purpose on a line where each agent has his location information as well as fractional preference to indicate how well they prefer the facilities. ... We first show that the lower bound for the objective of minimizing total cost is at least Ω(n 1 3 ). Hence, we use the utility function to analyze the agents satification. Our objective is to place two facilities on [0, L] to maximize the social utility or the minimum utility. For each objective function, we propose deterministic strategy-proof mechanisms. ... We first show that the lower bound for the objective of minimizing total cost is at least Ω(n 1 3 ). Then we present our results for maximizing the social utility and maximizing the minimum utility as follows. ... Proof. ... Theorem 2. Mechanism 1 is an optimal deterministic strategy-proof mechanism. Proof. ... Theorem 3. There does not exist any strategy-proof deterministic mechanism with an approximation ratio less than 1.06. Proof. ... Theorem 4. Mechanism 2 is a deterministic strategy-proof mechanism with an approximation ratio of 2. Proof. |
| Researcher Affiliation | Academia | a Department of Computer Science, City University of Hong Kong, Hong Kong. b Shanghai University of Finance and Economics, Shanghai, China. c Department of Informatics, Kyushu University, Motooka 744, Fukuoka, Japan. |
| Pseudocode | No | Mechanism 1. Let wj = n i=1 pi,j and define midj = 1 2wj. Put Fj at the location of agent mj where mj = arg mink{midj k i=1 pi,j}. (This is a description, not a formally structured pseudocode block.) |
| Open Source Code | No | The paper does not mention providing open-source code for the methodology or provide any links. |
| Open Datasets | No | The paper is theoretical and does not involve the use of datasets for training or evaluation, therefore no concrete access information for a public dataset is provided. |
| Dataset Splits | No | The paper is theoretical and does not involve experimental data splits, therefore no specific dataset split information for validation is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe experiments that would require specific hardware, thus no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and does not describe experiments with software dependencies, thus no specific ancillary software details with version numbers are provided. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or training configurations. |