Norman Petry and I (Ossipoff) recommended CSSD, but Schwartz Woodall is a better voting system for Debian
Hi--
My name is Michael Ossipoff. I and Norman Petry, some years ago,
recommended, to Debian, a voting system called Cloneproof Schwartz
Sequential Dropping (CSSD).. That voting system is also sometimes
referred to as "Beatpath", because of equivalent definition in terms
of beatpath strengths. And it's sometimes referred to as "Schulze",
because Markus Schulze was the first to propose both of the
abovementioned equivalent procedures.
At the time when we proposed CSSD here, we considered it the best. Now
I feel that, as regards freedom from strategy concerns, there are
better methods. I'm writing now because I feel that it's my
responsibility to tell about those better methods, because I was one
of those who advocated CSSD here.
First, let me say that CSSD has much good to say for it. As you
probably know, Condorcet, in the late 18th century, suggested that,
when there is no one candidate who pairwise-beats each of the other
candidates (such a candidate is now called a "Condorcet winner", or
"CW"), and there is, instead, a top-cycle, then the winner should be
the candidate whose greatest pairwise defeat is the least. That could
be expressed in terms of successively dropping the weakest defeats
till someone is unbeaten.
CSSD does what Condorcet said to do, except that it only drops defeats
among the current Schwartz set., the most win-deserving set of
candidates.
If ranking is assumed to be sincere, and strategy incentives and
situations are disregarded, then it would be difficult to come up with
a better majoritarian method than CSSD. Academic voting-system
discussion has tended to assume those conditions. But how realistic is
that? Yes, one thing that we liked about CSSD is that it's more
resistant to certain strategy incentives, the Condorcet offensive
strategies. But there are other, worse, strategy problems. At the time
that we proposed CSSD, we were in denial about the chicken dilemma.
Many of us still are.
Let me briefly say that, for official public elections, under current
conditions (disinformational media, and a public who completely trust
and believe those media), we need a voting system that can never give
any incentive "favorite-bury", to vote another candidate over one's
favorite. That's the problem in official public elections, under
current conditions. But those conditions don't apply to Debian's
elections, and I don't claim that CSSD's failure in that regard
matters for Debian voting. I just wanted to mention and dispose of
that consideration first.
No, relevant to Debian, CSSD's problem is the chicken dilemma. Let me
describe the chicken dilemma, and then give some examples of CSSD's
chicken dilemma.
Say there are 3 candidates, A, B, and C. The A voters + the B voters
add up to a majority. The size-relation of the canddiates'
support-factions is:
C>A>B
The A voters and the B voters greatly prefer both A and B to C. In
fact, the A voters and the B voters _despise and detest_ C.
For the sake of simplicity, let's say that the C voters are
indifferent between A and B.
Below, I'll show examples of what can happen, but first I'll just
verbally summarize what can happen: First of all, of course A is the
CW. A is the "sincere CW". In comparison to each of the other
candidates, more people prefer A to the other candidate than
vice-versa. A should win, and would win in CSSD, or any Condorcet
method, under sincere voting.
Obviously, if each faction just rank only their favorite, then C will
win. To defeat C, it's necessary that at least one faction rank both A
and B over C. So the A voters, being co-operative, and wanting to
defeat C, rank B in 2nd place. But the B voters, knowing that the A
voters are co-operative and responsible, decide to take advantage of
the A voters' co-operativenes and responsibility: The B voters refuse
to rank A. The result? B wins, by defection, by taking advantage of
the A voters' co-operativeness. By taking advantage of the fact that
the A voters wanted to help B.
The message that CSSD is sending is: "You help, you lose."
That isn't good. That's the chicken dilemma.
CSSD is always susceptible to the chicken dilemma, whenever the
above-stated conditions obtain.
The chicken dilemma is well known and much discussed in game theory.
As I said, we were in denial about the chicken dilemma. Many of us
still are. Many Condorcetists don't want to admit that the voting
system that we've been promoting has an unnecessary fault, and that it
would be easier and better to avoid that fault.
Now, let me show a few examples of CSSD's chicken dilemma:
In the example-tables below, the number on the left,on each line, is
the number of voters who have the preferences stated on that line, or
who vote the rankings stated on that line. "A>B>C" indicates
preference for A over B, and for B over C. ...or a ranking of A over
B, and B over C. ">>" indicates a much stronger preference.
I'll give 3 examples.
Example 1:
Sincere preferences:
99: A>B>>C
2: B>A>>C
100: C>>(A=B)
The A voters rank sincerely, and the B voters defect:
99: A>B
2: B
3: C
CSSD elects B. The B voters' defection has stolen the election from A,
the CW. ...even though there are only 2 voters to whom B favorite.
2 defecting B voters have stolen the election from 99 co-operative A voters.
----------------------------
Here's another example in which the 3 factions are nearly equal in size:
Sincere preferences:
33: A>B>>C
32: B>A>>C
34: C>>(A=B)
Actual votes, when A voters co-operate and B voters defect:
33: A>B
32: B
34: C
Again, though A is CW, B wins by defection.
------------------------------------------
Here's an example in which the A and B voters barely add up to a
majority, and are nearly equal to eachother:
Sincere preferences:
26: A>B>>C
25: B>A>>C
49: C>>(A=B)
Actual rankings, when the A voters rank sincerely and the B voters defect:
26: A>B
25: B
49: C
Again, the B voters' defection elects B, stealing the election from A, the CW.
---------------------------------------
If the chicken dilemma were unavoidable, then we could just say, "Oh
well", and hope for the best.
But the chicken dilemma is easily avoided. There are voting systems
that avoid it, while retaining CSSD's most important criterion
compliances.
Let me name a few important criteria met by CSSD:
The Mutual Majority Criterion.
First, let me define a mutual majority:
A mutual majority (MM) is a set of voters, comprising a majority of
the voters, who all prefer some same set of candidates to all of the
other candidates.
That set of candidates is that MM's "MM-preferred set".
[end of MM definition]
Mutual Majority Criterion (MMC):
If a MM vote sincerely, then the winner should come from their MM-preferred set.
[end of MMC definition]
As a supporting definition, it's necessary to define sincere voting:
A voter votes sincerely if s/he doesn't vote an unfelt preference, or
fail to vote a felt preference that the balloting system in use would
have allowed hir to vote in addition to the preferences that s/he
actually did vote.
To vote a preference for X over Y is to vote X over Y.
To vote a felt preference is to vote X over Y, if preferring X to Y.
To voe an unfelt preference is to vote X over Y if not preferring X to Y.
[end of sincere voting definition]
MMC is very important and valuable. It's what guarantees majority
rule, without requiring anythin more than sincere ranking.
The problem is that when there's a chicken dilemma, CSSD gives
dis-incentive for sincere ranking. The chicken dilemma can and will
(when it occurs) spoil a mutual majority. When that happens, that
chicken dilemma makes MMC compliance meaningless and useless.
So, we'd like a method that meets MMC and doesn't have the chicken dilemma.
Now, I hasten to clarify that IRV is not what I'm recommending to
Debian. But IRV is one method that meets MMC and doesn't have the
chicken dilemma.
Though IRV isn't my recommendation to Debian, in spite of IRV's
inadequacy for official public elections under current conditions,
IRV's above-stated combination of properties is a very powerful
combination. It means that a MM have no strategic reason to do other
than rank sincerely. That's the rank-balloting ideal. IRV guarantees
that for a MM. IRV's disadvantage is that, when IRV doesn't respect
differently-constituted majorities, when it fails to elect a CW.
For an amicable organization, IRV's sometime failure to elect the CW
compromise makes it too uncompromising, too inimical. It would be
better for a voting system to respect _all_ majorities, by electing
the CW.
Well, there are voting systems that meet MMC, have no chicken dilemma,
and always elect the CW when there is one. In fact, when there isn't a
CW, those method that I'm speaking of always choose from the top-cycle
("Smith set").
Let me define a few such methods. Then I'll give the URL of a journal
article about them.
First, because these methods make use of IRV, let me give a very brief
definition of IRV:
Repeatedly, cross off or delete from the rankings the candidate who
currently tops the fewest rankings.
(Of course the last-remaining un-deleted candidate wins)
[end of IRV definition]
(Of course, as soon as a candidate tops a majority of the rankings,
then s/he will inevitably win, and so s/he can immediately be declared
winner)
Benham's method (also called "Benham", or "Condorcet IRV"):
Do iRV till there is an un-deleted candidate who beats each of the
other un-deleted candidates. Elect hir.
X beats Y if more ballots rank X over Y than rank Y over X.
[end of Benham definition]
Woodall:
Do IRV till only one member of the initial Smith set remains
un-deleted. Elect hir.
For the purposes of this definition, the Smith set is the smallest set
of candidates such that each member of the set beats each candidate
outside the set.
[end of Woodall definition]
Benham and Woodall both always choose from the Smith set, but Woodall
is more particular about which Smith set member it chooses, and
therefore Woodall achieves slightly better social utility.
It goes wihout saying that if there is a CW, Benham or Woodall, by
their definitions,would immediately elect that CW, without doing any
IRV.
Schwartz Woodall:
Do IRV till only one member of the initial Schwartz set remains
un-deleted. Elect hir.
[end of Schwartz Woodall definition]
As you know, the Schwarz and Smith sets are identical if there are no
pairwise-ties. In large public elections, where pairwise ties are
vanishingly rare, those 2 sets are nearly always identical. No so in
organizational voting, where there are fewer voters. With a
smaller,organizational, electorate, the Schwartz set is more exclusive
than the Smith set. Tying with a member of the Smith set, while
beating everyone outside it, will get into the Smiith set. Not so the
Schwartz set.
Here are 2 equivalent definitions of the Schwartz set:
Cycle definition of the Schwartz set:
The Schwartz set is the set of candidates who don't have a defeat that
isn't in a cycle.
A defeat is what Y has, if X beats Y.
A cycle is a cyclical sequence of defeats, such a X beats Y beats Z beats X.
[end of cycle definition of the Schwartz sett]
Unbeaten set definition of the Schwartz set:
1. An unbeaten set is set of candidates none of whom are beaten by
anyone outside the set.
2. An innermost unbeaten set is an unbeaten set that doesn't contain a
smaller unbeaten set.
3. The Schwartz set is the set of candidates who are in innermost unbeaten sets.
[end of unbeaten set definition of the Schwartz set]
I recommend Schwartz Woodall as the best voting system for Debian.
Benham or Woodall would be adequate, but Schwartz Woodall would be the best.
Now, here is the URL of a journal article that discusses Benham and Woodall:
http://econ.ucsb.edu/~armytage/hybrids.pdf
The Condorcet Internet Voting Service (CIVS) is an automated polling
service, in which anyone can set up a public poll or a private poll.
One of the count rules implemented by CIVS is Condorcet-IRV (Benham).
Here is the URL of CIVS:
http://www.cs.cornell.edu/andru/civs.html
I strongly recommend Schwartz Woodall as the best voting system for Debian.
That method's compliance with the Mutual Majority Criterion, and its
freedom from chicken dilemma, make a powerful combination of
properties that give a mutual majority complete freedom from any
strategy-need. A MM, by merely ranking sincerely, can ensure that the
winner will come from their MM-preferred set--while freely choosing
from among that set via their sincere rankings.
And that sincere ranking isn't marred by a chicken dilemma.
Further, Schwartz Woodall (like Woodall and Benham) also always
chooses the CW compromise when there is one, and, when there isn't,
always chooses from the top cycle (Smith set). Of course Schwartz
Woodall also always chooses from the more exclusive Schwartz set.
Schwartz Woodall is the best voting system for Debian.
Michael Ossipoff
Reply to: