User:Homunq/SODA

Result criteria (absolute)

These are criteria that state that, if the set of ballots is a certain way, a certain candidate must or must not win.

• Majority criterion (MC)— Will a candidate always win who is ranked as the unique favorite by a majority of voters? This criterion comes in two versions:

1. Ranked majority criterion, in which an option which is merely preferred over the others by a majority must win. (Passing the ranked MC is denoted by "yes", because implies also passing the following:)

1. Rated majority criterion, in which only an option which is uniquely given a perfect rating by a majority must win. The ranked and rated MC are synonymous for ranked voting systems, but not for rated or graded ones. The ranked MC, but not the rated MC, is incompatible with the IIA criterion explained below.

SODA passes both. Proof is easy. Does not pass "woodall tied majority" but does with enough delegation... (useful conditions probably hard to specify)

• Mutual majority criterion (MMC)— Will a candidate always win who is among a group of candidates ranked above all others by a majority of voters? This also implies the Majority loser criterion—if a majority of voters prefers every other candidate over a given candidate, then does that candidate not win? Therefore, of the systems listed, all pass neither or both criteria, except for Borda, which passes Majority Loser while failing Mutual Majority.

Passes.

• Condorcet criterion— Will a candidate always win who beats every other candidate in pairwise comparisons? (This implies the majority criterion, above)

Passes majority voted Condorcet (with strong honest delegated equilibrium)

• Condorcet loser criterion (Cond. loser)— Will a candidate always win who is not the candidate who loses to every other candidate in pairwise comparisons?

Passes with same conditions as CC

Result criteria (relative)

These are criteria that state that, if a certain candidate wins in one circumstance, the same candidate must (or must not) win in a related circumstance.

• Independence of Smith-dominated alternatives (ISDA)— Does the outcome never change if a Smith-dominated candidate is added or removed (assuming votes regarding the other candidates are unchanged)? Candidate C is Smith-dominated if there is some other candidate A such that C is beaten by A and every candidate B that is not beaten by A etc. Note that although this criterion is classed here as nominee-relative, it has a strong absolute component in excluding Smith-dominated candidates from winning. In fact, it implies all of the absolute criteria above.

No.

• Independence of Irrelevant Alternatives (IIA)— Does the outcome never change if a non-winning candidate is added or removed (assuming votes regarding the other candidates are unchanged)?^[1] For instance, plurality rule fails IIA; adding a candidate X can cause the winner to change from W to Y even though Y receives no more votes than before.

No.

• Local Independence of Irrelevant Alternatives (LIIA)— Does the outcome never change if the alternative that would finish last is removed? (And could the alternative that finishes second fail to become the winner if the winner were removed?)

Yes (given the right definition of "finish last"; that is, delegates last and does not win).

• Independence of Clone Alternatives (Cloneproof)— Does the outcome never change if non-winning candidates similar to an existing candidate are added? There are three different phenomena which could cause a system to fail this criterion:

• Spoilers are candidates which decrease the chance of any of the similar or clone candidates winning, also known as a spoiler effect.
• Teams are sets of similar candidates whose mere presence helps the chances of any of them winning.
• Crowds are additional candidates who affect the outcome of an election without either helping or harming the chances of their factional group, but instead affecting another group.

No. Spoilers within an existing clone set (ie, in chicken dilemma). I believe there could be crowds too, but with the new version of SODA (fixed delegation order based on delegated votes, not approvals), maybe not.

• Monotonicity criterion (Monotone)— If candidate W wins for one set of ballots, will W still always win if those ballots change to rank W higher? (This also implies that you cannot cause a losing candidate to win by ranking him lower.)

I think so. God, I hope I can prove this.

• Consistency criterion (CC)— If candidate W wins for one set of ballots, will W still always win if those ballots change by adding another set of ballots where W also wins?

Almost surely not. But perhaps I can show that it holds for up to 3 candidates? No, not that either. Holds if delegation order is the same, certainly, but that's basically cheating.

• • Participation criterion (PC)— Is voting honestly always better than not voting at all? (This is grouped with the distinct but similar Consistency Criterion in the table below.^[2] )

No. But same footnote as MJ etc. Also, holds for single approvals, and for delegations with up to 3 candidates? Or even 4?

• Reversal symmetry (Reversal) —If individual preferences of each voter are inverted, does the original winner never win?

Umm.. I think so. Don't see an obvious proof though.

Ballot-counting criteria

These are criteria which relate to the process of counting votes and determining a winner.

• Polynomial time (Polytime)— Can the winner be calculated in a runtime that is polynomial in the number of candidates and linear in the number of voters?

Yes, but rational delegation might not be. But it's polytime in the number of candidates in the Smith set, which in practice is good enough.

• • Resolvable— Can the winner be calculated in almost all cases, without using any random processes such as flipping coins? That is, are exact ties, in which the winner could be one of two or more candidates, vanishingly rare in large elections?

Yes.

• Summability (Summable)— Can the winner be calculated by tallying ballots at each polling station separately and simply adding up the individual tallies? The amount of information necessary for such tallies is expressed as an order function of the number of candidates N. Slower-growing functions such as O(N) or O(N²) make for easier counting, while faster-growing functions such as O(N!) might make it harder to catch fraud by election administrators.

O(N)

Strategy criteria

These are criteria that relate to a voter's incentive to use certain forms of strategy. They could also be considered as relative result criteria; however, unlike the criteria in that section, these criteria are directly relevant to voters; the fact that a system passes these criteria can simplify the process of figuring out one's optimal strategic vote.

• Later-no-harm criterion and Later-no-help criterion— Can voters be sure that adding a later preference to a ballot will not harm or help any candidate already listed? ^[3]

LNHarm: no

LNHelp: I think so, but proof not immediately obvious.

• Favorite betrayal criterion (FBC) — Can voters be sure that they do not need to rank any other candidate above their favorite in order to obtain a result they prefer?^[4]

No. But yes if there are voted pairwise majorities (or, in strong equilibrium?, if there are votable pairwise majorities)

Note on terminology: A criterion is said to be "weaker" than another when it is passed by more voting systems. Frequently, this means that the conditions for the criterion to apply are stronger. For instance, the majority criterion (MC) is weaker than the multiple majority criterion (MMC), because it requires that a single candidate, rather than a group of any size, should win. That is, any system which passes the MMC also passes the MC, but not vice versa; while any required winner under the MC must win under the MMC, but not vice versa.