Pairwise Least Squares

Pairwise least squares is a description for a method that assigns a score to each candidate based on voters' pairwise preferences.

Overview

Least squares estimation is a technique from linear algebra that finds the closest solution to a system of equations.

A pairwise listing of preferences is the number of people who prefer a candidate to another.

Applying least squares to pairwise preferences produces a number of votes for each candidate. A difference between any two candidates votes can be found. The differences are a projection of the preferences. Any preference loops are not represented in these differences. The square distance between these differences and the preferences is minimized.

Math

Let ${\boldsymbol {A}}$ be the incidence matrix with a row for each preference and a column for each candidate.

Let ${\hat {\boldsymbol {x}}}$ be scores to be assigned to each candidate.

Let ${\boldsymbol {y}}$ be the number of voters with a preference.

The problem to solve is:

$\mathbf {A} {\hat {\boldsymbol {x}}}=\mathbf {y} .$

There are actually many solutions because the same score could be added to each candidate. So we set the score of the first candidate to 0 in order to solve for one solution.

$\mathbf {A_{0}} =\mathbf {A[:,1:]} .$

The solution is:

${\hat {\boldsymbol {x}}}=\left(\mathbf {A_{0}} ^{\operatorname {T} }\mathbf {A_{0}} \right)^{-1}\mathbf {A_{0}} ^{\operatorname {T} }\mathbf {y} .$

External Links

• MIT Linear Algebra - Lecture 12 - Graphs, Networks, Incidence Matrices
• MIT Linear Algebra - Lecture 16 - Projection Matrices and Least Squares