Abstract:In this research note we briefly connect two well-studied topics in computational social choice: metric distortion and the selection of undominated committees. In particular, we show that undominated committees are (in some sense) both necessary and sufficient to achieve bi-criteria metric distortion below $3$ (Banishashem et al., 2026). First, we show that any $\alpha$-undominated committee with $\alpha \le 0.5 - \Omega(1)$ has a bi-criteria metric distortion strictly of $3 - \Omega(1)$. In particular, this implies that a committee of size $5$ with distortion at most $2.7384$ exists. Secondly, we show that if a committee has a bi-criteria metric distortion strictly of $3 - \Omega(1)$, then it must also be $1 - \Omega(1)$-undominated.
From: Jannik Peters [view email]
[v1]
Fri, 12 Jun 2026 06:07:33 UTC (7 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。