Optimally Selecting Representative Agents from a Metric Space
Computer Science and Game TheoryMachine Learning
Summary
The authors study a way to choose representative locations (centers) fairly for groups of agents spread out in a space, focusing on a fairness rule called the Droop core. They improve previous results by showing that it is always possible to find a clustering solution within a factor of 2 in fairness and that this solution can use only agents' own locations as centers. Their proof uses an existing mathematical theorem (Scarf's theorem) about fair solutions in cooperative games. This work also solves an open problem about voting-based clustering in complex spaces. Interestingly, part of the main proof was generated by an AI model and then verified by the authors.
Proportionally fair clusteringDroop coreMetric spaceScarf's theoremNon-transferable utility gamesApproximation ratioCore stabilityβ-plurality problemCooperative game theoryAgent-based clustering
Authors
Benjamin Cookson, Eva Deltl, Yeeseok Oh
Abstract
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.