Approval Sorted Margins

From electowiki

Approval Sorted Margins is a voting system developed by Forest Simmons that selects a single winner using votes that express preferences, combined with an explicit approval cutoff. Approval Sorted Margins creates a sorted list of winners. It is also known as "Marginal Ranked Approval Voting" (MRAV).

If there is a candidate who is preferred over the other candidates, when compared in turn with each of the others, Approval Sorted Margins guarantees that that candidate will win. Because of this property, Approval Sorted Margins is (by definition) a Condorcet method. If there is no such candidate, Approval Sorted Margins initializes a ranking in descending order of approval, then reverses out-of-order pairs with the least difference in approval until all pairs are in order. One could consider this a form of "middle-out" sorting.

There are two heuristics to implement Approval Sorted Margins: Sorted Margins (as stated above), and Marginal Ranked Approval Voting.

Preliminary assumptions

How you vote:

  • A voter can rank all candidates and give more than one candidate the same rank. Equivalently, one can rate all candidates and give more than one candidate the same rating. Then the candidate ranking may be inferred from the rates.
  • For purpose of illustrating the method, we will use a 6-slot rating ballot with scores 0 through 5 (for example, zero through five stars), as in STAR voting or Majority judgment.
  • Rating a candidate 3 or above is considered approved (therefore ratings of zero, one or two are not approved), and giving one candidate a higher rate than another indicates that in a two-candidate race between the two, the voter would cast a vote for the higher rated candidate over the other.
  • The default rating (or score, a term we will use interchangeably) for an unrated candidate is zero.
  • A ballot will be considered invalid unless at least one candidate is rated higher than at least one other candidate. It is possible to approve all candidates or not approve all candidates.

Tabulating ballots

  • Ballots are tabulated as in other Condorcet methods, into a Virtual Round Robin pairwise array. In such an array, the value A[X,Y] is the number of ballots giving a higher rating to candidate X than to candidate Y.
  • Additionally, we also tabulate total approval for each candidate, resulting in a value of T[X] for each candidate X, with T[X] being the number of ballots that give an approved rating of 3 or more to candidate X. For convenience, we can store T[X] into the pairwise array location A[X,X], which would otherwise be unused.

Sorted Margins heuristic

Our goal is to rank candidates in a descending order such that each candidate pairwise defeats the next lower candidate. The first candidate in the resulting ordering is the winner. If a Condorcet Winner exists they will be the first candidate in the order, and if a Condorcet Loser exists, they will be the last candidate in the order.

Approval Sorted Margins

As stated above, our goal is to create a ranking in descending order, in which every sequential pair of candidates Xi and Xi+1 is in order pairwise. That is, candidate Xi is not beaten by candidate Xi+1

  • Initialize a ranking of all candidates in descending order of approval. That is, for any sequential pair of candidates X and Y in the initial ranking, T[X] >= T[Y].
  • While any candidate Y is defeated by the candidate X following it in the list (that is, A[X,Y] > A[Y,X]),
    • Find the X and Y of this type that has the least difference in approval (that is, difference D = T[Y] - T[X] is minimal), and modify the list by swapping the order of X and Y.

Notes on method

  • Before each swap, the higher alternative X will have greater approval than that of lower alternative Y, so the difference D in question will always be positive.
  • Why use the smallest absolute approval difference to decide which pairwise defeat to accept next?
    • Because if the approval difference is small, then the pairwise over-ride of the approval order does the least violence to that order. This reconciles the approval order with the pairwise defeats while keeping the strongest approval information intact.
  • When the sorting process is finished, the resulting ordering of the alternatives has this symmetry: if all of the ballots are reversed, then the final order will be reversed.
    • A sort that works from the top down or bottom up, like Bubble or Sink, will not enjoy this kind of symmetry. In other words, this is a middle-out sort.

Approval Sorted Margins has the following Monotonicity property:

  • If alternative A moves up relative to some other alternative, either pairwise or in approval, while none of the other alternatives move up or down relative to each other, then alternative A will either move up or remain in the same position in the final ordering.

By the symmetry mentioned above, we also have:

  • If alternative A moves down relative to some other alternative, either pairwise or in approval, while none of the other alternatives move down or up relative to each other, then alternative A will either move down or remain in the same position in the final ordering.

This method, like any approval seeded pairwise swap sorted method, is also clone independent. This is because (true) clones are seeded near each other by approval, and any alternative outside of a clone set will either pairwise defeat all of the members of the clone set or none of them. In other words, if it gets past one of them, it will make it past all of them, so that the clones will be together in the final order.

Marginal Ranked Approval Voting heuristic

When implemented using Marginal Ranked Approval Voting, the method only finds a winner. A full ranking can be obtained, as in other Condorcet methods, by re-running the steps with the previous winner removed. MRAV can be considered a refinement of Ranked Approval Voting, also known as Definitive Majority Choice (DMC).

The same Preliminary Assumptions and Tabulation as above are implemented.

