Proofs of early rejection cases for Condorcet proposals - DA0-DA0/dao-contracts GitHub Wiki

Definitions:

• A Condorcet matrix M that represents a set of ranked choices of N given choices is an NxN matrix, where the value of a cell [m][n] = (the number of times m has been ranked over n) - (the number of times n has been ranked over m).

• A Condorcet Winner is the candidate, given a set of ranked choices of candidates, that would beat every other candidate in a head-to-head race. That means that given a pairwise comparison of every candidate to every other candidate, the candidate that is preferred in the majority of cases to each of the others is the Condorcet winner.

• A Condorcet winner in a Condorcet Matrix will therefore be the column C in M that has a positive value in every cell except for the cell which corresponds to itself.

• A Condorcet paradox (or a Condorcet cycle) is a situation wherein no candidate is majority-preferred to every other candidate in a pairwise comparison. In the Condorcet Matrix, this would appear as a matrix with no rows or columns that have all positive values.

• For a column col, let distance_from_positivity(col) = sum(1 + abs(v) for v in col if v <= 0). Let min_distance_from_positivity = min(distance_from_positivity(col) for col in M), and let MIN_COL be the column for which distance_from_positivity(MIN_COL) = min_distance_from_positivity.

• For a column col, let max_negative_magnitude(col) = max(abs(v) for v in col if v <= 0)).

• Let power_outstanding be the remaining voting power to be cast. Every unit of voting power corresponds to one ballot.

• When a vote is cast with voting power V, and its highest ranked choice is m, then V is added to every cell for the column of m excluding the cell for m itself. This is because for each of the N-1 choices besides m, there are now V more times that m has been ranked over that choice. Therefore, V*(N-1) is added in total to m's column.

It helps to visualize the following Condorcet Paradox when thinking through these proofs:

Choices: A, B, C

Ranked votes: 

ABC
BCA
CAB

Condorcet matrix:

	A	B	C
A	0	1	-1
B	-1	0	1
C	1	-1	0

Claims and Proofs:

Claim A: In a matrix with a Condorcet Paradox, there will be no Condorcet Winner found if min_distance_from_positivity > power_outstanding * (N-1).

Claim B: In a matrix with a Condorcet Paradox, there will be no Condorcet Winner found if for every column col such that distance_from_positivity(col) <= power_outstanding * (N-1), max_negative_magnitude(col) >= power_outstanding.

Proof of claim A:

Our premise is that there is a matrix in a Condorcet Paradox M such that min_distance_from_positivity > power_outstanding * (N-1).  

Assume that there is a way that you can create a Condorcet Winner in matrix M using the remaining voting power.

Let this Condorcet Winner be W, and its corresponding column in M be C, and let C' be C's state after it becomes the Condorcet Winner.

let X = distance_from_positivity(C).

If C' is the Condorcet Winner, then power_outstanding * (N-1) >= X.  

min_distance_from_positivity must be <= X by definition, so min_distance_from_positivity <= X <= power_outstanding * (N-1).

But this contradicts our premise that min_distance_from_positivity > power_outstanding * (N-1).

Therefore, if min_distance_from_positivity > power_outstanding * (N-1), then there can be no possible Condorcet Winner in M.

Proof of claim B:

Our premise is that there is a matrix in a Condorcet Paradox M such that for every column col such that distance_from_positivity(col) <= power_outstanding * (N-1), max_negative_magnitude(col) >= power_outstanding. 

Let C be a column in M such that distance_from_positivity(C) <= power_outstanding * (N-1) and max_negative_magnitude(C) >= power_outstanding.

Assume that C can be made a Condorcet Winner. Let C' be C's state after it becomes the Condorcet Winner.

Let Y = max_negative_magnitude(C), and z be the corresponding cell for which C[z] = Y.

Let p = C'[z] - C[z]. p must be > Y since C'[z] must be positive by the definition of Condorcet Winner.

p must be <= power_outstanding, since the most that C[z] could have been increased by is power_outstanding.

So this means power_outstanding >= p > Y.

But this contradicts our premise that for every column col such that distance_from_positivity(col) <= power_outstanding * (N-1), max_negative_magnitude(col) >= power_outstanding.

Therefore, if for every column col such that distance_from_positivity(col) <= power_outstanding * (N-1), max_negative_magnitude(col) >= power_outstanding, then there can be no possible Condorcet Winner in M.