When Can the Maximin Share Guarantee Be Guaranteed?
Authors: David Kurokawa, Ariel Procaccia, Junxing Wang
AAAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our first major result drastically improves this upper bound: an MMS allocation may not exist even when the number of goods is linear in the number of players. Theorem 2.1. For all n 3, there is an instance with n players and m 3n+4 goods such that an MMS allocation does not exist. Theorem 3.1 Assume that for all i N, V[Di] c for a constant c > 0. Then for all ε > 0 there exists K = K(c, ε) such that if max(n, m) K, then the probability that an MMS allocation exists is at least 1 ε. Lemma 3.2 ((Dickerson et al. 2014)). Assume that for all i N, V[Di] c for a constant c > 0. Then for all ε > 0 there exists K = K(ε) such that if m K and m αn ln n, for some α = α(c), then the probability that an MMS allocation exists is at least 1 ε. Lemma 3.3. For all ε > 0 there exists K = K(ε) such that if n K and m < n8/7, then the probability that an MMS allocation exists is at least 1 ε. |
| Researcher Affiliation | Academia | David Kurokawa Computer Science Department Carnegie Mellon University dkurokaw@cs.cmu.edu Ariel D. Procaccia Computer Science Department Carnegie Mellon University arielpro@cs.cmu.edu Junxing Wang Computer Science Department Carnegie Mellon University junxingw@andrew.cmu.edu |
| Pseudocode | No | The paper mentions developing an allocation algorithm and discussing its design and analysis, but it does not provide structured pseudocode or an algorithm block within the text. |
| Open Source Code | No | The paper mentions Spliddit (www.spliddit.org) and its algorithm, but this is a reference to a third-party or previous work, not an explicit statement that the authors' code for the work described in this paper is open-source or available. |
| Open Datasets | No | The paper is theoretical and focuses on proofs and analysis of existence, rather than empirical studies with datasets. It mentions prior experimental work but does not use or provide access to a dataset for its own contributions. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments involving dataset splits (training, validation, test). |
| Hardware Specification | No | The paper is theoretical and does not mention any specific hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not list any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or system-level training settings. |