Building Consensus via Iterative Voting

Abstract

In networked systems comprised of many agents, it is often required to reach a common operating point of all agents, termed the network consensus. We consider two iterative methods for reaching a ranking (ordering) consensus over a voter network, where the initial preference of every voter is of the form of a full ordering of candidates. The voters are allowed, one at a time and based on some random scheme, to change their vote to bring them “closer” to the opinions of selected subsets of peers. The first consensus method is based on changing votes one adjacent swap at a time; the second method is based on changing a vote via averaging with the votes of peers, potentially leading to many adjacent swaps at a time vote. For the first model, we characterize convergence points and conditions for convergence. For the second model, we prove convergence to a global ranking and derive the rate of convergence to this consensus.