arXiv:2608.15247 · v2

Improved Metric Distortion Bounds for Deterministic Weighted-Tournament Voting Rules

首次提交 2026-08-15 22:13

版本更新 2026-11-12 01:09

雷达观测 2026-11-13 14:16

摘要

We study deterministic weighted-tournament voting rules, also known as C2 rules, which use only the fraction of voters who prefer one candidate to another for each pair of candidates. Voters and candidates lie in a common but unknown metric space, and voters rank candidates by distance. The goal is to select a candidate minimizing the sum of distances to the voters, and distortion measures the worst-case approximation ratio relative to an optimal candidate. Charikar et al.~[EC 2025] introduced the Unblanketed Set rule with distortion at most $3.9312$ and proved a lower bound of $3.1128$ for deterministic C2 rules. We extend their rule to the Path-Unblanketed Set rule, which runs in polynomial time and achieves distortion at most $1+2\sqrt{2}\approx3.8284$. The rule uses paths between candidates to combine pairwise comparisons without increasing the approximation loss with the path length. With computer assistance, we prove a better upper bound of $3.3346$ for five or six candidates and a general lower bound of $3.1828$ using a construction with 17 candidates.