The ACO Seminar (2024–2025)

We will start with a discussion of voting systems and a few of the criteria one may require of a voting system. We will show a few of the classic voting systems and discuss the criteria they satisfy. Most will assume voters rank the candidates which view as a weighted directed graph on the candidates.

Then we will consider a simple modification of the Perron-Frobenius eigenvector as a voting system of a strongly connected directed graph as a ranking system the candidates. In particular we dividing the rank of each candidate by her outdegree. Finally we scale the rankings so that the sum of the ranks is one giving us a score per candidate.

This scoring system has many nice properties:

1. The score of a candidate is invariant to selfloops
2. This system can be viewed as the stationary a Markov chain.
3. It can also be viewed as a standard random walk on the arc edge graph.
4. If we add an edge from A to B then the score of B will have the
largest percent gain of any candidate and A will have the largest lost.
5. If we add a 2-cycle with edges A to B and B to A, where the score of B is greater than A, then B score must decrease and A must increase.
6. Will discuss Markov Chain Tree Theorem and Tutte's tree count algorithm.
7. We return voting system criteria and our NPF scoring.