Envy-Free Division of Sellable Goods
Authors: Jeremy Karp, Aleksandr Kazachkov, Ariel Procaccia
AAAI 2014 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the envy-free allocation of indivisible goods between two players. Our novel setting includes an option to sell each good for a fraction of the minimum value any player has for the good. To rigorously quantify the efficiency gain from selling, we reason about the price of envy-freeness of allocations of sellable goods the ratio between the maximum social welfare and the social welfare of the best envy-free allocation. We show that envy-free allocations of sellable goods are significantly more efficient than their unsellable counterparts. Theorem 3. For any c (0, 1], the MAX-EFS(c) problem is NP-complete. Theorem 4. MAX-EFS(1) admits an FPTAS; i.e., there is an algorithm that, for any ϵ > 0, returns an envyfree allocation X (which possibly includes cash) such that SW(X, v A, v B) (1 ϵ) OPTEFS(v A, v B), and runs in polynomial time in the parameters of the problem and 1/ϵ. |
| Researcher Affiliation | Academia | Jeremy Karp Tepper School of Business Carnegie Mellon University jkarp@andrew.cmu.edu Aleksandr M. Kazachkov Tepper School of Business Carnegie Mellon University akazachk@cmu.edu Ariel D. Procaccia Computer Science Department Carnegie Mellon University arielpro@cs.cmu.edu |
| Pseudocode | No | The paper describes algorithmic approaches in prose, but does not include structured pseudocode or clearly labeled algorithm blocks. |
| Open Source Code | No | The paper does not contain any statement about releasing open-source code for the described methodology, nor does it provide any links to a code repository. |
| Open Datasets | No | This is a theoretical paper that does not use publicly available datasets for empirical experiments. |
| Dataset Splits | No | This is a theoretical paper and therefore does not include information about dataset splits for training, validation, or testing. |
| Hardware Specification | No | This is a theoretical paper and does not report on experiments requiring specific hardware specifications. |
| Software Dependencies | No | This is a theoretical paper and does not list specific software dependencies with version numbers. |
| Experiment Setup | No | This is a theoretical paper and does not include details on experimental setup, hyperparameters, or system-level training settings. |