This site is being phased out.

Higher order votes

From Mathematics Is A Science
Jump to navigationJump to search




Relation between ratings and rankings

The relation between ratings and rankings is shown below: $$\begin{array}{|ccc|} \hline V & f & O\\ \hline <C^0(K;{\bf Z})> & \to & C^0(K;{\bf Z})\\ \downarrow&\ne &\downarrow q\\ <R(K)> &\to& R(K)\\ \hline \end{array}$$ Here, $q$ is a function that converts rating to rankings according to the order. A rating, $X$ is reinterpreted as a rankings, $r$, for example: $$X(A_0)=...=X(A_k)=1,X(A_{k+1})=...=X(A_n)=0$$ $$\mapsto \ r: A_0=...=A_k>A_{k+1}=...=A_n.$$ The diagram doesn't commute! The reason is simple: $$\operatorname{sign} (a+b) \ne \operatorname{sign} a +\operatorname{sign} b.$$

Elections with comparison votes

This time, we consider comparison votes.

Just as before, the set of alternatives is $$A:=\{A_0,...,A_n\},$$ but now all of the edges are also present -- in the complete graph over $A$. The set of possible ratings is still the integers. The ratings aren't assigned to the alternatives but rather to the ordered pairs of alternatives, i.e., edges.

  • A vote is a comparison on $A$ with values in ${\bf Z}$, i.e., an arbitrary antisymmetric function $p:A\times A\to Q$. The notation is

$$V:=C^1(A;{\bf Z}).$$

  • An election is a formal sum of votes, and we have

$$E:=<V>.$$

  • An outcome is also a rating of pairs, i.e., an arbitrary symmetric function $p:A\times A\to {\bf Z}$. Thus, we have

$$O:=C^1(A;{\bf Z}).$$

  • A rating tally gives an outcome of any election of this type; i.e., it is any function

$$f:E=<V>\to O.$$ Note that the obvious algebraic structure of $O=C^0(A;{\bf Z})$, $$(X+Y)(P)=X(P)+Y(P),$$ is ignored for the time being.

We will restate some of the axioms. The first is without change.

Anonymity -- Commutativity: The election result is independent of the permutation of the votes; i.e., $$f(sPQ)=f(PQ),\ \forall s\in \mathcal{S}_A,\ \forall P,Q\in A.$$

This time, a tally is a function of $3$-dimensional $m\times m\times n$-matrices with matrices as its values. Each such matrix represents an election and its $(i,j,k)$-entry is the score assigned by the $k$th voter to the pair of the $i$th and $j$th candidates. This is what a single ballot/vote and the results look like: $$f: \left\{ \begin{array}{|c|ccc|} \hline k\text{-th ballot}&\text{candidates}\\ &\begin{array}{ccc}A_1&...&A_n\end{array}\\ \hline \begin{array}{ccc} \text{candidate } A_1\\ ...\\ \text{candidate } A_n \end{array} &\begin{array}{ccc} a_{11k}&...&a_{1nk}\\ ...&&...\\ a_{n1k}&...&a_{nnk} \end{array}\\ \hline \end{array} \right\} \mapsto \begin{array}{|c|ccc|} \hline {\bf Outcome}&\text{candidates}\\ &\begin{array}{ccc}A_1&...&A_n\end{array}\\ \hline \begin{array}{ccc} \text{candidate } A_1\\ ...\\ \text{candidate } A_n \end{array} &\begin{array}{cccccc} c_{11}&...&c_{1n}\\ ...&&...\\ c_{n1}&...&c_{nn} \end{array}\\ \hline \end{array} $$ Note that adding a zero ballot won't change the outcome.

According to Anonymity , reshuffling the ballots doesn't affect the outcome. In addition, we require that interchanging the rows and columns -- identically -- in all of these matrices interchanges the rows and columns in the outcome table in the exact same way.

Impartiality -- Symmetry: The election result is independent of the permutation of the candidates; i.e., $$f(X)(sPQ)=s^{-1}f(X)(PQ),\ \forall X\in E, \ \forall s\in \mathcal{S}_A,\ \forall P,Q\in A.$$

Just as before, renumbering the candidates, $A_1, ...,A_n$, in the ballots produces the same election outcome once we renumber them back.

Proposition. The summation tally $\Sigma$ satisfies Impartiality.

Once again, we apply the Uniqueness Theorem to conclude that there is, essentially, just one such decision function.

Theorem. A tally $f$ for comparisons that satisfies Stability and Triviality is the summation tally $\Sigma$.

Election manipulation?

For ratings, Independence of Irrelevant Alternatives takes the form of Monotonicity. For comparisons, we restate it by following the familiar link: the difference of the rating votes for candidates $P,Q$ is understood as a comparison vote for $PQ$: $$d(X)(PQ)=X(Q)-X(P).$$

Independence of Irrelevant Alternatives -- Positivity: If no voter has changed his preference for a given pair of candidates from the election to the next, then the preference of the election result for these candidates hasn't changed either; i.e., $$\begin{array}{llllll} \forall P,Q \in A,\ \forall X=\Sigma_i X_i,Y=\Sigma_i Y_i\in E,\ X_i,Y_i\in V=C^1(A;{\bf Z}),\\ \operatorname{sign}X_i(PQ) = \operatorname{sign}Y_i(PQ) \quad \Longrightarrow\\ \operatorname{sign}f(X)(PQ) = \operatorname{sign}f(Y)(PQ). \end{array}$$

