[EM] (not totally successful) attempt to summarize MDDA, DMC, ICA

[Warren Smith]

Three ranked-ballot plus approval type voting methods, all invented by Kevin Venzke,
but also refined and analysed by others on Electorama, including Forrest Simmons,
Mike Ossipoff, Jobst Heitzig, and (lately) Warren D. Smith.  This file attempts to
summarize info about them...

The DMDDA (and WMDDA) VOTING METHODS
---------------------------------------

MDDA has been much discussed on EM. Its full name is: 
Majority Defeat  Disqualification//Approval.
DMMDA which we describe here is "deluxe" MDDA.
MDDA was invented by Kevin Venzke in June 2005.

Here's DMDDA's definition:
0. Votes are preference-rank-orderings of the candidates, AND 
each vote also includes an "approval threshhold" where all candidates
ranked at or above it are "approved" by that voter.  Rankings can include both > and =
relationships, e.g. A>B=C>D=E>F=G.

1. A candidate is "disqualified" if another candidate is ranked over him/her 
by a majority of the voters.
   (Unless that rule would disqualify all the candidates, in which case no 
one is disqualified.  Warning: be careful - "A over B by a majority" means
over 50% of voters say A>B.  It does NOT mean, more voters say A>B than A<B.
The two are different becasue of the possibility of saying A=B.) 

2. The winner is the most-approved un-disqualified candidate.
[end of DMDDA definition]

Undeluxe MDDA is similar except there is no explicit approval and truncated ballots
are allowed (ranked candidates considered approved).  I consider MDDA often
unacceptable in many situations because it will generically lead to ties
(with substantial probability).  Ossipoff replies that that will not
happen because it will be vanishingly 
rare for two or more undisqualified candidatess to be ranked on exactly the 
same number of ballots.
I counter that I believe there likely are (or will be) a substantial subclass of 
public elections in which zero ballots are truncated (in fact in most of Australia 
truncation is forbidden by law).

I shall, in all the MDDA- and DMC- discussion below, forbid ballot truncation.

