Fair and Truthful Mechanisms for Dichotomous Valuations
Authors: Moshe Babaioff, Tomer Ezra, Uriel Feige5119-5126
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We consider the problem of allocating a set on indivisible items to players with private preferences in an efficient and fair way. We focus on valuations that have dichotomous marginals, in which the added value of any item to a set is either 0 or 1, and aim to design truthful allocation mechanisms (without money) that maximize welfare and are fair. For the case that players have submodular valuations with dichotomous marginals, we design such a deterministic truthful allocation mechanism. We then show that our mechanism with random priorities is envy-free ex-ante, while having all the above properties ex-post. Furthermore, we present several impossibility results precluding similar results for the larger class of XOS valuations. |
| Researcher Affiliation | Collaboration | Moshe Babaioff1, Tomer Ezra2, Uriel Feige3 1 Microsoft Research 2 Tel Aviv University 3 Weizmann Institute |
| Pseudocode | No | The paper describes the PE mechanism in Section 3.2 using natural language, but it does not contain any structured pseudocode or an algorithm block. |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. It only provides a link to a full version of the paper on arXiv. |
| Open Datasets | No | This paper is theoretical and does not use or reference any datasets for training or other purposes. |
| Dataset Splits | No | This paper is theoretical and does not report on experiments or dataset splits for validation. |
| Hardware Specification | No | This paper is theoretical and does not involve experiments, therefore no hardware specifications are mentioned. |
| Software Dependencies | No | This paper is theoretical and does not involve software implementation details or dependencies for experiments. |
| Experiment Setup | No | This paper is theoretical and does not describe any experimental setup or hyperparameters. |