证明了公平聚类的最优逼近比为2，且中心可选在用户位置。
Optimally Selecting Representative Agents from a Metric Space
- 利用斯卡夫定理证明公平聚类存在性
- 首次实现2倍逼近下界，紧致结果
- 适合关注公平算法设计的研究者
本文研究比例公平聚类问题，目标是从度量空间中选出k个中心，以公平代表同样位于该空间中的代理群体。特别地，聚焦于满足名为Droop core的公平性质的聚类。在可行中心位置包含所有代理位置的实用情形下，此前最佳结果保证(1+√2)近似，而最优下界为2。本文证明该下界是紧的，且始终存在2-Droop core的聚类。进一步表明，仅需从代理所在位置选择中心即可达成。这一结论基于斯卡夫定理对平衡非转移效用博弈的核心非空性保障。该结果带来多个有趣推论，最显著的是解决了Aronov等[2021]提出的β-多数问题在一般度量空间下的开放问题。本文主要结果由ChatGPT-5.6-Sol通过与作者多轮交互生成，作者验证并重写了证明以提升清晰度。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。