Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
The Complexity of Computing Maximin Share Allocations on Graphs
Authors: Gianluigi Greco, Francesco Scarcello2006-2013
AAAI 2020 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | First, we show that computing maximin share allocations is FΔP 2 complete, even when focusing on consistent scenarios, that is, where such allocations are a-priori guaranteed to exist. Moreover, the problem remains intractable if all agents have the same type, i.e., have the same utility functions, and if either the values returned by the utility functions are polynomially bounded, or the underlying graphs have a low degree of cyclicity (more precisely, have bounded treewidth). However, if these conditions hold all together, then computing maximin share allocations (or checking that none exists) becomes tractable. The result is established via machineries based on logspace alternating machines that use partial representations of connected bundles, which are interesting in their own. |
| Researcher Affiliation | Academia | Gianluigi Greco, Francesco Scarcello University of Calabria 87036 Rende (CS), Italy EMAIL |
| Pseudocode | Yes | Figure 2: Algorithm EXISTBUNDLES |
| Open Source Code | No | The paper is purely theoretical and focuses on complexity proofs and algorithm design; it does not mention the release or availability of any open-source code. |
| Open Datasets | No | This is a theoretical paper focused on complexity analysis and algorithm design, and it does not involve the use of datasets for training or experimentation. |
| Dataset Splits | No | This is a theoretical paper focused on complexity analysis and algorithm design, and it does not involve the use of datasets for validation or experimentation. |
| Hardware Specification | No | The paper is theoretical and does not report on experiments, therefore no hardware specifications are mentioned. |
| Software Dependencies | No | The paper describes theoretical algorithms and complexity results but does not mention specific software dependencies or version numbers required for implementation. |
| Experiment Setup | No | The paper is theoretical and focuses on complexity analysis; it does not include details about an experimental setup or hyperparameters. |