Reconfiguration of Resource Allocation

Abstract

Inspired by the multi-winner reconfiguration framework by Chen, Hatschka, and Simola [NeurIPS, 2024], we introduce a new framework of reconfiguration to resource allocation and analyze its computational complexity. Given a set of items, a set of agents, each with a utility function describing their preferences over the items, two fair allocations and a number delta, the task is to determine whether a reconfiguration path exists from one allocation to the other. A fair allocation is a function mapping items to agents, which satisfies a fairness concept, and a reconfiguration path is a sequence of fair allocations where consecutive allocations differ in the allocation of at most delta items. The fairness concepts used in this thesis are envy-freeness (EF) and envy-freeness up to 1 item (EF1), which result in the two versions of Resource Allocation Reconfiguration (RAR) examined: EF-RAR and EF1-RAR. Our reconfiguration framework generalizes the resource allocation reachability problem of Igarashi et al. [Algorithmica, 2024], which allows at most two items to exchange their ownerships between each two consecutive allocations. We examine the computational and parameterized complexity of EF-RAR and EF1-RAR, both in the general case and with a combination of restrictions, such as requiring the utility functions to be common, binary or both, and combining this with small, fixed values of delta. We show that EF-RAR and EF1-RAR are PSPACE-complete and remain PSPACE-complete even when restricted to instances with delta = 1. EF-RAR also remains PSPACE-complete when restricted to instances with binary utilities and delta = 2. When restricted to instances with common utilities, EF1-RAR is weakly NP-hard for delta = 1, while EF-RAR is polynomial-time solvable for delta <= 2. Both EF-RAR and EF1-RAR become polynomial-time solvable when the utilities are common and binary. Common, binary utilities along with delta >= 2 ensure the existence of a reconfiguration path. EF-RAR and EF1-RAR are FPT with regard to the number of items, and EF1-RAR is weakly para-NP-hard with regard to the number of agents, as it is weakly NP-hard for two agents.