MRAV Definitions

  • Strong defeat: Pairwise defeat by higher-approved candidate
  • Strong losers: Set of all strongly defeated candidates
  • Provisional set: Set of non-strongly-defeated candidates
    • Each provisional winner defeats all higher-approved members of the set. This is Forest Simmons' "P" set.
  • Clear upward defeat: Y has a clear upward defeat over X when lower-approved candidate Y pairwise defeats higher-approved candidate X and also pairwise defeats every other candidate with lower approval than X and higher approval than Y.
  • Marginal defeat: Pairwise defeat of provisional candidate X by strong loser Y under these conditions:
    • Y has a clear upward defeat over X.
      • If Y is strongly defeated by a candidate with lower approval than X, X is not marginally defeated by Y.
    • There is a candidate Z with greater approval than X who strongly defeats Y.
      • If no such Z exists, X is not marginally defeated by Y.
    • Approval(Y) - Approval(X) > Approval(X) - Approval(Z)
      • This means that Y's approval-margin defeat strength over X is more positive than X's over Z.
      • Note that both sides of the inequality are negative.
      • The inequality can be arranged to Approval(X) < (Approval(Z) + Approval(Y))/2; that is, X's approval is less than the average approval of Y and Z.
      • Another rearrangement of the inequality is:
        • Approval(X) - Approval(Y) < Approval(Z) - Approval(X)
      • Which means that X's approval is closer to the approval of the lower-approved candidate Y (who has a clear upward defeat of X) than to the higher approved candidate Z (who defeats Y).
  • Marginal losers: Set of all marginally defeated candidates
  • Strong set: set of candidates neither strongly nor marginally defeated

MRAV Procedure

  • Find the Strong Set.
  • Then there is a unique candidate in the strong set who is not defeated by any other members of the strong set. That candidate wins the election.

Note that by construction, the MRAV winner is the least-approved member of the strong set, and defeats all higher-approved candidates (whether in the strong set or not).

The philosophical motivation for removing marginally defeated candidates from consideration is that their approval "lift" is smaller than the "drag" of being defeated by lower-ranked candidates, and so they are dragged down.

The MRAV winner will differ from the DMC winner only when the DMC winner is marginally defeated. This can occur only when

  • There is a cyclic ambiguity in the pairwise preferences
  • The DMC winner is defeated by a strongly defeated candidate Y
  • The DMC's lift from defeating a candidate Z who defeats Y isn't large enough to overcome the drag of Y's clear upward defeat of X.

The Approval winner and the highest-approved member of the Smith set are always members of the strong set.

Example

Here's a set of preferences taken from Rob LeGrand's online voting calculator:

The ranked ballots: 

 98: Abby >  Cora >  Erin >> Dave > Brad
 64: Brad >  Abby >  Erin >> Cora > Dave
 12: Brad >  Abby >  Erin >> Dave > Cora
 98: Brad >  Erin >  Abby >> Cora > Dave
 13: Brad >  Erin >  Abby >> Dave > Cora
125: Brad >  Erin >> Dave >  Abby > Cora
124: Cora >  Abby >  Erin >> Dave > Brad
 76: Cora >  Erin >  Abby >> Dave > Brad
 21: Dave >  Abby >> Brad >  Erin > Cora
 30: Dave >  Brad >>  Abby >  Erin > Cora
 98: Dave >  Brad >  Erin >> Cora > Abby
139: Dave >  Cora >  Abby >> Brad > Erin
 23: Dave >  Cora >> Brad >  Abby > Erin

In ratings Comma-separated variable format, on a scale of 0 to 5, with scores 3 and above approved, this is equivalent to 

weight,Abby,Brad,Cora,Dave,Erin
98,5,0,4,1,3
64,4,5,1,0,3
12,4,5,0,1,3
98,3,5,1,0,4
13,3,5,0,1,4
125,1,5,0,2,4
124,4,0,5,1,3
76,3,0,5,1,4
21,4,2,0,5,1
30,2,4,0,5,1
98,0,4,1,5,3
139,3,1,4,5,0
23,1,2,4,5,0


The pairwise matrix, with the victorious and approval scores highlighted:

against
AbbyBradCoraDaveErin
for Abby 645 458 461 485 511
Brad 463 440 461 312 623
Cora 460 460 460 460 460
Dave 436 609 461 311 311
Erin 410 298 461 610 708

The candidates in descending order of approval are Erin, Abby, Cora, Brad, Dave.

After reordering the pairwise matrix, it looks like this:

against
Erin Abby Cora Brad Dave
for Erin 708 410 461 298 610
Abby 511 645 461 458 485
Cora 460 460 460 460 460
Brad 623 463 461 440 312
Dave 311 436 461 609 311

Calculating Example using Approval Sorted Margins

To find the winner using approval sorted margins, we start with the approval-seeded ordering:

Erin(708) >* Abby(645) > Cora(460) >* Brad(440) >* Dave(311)
  • There are 3 out-of-order pairs, Erin < Abby with an approval margin of 63; Cora < Brad with an approval margin of 20; and Brad < Dave with an approval margin of 129.
  • Cora < Brad has the smallest margin, so we swap those candidates to get
