arXiv:2608.29308cs.GTcs.AI2026-08

提出随机规模稳定抽奖机制,将投票系统扭曲度降至2.3282

Improving Randomized Metric Distortion to 2.3282

  • 引入随机规模稳定抽奖,通过期望倒数控制偏好概率
  • 结合集成否决法,将扭曲度优化至11641/5000=2.3282
  • 适用于追求最优随机投票规则的理论研究者

在度量社会选择中,每位选民根据未知度量空间中的距离对m个候选人排序。候选人的成本为其到所有选民的平均距离。随机投票规则仅使用排名结果选择候选人分布。其扭曲度定义为该分布下期望成本与最优候选人成本之比的最坏情况。Charikar等(JACM 2024)证明上界为2.753,确立了与确定性规则(最佳扭曲度为3)的常数差距。独立地,Frank(arXiv:2608.17863)和Ye(arXiv:2608.21202)将其改进至2.5,使用最大抽奖与集成否决的等权混合。现有论证无法通过任意混合进一步提升。本文突破此限制,引入新工具——随机规模稳定抽奖(RSL_D)。当D为正整数随机变量时,该机制保证:任意选民偏好固定候选人c超过从RSL_D中独立抽取D次的最优者的概率不超过𝔼[1/(D+1)]。当D=k为定值时,退化为Charikar等(EC 2025)提出的稳定k抽奖;k=1时即为最大抽奖。其极小极大分析可推广至随机D。核心贡献在于展示如何利用随机D下的稳定性来界定扭曲度。通过适配随机规模稳定抽奖与集成否决的混合策略,获得扭曲度不超过11641/5000 = 2.3282。证明结合无限维锥线性规划对偶、启发式非线性优化及伯恩斯坦基精确理性验证。

原文摘要 · Abstract (English)

In metric social choice, each voter ranks a set of $m$ candidates by her distance to them in an unknown metric space. The cost of a candidate is its average distance to the voters. A randomized voting rule must use only the rankings to choose a lottery over candidates. Its distortion is the worst-case ratio between the expected cost under the lottery it returns and the cost of the best candidate. Charikar, Ramakrishnan, Wang, and Wu [JACM 2024] prove an upper bound of $2.753$, establishing a constant separation from deterministic rules, for which the best achievable distortion is $3$. Independently, Frank [arXiv:2608.17863] and Ye [arXiv:2608.21202] improve the bound to $2.5$, using an equal mixture of maximal lottery and Integrated Veto. The existing arguments do not yield a better bound with any mixture of these rules. We break this barrier with a new ingredient, a random-size stable lottery. Let $D$ be a random variable over the domain of positive integers. A random-size stable lottery $\mathrm{RSL}_D$ guarantees that the probability of a random voter preferring any fixed candidate $c$ to her favorite of $D$ i.i.d. draws from $\mathrm{RSL}_D$ is at most $\mathbb{E}[1/(D+1)]$, where the probability also averages over $D$. When $D=k$ deterministically, this reduces to the stable $k$-lottery of Charikar, Ramakrishnan, Tan, and Wang [EC 2025]; the case $k=1$ is precisely a maximal lottery. Their minimax argument for a fixed $k$ easily generalizes to a random $D$. Our main contribution is to show how stability with respect to a random $D$ can be used to bound distortion. By mixing a suitably chosen random-size stable lottery with Integrated Veto, we get distortion at most $11641/5000=2.3282$. The proof combines infinite-dimensional conic linear-programming duality, heuristic nonlinear optimization, and exact rational verification via the Bernstein basis.

投票系统算法博弈论优化证明

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。