Source-linked AI summary
Optimally Selecting Representative Agents from a Metric Space
Benjamin Cookson, Eva Deltl, Yeeseok Oh
TL;DR
Classical clustering objectives did not provide compelling fairness guarantees, motivating proportional fairness when centers represent agents. The paper proves that, when every agent location is feasible, a 2-Droop-core clustering exists using agent locations, while computation via Scarf’s theorem remains unresolved.
Problem
Classical clustering objectives such as k-means and k-medians did not produce compelling fairness guarantees, motivating proportional representation when valid centers include agent locations.
Method
The proof establishes a fractional clustering and then derives an integral clustering in the 2-Droop core, using the balanced-game framework associated with Scarf’s theorem.
Results
2-Droop-core clusterings always exist for finite weighted instances with N ⊆ C, and centers can be selected only from agent locations.
Takeaways & Limitations
The condition N ⊆ C provides enough structure to guarantee a 2-approximation, separating this case from the general setting.
Takeaways & Limitations
Although the final integral clustering can be rounded in polynomial time given the fractional vector, computing the vector via Scarf’s theorem is not known to be polynomial-time feasible.
Abstract
from arXiv · showhide
This paper studies the problem of proportionally fair clustering, where the goal is to select $k$ ``centers'' from a metric space that fairly represent a set of agents who also lie in the metric space. Specifically, we focus on finding a clustering satisfying a fairness property known as the Droop core. In the practical special case in which the set of feasible center locations contains every agent location, the previous best-known result guaranteed a $(1 + \sqrt{2})$-approximation of the Droop core, while the best-known lower bound was $2$. In this paper, we show that this lower bound is tight and that a clustering in the $2$-Droop core always exists. Further, we show that such a clustering can be achieved by only selecting centers from locations in the metric space where an agent resides. We establish this using Scarf's theorem guaranteeing a nonempty core for balanced non-transferable utility games. This result has several interesting corollaries. Most notably, it resolves the $β$-plurality problem of Aronov et al. [2021] for general metric spaces. The main result of this paper was generated by $\mathtt{ChatGPT}$-$\mathtt{5.6}$-$\mathtt{Sol}$ through a series of interactions with the authors. The authors of this paper verified the generated proof and rewrote it for clarity.
1 Introduction
The paper studies proportionally fair clustering in metric spaces, focusing on the N ⊆C case where every agent location is an admissible center. It proves that the lower bound of 2 is tight for the Droop core and derives related consequences.
- 1 Introduction: Metric fair clustering selects k centers to represent agents whose preferences depend on agent–candidate distances.The setting connects fair committee selection with traditional metric clustering.
- 1.1 Our Contributions: 2 is the tight approximation bound for the N ⊆C case, where every agent location can be selected as a center.This resolves the previously open possibility of achieving a 2-approximation in this practical setting.
- 1.1 Our Contributions: The Droop quota allows groups with weight greater than 1/(k + 1) to deviate, strengthening the original Hare-quota core condition requiring weight at least 1/k.The paper’s guarantee therefore uses a stricter coalition-entitlement threshold than the original core definition.
- 1.1 Our Contributions: Theorem 1.1 guarantees a clustering X ⊆N in the 2-Droop core for every instance with N ⊆C.The result permits selecting centers only from locations occupied by agents.
- 1.1 Our Contributions: The result resolves the β-plurality problem for general metric spaces, which is the k = 1 case of approximate Droop-core clustering.The introduction also places the result among applications including representative committees, sortition, facility placement, and transit-stop placement.
- 1.1 Our Contributions: The proof uses fractional clusterings, Scarf’s theorem for balanced non-transferable-utility games, and greedy rounding to obtain an integral 2-Droop-core clustering.This differs from the geometric and greedy approaches used in much previous proportional-clustering work.
2 Preliminaries
The preliminaries define weighted metric clustering, agent losses, proportional-core notions, and the non-transferable-utility game framework used by Scarf’s theorem. These definitions formalize both the clustering problem and the stability concept proved later.
- Clustering instances: A clustering instance consists of agents N, centers C, a pseudometric d, and a maximum number k of selected centers.A clustering is a nonempty subset X ⊆C with |X| ≤k, and an agent’s loss is its distance to the closest selected center.
- Clustering instances: Weighted instances assign positive rational weights summing to 1, compactly representing multiple agents at the same location.The model permits agent elements to serve as centers and treats N ⊆C and N = C as explicit special cases.
- Clustering instances: When N ⊆C, the paper assumes k < |N| without loss of generality because choosing X = N gives every agent zero loss when |N| ≤k.This assumption excludes only instances that are already trivially fair under the considered loss functions.
- The (Droop) core and proportional fairness: Under the Droop quota, any group with total weight greater than 1/(k + 1) is entitled to one center, and the α-Droop core prohibits such groups from jointly α-improving.Every α-Droop-core clustering is also in the α-core defined using the Hare quota.
- NTU games and Scarf’s theorem: An NTU game assigns each nonempty coalition a payoff set, and an outcome is in the core when no coalition can give every member a strictly higher payoff.Scarf’s theorem states that every balanced NTU game has a nonempty core.
- NTU games and Scarf’s theorem: The paper characterizes coalition blocking through interiors of extended payoff sets and uses balancedness to invoke Scarf’s nonempty-core theorem.For coalition S, the extended set allows members outside S arbitrary utilities; blocking corresponds to membership in its interior.
3 The Existence of a 2-Droop Core Clustering
The paper proves existence of a clustering in the 2-Droop core by constructing a fractional core solution with Scarf’s theorem and greedily rounding it to agent locations. The argument first handles finite center sets, then extends the result to infinite sets.
- Proof strategy: The proof constructs a fractional clustering, applies Scarf’s theorem to obtain a fractional core solution, and rounds it into an integral clustering in the 2-Droop core.The fractional formulation represents clusterings as nonnegative mass vectors with total mass at most 1; mass 1 corresponds to k centers.
- Fractional formulation: For each agent, the fractional loss R_i(x) is the smallest radius containing at least the Droop quota δ of the clustering mass.If the total mass is below δ, R_i(x) is set to a distance bound D exceeding every agent-center distance.
- Fractional core: Scarf’s theorem yields a fractional clustering x* that no coalition can replace with a fractional clustering strictly improving every coalition member’s loss.The construction models utilities as u_i(x)=D−R_i(x) within a balanced non-transferable-utility game.
- Integral rounding: A greedy procedure orders agents by R_i(x*) and selects an agent whenever its ball B_i is disjoint from previously selected balls.Disjointness and the quota mass bound imply that at most k agents are selected; overlapping balls then provide the factor-2 distance guarantee.
- Integral rounding: The resulting clustering uses only agent locations and satisfies ℓ_i(X) ≤ 2R_i(x*) for every agent, which rules out any blocking Droop coalition.Assuming a blocking coalition would create a fractional deviation contradicting the defining property of x*.
- Infinite center sets: The finite-center result extends to infinite center sets by adding one representative center for each possible blocking pair and deriving a contradiction from the resulting finite instance.The finite set C′ contains the agent locations and selected representatives; a finite 2-Droop-core clustering would still be blocked by its corresponding representative.
4 Discussion
The paper identifies unresolved boundaries beyond the fully resolved N ⊆C case: lottery-based sortition, the general case, and efficient computation remain open in different respects.
- Further generalizations: The techniques do not readily establish a lottery over clusterings that makes the sortition model’s lower bound of 2 tight.In this model, each agent must be selected with probability k/|N| while every realized clustering receives a core-approximation guarantee.
- Separation between N ⊆C and the general case: The general case remains open, with known bounds of [2.1508, 1 + √2] and a 2-approximation available only under N ⊆C.The condition N ⊆C supplies enough structure for a 2-approximation, unlike the general setting.
- Separation between N ⊆C and the general case: Resolving the general-case gap is identified as the largest remaining theoretical open problem in core clustering.This open problem reflects the separation between the general case and the N ⊆C case.
- Polynomial-time computation: Polynomial-time computation is unresolved because Scarf’s theorem yields the needed utility vector, but finding such a vector is PPAD-complete in general.The fractional clustering can be rounded in polynomial time once obtained, but computing it lacks a clear polynomial-time path.