Papers for

task management platforms

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.

Online fairness in task assignment with eligibility limits

Online Fair Division under Eligibility Constraints

Abstract: We study fair division of indivisible items under eligibility constraints: each item may be assigned only to a subset of eligible agents. This model coincides with restricted assignment in scheduling, with agents as machines and items as jobs, and captures settings where work or resources must be split among parties with different capabilities. Eligibility makes the usual fairness benchmarks inadequate, as agents should not be measured against items they could never receive. We therefore use eligibility-aware versions of proportionality and envy-freeness, where an agent's proportional share splits each item equally among its eligible agents, and envy comparisons discount items the agents are not eligible for. Our main finding is a sharp chore--goods separation for proportionality. We focus on identical valuations: under arbitrary valuations, no online algorithm can guarantee even an $o(m)$-approximation for chores. For chores, Prop1 is achievable offline, whereas exact proportionality and proportionality up to any item are not. For online chores, the optimal approximation factor for Prop1 for deterministic algorithms is $Θ(\sqrt m)$, with the lower bound holding even for unit-size jobs. For goods, Prop1 is again achievable offline, but the tight online bound drops to $Θ(\log m)$. For envy-based fairness, the picture is different. Goods and chores are equivalent under eligibility-aware envy notions, while the choice of notion is decisive. Strong EF1 may fail to exist even offline and cannot be approximated online. In contrast, weak EF1 can be maintained online, while weak EFX separates offline from online. Together, these results give a systematic study of online proportional and envy-based fairness in restricted assignment and show which fairness guarantees remain achievable under eligibility constraints.

Tue 6 OctComputer Science and Game Theory
The gist
Dividing tasks or resources fairly can be tricky when only certain people are allowed to get some tasks. The authors study how to fairly distribute tasks (or chores) online, meaning as tasks arrive one by one, when not everyone can do every task. They show that traditional fairness rules don’t work well here, so they adapt fairness ideas to respect eligibility. They also find different limits on how closely fairness can be achieved depending on whether tasks are good or bad, and which fairness rules are used.
Open → 2610.08064v1