After all, the derivative of a monotonic function is either all positive or all negative.

Is election manipulation still a problem?

Let $n:=4$ and $m:=3$. Consider the same preferences as in the last example of election manipulation but this time we interpret the preferences as comparisons. Each voter assigns $1$ to $PQ$ if he prefers $P$ over $Q$: $$ \begin{array}{|c|cccc|} \hline X:&A&B&C&D\\ \hline A&0&1&1&1\\ B&-1&0&1&1\\ C&-1&-1&0&1\\ D&-1&-1&-1&0\\ \hline \end{array} + \begin{array}{|c|cccc|} \hline Y:&A&B&C&D\\ \hline A&0&-1&1&1\\ B&1&0&1&1\\ C&-1&-1&0&1\\ D&-1&-1&-1&0\\ \hline \end{array} + \begin{array}{|c|cccc|} \hline Z:&A&B&C&D\\ \hline A&0&-1&1&1\\ B&1&0&1&1\\ C&-1&-1&0&1\\ D&-1&-1&-1&0\\ \hline \end{array} $$ Here's $U=\Sigma(X,Y,Z)$, the outcome vote: $$\mapsto\begin{array}{|c|cccc|} \hline U:&A&B&C&D\\ \hline A&0&-1&3&3\\ B&1&0&3&3\\ C&-3&-3&0&3\\ D&-3&-3&-3&0\\ \hline \end{array} $$

In the second election, voter $X$, now $X'$, moves $B$ from the second place to the last on his list: $$ \begin{array}{|c|cccc|} \hline X':&A&B&C&D\\ \hline A&0&1&1&1\\ B&-1&0&-1&-1\\ C&-1&1&0&1\\ D&-1&1&-1&0\\ \hline \end{array} + \begin{array}{|c|cccc|} \hline Y:&A&B&C&D\\ \hline A&0&-1&1&1\\ B&1&0&1&1\\ C&-1&-1&0&1\\ D&-1&-1&-1&0\\ \hline \end{array} + \begin{array}{|c|cccc|} \hline Z:&A&B&C&D\\ \hline A&0&-1&1&1\\ B&1&0&1&1\\ C&-1&-1&0&1\\ D&-1&-1&-1&0\\ \hline \end{array} $$ Here's $V=\Sigma(X',Y,Z)$, the outcome vote: $$\mapsto\begin{array}{|c|cccc|} \hline U:&A&B&C&D\\ \hline A&0&1&3&3\\ B&-1&0&1&1\\ C&-3&-1&0&3\\ D&-3&-1&-3&0\\ \hline \end{array} $$

The election results match: $$U,V:\ B > A.$$ Thus, even though $X$ pushed $B$ to the bottom of his list, $B$ is still ahead of $A$. The manipulation failed.

Proposition. The summation comparison tally $f=\Sigma$ satisfies Independence of Irrelevant Alternatives.

That's why there is no impossibility theorem. The following sums up the results.

Theorem (Possibility of Comparison Tally). For $V=C^1(A;Q)$, the summation $f=\Sigma:E=<V> \to O=C^1(A;{\bf Z})$ satisfies Stability, Triviality, Impartiality, and Independence of Irrelevant Alternatives. Moreover, this is the only such tally.

What remains to be decided, with the comparison votes successfully tallied, who is the winner?

Who is the winner?

The winner is the one(s) with the largest rating. So, first of all, the outcome of the election must be a rating!

Let's consider the two elections we have studies combined into one: $$ \newcommand{\ra}[1]{\!\!\!\!\!\!\!\xrightarrow{\quad#1\quad}\!\!\!\!\!} \newcommand{\da}[1]{\left\downarrow{\scriptstyle#1}\vphantom{\displaystyle\int_0^1}\right.} \newcommand{\la}[1]{\!\!\!\!\!\!\!\xleftarrow{\quad#1\quad}\!\!\!\!\!} \newcommand{\ua}[1]{\left\uparrow{\scriptstyle#1}\vphantom{\displaystyle\int_0^1}\right.} % \begin{array}{|rcccl|} \hline \text{Election:}& & &&\text{Outcome:} &\\ \hline \text{comparison votes}&E_1 & \ra{\Sigma} &O_1& \text{a rating comparison vote}\\ &\ua{D} & & \ua{d}\\ \text{rating votes}&E_0 & \ra{\Sigma} &O_0& \text{a rating vote} \\ \hline \end{array} $$ Here, $d$ is the usual coboundary operator $$d:C^0(A)\to C^1(A),$$ while $$D:<C^0(A)>\to <C^1(A)>$$ is its extension: $$D(\Sigma_iX_i)=\Sigma_id(X_i).$$

By the Uniqueness Theorem, there are no other tallies!

Proposition. The diagram commutes: $$\Sigma D=d\Sigma:E_0\to O_1.$$

Proposition. The outcome of a comparison election with only rating comparison votes is a rating comparison vote: $$\Sigma D(x)=d\Sigma (x).$$

Even though the top row gives us an election that satisfies IIA, it doesn't give us a rating. The avenues we are interested in would have to end at the bottom right corner.

The first option is to we run a rating election. Then, IIA is violated.

