#voting theory

[vacuously-true]

"That's what people are concerned about, unless they're the ones doing it"

-A prof explaining gerrymandering

[vacuously-true]

Friendly reminder that

"Who I like best as a person," "who I think would make the best president," "who I think would have the best chance in the general election," and "who I should vote for in the primary," are all different questions and may all have different answers.

[vacuously-true]

Cool so what I'm learning is that the caucus system is an absolute nightmare as far as like any voting theory would indicate. Jesus Christ.

[tilde-he]

Generalization of the smith set?

Note: The generalization in this post seems fairly obvious and I assume has already been studied. I don’t remember seeing it described before, but I would guess it has been.

(skip to heading “the generalization part” if you are already familiar with the concept of a smith set and a dominating set in the context of voting mechanisms, and don’t want a refresher on the background)

Background:

The smith set is “the smallest non-empty set of candidates in a particular election such that each member defeats every candidate outside the set in a pairwise election”. Let w(x,y) be the proportion of the vote that x gets in a pairwise election against y. (w(x,y) isn’t a standard notation, I just picked a random letter. I don’t know what the standard letter to use for this is, if there is a standard letter to use.) For all x,y, w(y,x) = 1 - w(x,y) , i.e. w(y,x)+w(x,y)=1. Let C be the set of candidates. A subset X of C is called a dominating set if each element of X defeats each element of C\X in a pairwise election. i.e. a subset X of C is a dominating set if for all x in X, for all y in C\X , w(x,y) > 1/2 .

Let X and Y be dominating sets. Consider the intersection of X and Y, i.e. X \cap Y. Let x be an element of X \cap Y. Let t be an element of the complement of the intersection, i.e. of C\(X \cap Y). The complement of the intersection of X and Y is the union of the complements of X and Y, i.e. of (C \ X) \cup (C \ Y). Therefore, either t is in C\X, and therefore as x in X, w(x,t) > 1/2 , or t is in C\Y , and therefore as x in Y, w(x,t) > 1/2 . So, in any case, w(x,t) > 1/2 . So, for any x in X \cap Y and any t in C\(X \cap Y), w(x,t) > 1/2 . That is, when X and Y are dominating sets, the intersection of X and Y is also a dominating set. Therefore, the intersection of a finite set of dominating sets is also a dominating set. Suppose X and Y are both dominating sets, and are both non-empty. If the intersection of X and Y were empty, then each would be a subset of the complement of the other. But then, for x in X and y in Y, because x in X and X is a dominating set, and y in the complement of X, we would have w(x,y) > 1/2 , while at the same time, because Y is a dominating set, and y in Y, and x in the complement of Y, would have w(y,x) > 1/2 , and therefore w(x,y) + w(y,x) > (1/2) + (1/2) = 1, so w(x,y) + w(y,x) > 1 , which contradicts the fact that we always have w(x,y)+w(y,x)=1. So, for X and Y two non-empty dominating sets, their intersection is also non-empty, as well as being a dominating set.

Therefore, the intersection of a finite set of non-empty dominating sets is also a non-empty dominating set.

If C is finite, the set of subsets of C is also finite, and therefore the set of dominating sets is finite. C itself is always a dominating set, because its complement is empty, and therefore, vacuously, all elements of its complement lose a pairwise race against all elements of it. So, if C is finite and non-empty, the set of non-empty dominating sets is both finite and non-empty. If we take the intersection of all non-empty dominating sets, the result will be a non-empty dominating set which is a subset of all other non-empty dominating sets. i.e. it will be the smallest non-empty set of candidates such that each member defeats every candidate outside the set in a pairwise election, i.e. it will be the smith set. So, the smith set is the intersection of all non-empty dominating sets.

the generalization part:

For any p ≥ (1/2) , define a “p-dominating set” as: for a subset X of C, X is a p-dominating set if, for all x in X, and for all y in C\X , w(x,y) > p.

Note that a (1/2)-dominating set is the same thing as a dominating set. Note also that for any p > (1/2) , the condition that X is a p-dominating set is a stricter condition than that X is a dominating set. In general, for any p2 ≥ p1 ≥ (1/2) , (X is a p2-dominating set) implies (X is a p1-dominating set).

