Voting

The setup

Consider an election in which there are candidates and voters. Each voter associates a cost with each candidate, and we want to elect a candidate such that the total cost imposed by that candidate upon all voters is minimized. How can we do this?

Well, if we know the exact cost table for all (voter, candidate) pairs, all is well; we just need to do some arithmetic.

Summing costs for each candidate across all voters, we determine that we should elect the third candidate because he minimizes total cost.

Losing information

However, what if we don’t know the exact costs each voter associates with each candidate? In practice, even the voters themselves often cannot quantify their exact cost profiles: instead, they are typically asked to rank the candidates from most to least favorite. Therefore, instead of full cardinal information, we now receive only ordinal information.

How can we decide which candidate to elect in this new scenario?

Before we proceed, some terminology: a voting mechanism is any algorithm that takes in ordinal rankings as input, then outputs which candidate should be elected. For instance, a simple mechanism in the 2-candidate () case illustrated above could be:

Elect whichever candidate is preferred by more voters. In case of a tie, pick an arbitrary one.

For instance, in the above illustration, two voters prefer the first candidate, and two voters prefer the second. This is a tie, so we arbitrarily elect the second candidate.

Distortion

Now, can we evaluate how good this mechanism is?

Well, in the above example, the optimal total cost was 10, but we picked a candidate whose total cost was 115; therefore, we’ve missed the optimal cost by a factor of 11.5. However, we can construct an even worse case:

We’re now off by a factor of…infinity???

Formally, the existence of this case means that the distortion of our mechanism is infinite, since there exists a construction of costs that causes our mechanism to incur cost worse than the optimal cost by a factor of .

Metric social choice

To prevent distortion from blowing up, we can try placing reasonable constraints on the underlying costs of each voter. The constraint we will consider today is the metric constraint, in which costs must be determined according to a metric embedding of voters and candidates.

In this illustration, the voters and candidate are placed along a single number line, and the costs equal the distances between each (voter, candidate) pair. For instance, the left voter associates 0 cost with the first candidate and 1 cost with the second candidate. On the other hand, the right voter associates cost with the first candidate and cost with the second candidate.

However, recall that we don’t know these exact distances: instead, we only know that one voter prefers candidate 1 to candidate 2, and the other prefers candidate 2 to candidate 1. Both candidates are thus symmetric, so WLOG assume our mechanism elects the second candidate. What is the resultant distortion?

Well, the first candidate induces a total cost of , while the second candidate induces a total cost of . Therefore, our distortion is .

Metric constraints

Before we move on, we should formally define what it means for an arrangement to be a valid metric embedding. Formally, a metric embedding is a function which returns the distance between points and , which must satisfy the following four conditions:

The first three are fairly intuitive, and the 4th condition is just the triangle inequality.

Note that this means our distance function is NOT constrained to only Euclidean geometry. In fact, it will be more convenient to visualize distances as a weighted graph, like so:

The distance between two points is then defined as the shortest path between them in this graph.

A basic upper bound for

The above counter-case above shows that the distortion of any deterministic mechanism must be at least . However, using the metric constraints, we can actually show there exists a mechanism whose distortion is at most , thereby proving that is the optimum distortion of any deterministic mechanism.

Some preliminary notes:

• Let and denote the fraction of voters that prefer candidates and , respectively. For instance, in our above case, we have .
• WLOG assume ; since our mechanism has no other information, it follows that we should then always elect candidate .
• Since we want to maximize distortion, we should then also configure our distances such that candidate 1 is optimal.

A helpful way to rewrite distortion here, henceforth denoted as , is as

where denotes the cost of electing candidate . Therefore, to maximize distortion, we want to minimize (the optimal cost) and maximize (the overhead created by our mechanism).

To minimize :

• Note that voters can be placed exactly on top of candidate , therefore contributing cost.
• However, the remaining voters must satisfy . Combining this with the triangle inequality which requires , we have that . Therefore, each of these voters contributes at least to .
• From here, it follows that the minimum value of is .

To maximize :

• The voters placed on top of candidate contribute , which can be shown by the triangle inequality to be the maximum.
• The remaining voters must satisfy , so the maximum value of they can contribute is .
• Therefore, the maximum value of is .

In other words, we have shown that no construction can be worse than the one we showed above, in which voters are placed on top of candidate , and voters are placed halfway, since this simultaneously maximizes the numerator and minimizes the denominator .

Plugging these values back into our distortion expression, we have

where the last inequality arises from the requirement that .

Some intuition

Consider the adversarial case we constructed without the metric constraint, in which voters who prefer candidate 1 associate a pathologically high cost with candidate 2. Because of the metric constraint, this means that candidate 1 must also be very far from candidate 2. Then, if the distance between them is , voters who prefer candidate 2 must associate cost at least with candidate .

In other words, the metric constraints ensure to some degree that the preferences of all voters are “equally weighted”, and that none are negligible in comparison to others.