The second option is to bypass the direct route from rating election to the total rating: up, right, then down. In other words, we first convert each voter's rating vote into a comparison vote, then tally the votes into a total comparison vote, and then finally convert it back to a rating vote. (The last step is made possible by the last proposition.) Unfortunately, since the start and the end points of the route remain the same as in the first case, this scheme fails due to the commutativity of the diagram.

The third option to start with a comparison election and then to proceed to convert the resulting comparison vote to a rating. The last step may, however, be impossible.

Ratings and comparisons

As common it is to rate the alternatives, it is very uncommon to compare them -- pairwise -- to evaluate the perceived inequality of value. As we just saw, the latter approach doesn't face the some issues as the former.

The general setup is as follows. There are $n$ alternatives/candidates and they are the nodes of a directed graph $K$: $$K^{(0)}:=\{A_0,A_1, A_2, ... ,A_{n-1}\}.$$ All candidates are subject to evaluation but the presence of edge $AB$ in $K$ reflects the fact that $A$ and $B$ are comparable: $$K^{(1)}:=\{A_0A_1, A_0A_2, ... ,A_{n-1}A_n\}\subset K^{(0)}\times K^{(0)}.$$

Directed graph.png

A rating vote is a number $X\in {\bf Z}$ assigned to each candidate, as well as a combination of all these numbers. Therefore, it is simply a function $s:K^{(0)}\to {\bf Z}$, known as a $0$-cochain on $K$. The set of rating votes is denoted by $$C^0(K;{\bf Z}).$$

Rating vote.png

A comparison vote is a number $x\in {\bf Z}$ assigned to each pair of candidates (i.e., the edge between them), as well as a combination of all these numbers. Therefore, it is simply an antisymmetric, i.e., $f(AB)=-f(BA)$, function $s:K^{(1)}\to {\bf Z}$, known as a $1$-cochain on $K$. The set of all comparison votes is denoted by $$C^1(K;{\bf Z}).$$

Comparison vote.png

The differences, according to the order of vertices, over a given rating vote for each pair of candidates produces a comparison vote: $$x(12)=d X(12):=X(2)-X(1).$$ Combined, this is the coboundary operator $d:C^0\to C^1$.

A rating comparison vote is one that comes from some rating vote of the candidates, as described. It is known as a $1$-coboundary. The set of all rating comparison votes is denoted by $$B^1=\operatorname{Im}d.$$

A non-circular comparison vote is one that satisfies the condition: as one takes any circular route through the candidates/vertices of $K$, the preferences always add up to zero. It is known as a $1$-cocycle. The set of all non-circular comparison votes is denoted by $$Z^1=\ker d.$$

We now use this terminology to restate what we know form algebra.

“Every coboundary is a cocycle” is restated as follows.

Proposition. Every rating comparison vote is non-circular.

“Every $k$-cocycle is a $k$-coboundary if $K$ is acyclic” is restated as follows.

Proposition. If $K$ is a tree, every comparison vote is rating.

