学术报告|
当前位置:首页 > 科研 > 学术报告
发表时间:2019-01-11 阅读次数:41次
报告题目: 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

Copyright © |2012 复旦大学数学科学学院版权所有 沪ICP备042465  

电话:+86(21)65642341 传真:+86(21)65646073