The Complexity of Computing Maximin Share Allocations on Graphs
The Complexity of Computing Maximin Share Allocations on Graphs
复制标题
计算图上最大最小份额分配的复杂性
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Francesco Scarcello
中科院分区：
文献类型：
--
作者：
G. Greco;Francesco Scarcello
最小份额是Buddish提出的一个令人信服的公平概念，作为对公平分配不可分割商品的更传统概念的放松。在本文中，我们认为这一概念内的设置，捆绑的货物必须诱导连接的子集在一个底层图。这种设置在早期的文献中受到了很大的关注，我们的研究回答了一些悬而未决的问题。首先，我们证明了计算最大最小份额分配是FΔ 2 P-完全的，即使是在一致的情况下，也就是说，这样的分配是先验保证存在的。此外，如果所有代理都具有相同的类型，即，具有相同的效用函数，并且如果由效用函数返回的值是多项式有界的，或者底层图具有低的循环度（更准确地说，具有有界树宽）。但是，如果这些条件都成立，那么计算maximin共享分配（或检查不存在）就变得容易处理了。结果是通过机器建立的对数空间交替机，使用部分表示的连接束，这是有趣的，在自己的基础上。
Maximin share is a compelling notion of fairness proposed by Buddish as a relaxation of more traditional concepts for fair allocations of indivisible goods. In this paper we consider this notion within a setting where bundles of goods must induce connected subsets over an underlying graph. This setting received much attention in earlier literature, and our study answers a number of questions that were left open. First, we show that computing maximin share allocations is FΔ2P-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.