These sets are all groups with respect to the obvious operation. They are related to each other in the cochain complex: $$\newcommand{\la}[1]{\!\!\!\!\!\xleftarrow{\quad#1\quad}\!\!\!\!\!} \begin{array}{ccccccc} C^1 & \la{d} & C^0 \\ \cup & & || \\ Z^1 & \la{d} & C^0 \\ \cup & & || \\ B^1 &\la{d (onto)} & C^0. \end{array}$$

Even in the case of a single voter, who wins?

In the simplest case, there is only a single rating. Then, we choose the winner to be the one (perhaps tied) with the largest rating.

What if the voter casts a comparison vote $b$ instead? Even though what we really need is a rating vote, we don't have to discard $b$. The reason is that $b$ may be a rating comparison vote: $b=d(c)$ for some rating $c$ (i.e., $b$ is a coboundary). Then the winner should be the one with the largest value of $c$. Based on the last proposition, we conclude that we can guarantee that there is such a $c$ if and only if $K$ is a tree, which is certainly atypical. Finally, if this is the case, the choice of the winner(s) is unambiguous.


Ratings and comparisons

In several stages, we will consider the foundation of a basic voting system. In a typical political election, the voter ranks the candidates with no numbers involved. We will concentrate on simpler, numeric voting methods that are meant to evaluate rather than just to rank. These methods require us to use our ring $R$ again.

This is how, typically, votes are used for evaluation. The customer/voter assigns a number from $\{1,2, ...,N\}$ to a product or service as a substitute of its perceived quality, such as:

  • books,
  • movies,
  • hotels,
  • various products,
  • service providers,
  • etc. $\\$

The choice is commonly visualized by $5$ stars: $$\star\quad \star\star\quad \star\star\star\quad \star\star\star\star\quad \star\star\star\star\star\ .$$ In political elections, it is simple: $$Yes: \underline{\checkmark} \quad No: \underline{\quad}$$

As common it is to rate the alternatives, it is very uncommon to compare them -- pairwise -- to evaluate the perceived inequality of value. As we will see, the latter approach will help us resolve some of the issues with the former.

The general setup is as follows. There are $n$ alternatives/candidates: $$A:=\{0,1,2, ...,n-1\}=\{A_0,A_1, A_2, ... ,A_{n-1}\}.$$ They are ordered. We also suppose that these candidates are the vertices of an oriented simplicial complex $K$. All candidates are subject to evaluation but the presence of edge $AB$ in $K$ reflects the fact that $A$ and $B$ are comparable.

At first, we will only consider what a single voter does; however, a single vote may come from aggregated votes.

We initially assume that $K$ is simply a (directed) graph:

Directed graph.png

A rating vote is a number $X\in R$ assigned to each candidate, as well as a combination of all these numbers. Therefore, this is a $0$-cochain on $K$. The totality is $C^0=C^0(K)$.

Rating vote.png

A comparison vote is a number $x\in R$ assigned to each pair of candidates (i.e., the edge between them), as well as a combination of all these numbers. Therefore, this is a $1$-cochain on $K$. The totality is $C^1=C^1(K)$.

Comparison vote.png

That's all.

The differences, according to the order of vertices, over a given rating vote for each pair of candidates produces a comparison vote: $$x(12)=\partial^0 X(12):=X(2)-X(1).$$ Combined, this is the $0$-coboundary operator $\partial^0:C^0\to C^1$.

A rating comparison vote is one that comes from some rating vote of the candidates, as described. Therefore, this is a $1$-coboundary. The totality is $B^1=\operatorname{Im}\partial^0$.

A non-circular comparison vote is one that satisfies the condition: as one takes a circular route through the candidates/vertices of $K$, the preferences always add up to zero. Therefore, this is a $1$-cocycle. The totality is $Z^1=\ker \partial^1$.

We now use this terminology to restate what we have learned in the this section.

“Every coboundary is a cocycle” is restated as follows.

Proposition. Every rating comparison vote is non-circular.

“Every $k$-cocycle is a $k$-coboundary if $H^1(K)=0$” is restated as follows.

Proposition. If $K$ is a tree, every comparison vote is rating.

The cochain complex and these subspaces are shown below: $$\newcommand{\la}[1]{\!\!\!\!\!\xleftarrow{\quad#1\quad}\!\!\!\!\!} \begin{array}{ccccccc} 0 & \la{\partial^{2}=0} & C^2 & \la{\partial^1} & C^1 & \la{\partial^0} & C^0 \\ & & \cup & & \cup & & || \\ & & 0 & \la{0} & Z^1 & \la{} & C^0 \\ & & || & & \cup & & || \\ & & 0 & \la{0} & B^1 &\la{onto} & C^0. \end{array}$$

Even in the case of a single voter, who wins?

In the simplest case, there is only a single rating. Provided $R$ is equipped with an order relation, we choose the winner to be the one (perhaps tied) with the largest rating.

What if the voter casts a comparison vote $b$ instead? Even though what we really need is a rating vote, we don't have to discard $b$. The reason is that $b$ may be a rating comparison vote: $b=\partial^0(c)$ for some rating $c$ (i.e., $b$ is a coboundary). Then the winner should be the one with the largest value of $c$. Based on the last proposition, we conclude that we can guarantee that there is such a $c$ if and only if $K$ is a tree, which is certainly atypical. Finally, if this is the case, the choice of the winner(s) is unambiguous.

Example (utility). Once such a vote is given, we may also produce a vote for every linear combination of candidates: $$X\Big(\sum_i p_iA_i\Big):=\sum_i p_iX(A_i).$$ We recognize this as the expected utility on $K$:

Utility function.png

$\square$

Instead of just pointing out an ideal location, either of the two hikers may attempt to express a more complex set of preferences.

Typically, the hiker can assign a number to each location in the forest reflecting his appreciation (i.e., the utility) of this choice. In the discrete interpretation, we suppose there are three camp sites, $A,B,C$, set up in the forest. Then hiker $X$ assigns a number to each camp site.

Beech fork as triangle.png

Then $X$'s vote is a triple $(a,b,c)\in R^3$, and so is $Y$'s, where $R={\bf R}$ or ${\bf Z}$ is our ring of coefficients. The goal is to find a triple that best approximates the desires of the two. A compromise-producing rule for the two hikers is then a function: $$f: R^3\times R^3 \to R^3.$$ Even though Continuity doesn't apply anymore, Symmetry and Diagonality are natural requirements. We will see that such a function still might not exist, depending on our choice of $R$.

The main examples of this choice-making are:

  • ratings: $X(A)=1,\ X(B)=4$, etc.;
  • comparisons;
  • rankings: $X(A)=\#1,\ X(B)=\#2$, etc.; and
  • preferences: $A < _x B,\ B < _x C$, etc.

Can any of these votes be combined into one compromise vote following the fairness principles presented in the last subsection?

More generally, there are $n$ alternatives or candidates: $$A:=\{0,1,2, ...,n-1\}=\{A_0,A_1, A_2, ... ,A_{n-1}\}.$$ They are ordered. We also suppose that these candidates are the vertices of a path-connected simplicial complex $K$. All candidates are subject to evaluation but the presence of edge $AB$ in $K$ reflects the fact that $A$ and $B$ are comparable.

Simplex of choices.png

We will look into the first two options as they are subject to the algebra we know. A rating vote is an element of $C^0=C^0(K)$. In particular, a rating vote is a combination of numbers assigned to each candidate. Therefore, this is a $0$-cochain on $K$, $X\in C^0(K)$.

Example (utility). Once such a vote is given, we may also produce a vote for every linear combination of candidates: $$X\Big(\sum_i p_iA_i\Big):=\sum_i p_iX(A_i).$$ We recognize this as the expected utility on $K$:

Utility function.png

$\square$

Furthermore, a comparison vote is a combination of numbers assigned to each pair of candidates. Therefore, this is a $1$-cochain on $K$, $x\in C^1(K)$.

Google's PageRank

PageRank is a popular method of evaluating the relative importance of web-pages based on their incoming and outgoing links. It is a mathematical idea that was at the core of Google's web search algorithm. According to Google, “PageRank thinks of links as `votes', where a page linking to another page is essentially casting a vote for that page... PageRank also considers the importance of each page that casts a vote, as votes from some pages are considered to have greater value, thus giving the linked page greater value.” This is how such evaluation is supposed to work; however, the actual formula for PageRank shows that it's not an electoral system in the sense we have put forward.

Let's review the basics of the algorithm of PageRank and subject them to mathematical scrutiny...

The idea of the definition is recursive.

Pagerank flow.png

Suppose a given page has three (or any other number) incoming links and five outgoing links. Let's assume that at the last stage the page received $9$ points of “PageRank” from the incoming links. Then, at the next stage, these $9$ points are distributed equally to the five outgoing links that carry these points to those pages. Consequently, each carries $9/5$ points.

Starting with an equal number of points for every page, we allow the flow go around the web following the links and we recompute the PageRank for every page at every step. Once everything settles, the pages have accumulated their PageRanks as ratings and they are then ranked accordingly.

The simple formula fails when there are loops in the graph of links:

Pagerank loop.png

The reason is that a proportion of the initial PageRank of one of these pages will travel the full loop.

Example. Consider the propagation of PageRank through this simple graph: $$ \newcommand{\ra}[1]{\!\!\!\!\!\!\!\xrightarrow{\quad#1\quad}\!\!\!\!\!} \newcommand{\da}[1]{\left\downarrow{\scriptstyle#1}\vphantom{\displaystyle\int_0^1}\right.} % \begin{array}{ccccccc} & 1 & \ra{} & 1 \\ & & \nwarrow & \da{}\\ & 1 & \ra{} & 1 \end{array} \leadsto \begin{array}{ccccccc} & 1 & \ra{} & 1 \\ & & \nwarrow & \da{}\\ & 0 & \ra{} & 2 \end{array} \leadsto \begin{array}{ccccc} & 2 & \ra{} & 1 \\ & & \nwarrow & \da{}\\ & 0 & \ra{} & 1 \end{array} \leadsto \begin{array}{ccccc} & 1 & \ra{} & 2 \\ & & \nwarrow & \da{}\\ & 0 & \ra{} & 1 \end{array} \leadsto \ ... \quad\ra{\quad\quad\quad} \quad ? $$ There is no convergence! $\hspace\fill\square$

In order to ensure its convergence, the algorithm is modified. This time, only a proportion, $r$, of the current PageRank is passed to the target pages. This number, called the decay coefficient, is commonly chosen to be $r=.85$. As there is no justification for choosing this over another value, $r$ is a non-mathematical, made-up parameter of this model.

Even after such a modification, there are examples of undesirable behavior, such as accumulation of PageRank at the dead-ends.

Example. Suppose pages are linked to each other consecutively: $$A \to B \to C \to ... \to Y \to Z. $$ Then all pages will eventually pass their entire PageRanks to $Z$. As a result, pages $A$-$Y$ are tied at $0$. Then the seemingly obvious ranking, $$A < B < C < ... < Y < Z,$$ is lost! $\hspace\fill\square$

In order to ensure that every page will get some of the PageRank, the algorithm is modified, again. This time, it is assumed that pages with no outbound links are linked to all other pages.

Further examples may cause (and perhaps may have caused) further modifications of the algorithm. Instead, we simply present the most common way to compute the PageRank.

Definition. Suppose the web is represented as a directed graph and let $E$ be the set of edges and $N$ the set of nodes in the graph. Then $P_i$, the PageRank of the $i$th node $i$, is defined by the recursive formula: $$P_i=(1-r ) \displaystyle\sum _{ij\in E}\frac{P_j}{\deg j}+\frac{r}{\#N}.$$

The totality of the PageRanks is a rating (not a ranking).

There are still a number of surprising features. One is this:

  • adding outbound links to your page may improve its PageRank.

Example (adding outbound links). Suppose we have ten “web-pages”: $A, B, ..., J$. They are listed in the table as both rows and columns. The links are the entries in the table.

First we suppose that they link to each other consecutively: $$A \to B \to C \to ... \to J. $$

Pagerank-chain.png

The PageRank points, as well as the rankings, of the pages are computed and displayed on the right. The scores for $A, ..., J$ are increasing in the obvious way: from $0$ to $.1$. In particular, $F$ is $\#$5.

Next, suppose $F$ adds a link to $A$, $F \to A$, which completes the loop. You can see that $1$ has appeared in the first column of the table:

Pagerank-chain-with-cycle.png

Now, suddenly $F$ ranks first! Thus, adding an outbound link has brought this page from $\#$5 to $\#$1. $\hspace\fill\square$

Another undesirable but not unexpected feature is:

  • changing the decay coefficient may change your rankings. $\\$

PageRank's paradigm is about passing something valuable (popularity, significance, authority, etc., but not a vote) from a page to the next along its links. Then, the PageRank points show who, after all this “redistribution of wealth”, ends up on top. This process is called advection: a fluid flow carries some substance, such as sand, around and gradually deposits it in different locations. Certainly, the amount of sand accumulated “at the end of the day” at a given location should be expected to depend on the percentage of sand deposited per unit of time.

The approach to voting explained in this section is applied to web search as follows:

  • the presence of a link from $A$ to $B$ is a comparison vote of $-1$ on $AB$.

Combining ratings with comparisons

The outcome of an election is a single vote. It may be a comparison vote and it can be “inconsistent” (even when each vote isn't), such as $$A>B>C>A.$$ When the differences are identical, the outcome should be treated as a tie (left):

Circular voting.png

Definition. A perfectly circular vote is a comparison vote $x\in C^1$ with $$x(A_iA_i)=p\in R,$$ for some circular sequence of adjacent vertices $A_0,A_1, . . .,A_n=A_0$, and $0$ for the rest.

Now, more complex votes may contain non-circular components (above right): $$A>B>C>A,\quad D>A,D>B,D>C.$$ Here, $D$ is the winner.

We need to learn how to extract the circular component (left) from a given vote so that we can discard it, as follows: $$A=B=C,\quad D>A,D>B,D>C.$$

A related idea appears, for example, when we study the motion on an inclined surface. Then only the component of the force parallel to the surface matters and the normal component is to be discarded. Then we will need the concept of the orthogonal complement of a subset $P$ of an inner product space $V$: $$P^\perp := \{v\in V: v\perp u,\ \forall u \in P\}.$$ It is a submodule.

Proposition. Suppose $P$ is a subset of an inner product space $V$. Then its orthogonal complement is a summand: $$V=< P >\oplus P^\perp.$$ Moreover, every element of $V$ is uniquely represented as the sum of its parallel and orthogonal components: $$v=v^{||}+v^\perp,\quad v^{||}\in < P >,v^\perp\in P^\perp.$$

Orthogonal decomposition.png

We next consider progressively more complex voting situations, which will eventually bring us to this concept.

In a basic electoral system, we have $n$ candidates located at the vertices of a simplicial complex $K$. We assume that the ring of coefficients $R$ is either ${\bf Z}$ or ${\bf R}$. A vote $x$ is an element of $C^*=C^*(K)$: $$a=a^0+a^1+a^2+...,\ a^i\in C^i(K).$$ The vote may be cast by a single voter or is the result of an election. In either case, we don't assume any consistency or strategy on behalf of the voter and, therefore, no interdependence among $a^0,a^1,a^2, ...$.

Who is the winner?

Definition. For a given vote $a$, the winner of degree $0$ is the candidate(s) with the largest value of $a^0$.

Thus, $$winner:=\arg\displaystyle \max _{i\in K^{(0)}} a^0(i).$$ Above, $a^0$ is a rating vote and $a^1$ is a comparison vote. We discarded the comparison vote $a^1$ in the definition. However, it is unwise to throw out meaningful information and it is in fact unacceptable when there is a tie.

Example. We have already seen that for the vote $$a^0=1,\quad a^1(AB)=1,\ a^1(BC)=-1,\ a^1(CA)=0,$$ the tie in dimension $0$ is broken by using the fact that $a^1$ is a coboundary: $$\hspace{.23\in}b^0(A)=0,\ b^0(B)=1,\ b^0(C)=0 \Longrightarrow \partial^0 b^0=a^1.\hspace{.23\in}\square$$

Definition. Suppose we are given a vote $a$ with the comparison component $a^1$ that is a coboundary. Then the winner of degree $1$ is the candidate(s) with the largest value of $a^0+b^0$, where $b^0$ is any $0$-chain that satisfies $\partial^0b^0=a^1$.

However, being a coboundary isn't necessary for the comparison component to be useful.

Example. We consider the simple case when the ratings are tied but the comparisons aren't:

  • $a^0(A)=a^0(B)$,
  • $a^1(A) < a^1(B)$.
Voting degree 0 1 with tie inexact.png

Then, plainly, $B$ is the winner! $\square$

Example. In the next example, we have a circular comparison vote. Then subtracting the average of its values reveals a rating vote:

Circular vote and its rating.png

$\square$

Exercise. State and prove a theorem that generalizes the above example.

Now, what if we can't see the winner by just an examination of the vote as in these examples? We do have an algebraic procedure for the case when $a^1$ happens to be a coboundary and now we need one for the general case.

Example. We consider the simple case above: $$a^0=(1,1,1),\ a^1=(1,0,0).$$

Voting degree 0 1 with tie inexact w projection.png

$\square$

Decycling: how to extract ratings from comparisons

At this point, we choose our ring of coefficients to be the reals $R={\bf R}$. Then we are in the realm of linear algebra: $C^1$ is a finite dimensional vector space and so is its subspace $B^1$. The projection of the former on the latter has a clear meaning which makes the following well-defined.

Definition. The best rating approximation of a comparison vote $a^1\in C^1$ is defined to be $$b^1:=\arg\displaystyle \min_{x\in B^1} ||x-a^1|| .$$

Next, $(\partial^0)^{-1}(b^1)$ is an affine subspace of $C^0(K)$. The elements are linear maps over $C_0(K)$ and, since $K$ is connected, they differ by a constant. We can say the same about $a^0+(\partial^0)^{-1}(b^1)$ for any $a^0\in C^0$. It follows each of them attains its maximum at the same location(s). Therefore, the following is also well-defined.

Definition. For a given vote $a$, a winner of degree $1$ is a candidate with the largest value of $a^0+b^0$, where $b^0$ is any $0$-chain that satisfies $\partial^0b^0=b^1$ and $b^1$ is the best rating approximation of $a^1$.

The construction is based on the following decomposition: $$C^1=B^1\oplus (B^1)^\perp.$$ What is the meaning of $(B^1)^\perp $ in the voting context?

Example. Observe that in the above example, the difference between $a^1=(1,0,0)$ and its best rating approximation is $$a^1-b^1=(1,0,0)-\Big(\tfrac{2}{3},-\tfrac{1}{3},-\tfrac{1}{3}\Big) =\Big(\tfrac{1}{3},\tfrac{1}{3},\tfrac{1}{3}\Big)=\tfrac{1}{3}(1,1,1).$$ Plainly, this is a vector perpendicular to the space of coboundaries and it is also a prefectly circular vote.

Decomposition of comparison votes.png

Thus, each comparison vote is (uniquely) decomposed into the sum of a non-circular vote and a perfectly circular vote. $\square$

Definition. The projection $D:C^1\to B^1$ will be called the decycling operator (technically, “de-co-cycling”).

Example. Suppose we have a perfectly circular vote $x$, i.e., a special $1$-cochain: $$x(AB)=x(BC)=x(AC)=p\in R.$$ We recognize it as the dual of a $1$-boundary: $$x=p(\partial_2ABC)^*.$$ Next, let's consider the coboundary of the dual of vertex $A$: $$c:=\partial^0A^* \in B^1.$$ Then, for every vertex $B_i$ adjacent to $A$, we have $$c(AB_i)=\partial^0A^*(AB_i)=A^*(\partial_1(AB_i))= A^*(B_i-A)= A^*(B_i)-A^*(A)=0-1=-1.$$ The rest are $0$s. The inner product of such $c$ and $x$ is illustrated below:

Cochains orthogonal to coboundaries.png

It is zero! $\square$

Theorem. $$(B^1)^\perp=(B_1)^*.$$

Exercise. Find explicit formulas for the decycling operator for $n=3$.

Corollary (Hodge decomposition). $$C^1=B^1\oplus (B_1)^*.$$

Accordingly, decycling doesn't just remove from each comparison vote something nonsensical, such as $$... < \text{ rock } < \text{ paper } < \text{ scissors } < \text{ rock } < ... ,$$ it removes exactly the component that prevents this comparison from being a rating.

With the decycled comparison vote $b^1$ at hand, we proceed to maximize $(\partial^0)^{-1}(b^1)$ as explained before. Alternatively, we look at a comparison vote as a weighted directed graph, a flow. With the circular patterns removed by decycling, this is an irrotational flow. Then the solution is:

  • follow this flow towards better and better candidates. $\\$

We find the best ones at its dead ends:

There may be many dead ends. If, as shown above, we ignore the edges with zero comparison votes, the graph may be disconnected. Then there will be at least one winner in each component of the graph. To choose the $\#1$ winner, we may compare the number of voters upstream from each of them:

This is how we decycle data with a spreadsheet.

We start with a comparison vote given as an antisymmetric $n\times n$ matrix $X$. We need to construct a rating vote, as an $n$-vector $R$, so that $\partial^0R$ is the closest to $X$.

As we have seen, there is a direct way, via linear algebra, to compute $R$ from $X$. We treat the task as an optimization problem instead: $$R:=\arg\displaystyle \min_R ||X-\partial^0R||.$$ To find the function to be minimized, we replace the norm with its square and then expand: $$\Phi (R_1, ...,R_n):= \displaystyle\sum _{ij}\Big(X_{ij}-(R_i-R_j)\Big)^2.$$ We will “chase” (the negative of) its gradient by the iteration: $$R_j':=R_j+h\Delta R_j,$$ where $h$ is the parameter of the process that controls the length of its step.

The spreadsheet shown below finds the ranking of the webpages for the web discussed previously:

Decycling comparison elections.png

Is there a fair electoral system?

First of all, the outcome must be a rating! Then the possible avenues presented in the diagram below have to end at the bottom right corner: $$ \newcommand{\ra}[1]{\!\!\!\!\!\!\!\xrightarrow{\quad#1\quad}\!\!\!\!\!} \newcommand{\da}[1]{\left\downarrow{\scriptstyle#1}\vphantom{\displaystyle\int_0^1}\right.} \newcommand{\la}[1]{\!\!\!\!\!\!\!\xleftarrow{\quad#1\quad}\!\!\!\!\!} \newcommand{\ua}[1]{\left\uparrow{\scriptstyle#1}\vphantom{\displaystyle\int_0^1}\right.} % \begin{array}{ccccc} \text{Election:} & & &&\text{Outcome:} \\ \text{comparison votes} &\ \ra{tally} & \text{a comparison vote} &\ \ra{decycling} & \text{a rating comparison vote}\\ \ua{(\partial^0)^m} & & & & \ua{\partial^0}\\ \text{rating votes} & \cdots\cdots & impossible & \cdots\cdots > & \text{a rating vote} \end{array} $$

Let's make a few observations.

First, we cannot run a rating election, because we cannot tally it fairly according to the impossibility theorem in this section. (Moreover, if we replace ratings with rankings, there is still no fair tally according to the original Arrow's Impossibility Theorem.)

Second, we can run a comparison election.

Third, we can bypass the impossible direct route from rating election to the total rating: we first convert each voter's rating vote into a comparison vote, then tally the votes into a total comparison vote, and then finally convert it to a rating vote via decycling. Unfortunately, since the start and the endpoints of the route remain the same as in the first case, this scheme fails due to the commutative nature of the diagram.

Fourth, we can truly circumvent the impossibility theorem by choosing a different starting point: run a comparison election and then proceed to the ratings as described above. In other words, a decycled comparison election is implemented by the following composition of homomorphisms: $$ \newcommand{\ra}[1]{\!\!\!\!\!\!\!\xrightarrow{\quad#1\quad}\!\!\!\!\!} \newcommand{\da}[1]{\left\downarrow{\scriptstyle#1}\vphantom{\displaystyle\int_0^1}\right.} \newcommand{\la}[1]{\!\!\!\!\!\!\!\xleftarrow{\quad#1\quad}\!\!\!\!\!} \newcommand{\ua}[1]{\left\uparrow{\scriptstyle#1}\vphantom{\displaystyle\int_0^1}\right.} % \begin{array}{ccccc} \text{Election:} & & &&\text{Outcome:} \\ {(C^1)^m} & \ra{\quad \Sigma\quad} & {C^1} &\ \ra{\quad D\quad} & {B^0}\\ & & & & \quad \quad \da{(\partial^0)^{-1}}\\ & & & & {C^0} \end{array} $$

Is decycling the answer? Let's examine $D\Sigma$.

It is a comparison tally and it satisfies Additivity, Symmetry I, and Symmetry II.

What about Diagonality? Do we have $D\Sigma\delta=k\operatorname{Id}$? Not unless $B^1=C^1$.

What about Positivity? Once again, not unless $B^1=C^1$.

Example. This is how decycling replaces the vote of $A>B$ with $A<B$:

Decomposition of comparison votes w reversal.png

$\square$

Algebraically, will a point with a positive first coordinate always have a projection with a positive first coordinate? Of course not: just consider the projection of the plane onto an inclined line (left):

There is, however, a monotonic relation (right) between these two numbers. This idea is put in the form of this simple algebraic lemma.

Lemma. Under an orthogonal projection, the dependence of any vector on itself is non-decreasing. In particular, the dependence on any coordinate on itself is non-decreasing.

In other words, an increase of a comparison vote on $A$ vs. $B$ will not cause a decrease of this vote after the decycling operator $D:C^1\to C^1$. Combined with what we know about the sum tally $\Sigma$, this implies the following useful property.

Theorem (Monotonicity). If a voter increases his comparison vote on $A$ over $B$, in the outcome of the decycled comparison election, $D\Sigma$, candidate $B$ will not improve his position relative to $A$.

Such a step, however, may change relative positions of other candidates. Let's take another look at the independence of irrelevant alternatives.

Example (election manipulation). We consider a simple comparison vote $P\in C^1$: $$P(AB)=1,\ P(BC)=-1,\ P(AC)=0.$$ It is a rating vote: $$B>A=C.$$ Suppose this vote came -- via the sum tally -- from the following comparison election: $$\begin{array}{c|ccccccc} &AB&BC&CA&\\ \hline X&1&0&0\\ Y&0&-1&0\\ \text{rest}&0&0&0\\ \hline P&1&-1&0\\ \end{array}$$ The winner is $B$...

Suppose the voters have changed their votes -- but not about $A$ vs. $B$: $$\begin{array}{c|ccccc} &AB&BC&CA&\\ \hline X&1&0&0\\ Y&0&-1&0\\ \text{rest}&0&5&4\\ \hline Q&1&4&4\\ \end{array}$$ Now, $Q$ is not a rating comparison vote. As we know, it is decomposed as follows: $$Q=(1,4,4)=(-2,1,1)+(3,3,3).$$ The outcome of the second election is then: $$D(Q)=(-2,1,1),$$ and the winner is $A$!

Predictably, when enough voters change their minds about $A$ vs. $C$ or $B$ vs. $C$, the outcome of $A$ vs. $B$ may change too. $\square$

It appears that $D\Sigma$ does not produce a fair election method...

Let's, nonetheless, consider how this method applies to rating of web-pages. First, we set up the votes:

  • if there is a link from page $A$ to page $B$, edge $AB$ is given a value of $-1$;
  • if there isn't, it's $0$. $\\$

The totality of these values is a comparison vote.

What makes the setting of interlinked websites different is the source and the nature of the votes. In a standard electoral system, there are voters and there are candidates and the former vote for the latter. On the web, there are only pages and they vote for each other. What's crucial, each page can only vote against itself!

This inability to increase your own standing is preserved under decycling due to the Monotonicity Theorem. An immediate consequence is that under the decycling scheme, unlike under PageRank,

  • adding outbound links to your site won't increase your ranking.

This approach can be used as a foundation of an “against-self electoral system”. In such a system, every voter is also a candidate but as a voter he has limited voting powers. Compare:

  • the standard system:
    • voter $X$: candidate $A$ $>$ candidate $B$;
  • the against-self system:
    • voter $X$: candidate $A$ $>$ candidate $X$. $\\$

By voting this way, voter $X$ says: “voter $A$ is a better choice than me to decide on this issue”. There are only two comparison votes for each pair of candidates -- by the candidates themselves.

Just as explained previously, with the circular patterns removed by decycling, this mode of voting creates

  • a flow towards better and better voters, or, which is the same thing,
  • a flow towards better and better candidates. $\\$

Finally, one can follow this flow to its end(s) to find the best candidate(s).