Centrifugal Margins
Hello everyone. I've lurked in the archives off and on for a while. I finally decided to join since I've been playing around with a method and I'm at a point where outside feedback/criticism could help. Also, someone might have already described this in some paper I don't know about.
I'm calling it centrifugal margins for now, and it stochastically chooses an ordering based on ordinal ballots. (Since single-outcome methods can be contentious, assume multiple outcomes wouldn't make sense in the particular context or we're satisfying some external constraint.) Centrifugal margins generally requires ballot-level detail, but sometimes the head to head margins suffice.
The reason for the name is that it tries to maximize winning comparisons' margins and minimize them for losing ones. Majority voting with 2 candidates is the prototype: a candidate with >50% of the votes wins 100% of the time. Although cycles can prevent us from reaching 100%, the method tries to push non-ties away from the tie point. Ties remain perfectly balanced, like a pencil on its tip.
Let E be the set of non-losing edges over the ballots B. Centrifugal margins looks for new ballots B' that leximax (the margins of E over B') - (the margins of E over B). Note that E is determined solely by the actual ballots. For simple elections this suffices. Otherwise, we do the same for 3-candidate subgraphs after leximaxing the edges, then 4-candidate subgraphs, etc. The final ballots B' give the distribution.
The actual calculation resembles the nucleolus in game theory (a big inspiration) and has similar pitfalls. It involves iterated linear programming problems and using the duals to lock constraints.
Centrifugal margins satisfies Smith, and orderings with nonzero weight should have successive Smith sets in order, similar to ranked pairs. I think it's possibly cloneproof for ballot-level clones. Every ordering can have nonzero weight when all candidates tie, so worst-case complexity for n candidates is at least n!
Notably, centrifugal margins fails the blank ballot criterion. I think that's defensible, though it's probably a discussion for another time.
I'll leave it there for now to keep this brief, but questions are welcome! No promises that I have answers yet, though.
On 11/26/23 23:31, Joshua Boehme wrote:
Hello everyone. I've lurked in the archives off and on for a while. I
finally decided to join since I've been playing around with a method and
I'm at a point where outside feedback/criticism could help. Also,
someone might have already described this in some paper I don't know about.
I'm calling it centrifugal margins for now, and it stochastically
chooses an ordering based on ordinal ballots. (Since single-outcome
methods can be contentious, assume multiple outcomes wouldn't make sense
in the particular context or we're satisfying some external constraint.)
Centrifugal margins generally requires ballot-level detail, but
sometimes the head to head margins suffice.
The reason for the name is that it tries to maximize winning
comparisons' margins and minimize them for losing ones. Majority voting
with 2 candidates is the prototype: a candidate with >50% of the votes
wins 100% of the time. Although cycles can prevent us from reaching
100%, the method tries to push non-ties away from the tie point. Ties
remain perfectly balanced, like a pencil on its tip.
Let E be the set of non-losing edges over the ballots B. Centrifugal
margins looks for new ballots B' that leximax (the margins of E over B')
- (the margins of E over B). Note that E is determined solely by the
actual ballots. For simple elections this suffices. Otherwise, we do the
same for 3-candidate subgraphs after leximaxing the edges, then
4-candidate subgraphs, etc. The final ballots B' give the distribution.
The actual calculation resembles the nucleolus in game theory (a big
inspiration) and has similar pitfalls. It involves iterated linear
programming problems and using the duals to lock constraints.
I'm not quite sure what you mean. Could you give a simple example, say
where the first step suffices so we don't have to get into linear
optimization nitty-gritty?
-km
Sure! Fortunately, 3-cycles are simple enough to evaluate directly
First, a quick side note about a simplification I'll be using. Suppose we have orderings X and Y such that Y satisfies every non-losing edge that X does for an election, plus at least one additional edge. For example, in an A>B>C>A cycle ACB satisfies AB but ABC satisfies AB plus BC. We can consider ordering Y to dominate ordering X. The leximax solution can never allocate weight to a dominated ordering -- otherwise, we can strengthen at least one edge without weakening any others by shifting X's weight to Y. I'm going to silently ignore any dominated orderings for a given election.
Consider:
2 A>B>C
3 B>C>A
3 C>A>B
Head to head comparisons:
A over B 62.5% to 37.5%
B over C 62.5% to 37.5%
C over A 75% to 25%
We want a solution that maximizes the minimum of AB-0.625, BC-0.625, and CA-0.75. It turns out to be the ballots we already have, since the total proportional margins in a 3-cycle can't exceed 2 (no ordering can satisfy more than 2 edges out of the three). All the "excesses" are zero. If we try shifting the weights around in any way to increase an edge's strength, we will cause at least one other edge's excess to go negative and thus end up worse off in the leximax sense than the all zero solution we already have.
Thus our solution is 25% ABC, 37.5% BCA, 37.5% CAB
Now let's add 992 blank (all-tied) ballots. The margins are the same in terms of vote counts (2, 2, and 4 votes). However, the proportions are different:
A over B 50.1% to 49.9%
B over C 50.1% to 49.9%
C over A 50.2% to 49.8%
Now, since the three margins add up to less than 2, we are going to end up with a solution that differs from the underlying ballots. It turns out to be 33.27% ABC, 33.37% BCA, 33.37% CAB. These give AB and BC a 66.63% weight (16.53% excess for each) and CA a 66.73% weight (also 16.53% excess). We're back up to that maximum total across all three edges of 2, so the only way to strengthen one edge is to weaken another. Thus, this is the leximax solution in this second case. In a 3-cycle, what we end up doing is taking any slack between the actual margins and that upper bound of 2, splitting it up three ways, and dishing it out evenly to the three edges.
Note that adding blank ballots has changed the solution by flattening it closer to a 1/3, 1/3, 1/3 tie. Given the circumstances, I think this is reasonable. In the first election, we see stark contrasts. The ballots are actually a minimal set for the pairwise margins so there's no "slack" in the results. In the second election, literally 99+% of the electorate is indifferent between the three candidates, suggesting they're very similar.
Hopefully those examples help!
On 12/1/23 08:41, Kristofer Munsterhjelm wrote:
On 11/26/23 23:31, Joshua Boehme wrote:
Hello everyone. I've lurked in the archives off and on for a while. I finally decided to join since I've been playing around with a method and I'm at a point where outside feedback/criticism could help. Also, someone might have already described this in some paper I don't know about.
I'm calling it centrifugal margins for now, and it stochastically chooses an ordering based on ordinal ballots. (Since single-outcome methods can be contentious, assume multiple outcomes wouldn't make sense in the particular context or we're satisfying some external constraint.) Centrifugal margins generally requires ballot-level detail, but sometimes the head to head margins suffice.
The reason for the name is that it tries to maximize winning comparisons' margins and minimize them for losing ones. Majority voting with 2 candidates is the prototype: a candidate with >50% of the votes wins 100% of the time. Although cycles can prevent us from reaching 100%, the method tries to push non-ties away from the tie point. Ties remain perfectly balanced, like a pencil on its tip.
Let E be the set of non-losing edges over the ballots B. Centrifugal margins looks for new ballots B' that leximax (the margins of E over B') - (the margins of E over B). Note that E is determined solely by the actual ballots. For simple elections this suffices. Otherwise, we do the same for 3-candidate subgraphs after leximaxing the edges, then 4-candidate subgraphs, etc. The final ballots B' give the distribution.
The actual calculation resembles the nucleolus in game theory (a big inspiration) and has similar pitfalls. It involves iterated linear programming problems and using the duals to lock constraints.
I'm not quite sure what you mean. Could you give a simple example, say where the first step suffices so we don't have to get into linear optimization nitty-gritty?
-km
Here are some additional tidbits about the method...
When we use examples with minimal sets of ballots, it's not unusual for the centrifugal margin solution to come out the same as random ballot. However, here's a quick example to show that 100% of the weight can end up on orderings that don't appear on any ballots:
1 B>A>C>D
1 A>C>B>D
1 A>B>D>C
The solution is 100% A>B>C>D. This puts all the non-losing edges at 100%, so no other solution can possibly beat it (every excess is at its absolute maximum).
The approach I'm using for the higher-order steps follows two rules.
-
A k-tuple is non-losing if it has at least 1/k! strength on the actual ballots. For an edge, that's 1/2, exactly as we'd expect
-
Resolve the edges first, then the 3-tuples, then the 4-tuples...
The reason for those specific rules is that every variant I've tested that modified either/both of them failed to be cloneproof, and typically it was relatively easy to find a counterexample. With those two rules, I have yet to find any failures, though that doesn't mean it's cloneproof for sure
Here's another set of examples that blew my mind when I saw the results. Consider an election where every candidate ties head to head. Centrifugal margins handles some straightforward scenarios exactly as we'd intuitively expect.
If all four candidates are clones (A=B=C=D) then the solution is an equal 25% toss-up between the four.
If there are two equal factions, A > B=C=D and vice versa, then it splits 50% for A and 1/6 for each of B, C, and D
If the electorate is equally split between A, B, and C=D (i.e., 1/6 for each of the six distinct orderings), then it's 1/3 A, 1/3 B, 1/6 C, 1/6 D.
Random ballot can do that too, but it's not Condorcet or Smith. Maximal lottery would allow each of those respective solutions, but it also allows literally every other possible distribution in each case.
On 11/26/23 17:31, Joshua Boehme wrote:
Hello everyone. I've lurked in the archives off and on for a while. I finally decided to join since I've been playing around with a method and I'm at a point where outside feedback/criticism could help. Also, someone might have already described this in some paper I don't know about.
I'm calling it centrifugal margins for now, and it stochastically chooses an ordering based on ordinal ballots. (Since single-outcome methods can be contentious, assume multiple outcomes wouldn't make sense in the particular context or we're satisfying some external constraint.) Centrifugal margins generally requires ballot-level detail, but sometimes the head to head margins suffice.
The reason for the name is that it tries to maximize winning comparisons' margins and minimize them for losing ones. Majority voting with 2 candidates is the prototype: a candidate with >50% of the votes wins 100% of the time. Although cycles can prevent us from reaching 100%, the method tries to push non-ties away from the tie point. Ties remain perfectly balanced, like a pencil on its tip.
Let E be the set of non-losing edges over the ballots B. Centrifugal margins looks for new ballots B' that leximax (the margins of E over B') - (the margins of E over B). Note that E is determined solely by the actual ballots. For simple elections this suffices. Otherwise, we do the same for 3-candidate subgraphs after leximaxing the edges, then 4-candidate subgraphs, etc. The final ballots B' give the distribution.
The actual calculation resembles the nucleolus in game theory (a big inspiration) and has similar pitfalls. It involves iterated linear programming problems and using the duals to lock constraints.
Centrifugal margins satisfies Smith, and orderings with nonzero weight should have successive Smith sets in order, similar to ranked pairs. I think it's possibly cloneproof for ballot-level clones. Every ordering can have nonzero weight when all candidates tie, so worst-case complexity for n candidates is at least n!
Notably, centrifugal margins fails the blank ballot criterion. I think that's defensible, though it's probably a discussion for another time.
I'll leave it there for now to keep this brief, but questions are welcome! No promises that I have answers yet, though.