Algorithmic Asset Voting

From Electowiki
Jump to navigation Jump to search

(Work in progress)

A flowchart explaining how Algorithmic Asset works.

Asset Voting can, depending on which relevant assumptions are made about how negotiators act, be turned into a Smith-efficient Condorcet method in the single-winner case, and a Condorcet PR method in the multiwinner case (akin to CPO-STV and Schulze STV). Its variants, Sequential Asset Voting and Bloc Asset Voting, can also be algorithmized.

Assumptions[edit | edit source]

Some of the assumptions are:

  • Voters submit ranked or rated ballots.
  • The negotiators strictly follow the preferences of those ballots and try to maximize those ballots' satisfaction with the outcome i.e. if a negotiator is asked to negotiate on behalf of a voter whose ballot was A>B>C, and the negotiations are at such a stage that the negotiator can use their assets to decide which of A, B, or C will win, then the negotiator must help elect A.
  • The candidates with the most votes at the end of the negotiations are sequentially elected until all seats are filled.
  • The negotiators have as much time as necessary to reach a final outcome or set of outcomes.
  • The negotiators move one negotiating step at a time (i.e. if some negotiators agree to support a candidate, they must first all give their votes to that candidate before any further negotiating actions occur)

Some optional assumptions are:

  • When a negotiator is indifferent between certain outcomes (i.e. because their voters equally ranked those outcomes), they use their assets to help pick the socially best of those outcomes. As an example, if the voters cast rated ballots

    49 A5 B4 3 A5 B5 48 B5

    then treat the 3 A=B votes as preferring B, because B has the most points, giving B 51 > A 49 votes, making B the winner even though more voters actually prefer A.
  • In the multiwinner case, when a voter submits a rated ballot, and their negotiator can choose between electing, say, the voter's first choice, or both of their second and third choices, the negotiator somehow uses the rated information to decide which outcome is preferable (i.e. they might add up the utilities for the voter in either outcome and pursue the higher-utility outcome.)
  • A resolution method is applied when there are multiple outcomes in the Smith Set, and the candidates' preferences can change in order to change the Smith Set in favor of maximizing their voters' satisfaction (though this might break the algorithm or make it fail to be Condorcet-efficient in certain scenarios). As a further possibility, the candidates might also be allowed to try to induce Condorcet cycles or otherwise grow the Smith Set in ways that allow them to then resolve the election in favor of their voters' satisfaction (though this also might break the algorithm).

Procedure[edit | edit source]

