研究了社会选择中度量失真问题,给出了一种新的投票规则,通过随机化最大允许值与新规则可实现失真小于 2.753,其为计算社会选择中重要而具有挑战性的问题。
Jun, 2023
提出了一种名为 Plurality Veto 的简单的投票规则,它只需进行两次查询,就可以实现 “失真度” 的最优解,并进一步将其推广为更广泛的随机化投票规则。
Jun, 2022
本篇文章是通过一种效用歪曲的框架来评估社会选择(投票)规则,其中利用代理人提交的完整排名来生成社会成本,从而探讨选举规则的失真度和公平比率等概念。其中提出的 Copeland rule 实现了至多 5 的失真度和公平比率的两个指标,并将单赢家规则的失真度和多赢家规则联系起来,基于此引出 Recursive Copeland 规则在选择一组备选方案时,实现了 5 的失真度和 7 以下的公平比率。
Oct, 2018
本文研究了社会选择规则在利益最大化失真框架下的表现,并探讨了 Ranked Pairs 及 Copeland rule 的最坏失真情况,以及随机化对于比赛的影响。另外,我们证明了 Copeland 和 Randomized Dictatorship 具有较低的公平性比率。
Dec, 2016
该研究开发了一种新的投票机制,旨在选择能够最大程度降低社会成本(即选民与候选人之间的总距离)的候选人,并量化了关于候选人失真度和投票者偏好力量信息之间的权衡。
Jun, 2019
研究度量扭曲问题:有两个点集 V 和 C,它们在相同的度量空间中,我们的目标是选择 C 中一点,其到 V 点的总距离尽可能小。我们提出了使用排名作为输入的算法,并提供了它们的扭曲界限。
Apr, 2020
本文研究了基于代理人的顺序偏好设计投票规则的问题,并使用 “变形度量” 来衡量投票规则的性能,旨在最大化所有代理人的快乐度,文中研究了两个不同的投票变形世界:功利变形和度量变形,并证明了可以通过设计新的投票规则同时达到两种变形下的最优性能。
May, 2023
本文研究了计算社会选择中投票规则的畸变,通过研究选民效用分布上的期望畸变,设计和分析了一种新颖且直观的规则 —— 二项式投票,为所有分布提供了强大的期望畸变保证。
我们研究社会选择机制中的失真问题,提出了具有恒定样本复杂度和恒定失真度的社会选择机制 Random Referee。我们证明了这种机制使用比较查询是必要的,通过正态指标证明了这种机制的失真最小,并介绍了一种只需要 3 个查询的机制 Random Oligarchy。
Nov, 2018
本文考虑选举中的社会福利和代表性候选人对社会福利的影响,采用度量优先模型来探索社会最佳的程度和度量空间的复杂性对其影响,得到了多个近似比例的下限和上限。
May, 2017