Algorithms for Manipulating Sequential Allocation
Authors: Mingyu Xiao, Jiaxing Ling2302-2309
AAAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we give a novel algorithm that solves the problem in polynomial time for each fixed number of agents. We also show that an agent can always get at least half of its optimal utility by simply using its truthful preference as the response. In this paper, we fully answer this question by giving a dynamic programming algorithm for BEST RESPONSE that runs in polynomial time for any fixed number of agents and any additive utility functions. Besides, we show that the manipulator can always get at least half of the optimal utility if it simply uses the truthful preference ranking, where the approximation ratio is tight as far as using the truthful preference ranking. |
| Researcher Affiliation | Academia | Mingyu Xiao, Jiaxing Ling School of Computer Science and Engineering University of Electronic Science and Technology of China myxiao@gmail.com, lingjiaxing@std.uestc.edu.cn |
| Pseudocode | Yes | Algorithm 1: Subalgorithm OPT |
| Open Source Code | No | The paper does not provide any specific links or statements about the availability of open-source code for the described methodology. |
| Open Datasets | No | The paper describes a theoretical algorithm and does not use or refer to any datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve data splits for training, validation, or testing. |
| Hardware Specification | No | The paper describes a theoretical algorithm and does not provide details of specific hardware used for experiments. |
| Software Dependencies | No | The paper describes a theoretical algorithm and does not specify any software dependencies with version numbers. |
| Experiment Setup | No | The paper describes a theoretical algorithm and does not include details on experimental setup parameters like hyperparameters or training configurations. |