Relation-algebraic and Tool-supported Control of Condorcet Voting
We present a relation-algebraic model of Condorcet voting and, based on it, relation-algebraic solutions of the constructive control problem via the removal of voters. We consider two winning conditions, viz. to be a Condorcet winner and to be in the (Gilles resp. upward) uncovered set. For the first condition the control problem is known to be NP-hard; for the second condition the NP-hardness of the control problem is shown in the paper. All relation-algebraic specifications we will develop in the paper immediately can be translated into the programming language of the BDD-based computer system RelView. Our approach is very flexible and especially appropriate for prototyping and experimentation, and as such very instructive for educational purposes. It can easily be applied to other voting rules and control problems.
Code (0)
등록된 구현이 없습니다.
Tasks
RelationSimilar Papers 제목 키워드 기반
A jury evaluation theorem
Majority voting (MV) is the prototypical ``wisdom of the crowd'' algorithm. Theorems considering when MV is optimal for group decisions date back to Condorcet's 1785 jury decision theorem. The same assumption of error in…
Closeness Centrality via the Condorcet Principle
We uncover a new relation between Closeness centrality and the Condorcet principle. We define a Condorcet winner in a graph as a node that compared to any other node is closer to more nodes. In other words, if we assume …
Differentially Private Condorcet Voting
Designing private voting rules is an important and pressing problem for trustworthy democracy. In this paper, under the framework of differential privacy, we propose a novel famliy of randomized voting rules based on the…
AlgDiff: An open source toolbox for the design, analysis and discretisation of algebraic differentiators
Algebraic differentiators have attracted much interest in recent years. Their simple implementation as classical finite impulse response digital filters and systematic tuning guidelines may help to solve challenging prob…
Fault DiagnosisFinding Preference Profiles of Condorcet Dimension $k$ via SAT
Condorcet winning sets are a set-valued generalization of the well-known concept of a Condorcet winner. As supersets of Condorcet winning sets are always Condorcet winning sets themselves, an interesting property of pref…