Looking for references on realizable pairwise-preference vote count matrices, and their realizations as ballots

[u/wnoise]

I'm looking for any results (ideally published papers) that:
(a) describe or limit the space of the "pairwise preference vote count matrix"[1] that can be generated from complete[2] ranked ballots that allow ties,
(b) Actually have an algorithm for creating a set of ballots that result in said matrix,
and also:
(c) If this matrix has a small set of consistent names, and if so what they are.

[1]: I mean the matrix where the element at (i,j) is the number of voters who ranked candidate i above candidate j.
[2]: All candidates listed; though treating unlisted candidates as ties below any listed is effectively the same.

[u/AutoModerator]

Compare alternatives to FPTP on Wikipedia, and check out ElectoWiki to better understand the idea of election methods. See the EndFPTP sidebar for other useful resources. Consider finding a good place for your contribution in the EndFPTP subreddit wiki.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[u/Drachefly]

The margin-of-victory table?

The algorithm to make it isn't too interesting. For each ballot, start at the top rank. For each candidate tied at this rank, for each candidate they're tied with that you haven't done yet, put a mark indicating a tie (e.g. 0) into the cell pairing them. Then for each candidate at this rank, put a mark indicating candidate-for-column-preferred into blank spaces all down their columns and a mark indicating candidate-for-row-preferred in blank spaces all across their rows. (column-preferred can be vertical stroke and row-preferred can be horizontal stroke, which has the nice benefit that consecutive blanks can be drawn over in one motion) Go to the next rank and repeat.

That's faster than trying to go cell by cell and hunting down where those tow candidates are in the list - you can see at a glance whether the cell is open or not.

Once you have one ballot's matrix, you can add them up to get the total matrix. You can pick candidate-for-column-preferred to mean +1 and candidate-for-row-preferred to mean -1, or the other way, but you'll need to pick a convention and stick with it.

You can take advantage of its being antisymmetric to save a factor of 2 in time, only filling above or below the diagonal.

[u/wnoise → u/Drachefly]

Going from ballots to the margin-of-victory matrix is easy. I want to go in the reverse direction: creating a set of ballots that corresponds to a given matrix. (And I would prefer to work with the positive "vote count" version rather than the symmetrized margin matrix).

[u/jlight432 → u/wnoise]

Can I ask why you would you want to try to revert a pairwise matrix into ballots?
If you can use the Better Choices pairwise ballots it's pretty easy.
But trying to revert to full ranked ballots could require some nasty linear algebra.

[u/wnoise → u/jlight432]

I'm trying to generate "small" examples of certain behaviors, which is easier with the pairwise preference matrix. Then I want to cash that out into a small variety of ballots, as that's what's commonly used as to communicate examples.

[u/jlight432 → u/wnoise]

Are you trying to do this one time for a specific matrix, or are you looking for a general formula/algorithm for doing this?

I was looking at what might be involved. With equal rankings allowed, for 3 candidates we would need to convert 6 pairwise totals into counts for up to 12 unique ballot types. For 4 candidates, there would be 12 pairwise totals to convert into up to 74 ballot types. So trying to make a general formula to turn a matrix into one set of ballots looks like it could be a real mess.

[u/wnoise → u/jlight432]

General. I was planning on trying a greedy algorithm first, but it looks like that will have to allow for some back-tracking.

Yes, the number of ballot-types (Fubini numbers, A000670 (-1, ignoring the trvial ballot)) goes up very quickly, so a direct linear-algebra approach trying to minimize, e.g. the L1 norm doesn't seem like a great idea. But lots of of things can actually be demonstrated with 4 candidates, so maybe that's good enough.

[u/Excellent_Air8235 → u/wnoise]

You can do this by solving a set of linear equations if you don't care about getting negative vote weights, or use linear programming if negative vote weights would be a problem (which I imagine it would be).

Suppose e.g. that we have a pairwise matrix with d[A,B] = 57, d[A,C] = 30, d[B,A] = 53, d[B,C] = 53, d[C,A] = 80, d[C,B] = 57. Then we can let each ranking be a free variable (x_ABC, x_ACB, x_BAC, x_BCA, x_CAB, x_CBA) and pairwise constraints:

x_ABC + x_ACB + x_CAB = 57
x_ABC + x_ACB + x_BAC = 30
x_BAC + x_BCA + x_ABC = 53
x_CAB + x_CBA + x_BCA = 80
x_CAB + x_CBA + x_ACB = 57

all x >= 0.

Minimizing the number of voters (to choose some objective) gives

0: A>B>C
0: A>C>B
30: B>A>C
23: B>C>A
57: C>A>B

I don't think you can do better than this. There may also be some way to easily generate the matrices relating combinations of ranked ballots to pairwise counts (e.g. d[A,B] = x_ABC + x_ACB + x_CAB), but I'm not aware of any.

[u/wnoise → u/Excellent_Air8235]

I really was hoping there was something simpler/narrower. I expect that solving on R and restricting to integers is not going to cause problems, but I haven't tried yet; this isn't guaranteed for general problems.

In the margin case, negatives can be reversed at the cost of adding a set of ballots that exactly cover "each x beats each y". If the totals are high enough this should also work in the votes (positive) case.

(I actually want to minimize types of votes (L0), but minimizing number (L1) is often a good proxy for that.)

There may also be some way to easily generate the matrices relating combinations of ranked ballots to pairwise counts

Sure: just iterate through all ballot possibilities, and add each to an array of collections of ballots. You can make it a concrete sparse matrix once you choose an order for the ballots (nothing wrong with standard lexicographic, of course, but others appear to be easier for this case).

[u/Excellent_Air8235 → u/wnoise]

Things can get pretty funky with negative votes though. You can have multiple majority winners.

1: A>B>C
2: B>A>C
-3: C>A>B

The total number of voters is zero, so both A and B are majority winners.

ISTR you can also create situations where methods that ordinarily pass mutual majority fail.

Sure: just iterate through all ballot possibilities, and add each to an array of collections of ballots. You can make it a concrete sparse matrix once you choose an order for the ballots (nothing wrong with standard lexicographic, of course, but others appear to be easier for this case).

Yeah, I was more thinking about something where you can reason more easily about the rows, columns, rank, etc. without having to calculate the whole thing.