Complexity of Manipulating Sequential Allocation
Authors: Haris Aziz, Sylvain Bouveret, Jrme Lang, Simon Mackenzie
AAAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We show that the problem is NP-complete for one manipulating agent with additive utilities and several nonmanipulating agents. In doing so, we correct a wrong claim made in a previous paper. We then give two additional results. First, we present a polynomial-time algorithm for optimal manipulation when the manipulator has additive binary utilities. Second, we consider a stronger notion of manipulation whereby the untruthful outcome yields more utility than the truthful outcome for all utilities consistent with the ordinal preferences; for this notion, we show that a manipulation, if any, can be computed in polynomial time. |
| Researcher Affiliation | Academia | Haris Aziz Data61, CSIRO and UNSW Sydney, Australia haris.aziz@data61.csiro.au Sylvain Bouveret LIG Grenoble INP France sylvain.bouveret@imag.fr J erˆome Lang Universit e Paris-Dauphine, PSL Research University CNRS, LAMSADE, Paris, France lang@lamsade.dauphine.fr Simon Mackenzie Carnegie Mellon University, Pittsburg, USA simonm@andrew.cmu.edu |
| Pseudocode | Yes | Consider the following algorithm BR: Input: O+, π, ( 2, . . . , n) Output: 1 k 1; n1 number of occurrences of 1 in π; While k n1 and O+ = and π = 11 . . . 1 O Allocate(head(π), 2, . . . , n); remove O from O, O+, and ( 2, . . . , n); π tail(π); ak First(π 1, 2, . . . , n, O+); remove ak from O, O+, and ( 2, . . . , n); k k + 1; End While 1 (a1, . . . , ak); complete 1 with the remaining items of O+ (if any) in an arbitrary way, and then by other items in an arbitrary way; Return 1 |
| Open Source Code | No | The paper does not provide any statement or link regarding the availability of open-source code for the methodology described. |
| Open Datasets | No | This is a theoretical paper focusing on complexity proofs and algorithms, and it does not involve the use of datasets for training or evaluation. Therefore, there is no information about dataset availability. |
| Dataset Splits | No | This is a theoretical paper and does not involve experimental validation with dataset splits. |
| Hardware Specification | No | This is a theoretical paper and does not describe empirical experiments that would require specific hardware specifications. Therefore, no hardware details are mentioned. |
| Software Dependencies | No | This is a theoretical paper and does not discuss software dependencies with version numbers for reproducibility of experiments, as it does not conduct empirical studies. |
| Experiment Setup | No | This is a theoretical paper and does not describe empirical experiments or their setup, such as hyperparameters or training configurations. |