Selfish Knapsack
Authors: Itai Feigenbaum, Matthew Johnson
AAAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We provide a randomized mechanism with attractive strategic properties: it has a price of anarchy of 2 for Bayes-Nash and coarse correlated equilibria. For overstating-only agents, it becomes strategyproof, and has a matching lower bound. For the case of two understating-only agents, we provide a specialized randomized strategyproof 5+4 2 7 1.522-approximate mechanism, and a lower bound of 5 5 9 2 1.09. When all agents but one are honest, we provide a deterministic strategyproof 1+ 5 2 1.618-approximate mechanism with a matching lower bound. The latter two mechanisms are also useful in problems beyond the one in consideration. |
| Researcher Affiliation | Academia | Itai Feigenbaum and Matthew P. Johnson Lehman College and the Graduate Center, City University of New York |
| Pseudocode | Yes | ALGORITHM 1: GREEDY Input: Sets of reported items R X n S , T i NRi while T = do next max T T T\{next} if s(S \{next}) 1 then S S \{next} else break return S |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. It links to an online appendix for proofs and additional results, but not source code. |
| Open Datasets | No | This is a theoretical paper that focuses on algorithm design and mathematical analysis, not empirical studies using datasets for training or evaluation. Therefore, it does not provide information about publicly available datasets. |
| Dataset Splits | No | This is a theoretical paper that does not involve empirical experiments requiring dataset splits for training, validation, or testing. |
| Hardware Specification | No | This is a theoretical paper. It does not describe any empirical experiments that would require hardware specifications. |
| Software Dependencies | No | This is a theoretical paper that designs and analyzes mechanisms. It does not describe implementations of these mechanisms or empirical experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | This is a theoretical paper focusing on mechanism design and analysis. It does not describe an experimental setup with hyperparameters or system-level training settings. |