The Complexity of Computing Maximin Share Allocations on Graphs
Authors: Gianluigi Greco, Francesco Scarcello2006-2013
AAAI 2020 | Conference PDF | Archive PDF | Plain Text | 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 {gianluigi.greco, francesco.scarcello}@unical.it |
| 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. |