Here is the definition of a related (to DMDDA) voting method devided by Warren D Smith,
(actually originally due to a misunderstanding of DMMDA, but I'll take it:)
call it WMDDA:
1. A candidate is "disqualified" if not in the "Smithmaj set"
The "Smithmaj set" is the candidates S such that each candidate in S is 
ranked over each candidate not in S, by a majority.  [Different Smith - not me.]
Warning: again we need to be careful: 50% of voters say A>B for each A in S and each B not in S.

2. The winner is the most-approved un-disqualified candidate.
[end of WMDDA definition]

Virtues of DMDDA and WMDDA:

FBC compliance ("favorite betrayal")
means that no one ever has any strategic incentive to vote someone else 
over his/her favorite, i.e. there always exists a strategically-optimal vote
rating that voter's favorite top or coequal-top.

(Neither Schulze's method nor DMC, meet FBC.  Approval & Range voting meet FBC,
and so does range voting based on averaging after outlier-discarding.)

SFC compliance:
If no one falsifies a preference, and if a majority prefer X to Y and vote 
sincerely, then Y can't win. 

Schulze's method and (D)MDDA meet SFC. DMC and range do not meet SFC.

SDSC compliance means that if a majority of the voters prefer X to Y, then 
they have a way of ensuring that Y won't win, without reversing a preference 
or failing to vote their genuine preferences among all the candidates whom 
they vote over other candidates.

Schulze's method and MDDA and Range Voting (and Approval) all meet SDSC.

PROOFS of above 3 DMDDA claims (by Venzke) with WMDDA add-on proofs by WD Smith:
* satisfies SDSC because if a majority prefer X to Y, and don't approve Y,
then Y will have a majority-strength defeat. If not all candidates have such
defeats, then Y can't win. If all candidates have such defeats, then Y still
can't win, because X has greater approval than Y.
WDSmith adds: WMMDA also satisfies SDSC because of the same proof with this addition:
Y is either not in the Smithmaj set (in which case Y cannot win) or is, in which case
X and Y will both be in the Smithmaj set.
In that latter case Y cannot win because X has greater approval than Y.

* satisfies SFC because if no majority prefers anyone to X, then X will
not be disqualified. If X has a majority-strength win over Y, then Y will
be disqualified, so that Y can't win.
WDSmith adds: WMMDA also satisfies SFC because of the same proof.

* satisfies FBC because if X wins, and a faction has ranked Y insincerely
low, then if this faction raises X and Y to the first position, the winner
will then be either X or Y. This is because X and Y can only lose defeats in
this way, and other candidates can only gain them. Also, X and Y's
approval can only increase.
  NOTE: this FBC proof only works if the "ranking" is allowed to include EQUALITIES not
  just ">" relations, e.g. A>B=C=D>E=F>G=H.
WDSmith adds: WMMDA also satisfies FBC because of the same proof.

More properties of DMDDA and WMDDA:
Fairly simply defined, though not as simple as range voting.

DMDDA seems plainly monotonic in both senses (ranking and approval thresh) simultaneously.

IT IS NOT TRUE THAT it elects a Condorcet Winner if one exists, although
it would be true if "=" were disallowed in rankings.  Note that the subcase
where  "=" is disallowed is actually of considerable importance, since with honest 
non-ignorant voters (assuming generic real utility values) "=" will never occur
in any vote.

IT IS NOT TRUE THAT it refuses to elect a Condorcet loser, although
it would be true if "=" were disallowed in rankings.

It is generically untied.

IT IS NOT TRUE THAT it is Clone-immune, although
it would be true if "=" were disallowed in rankings.
If candidate A wins, it is possible that when A is replaced by a set of candidates in 
a cycle, the winner won't be in this set.

It is "summable" i.e. precincts can only send in "subtotals" to central tabulators
and that suffices to compute the results (there is a subtotal for each
candidate-pair and another approval-count for each candidate singleton). (Unlike IRV.)

As we saw DMDDA and WMDDA satisfy FBC, SFC, and SDSC.

Those things were all good.  Now for some bad properties:

It is not doable on dumb-plurality-totaling voting machines, unlike range voting.
(For example, no way such a machine could check ballot-validity, i.e. acyclicity.)

It does NOT satisfy subdistrict consistency, that is, if district 1 elects winner W
and so does disjoint district 2, that does not imply that the combined winner is W.

It does NOT satisfy incentive to participate, in the sense that you can be better
off by "not showing up" to vote, because your honest vote can actually hurt you.

It fails "add top", i.e. adding votes all ranking A top, can harm A.
Venzke clarifies: MMDA fails Mono-add-top because adding A-top votes could cause a lower-ranked
candidate to lose a majority-strength loss, so that this candidate becomes the only
one not disqualified.

Now this does not technically count as an FBC failure, because I daresay there
exists some way to rank A top and dishonestly order the remaining candidates,
which still leaves A the winner.   However, in practice, it perhaps might have some 
vaguely similar effects to FBC failure.  

Incidentally, Deluxe MDDA is probably even worse than un-deluxe ranked-ballot methods
with respect to add-top failure, no-show paradoxes, and the like, because you can
use the approval counts quite easily to set up bad scenarios where the new
voter creates (unfortunately for him) a Condorcet winner, who then wins regardless of how
approved (or not) he is.
By "even worse" I mean, such failures are more common, or at least are easier to devise.

Finally, consider what I call the "DH3 scenario" 
   http://math.temple.edu/~wds/crv/DH3.html .
This is a horribly-common and horribly-severe problem that Borda and all Condorcet methods
based on full-ranking-ballots suffer from in the presence of strategic voters.  
But Deluxe MDDA might be able to avoid it because it is not just a 
ranked-ballot method - there are also those approval threshholds.  Let's see.
The situation is there are 3 main rival candidates A,B,C with comparable 
support, and a "dark horse" D whom all feel is inferior and has "no chance."
The pathology is the A-supporters strategically rank A>D>B&C
and so on (although they honestly feel  A>B&C>D), resulting in D winning.
With Deluxe MDDA, they presumably still will act that way, BUT only approving
the top one and disapproving the bottom three.  In that case D is the Condorcet
winner and wins despite zero approval.  So it appears Deluxe MDDA still suffers
from the horribly-common and horribly-severe DH3 pathology.  

This DH3 failure is a very bad
thing and would severely increase its Bayesian Regret.
 
CLARIFICATION:  I claimed WMDDA and DMDDA "fail" DH3
   http://math.temple.edu/~wds/crv/DH3.html .
However, at the time I failed to appreciate that these methods permit equality rankings.
Then the A-supporters could strategically rank A>B=C=D instead of honestly A>B=C>D
(and approve A only).  Result with that voter behavior would be good: C would win,
not D.  If voters rank A>D>B,C however, then DH3 test is failed.  This latter is
more strategically sensible so I still conclude DH3 is failed.

Venzke:
I'm not a fan of an explicit approval cutoff for MDDA, since it makes burial
strategy risk-free unless your opponents also use burial strategy.

WDSmith: I do not understand this, too much jargon is used for my poor mind.
("burial strategy"? "risk free"?)
I'm not saying it is wrong, I'm just saying let's have some explicit examples so I know
what we are talking about.


---------------------------------------------

THE DMC VOTING METHOD:
0. Votes are preference-rank-orderings of the candidates, AND 
each vote also includes an "approval threshhold" where all candidates
ranked at or above it are "approved" by that voter.  Rankings can include both > and =
relationships, e.g. A>B=C>D=E>F=G.

1. The winner is the unique "acceptable" candidate which defeats
pairwise each other acceptable candidate.
A candidate is "acceptable" if s/he is not pairwise defeated by any
more approved candidate.
[End of DMC defn]

Equivalent (somewhat more algorithmic) definition:
Successively remove the least approved
candidate until there is a Condorcet Winner (=until some candidate
pairwise defeats all of the remaining candidates, i.e. until there is a 
pairwise-undefeated candidate if we csan ignore ties).
[end of equiv defn]

Other algorithms have also been suggested.

DMC is "summable" i.e. precincts can only send in "subtotals" to central tabulators
and that suffices to compute the results (there is a subtotal for each
candidate-pair and another approval-count for each candidate singleton). (Unlike IRV.)

*If a majority of voters agree X is best, they can arrange for X to win.
*If a Condorcet winner exists, he is the DMC winner.
*If there is a majority of voters for which it is true that they all rank a set of candidates
above all others, then one of these candidates must win.

Fairly simply defined, though not as simple as range voting.

DMC like all approval&ranking hybrid methods,
allows to distinguish important from minor preferences. 

But this is more true of Range voting.

DMC has Immunity from second place complaints. Unlike in MinMax and 
Beatpath, the DMC winner always pairwise-defeats the candidate which would win
if the winner were not present. 

(Also true of range provided all pairwise defeats are assessed using range voting also
and the same range votes.)

Smith-efficiency: The DMC winner
always has a beatpath to each other candidate...

DMC defeats other methods. In every situation, the DMC 
winner is either identical to or pairwise-defeats the winner of each of the 
following methods: Approval Voting, Condorcet//Approval, 
Smith//Approval, DFC, TAWS.

WDSmith: I consider this criterion be artificial.  No matter what ranked ballot method you
have (X) I con construct a new one Y so the Ywinner always is same as or beats the Xwinner
pairwise.  In particular I can make X=DMC to get Y=a method that pairwise beats DMC...
This fact suggests to me that this criterion is meaningless...
Heitzig counters he considers it more natural in this particular case...

DMC winner always defeats or is more approved than any other 
candidate (unlike in Beatpath).

Strange winners are seldom. Unlike in Beatpath, the least approved
candidate cannot win in DMC unless she defeats all other candidates.

Robustness against "noise" candidates.. cloneproof...
(also true of range).

DMC also can be extended to allow constructing a complete ordering. If necessary, one can 
also assign final ranks to all candidates such that the k-th ranked 
candidate is the DMC winner when all k-1 candidates above her are 
removed from the race.   
WDSmith: This claim can be made about any voting method whatever so it does
not impress me much.  Heitzig counters that DMC gives this 
same order in other natural ways too.

Monotonicity. Unlike IRV, DMC is monotonic, that is, reinforcing
the DMC winner on some ballots cannot turn her into a loser.
DMC obeys both of the following TWO MONONITICITY PROPERTIES:
  M1:  interchange order of two neighboring candidates in your rank-order vote ==>
     (A>B becomes B>A) cannot decrease B's chance of winning, cannot increase A's.
  M2:  minimally change your vote so now approve of A ==> cannot decrease A's chance of winning.

WMDDA and DMDDA also obey both kinds of monotonicity.

"DMC" is a better name.  It doesn't matter if the D stands for
Definitive, Definite, or Democratic, "D Majority Choice" is a good sell.

Looking through the EM archives, Kevin Venzke finds that this is the history of DMC:

Sep 1, 2003: Venzke: suggested it as an alternative to Smith//Approval.
http://listserver.dreamhost.com/pipermail/election-methods-electorama.com/2003-September/010799.html

Nov 4, 2004: V suggested it as a rule to be used in conjunction with a method
I came up with to more easily hand-count three-slot ballots.
http://listserver.dreamhost.com/pipermail/election-methods-electorama.com/2004-November/014115.html

Jobst Heitzig criticized this method because in a three-candidate cycle, the approval
winner is not necessarily the winner. Also, when you rank A>B and approve both,
this can contribute to the strength of the reverse defeat B>A. Jobst criticized
that this would make it difficult to convince people to vote.
http://listserver.dreamhost.com/pipermail/election-methods-electorama.com/2004-November/014127.html

Mar 5, 2005: Russ Paielli brought the method up again as being a good public 
proposal. He referred to my 2003 post.
http://listserver.dreamhost.com/pipermail/election-methods-electorama.com/2005-March/014955.html
http://listserver.dreamhost.com/pipermail/election-methods-electorama.com/2005-March/015066.html

by Mar 17: The name "DMC" was suggested by Forest, and generally accepted.
http://listserver.dreamhost.com/pipermail/election-methods-electorama.com/2005-March/015181.html

DMC elects a Condorcet Winner if one exists.

DMC refuses to elect a Condorcet loser.

DMC is generically untied.

DMC is Clone-immune.

DMC Fails FBC and fails SFC.

DMC is not doable on dumb-plurality-totaling voting machines, unlike range voting.
(For example, no way such a machine could check ballot-validity, i.e. acyclicity.)

It does NOT satisfy subdistrict consistency, that is, if district 1 elects winner W
and so does disjoint district 2, that does not imply that the combined winner is W.

It does NOT satisfy incentive to participate, in the sense that you can be better
off by "not showing up" to vote, because your honest vote can actually hurt you.

It fails "add top", i.e. adding votes all ranking A top, can harm A.

All of the last three failures happen automatically by theorem for essentially any
Condorcet method, and DMC is just a Condorcet method if all voters approve
or disapprove all candidates (or anyway if all approval counts are tied) enabling
you to re-use the same counterexample elections to show them.
Incidentally, DMC is probably even worse than un-deluxe ranked-ballot methods
with respect to add-top failure, no-show paradoxes, and the like, because you can
use the approval counts quite easily to set up bad scenarios where the new
voter creates (unfortunately for him) a Condorcet winner, who then wins regardless of how
approved (or not) he is.
By "even worse" I mean, such failures are more common, or at least are easier to devise.

Finally, consider what I call the "DH3 scenario" 
   http://math.temple.edu/~wds/crv/DH3.html .
This is a horribly-common and horribly-severe problem that Borda and all Condorcet methods
based on full-ranking-ballots suffer from in the presence of strategic voters.  
But DMC might be able to avoid it because it is not just a 
ranked-ballot method - there are also those approval threshholds.  Let's see.
The situation is there are 3 main rival candidates A,B,C with comparable 
support, and a "dark horse" D whom all feel is inferior and has "no chance."
The pathology is the A-supporters strategically rank A>D>B&C
and so on (although they honestly feel  A>B&C>D), resulting in D winning.
With DMC, they presumably still will act that way, BUT only approving
the top one and disapproving the bottom three.  In that case D is the Condorcet
winner and wins despite zero approval.  So it appears DMC still suffers
from the horribly-common and horribly-severe DH3 pathology.  

----------------------------------------------------------------------

THE ICA VOTING METHOD  (Venzke May 2005)
"improved Condorcet Approval" method does not suffer from favorite
betrayal incentive. 

ICA:
1. The voter submits a ranked ballot, with equal-ranking and truncation permitted.
2. A voter implicitly approves every candidate whom he explicitly ranks.
3. Let v[a,b] signify the number of voters ranking candidate a above candidate b, 
 and let t[a,b] signify the number of voters ranking a and b equally at the top of
 the ranking (possibly tied with other candidates).  (t stands for "tied at the top".)
4. Define a set S of candidates, which contains every candidate x for whom there is no 
 other candidate y such that v[x,y]+t[x,y] < v[y,x].
5. If S is empty, then let S contain all the candidates.
6. Elect the candidate in S with the greatest approval.
[end of ICA defn]

In other words:
* every candidate A is disqualified who pairwise loses to some other candidate B, 
 and would still lose to B even when the voters supporting both equally as first preferences 
 are counted in favor of A. 
* If everyone is disqualified, then no one is. 
* Then the most approved candidate who isn't disqualified is elected.

ICA satisfies the favorite betrayal criterion FBC.

POSSIBLE VARIANT (VICA):
Redefine t[x,y] to be the
number of voters ranking x equal to y and explicitly voting for ("approving") both.

NOTES:
Instead of looking first for a candidate with only pairwise wins (the Condorcet winner),
ICA selects as finalists every candidate with no pairwise losses.

Venzke does not like ICA with explicit approval threshholds, for some reason he did not say.
Venzke: Its main shortcoming relative to DMC is that Venzke does not
recommend an explicitly-placed approval cutoff under ICA.
[WDsmith: I would like explicit examples to help me understand Venzke's reasons for this.]

WDSmith: I regard ICA as often unacceptable due to its lack of an explicit approval cutoff
or due to its need for ballot truncation, precisely because I believe there will
be a substantial subclass of public elections without any truncated ballots - in which
case ICA would often yield a tie.

Hence ICA can fail to satisfy the Condorcet criterion.  Example:
It is possible that the ICA winner could lose to another candidate, 
due to voters tying both candidates at the top, and the Condorcet winner having lower approval.
Here is an example:
8 A>B
7 A=B
5 B
The Condorcet winner is A, but ICA elects B, the Condorcet loser.

More properties of ICA:
Fairly simply defined, though not as simple as range voting, DMC, or MDDA.

Monotonic with respect to adjacent interchanges: A>B to B>A cannot make it
less likely for B to win.

It is generically untied.

IT IS NOT TRUE THAT it is Clone-immune, although
it would be true if "=" were disallowed in rankings.
If candidate A wins, it is possible that when A is replaced by a set of candidates in 
a cycle, the winner won't be in this set.

It is "summable" i.e. precincts can only send in "subtotals" to central tabulators
and that suffices to compute the results (there is a subtotal for each
candidate-pair and another approval-count for each candidate singleton
and another for each t[pair]). (Unlike IRV.)

Obeys FBC.

Satisfies SDSC.

Satisfies SFC.

ICA is not doable on dumb-plurality-totaling voting machines, unlike range voting.
(For example, no way such a machine could check ballot-validity, i.e. acyclicity.)

It does NOT satisfy subdistrict consistency, that is, if district 1 elects winner W
and so does disjoint district 2, that does not imply that the combined winner is W.

WDSmith: I have not checked these two:
incentive to participate?
 "add top"?

ICA fails DH3.

======
wds