您的位置 > 首页 > 会议讲座 > Byzantine Preferential Voting

Byzantine Preferential Voting

来源:复旦大学数学科学学院 | 2019-01-11 | 发布:经管之家

报告题目: Byzantine Preferential Voting报 告 人:Dr. Yuyi Wang报告人所在单位:ETH Zürich报告日期:2019-01-11 星期五报告时间:13:30-14:30报告地点:光华东主楼1704报告摘要:
In the Byzantine agreement problem, n nodes with possibly different input values aim to reach agreement on a common value in the presence of t<n/3 Byzantine nodes which represent arbitrary failures in the system. This paper introduces a generalization of Byzantine agreement, where the input values of the nodes are preference rankings of three or more candidates. We show that consensus on preferences, which is an important question in social choice theory, complements already known results from Byzantine agreement. In addition, preferential voting raises new questions about how to approximate consensus vectors. We propose a deterministic algorithm to solve Byzantine agreement on rankings under a generalized validity condition, which we call Pareto-Validity. These results are then extended by considering a special voting rule which chooses the Kemeny median as the consensus vector. For this rule, we derive a lower bound on the approximation ratio of the Kemeny median that can be guaranteed by any deterministic algorithm. We then provide an algorithm matching this lower bound. To our knowledge, this is the first non-trivial generalization of multi-valued Byzantine agreement to multiple dimensions which can tolerate a constant fraction of Byzantine nodes.

海报


本年度学院报告总序号:17
本文已经过优化显示,查看原文请点击以下链接:
查看原文:http://math.fudan.edu.cn/Show.aspx?info_lb=765&info_id=6121&flag=527

点击风云榜

看图学经济more

院校点评more

京ICP备11001960号  京ICP证090565号 京公网安备1101084107号 论坛法律顾问:王进律师知识产权保护声明免责及隐私声明   主办单位:人大经济论坛 版权所有
联系QQ:2881989700  邮箱:service@pinggu.org
合作咨询电话:(010)62719935 广告合作电话:13661292478(刘老师)

投诉电话:(010)68466864 不良信息处理电话:(010)68466864