Low Cost, Fair, and Representative Committees in a Metric Space
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908609310359552 |
|---|---|
| author | Jerrett, Christopher Anshelevich, Elliot |
| author_facet | Jerrett, Christopher Anshelevich, Elliot |
| contents | We study the problem of selecting a representative committee of $k$ agents from a collection of $n$ agents in a common metric space. This problem is related to choosing $k$ facilities in facility location and $k$-median problems. However, unlike in more traditional facility location where each agent only cares about the closest selected facility, in the settings we consider each agent desires that all selected committee members are close to them. More precisely, we look at the sum objective, in which the goal is to minimize the total distance from all agents to all members of the chosen committee. We show that it is always possible to find a committee which is both low-cost according to this objective, and also fair according to many existing notions of fairness and proportionality defined for clustering settings. Moreover, we introduce a new desirable axiom for representative committees we call NORP, which prevents over-representation of any subset of agents. While all existing algorithms for fair committee selection do not satisfy this intuitive property, we provide new algorithms which form simultaneously low-cost, fair, and NORP solutions, thus showing that it is always possible to form low-cost, fair, and representative committees for our settings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_21039 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Low Cost, Fair, and Representative Committees in a Metric Space Jerrett, Christopher Anshelevich, Elliot Computer Science and Game Theory We study the problem of selecting a representative committee of $k$ agents from a collection of $n$ agents in a common metric space. This problem is related to choosing $k$ facilities in facility location and $k$-median problems. However, unlike in more traditional facility location where each agent only cares about the closest selected facility, in the settings we consider each agent desires that all selected committee members are close to them. More precisely, we look at the sum objective, in which the goal is to minimize the total distance from all agents to all members of the chosen committee. We show that it is always possible to find a committee which is both low-cost according to this objective, and also fair according to many existing notions of fairness and proportionality defined for clustering settings. Moreover, we introduce a new desirable axiom for representative committees we call NORP, which prevents over-representation of any subset of agents. While all existing algorithms for fair committee selection do not satisfy this intuitive property, we provide new algorithms which form simultaneously low-cost, fair, and NORP solutions, thus showing that it is always possible to form low-cost, fair, and representative committees for our settings. |
| title | Low Cost, Fair, and Representative Committees in a Metric Space |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2510.21039 |