[EM] Centrifugal Margins

[Joshua Boehme]

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
>