Metraipolis › archive › dc_655cc1bfdfa4

Group-Fair Metric Distortion of Facility Assignment Problems — arXiv:2608.16252

Source: arXiv (en)
Original: https://arxiv.org/abs/2608.16252
License (as archived): CC0-1.0
Archived: 2026-10-18T19:08:06.251Z
SHA-256 of the archived text: a20d906baecfc3c39df03338d08ece56536bdd30779564e2e02373e6b50f16a7
Stable URL of this page: https://metraipolis.com/documento/dc_655cc1bfdfa4

How to cite

Group-Fair Metric Distortion of Facility Assignment Problems — arXiv:2608.16252 — arXiv (en), https://arxiv.org/abs/2608.16252 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_655cc1bfdfa4 (Metraipolis archive dc_655cc1bfdfa4, sha256 a20d906baecfc3c39df03338d08ece56536bdd30779564e2e02373e6b50f16a7)

BibTeX

@misc{dc655cc1bfdfa4,
  title = {Group-Fair Metric Distortion of Facility Assignment Problems — arXiv:2608.16252},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.16252},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_655cc1bfdfa4; sha256 a20d906baecfc3c39df03338d08ece56536bdd30779564e2e02373e6b50f16a7},
  year = {2026}
}

Archived text

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

We study the group-fair distortion of metric facility assignment problems, where a set of agents, partitioned into unknown groups, must be assigned to a collection of facilities, possibly subject to capacity or other feasibility constraints. Given an assignment, each agent incurs a cost that depends on both its distance to its assigned facility and, via an affinity factor, the average distance of the other members in its group to their assigned facilities. We consider full-information algorithms, which have complete knowledge of the metric space, and ordinal-information algorithms, which know the distances between facilities and only the rankings of the agents over facilities (sorted by increasing distance). We establish worst-case distortion upper bounds in terms of the Max-of-Sum and Sum-of-Max social objectives, which combine the classic utilitarian and egalitarian social cost measures. We also derive informational lower bounds for one-sided matching and clustering, two fundamental and well-studied problems captured by our model, that match our upper bounds exactly for Max-of-Sum and asymptotically for Sum-of-Max.

Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-08-18 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2608.16252 — 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-18T18:12:50.750Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-08-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).