Multi-winner voting is the process of selecting a fixed-size set of representative candidates based on voters' preferences. It occurs in applications ranging from politics (parliamentary elections) to the design of modern computer applications (collaborative filtering, dynamic Q&A platforms, diversifying search results). All these applications share the problem of identifying a representative subset of alternatives -- and the study of multi-winner voting is the principled analysis of this task. This book provides a thorough and in-depth look at multi-winner voting based on approval preferences. One speaks of approval preferences if voters express their preferences by providing a set of candidates they approve. Approval preferences thus separate candidates in approved and disapproved ones, a simple, binary classification. The corresponding multi-winner voting rules are called approval-based committee (ABC) rules. Due to the simplicity of approval preferences, ABC rules are widely suitable for practical use. Recent years have seen a rising interest in ABC voting. While multi-winner voting has been originally a topic studied by economists and political scientists, a significant share of recent progress has occurred in the field of computational social choice. This discipline is situated in the intersection of artificial intelligence, computer science, economics, and (to a lesser degree) political science, combining insights and methods from these distinct fields. The goal of this book is to present fundamental concepts and results for ABC voting and to discuss the recent advances in computational social choice. The main focus is on axiomatic analysis, algorithmic results, and relevant applications.
翻译:多赢者投票是根据选民偏好选择一组固定规模的代表性候选人的过程,它出现在从政治(议会选举)到设计现代计算机应用程序(协作过滤、动态+A平台、搜索结果多样化)等各种应用中。所有这些应用都存在确定一组有代表性的替代方案的问题,而多赢者投票的研究则是对这项任务的原则分析。这本书对基于批准选择的多赢者投票进行了彻底和深入的审视。如果选民通过提供一组他们认可的候选人来表达他们的偏好,就表示他们的赞同偏好。批准偏好因此将经核准和不批准的候选人分开,简单、二进制分类。相应的多赢者投票规则被称为基于委员会的规则。由于批准偏好简单,ABC规则是广泛适合实际使用的。近年来,多赢者投票对ABC投票的兴趣日益浓厚。虽然多赢者投票最初是经济学家和政治科学家研究的一个专题,但在计算社会选择领域已经取得了相当大的进展。这一学科是将人造见解、计算机选举结果和BC基本计算方法的交叉化。这一学科是当前政治见解、计算机学、计算机学和基本分析领域的主要研究领域。