Do pairwise matchups between all possible outcomes. (To speed up computation, some matchups can be ignored if the outcome is certain. Also, some outcomes can be checked first if they're more likely than others).

When doing a matchup, transfer votes in such a way as to ensure a voter gets as many of their favorite candidates as possible. (If the voter submitted a rated ballot, optionally attempt to instead maximize their overall utility i.e. if electing their 1st choice is worth 9 utility points, and electing their 2nd and 3rd choice is 8+5= 13, prioritize electing the latter two).

If there isn't a stable winner in a pairwise matchup (the negotiators are never able to make one outcome beat the other without some negotiators making strategically rational moves that help the other outcome win), declare the matchup a tie.

Use a Smith-efficient Condorcet method to elect from the Smith Set of outcomes (or use any Condorcet cycle resolution method).

Example[edit | edit source]

An Algorithmic Asset 2-winner PR example.

3-winner election, Hagenbach-Bischoff quota 25:

26 A
34 C>B>D
6  B>D
8  D>B
5  D>S
21 S>D

It can immediately be observed that A and C have over a quota of 1st choices, so they will win. (D, S) form a Droop solid coalition of 26 votes, so one of them must win. Therefore, the only outcomes to compare are (A, C, D), and (A, C, S).

(A, C, D) vs. (A, C, S):

26   A
26.5 C
26.5 D
21   S

Here, 7.5 CBD votes and the 19 other votes that prefer D to S give their votes to D. A, C, and D are then the 3 candidates with the most votes, and since the voters who prefer S>D don't have enough votes to change the outcome, (A, C, D) win this matchup. Since we already know (A, C, D) can win all other matchups, (A, C, D) is the Condorcet winner and wins.

Another example:

If there are 51 voters who prefer Party A and 49 for Party B, then in a 5-winner election, the 49 B voters can always ensure two of their candidates are in the final winner set.

Chicken dilemma:

Number Ballots
34 A>B>C
25 B>A>C
40 C

C has the most 1st choices, so A>C preferring voters could shift their votes to A, at which point no voter can improve the winner. Note that if voters had shifted their votes to B to beat C first, then some special steps would need to be applied to elect the Condorcet winner A. [1]

Number Ballots
1 A
34 A>B>C
25 B>A>C
40 C


Explanation of how Asset Voting is, under certain assumptions, a Condorcet method (and how this enables it to be done as an algorithm)[edit | edit source]

Algorithmic Asset to elect a Condorcet winner.
Algorithmic Asset identifying the Smith Set.

In the single-winner case, if the negotiators are honest, strictly follow voter preferences, and have enough time to negotiate, then Asset becomes a Smith-efficient Condorcet method, and in the multiwinner case, resembles Condorcet PR methods such as CPO-STV and Schulze STV (these transformations can be observed by turning Asset Voting into an algorithm using various assumptions, as mentioned below). The reasoning for this can in part be linked to the fact that Asset is an iterative voting method (it is almost like an iterative version of FPTP; iterative voting methods are generally more Condorcet efficient than their non-iterative equivalents[2]) where the voters/negotiators are constantly updated on who is about to win if no change in votes occur (i.e. which set of candidates of a size equal to the number of seats to be filled have more votes committed to them than all other candidates so far), and they can, therefore, plan to defeat such candidates. Pairwise comparison is implicitly involved in this planning, as the negotiators must see if the candidates they prefer over those about to win can obtain more votes from all negotiators than those who are about to win.

Asset Voting can be done algorithmically on ranked or rated ballots when certain assumptions are applied, such as the ones mentioned above (here is a visualization of the algorithm). One main assumption is that every negotiator attempts to maximize their assigned voters' satisfaction with the outcome.

Lewis Carroll's own likely observations that Asset is intended to be Condorcet-efficient[edit | edit source]

Lewis Carroll is the first known inventor of Asset Voting. In a passage in an article[3] describing his thought process in developing Asset, Carroll appears to have noted that the ideal PR scheme would involve voters forming into sets of coalitions, and then, when enough voters prefer a different set of coalitions than the one that is currently formed, a different set of coalitions is formed, and this repeats until no more improvement is possible. He also notes that it is possible to, by looking at ranked ballots, figure out what sets of coalitions might occur if the voters were acting "rationally" (most likely meaning maximally strategically), and he even solves a few examples where such an approach yields different results from STV, though it is noted that at the time, the full computation for this process when looking at the ballots for a large-scale election would've been "indeterminate". This all appears to establish that Carroll was interested in finding a Condorcet equilibrium for the final set of winners, and saw Asset as the easiest way to do it, because he believed the candidates' preferences would be close enough to the voters' preferences to make the candidates' Condorcet equilibrium more Condorcet-efficient by voter preference standards than STV.

Notes[edit | edit source]

It could be possible for a voter to submit a ballot indicating partial preferences in certain pairwise matchups i.e. that they'd want to only give 0.2 votes to help Candidate A be in the winner set rather than candidate B, but 1 full vote to help Candidate A and/or B be in the winner set over Candidate C. So for example, if they voted with a rated ballot A10>B8, A10>C0 and B10>C0. See the "connections to cardinal methods" section of the Condorcet methods page for more information. Note that this may be possible even in the multiwinner case.

2-winner example:

11 A>B

5 B

10 C>B

11 D>E

5 E

10 F>E

Condorcet PR methods should probably pick (B, E) as the winner set, because both candidates in the set are the Condorcet winners within their respective Hare Quotas (the top 3 lines and bottom 3 lines), so if for example you tried to go with (A, E), the 10 totally unrepresented C voters could give B their votes, giving B 10+5=15 votes total to beat A's 11. But if say all voters indicate that B and E are only 10% better than less-preferred candidates, this is no longer the case (B and E actually become Condorcet losers in their quotas, because they get only 5 + 1 or 1.1 votes in their pairwise matchups against their quota competitors, who have 10 or 11 votes) and then (A, D) looks like a better Condorcet PR winner set, since C and F, the only viable competitors left, simply have fewer voters preferring them than A and D.[4]

Note that a voter could even be allowed to give less than a full vote to any candidate, even their 1st choice, in all pairwise matchups.

The use of the KP transform on rated ballots and then converting those Approval ballots to ranked ballots allows voters to submit, for example, a rated ballot A5 B4 C3, and have it treated either as 0.2 votes A>B, 0.2 votes B>C, and 0.4 votes A>C (score for preferred candidate minus score for less preferred candidate divided by max score yields the number of votes in each matchup) or 1 vote A>B, 1 vote B>C, 1 vote A>C.

Note that in a pairwise match-up between two winner sets, a third winner set can actually emerge as the winner. This is because some voters may prefer some candidates from one set and some from the other. For example, in a matchup between a set with only the majority's preferred candidates and another set with mostly candidates with almost no support, but one candidate whom a quota prefer, the final winner will actually be a new winner set where most of the candidates are the majority's preferred candidates and the final candidate is the quota's preferred candidate. Example:

5-winner election:

51: Party A candidates

20: Party B candidates

20: Party C

9: split between random candidates, call them D, E, F, G

Winner set (5 A’s) vs. (B, D, E, F, G)

I’d argue that the winning winner set of the pairwise matchup here is actually (4 A’s, B). The B voters have enough votes to force B to be one of the top 5 candidates in a iterated cumulative voting election or an Asset negotiation, and no voters can force an improvement from their perspective from there.

Edit: To be clear no improvement based on the candidates in either set is possible. If we take (4 A’s, B) and compare it to all remaining candidates, it’s clear the C voters can force 1 C to be among the top 5 as well, and that would be the equilibrium outcome, so the final Condorcet PR winner set is 3-1-1 A-B-C.[5]

The multi-winner Smith Set and Smith-efficient cycle resolution[edit | edit source]

8 D>A>B>C

7 B>C>A>D

5 C>B>A>D

8 D2>A2>B2>C2

7 B2>C2>A2>D2

5 C2>B2>A2>D2

Initializing an algorithmic Asset negotiation, D and D2 have the most votes (1st choices). But within each Hare Quota, ABC and A2 B2 C2 are in a Condorcet cycle. Therefore, once a few negotiating moves (pairwise comparisons) have been done, D and D2 won’t be in any of the 2-winner winner sets the negotiators cycle through. For example, if the negotiators are currently supporting (B, B2), and D and D2 attempt to gather enough support to win, 12 ballots prefer B to 8 for D or D2, and the same for B2. So the Smith Set here is all of the outcomes in the Condorcet cycles, which is a proper subset of all possible 2-winner sets.[1]

Some reasoning for why this method is most likely Droop-proportional and even Hagenbach-Bischoff-proportional: mathematically, if any candidate has an HB quota, no matter how the votes are arranged among other candidates, the quota-preferred candidates can guarantee they are one of or are tied to be one of the (number of winners) top candidates. Examples: with 1 winner, HB quota is 1/2 (half), and even if a non-quota candidate has all of the other 1/2 of the votes, the quota-preferred candidate is at least tied for being the top candidate. With 2 winners, HB quota is 1/3rd, and even if two non-quota candidates split the remaining 2/3rd of the votes perfectly evenly, the quota-preferred candidate is still tied to be one of the top two. And so on. It would appear that so long as you always elect from the Smith Set of winner sets, HB-proportionality is guaranteed, because winner sets that pass HB ought to always beat winner sets that don't. Consider that Minimax, a Condorcet method, fails Smith and happens to also fail mutual majority[6], and in the single-winner case mutual majority is equivalent to Droop proportionality.

It's possible to use another optimal or sequential PR method on the Smith Set winner sets to decide the final winner set. With optimal PR methods, this can be done by just picking the best winner set in the Smith Set, while with sequential PR methods, one way is to at times eliminate all candidates from contention whose election would guaranteeably result in a non-Smith winner set being the final result. As an example, suppose Sequentially Spent Score is used to determine the winner among the Smith Set winner sets in the following 2-winner example using scored ballots, with the max score being 10 and the rankings inferred from the scores:

8 D:10>A:3>B:2>C:1

7 B:10>C:9>A:8>D:5

5 C:10>B:9>A:8>D:5

8 D2:10>A2:3>B2:2>C2:1

7 B2:10>C2:9>A2:8>D2:5

5 C2:10>B2:9>A2:8>D2:5

Scores for each candidate are D and D2 140, A/A2 120, B/B2 131, and C/C2 121

D and D2 would be the winners in regular SSS, SMV, and RRV because they each have the highest scores in their respective Hare Quotas. But the Smith Set here is all winner sets with at least 1 candidate from (A, B, C) and at least 1 candidate from (A2, B2, C2) since 12 voters prefer each of them over 8 voters for D and D2 each, which means D and D2 must not win in order for the winner set to satisfy the Smith criterion (this can be discovered using a combinatorics calculator such as https://www.mathsisfun.com/combinatorics/combinations-permutations-calculator.html). Therefore, one way of applying SSS here would be to run SSS but first eliminate D and D2 to ensure they can't win, making one of B or B2 tie for the first seat. WLOG supposing B won, then A and C must be eliminated, because if one of them were to win the second seat, then it'd be impossible for 1 of (A2, B2, C2) to win, violating the Smith criterion. Then B2 wins the second seat, making the final winner set (B, B2). In the single-winner case, using cardinal PR methods to select from the Smith Set is equivalent to using Smith//Approval or Smith//Score. If a method such as STV is used to decide the winning set among the Smith winner sets, then it may even be necessary at times to prevent the elimination of a candidate who, if eliminated, would guarantee that a non-Smith winner set would be the final result.

Resisting Favorite Betrayal and burying[edit | edit source]

In some cases, it's possible to use the concept of AAV to reduce Favorite Betrayal incentive. For example:

48 A>B

5 B

47 C

There's a Condorcet cycle here between all 3 candidates. But note that if the 47 A>B voters vote B>A, then B is the Condorcet winner. Notably, there is no way for any other voter to improve the outcome for themselves (the A>B preferring voters can't make A CW and neither can the C>B preferring voters), so B is a strategically stable winner. Using AAV along with a cycle resolution method that would elect C would automatically elect B because of this. This step might be usable solely to shrink the Smith Set at times rather than find a single strategic CW. But note that with a Condorcet cycle of

1 A>B>C

1 B>C>A

1 C>A>B

there is no strategically stable winner, because if any voter attempts Favorite Betrayal to make their preferred candidate the CW, then 2 other voters have incentive to alter their votes to make someone they prefer the CW, and so on.

Semi-solid coalitions[edit | edit source]

A semi-solid coalition (a possibly incorrect idea based off of solid coalitions) is a group of voters who prefer a set of candidates over all others, but some voters in the group may prefer other candidates over the candidates the group prefers over all others. So, for example,

20 A

5 B>A

would be a semi-solid coalition of size 25 for {A, B}. A solid coalition would also technically be a semi-solid coalition, so any voting method that always elects proportionally from semi-solid coalitions should pass PSC.

It may be possible to make AAV always elect proportionally from Droop semi-solid coalitions. If so, then this may greatly speed up computation of the result, as only winner sets that satisfy all semi-solid coalitions need be considered; discovering semi-solid coalitions can be done by checking ballots and observing which candidates are ranked higher than others and by which voters. [7] Semi-solid coalitions may overlap.

It's important to keep in mind that when discussing coalitions in the context of voter preferences as recorded on ballots, the loosest possible definition would be groups of voters who mutually prefer at least one candidate above at least one other candidate, though there may be disagreement on other candidates. Thus, even if the only thing two groups of voters have in common is that they mutually rank some candidate last, they are still a coalition in the sense that they mutually prefer all other candidates to that last-ranked candidate.

References[edit | edit source]

  1. https://www.reddit.com/r/EndFPTP/comments/ewgjss/comment/fg2fd63
  2. Grandi, Umberto; Loreggia, Andrea; Rossi, Francesca; Venable, Kristen Brent; Walsh, Toby (2013). Perny, Patrice; Pirlot, Marc; Tsoukiàs, Alexis (eds.). "Restricted Manipulation in Iterative Voting: Condorcet Efficiency and Borda Score". Algorithmic Decision Theory. Lecture Notes in Computer Science. Springer Berlin Heidelberg: 181–192. doi:10.1007/978-3-642-41575-3_14. ISBN 978-3-642-41575-3.
  3. Lewis Carroll and the Theory of Games, Duncan Black (starting at the sentence "Suppose we have a multimember constituency..." on Page 4 and ending at the sentence "In general, however, an operational answer to the problem is again not feasible." on Page 5)
  4. https://www.reddit.com/r/EndFPTP/comments/ep0tq1/using_weak_preferences_in_condorcet_pr_methods/
  5. https://forum.electionscience.org/t/monroe-pr-doesnt-work-properly/528/9?u=assetvotingadvocacy
  6. https://en.m.wikipedia.org/wiki/Mutual_majority_criterion#Minimax
  7. https://www.removeddit.com/r/EndFPTP/comments/euiup2/a_new_pr_concept_of_semisolid_coalitions/