Papers for

resource managers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Fair allocation of renewable resources over multiple time periods

Sustainable and Envy-free Multi-Period Allocation

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.

Mon 19 OctComputational ComplexityComputer Science and Game Theory
The gist
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.
Open → 2610.26032v1

Fair item allocation method works for two types of chores and goods

Maximin share allocations for two types of items

Abstract: We study the fair allocation of indivisible items among $n$ agents with additive valuations (or costs) using the fairness notion of maximin share (MMS). Since MMS allocations do not always exist when $n > 2$, one direction in the literature has been to identify special classes of instances in which exact MMS allocations can be guaranteed. We show that, when items can be divided into two types of chores, MMS allocations always exist and can be computed in polynomial time using a novel geometric approach inspired by prior work in job scheduling. We further discuss how our technique extends to instances with two types of goods, as well as mixed instances consisting of one type of objective good and one type of objective chore.

Tue 13 OctComputer Science and Game Theory
The gist
Dividing items fairly among people is hard, especially when items can't be split and are disliked chores. The authors show that if items are split into two groups of chores, there is always a fair way to allocate them, based on a fairness idea called maximin share, and it can be found quickly using a new geometric method. They also explain how this method works if the items are two types of desirable goods or a mix of one good type and one chore type.
Open → 2610.19099v1