Note that the same argument as the one above (one of the ones under the “background” heading) that shows that the intersection of two dominating sets is also a dominating set, applies just as much to this case. Similarly, because for any p ≥ (1/2) , have that the sum of any two numbers which are both strictly greater than p is strictly greater than 1, and so the argument that the intersection of two non-empty dominating sets is non-empty and a dominating set, easily extends to show that the intersection of any two non-empty p-dominating sets is a non-empty p-dominating set. Also, the argument that C is always a dominating set extends to show that C is always a p-dominating set.

So, for any p ≥ (1/2) , if C is non-empty and finite, then the set of non-empty p-dominating sets is non-empty and finite, and so the intersection of all non-empty p-dominating sets is itself a non-empty p-dominating set, which is a subset of all non-empty p-dominating sets. Call this intersection the p-smith set.

A property of the p-smith set: For any p2 ≥ p1 ≥ (1/2) , the p1-smith set is a subset of the p2-smith set. (This is because the set of non-empty p2-dominating sets is a subset of the set of non-empty p1-dominating sets , and so the intersection of all non-empty p1-dominating sets is the intersection of all p2-dominating sets and also possibly some more sets, and is therefore a subset of the intersection of all p2-dominating sets.)

We can therefore generalize the smith-criterion for voting systems to get the weaker p-smith-criterion. Instead of requiring that the winner always be in the smith-set, as the smith-criterion requires, the p-smith-criterion instead requires that the winner always be in the p-smith set.

Some voting systems do not satisfy the smith criterion. For example, any system which satisfies the participation criterion (casting a ballot for one’s preference cannot increase the chance of one’s preference losing to a candidate one ranks strictly lower) , and has more than 3 candidates and more than 11 voters, can simultaneously satisfy the smith criterion.

So, I think a natural question to ask, could be, “For each p > (1/2), can a system be designed which satisfies the participation criterion, and also satisfies the p-smith-criterion?” . (For p=1 , the p-smith set, (i.e. the 1-smith set) is the smallest set of candidates that is unanimously preferred to all candidates outside the set. I’m fairly confident that the 1-smith-criterion is compatible with the participation criterion, and with basically any reasonable criterion, though that’s mostly based on intuition, not any real argument.)

Question: What is the smallest p such that the p-smith-criterion is consistent with the participation criterion (with any number of voters and any number of candidates)? Edit: Turns out “half-way monotonicity”, i.e. “completely reversing the order preference you express on your ballot compared to your true preferences cannot improve the outcome from your perspective, compared to if you voted your true preferences”, which is a weaker condition than the participation criterion, is also incompatible with the Condorcet criterion, and therefore incompatible with the smith-criterion. Therefore, Question: What is the smallest p such that the p-smith-criterion is consistent with the “half-way monotonicity” condition?

[privatedetectivesoffice-blog]

[griceslittlemaxim]

some of my notes for math

[sgreffenius]

The fallacy of subtractive vote counting

The fallacy of subtractive vote counting

You saw the subtraction fallacy a lot during the election season just past. The subtraction fallacy might be stated as follows: “A vote added to one column equals a vote subtracted from all other columns.” To take an example from the November 8 presidential poll: a vote in Trump’s column equals a vote subtracted from Clinton’s, Johnson’s, and Stein’s column. A vote’s negative weight, by this…

View On WordPress

[coolmathstuff]

Voting Systems

This year will have the first elections in which I’m able to vote, so I’ve been paying more attention to the political process than I have in the past. I'm going to talk a little bit about the mathematics of voting systems, but first I want to encourage everyone reading this, assuming they are eligible, to vote this year, and to share a few helpful links about voting in the US: When presidential primaries and caucuses will be held in each state How to register to vote and how to vote States with online voter registration and links to register online in these states (Some of these just make a form for you, which you will have to print and mail as well) Summary of all the US elections (not just presidential) happening in 2016 Now that that’s out of the way, let’s talk about something more mathematical: voting systems. I will only discuss a few in this post, but there are many more. 1. Plurality Most elections in the US, with the notable exception of the presidential election, use a simple plurality voting system. Every voter has one vote, and the candidate who gets the most votes wins. This seems logical, and it works well when there are only two candidates. However, when there are more than two, it can get complicated. Imagine 2 candidates are running for the same office, and 100 voters cast votes for them as follows: Candidate A: 45 Candidate B: 55 Now imagine the same election, but with a third candidate, Candidate C, running. Candidate C has similar opinions to Candidate B, and some voters who would have otherwise voted for Candidate B choose to vote for Candidate C. Candidate A: 45 Candidate B: 35 Candidate C: 20 Now Candidate A wins the race. This is called the spoiler effect, and it has often been an issue in US elections. The existence of the spoiler effect discourages voters from voting for third-party candidates. But it is possible to eliminate the spoiler effect?

