Van Zuylen et al. introduced the notion of a popular ranking in a voting context, where each voter submits a strictly-ordered list of all candidates. A popular ranking $\pi$ of the candidates is at least as good as any other ranking $\sigma$ in the following sense: if we compare $\pi$ to $\sigma$, at least half of all voters will always weakly prefer~$\pi$. Whether a voter prefers one ranking to another is calculated based on the Kendall distance. A more traditional definition of popularity -- as applied to popular matchings, a well-established topic in computational social choice -- is stricter, because it requires at least half of the voters \emph{who are not indifferent between $\pi$ and $\sigma$} to prefer~$\pi$. In this paper, we derive structural and algorithmic results in both settings, also improving upon the results by van Zuylen et al. We also point out strong connections to the famous open problem of finding a Kemeny consensus with 3 voters.


翻译:Van Zuylen et al. 介绍了在投票背景下民众排名的概念,即每个选民提交严格排序的所有候选人名单。在以下意义上,受欢迎的排名$pi$至少与任何其他排名$$$gma$一样好:如果我们把美元比作美元,那么,至少一半选民总是不太喜欢~$pi$。选民是否偏爱排名中的排名,根据Kendall距离来计算。更传统的流行定义 -- -- 适用于民众匹配,这是计算社会选择中公认的主题 -- -- 更为严格,因为它要求至少一半的选民在$pi$和$\sgma$之间不无差别,而不是选择~$\pi$。在本文中,我们从两种环境中都得出结构和算法结果,同时改进van Zuylen等人的结果。我们还指出,在与与3名选民达成Kemeny共识的著名公开问题之间有着密切的联系。

0
下载
关闭预览

相关内容

专知会员服务
123+阅读 · 2020年9月8日
MIT-深度学习Deep Learning State of the Art in 2020,87页ppt
专知会员服务
61+阅读 · 2020年2月17日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
大数据 | 顶级SCI期刊专刊/国际会议信息7条
Call4Papers
10+阅读 · 2018年12月29日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
LibRec 精选:推荐的可解释性[综述]
LibRec智能推荐
10+阅读 · 2018年5月4日
计算机类 | 国际会议信息7条
Call4Papers
3+阅读 · 2017年11月17日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2021年3月25日
Arxiv
0+阅读 · 2021年3月25日
Arxiv
0+阅读 · 2021年3月24日
Arxiv
0+阅读 · 2021年3月23日
The Evolved Transformer
Arxiv
5+阅读 · 2019年1月30日
VIP会员
相关VIP内容
专知会员服务
123+阅读 · 2020年9月8日
MIT-深度学习Deep Learning State of the Art in 2020,87页ppt
专知会员服务
61+阅读 · 2020年2月17日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
大数据 | 顶级SCI期刊专刊/国际会议信息7条
Call4Papers
10+阅读 · 2018年12月29日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
LibRec 精选:推荐的可解释性[综述]
LibRec智能推荐
10+阅读 · 2018年5月4日
计算机类 | 国际会议信息7条
Call4Papers
3+阅读 · 2017年11月17日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
相关论文
Arxiv
0+阅读 · 2021年3月25日
Arxiv
0+阅读 · 2021年3月25日
Arxiv
0+阅读 · 2021年3月24日
Arxiv
0+阅读 · 2021年3月23日
The Evolved Transformer
Arxiv
5+阅读 · 2019年1月30日
Top
微信扫码咨询专知VIP会员