Subjective valuations increase difficulty of fair group resource sharing
Subjective Valuations Make It Hard to be Fair: The Complexity of Resource Allocation to Groups of Agents
Computer Science and Game TheoryComputational ComplexityData Structures and Algorithms
Summary
Dividing resources fairly among groups of people is tricky when different people value items differently. The authors study how hard it is to find a solution where no one envies another too much when groups share items. They show that even with few people, the problem is tough to solve, but they find special cases where algorithms can work well. Their work helps explain when fair sharing among groups is possible and when it is computationally difficult.
What this means in practice
- •For resource allocation system designers: Design algorithms for fair group sharing focusing on item types or subjective item properties to handle computational challenges effectively.
- •For fair division software developers: Develop tools to allocate goods fairly to groups when agent preferences differ, using parameterized methods informed by this work.
A theory result. No direct application yet.
Authors
Argyrios Deligkas, Eduard Eiben, Robert Ganian, Tiger-Lily Goldsmith, Marlene Gründel, Simon Wietheger
Abstract
We study the parameterized complexity of finding an EF1 allocation of indivisible items in the group-sharing setting, which has received increasing attention in recent years. There, items are not allocated to individual agents but rather to one of two (or possibly more) groups, and agents within that group all share the assigned items. We consider both the "fixed" (EF1-Fix) and "variable" (EF1-Var) group cases, where in the former the assignments of agents to groups are prescribed. While both are NP-hard in the classical sense, we show that their algorithmic behavior differs significantly from the parameterized perspective. As our main results, we: (1) prove that both cases are NP-hard even when the number of agents is a small constant; (2) circumvent this hardness by establishing fixed-parameter tractability for EF1-Var w.r.t. the number of "subjective" items, that is, items which are viewed as chores or goods by different agents---but rule out an analogous result for EF1-Fix; and (3) establish fixed-parameter tractability for EF1-Fix w.r.t. the number of item types, but link the existence of an analogous fixed-parameter algorithm for EF1-Var to a fundamental open question in the setting of Integer Linear Programming.