2. Instant Runoff Voting/Single Transferable Vote You will hear both of these terms used, and they mean the same thing mathematically. The way an instant runoff election works is like this: 1. Voters fill in their ballots, ranking all the candidates according to preference. 2. Each candidate is given one vote for each voter who has ranked them first. 3. If a candidate has over 50% of the votes, that candidate wins. 4. If not, the candidate with the lowest number of votes is eliminated (some systems may eliminate multiple candidates to make the process go faster). 5. Every ballot which put the candidate that got eliminated first gets looked at again. Whoever the next highest eligible candidate is gets one vote. 6. Repeat steps 3-5 until there is a winner.

Under this system, voters can vote for candidates that don’t seem to have a strong chance of winning without having to worry about wasting their votes. The system is complicated, and to some, confusing, but aside from that, is there anything wrong with it? Unfortunately, yes. Let’s look at that group of people who support Candidate C, would be willing to accept Candidate B, and are strongly opposed to Candidate A. If they vote for Candidate C first and Candidate B second, then Candidate B’s chances of winning will not be harmed if Candidate C is eliminated. However, suppose Candidate C beats Candidate B.

Candidate A: 45 Candidate B: 25 Candidate C: 30 In this situation, Candidate B is eliminated, and the race is now between Candidate A and Candidate C. Now, unless 21 or more Candidate B supporters put Candidate C as their second choice, Candidate A will win. If Candidate C supporters had simply voted for Candidate B, Candidate B would have won, but instead, Candidate A wins. The spoiler effect has not been eliminated, although it has been reduced. Instant runoff voting may have many advantages over plurality voting, but it is not perfect.

3. Approval and Range Voting In range voting, every voter is allowed to rate every candidate on a scale, for example, from 0 to 100, and then each candidate receives a number of votes equal to the sum of the rating each candidate has given them. Approval voting is a special case of range voting, in which voters can either give candidates either a 1 (approve) or a 0 (do not approve). The two are very similar, and both solve a lot of the problems present in other systems. For instance, in approval and range voting, giving any one candidate a higher rating will never make it more likely that a different candidate wins. But these systems have their own problems. If two Candidates A and B are both perceived as the most likely to win, then people who prefer Candidate A over Candidate B might give B a lower rating than what they actually believe, and vice versa. If the two candidates are evenly matched, this could result in a different candidate winning. On the other hand, if most voters in this situation give Candidates A and B around the same rating, the election could be decided by a few voters who do rate one of the candidates significantly lower.

Voting in a way that does not match your true beliefs because you believe it is the best way to push the election in the direction you want is called “tactical voting,” and it has been present in every system we have discussed so far. The Gibbard-Satterthwaite theorem says that any voting system dealing with more than two candidates is susceptible to tactical voting, unless it has a dictator (a single voter who decides the election), has some candidates who cannot win, or uses our final method...

4. Random ballot Strangely enough, in some ways, the random ballot is fairer than any other voting system. This is how it works: every voter casts a vote for whichever candidate they like the best. Then, a random ballot is chosen, and the candidate on that ballot is the winner. The more people vote for a candidate, the better chance that candidate will have of winning. And if you’re trying to decide between two candidates, one whom you prefer and one whom you expect to be more popular, you can vote for the candidate you prefer, and the probability of either candidate winning remains the same. 

Aside from the obvious issues, there is the problem of how to actually execute the random decision. Any method runs the risk that the people in charge of executing it will cheat, since this is a situation in which few people are impartial. Physical methods would be very challenging in a large voting population, and electronic methods depend on effective random number generation, the logistics of which could be a whole other post. Random voting is an absurd idea which will most likely never be used in a significant election, and yet, it does get solve the problem of tactical voting. Is that worth it?