On Truthful Mechanisms for Maximin Share Allocations
Authors: Georgios Amanatidis, Georgios Birmpas, Evangelos Markakis
IJCAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study a fair division problem with indivisible items, namely the computation of maximin share allocations. Given a set of n players, the maximin share of a single player is the best she can guarantee to herself, if she would partition the items in any way she prefers, into n bundles, and then receive her least desirable bundle. The objective then is to find an allocation, so that each player is guaranteed her maximin share. Previous works have studied this problem purely algorithmically, providing constant factor approximation algorithms. In this work, we embark on a mechanism design approach and investigate the existence of truthful mechanisms. We propose three models regarding the information that the mechanism attempts to elicit from the players, based on the cardinal and ordinal representation of preferences. We establish positive and negative (impossibility) results for each model and highlight the limitations imposed by truthfulness on the approximability of the problem. |
| Researcher Affiliation | Academia | Georgios Amanatidis, Georgios Birmpas, Evangelos Markakis Department of Informatics, Athens University of Economics and Business, Athens, Greece {gamana, gebirbas, markakis}@aueb.gr |
| Pseudocode | No | The paper describes various mechanisms (e.g., Mechanism M, M1, M2, Mn) in text, but it does not include formal pseudocode blocks or algorithms explicitly labeled as such. |
| Open Source Code | No | The paper does not provide any information or links regarding the availability of open-source code for the described methodology. |
| Open Datasets | No | This paper is theoretical and does not conduct experiments on datasets, thus it does not mention publicly available training data. |
| Dataset Splits | No | This paper is theoretical and does not conduct experiments with datasets, so it does not discuss training/validation/test splits. |
| Hardware Specification | No | This paper is theoretical and does not describe any experimental hardware specifications. |
| Software Dependencies | No | The paper does not mention any specific software dependencies or their version numbers, as it is a theoretical work. |
| Experiment Setup | No | This paper is theoretical and does not describe an experimental setup with hyperparameters or system-level training settings. |