Fair allocation of renewable resources over multiple time periods
Sustainable and Envy-free Multi-Period Allocation
Computational ComplexityComputer Science and Game Theory
Summary
When sharing resources that renew over time, decisions made today affect what’s available tomorrow. The authors study how to fairly divide these resources among people over many time periods, making sure no one feels unfairly treated throughout the entire schedule. They explore how difficult it is for a computer to find such fair allocations as the number of people, resources, and time periods change. The study finds that even simplified cases can be computationally hard, but some special cases become manageable with clever approaches.
What this means in practice
- •For resource managers: Assess which allocation scenarios can be solved efficiently when distributing renewable resources over time.
- •For supply chain planners: Determine feasibility and complexity of fair allocation strategies for renewable goods across multiple periods.
A theory result. No direct application yet.
Authors
Robert Bredereck, Eva Deltl, Till Fluschnik
Abstract
Allocating renewable resources fairly requires accounting for how present decisions affect future availability. We introduce Sustainable and Envy-Free Multi-Period Allocation, in which agents are assigned over multiple periods to renewable resources whose quantities evolve over time according to renewal functions. An allocation must respect viability and capacity constraints while being envy-free over the whole time horizon. We study the computational and parameterized complexity of finding such allocations, with a focus on the three dimensions of the problem: the numbers of agents, resources, and periods. We show that finding such an allocation is NP-hard already for unary encoding and any single one of them being fixed to a constant. Whether two small dimensions suffice for tractability depends on the pair, the class of renewal functions, and the numerical encoding. For few resources and periods, binary-encoded instances remain hard in general, whereas unary encoding yields XP-time algorithms. For few resources and agents, binary-encoded instances also remain hard in general but become XP-time solvable when all renewal functions are translations. Few agents and periods yield fixed-parameter tractability, but no polynomial kernel under standard complexity assumptions.