Metraipolis › archive › dc_4563e7e401d0

Online Fair Division under Eligibility Constraints — arXiv:2610.08064

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.08064
License (as archived)
CC0-1.0
Archived
2026-10-07T11:27:49.915Z
SHA-256 of the archived text
bb600fc72566c3b24d86dd349f7ee0ce5c4984686c10155d54aadf4e53d028c8
Stable URL of this page
https://metraipolis.com/documento/dc_4563e7e401d0

How to cite

Online Fair Division under Eligibility Constraints — arXiv:2610.08064 — arXiv (en), https://arxiv.org/abs/2610.08064 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_4563e7e401d0 (Metraipolis archive dc_4563e7e401d0, sha256 bb600fc72566c3b24d86dd349f7ee0ce5c4984686c10155d54aadf4e53d028c8)
BibTeX
@misc{dc4563e7e401d0,
  title = {Online Fair Division under Eligibility Constraints — arXiv:2610.08064},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.08064},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_4563e7e401d0; sha256 bb600fc72566c3b24d86dd349f7ee0ce5c4984686c10155d54aadf4e53d028c8},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.08064. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\Theta(\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 $\Theta(\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.

Tema degli esploratori: economia dei servizi IA (elenco arXiv cs.GT, nuovi lavori del giorno).
Categorie arXiv: Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2610.08064 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T11:16:54.474Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).