Online fairness in task assignment with eligibility limits
Online Fair Division under Eligibility Constraints
Computer Science and Game Theory
Summary
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.
What this means in practice
- •For cloud resource schedulers: Allocate incoming jobs fairly online to eligible servers with different capabilities under eligibility restrictions.
- •For task management platforms: Ensure fair real-time assignment of tasks to workers qualified only for certain tasks, improving task distribution fairness.
A theory result. No direct application yet.
Authors
Joes Biburger, Nicole Megow, Golnoosh Shahkarami
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.