Erin(708) >* Abby(645) > Brad(440) > Cora(460) >* Dave(311)
  • There are two out of order pairs, Erin < Abby with 63 and Cora < Dave with 149. Erin < Abby has the smaller approval margin, so we swap them to get
Abby(645) > Erin(708) >* Brad(440) > Cora(460) >* Dave(311)
  • There is only one out-of-order pair, Cora < Dave, so we swap those candidates to get:
Abby(645) > Erin(708) >* Brad(440) >* Dave(311) > Cora(460)
  • There are two out-of-order pairs: Erin < Brad, with an approval margin of 268; and Brad < Dave, with an approval margin of 129, so we swap Brad and Dave to get:
Abby(645) > Erin(708) > Dave(311) > Brad(440) > Cora(460)

Notice that both Abby and Erin lose to Brad, but they are defended from Brad because Dave (who loses to Erin) was able to sift upward over Brad before he could defeat Erin.

Notice also that Condorcet loser Cora ends up last in the ordering, demonstrating symmetry.

Calculating Example using Marginal Ranked Approval Voting

  • We start at the lower right diagonal entry in the permuted pairwise array, and start moving upward and leftward along the diagonal.
  • We're looking for a candidate who has a solid row of victories to the left of the diagonal.
  • Brad is the first such candidate encountered. Under DMC, Brad would be the winner.
  • Starting at Brad's approval score in the Brad>Brad cell, we start looking down the 4th column to see if any lower-approved candidates defeat Brad.
  • We see a defeating score of 609 in the Dave>Brad cell.
  • Dave has a clear upward defeat over Brad, since there are no other candidates with approval scores between Brad and Dave.
  • From the Dave>Brad cell, we move left along Dave's row until we find a losing score against a candidate with higher approval than Brad.
  • The least-approved candidate who defeats Dave is Abby.
  • Approval(Brad) - Approval(Dave) = 99. Approval(Abby) - Approval(Brad) = 235.
  • Brad is therefore marginally defeated by Dave and is a marginal loser.
  • Starting at Brad's diagonal Brad>Brad approval score, we continue up the diagonal, looking for another candidate with a solid row of victories to the left of the diagonal.
  • Abby is the next such candidate encountered.
  • Looking down the 2nd column from Abby's approval score in Abby>Abby, the only loss is to Brad, an already-eliminated marginal loser. Note that Abby's Abby>Dave>Brad beatpath to Brad is stronger than Brad's Brad>Abby beatpath, using approval margins as the defeat strength.
  • By quick inspection, we see that the only remaining strong candidate is Erin.
  • The strong set contains candidates Erin and Abby.
  • Abby is the least-approved strong candidate and defeats Erin directly. So Abby is the MRAV winner.

Satisfied Criteria

Approval Sorted Margins satisfies the following criteria:

  1. Mutual majority criterion
  2. Monotonicity criterion
  3. Pareto criterion
  4. Condorcet criterion
  5. Smith criterion (a.k.a. Generalized Condorcet criterion)
  6. local independence from irrelevant alternatives
  7. Plurality criterion
  8. the winner is always chosen from the Immune set
  9. Chicken dilemma criterion (incompatible with Minimal Defense criterion)
  10. Strategy-Free criterion
  11. Generalized Strategy-Free criterion
  12. Strong Defensive Strategy criterion
  13. Weak Defensive Strategy criterion
  14. Summability criterion
  15. Independence of clones
  16. Neutrality of Spoiled Ballots

Approval Sorted Margins violates the following criteria:

  1. Participation criterion
  2. Consistency criterion
  3. invulnerability to compromising
  4. invulnerability to burying (but has higher resistance than Beatpath)
  5. Favorite Betrayal criterion
  6. Later-no-harm criterion

(TODO: check and find examples)

Score Sorted Margins variation

Instead of using an explicit approval cutoff, one can apply the Sorted Margins procedure to an initial seed ordering based on total score sum.

With sufficiently large range, e.g., zero to five or zero to 10, Score Sorted Margins usually yields the same winner as Approval Sorted Margins with a an appproval cutoff of Floor(MAXSCORE / 2).

Formally summarized, as in Approval Sorted Margins, the result of Score Sorted Margins is a ranking in descending order, in which every sequential pair of candidates Xi and Xi+1 is in order pairwise. That is, candidate Xi is undefeated by candidate Xi+1

  • Initialize a ranking of all candidates in descending order of total score sum. That is, for any sequential pair of candidates X and Y in the initial ranking, T[X] >= T[Y].
  • While any candidate Y is defeated by the candidate X following it in the list (that is, A[X,Y] > A[Y,X]),
    • Find the X and Y of this type that has the least difference in total score sum (that is, difference D = T[Y] - T[X] is minimal), and modify the list by swapping the order of X and Y.

References

[1] GitHub python code that compares Approval Sorted Margins to other Condorcet methods with explicit approval cutoff. See also ssmpr.py, a command-line python script to run Score Sorted Margins as a Hare-quota-based score reweighted voting method.

Retrieved from "https://electowiki.org/wiki/Approval_Sorted_Margins?oldid=16170"