Paul Kislanko | 1 Nov 17:12 2004
Picon

Sports-based models for voters and votes

One problem with using wins between teams as "votes" is that in this case
the "voters" are the games played, so an A>B voter is different from a C>D
voter and no "voter" ranks more than 2 alternatives. It's as good as a way
as any to put random numbers into a pairwise matrix, but it's a lot faster
to just generate 100*R and 100*(1-R) if you've got a computer.

But here's a source for ranked ballots that could be used to model any
system. Kenneth Massey has collected up nearly 100 polls and ranking systems
for American College Football. Each of these is a "ranked ballot" that
orders (possibly a subset) of the 117 teams in division 1A.

On this page the "voters" are listed across the top, and the candidates down
the side. 

The data as it exists is not very interesting, because there's really not
that much disagreement at the top and bottom of the ballot, since even
though all of the "voters" have different weights for "issues" (margin of
victory versus opponents' winning percentage, etc) they all have the same
goal of picking the most dominant team, which is by definition likely to be
very highly rated in "issue" that is relevant.

However, if you threw out all the options that appeared on any voters top
10, I think you'd have a pretty good set of data to test against various
alternatives (and lots of cycles and sub-cycles).

His site is at http://www.mratings.com/cf/compare.htm

----
Election-methods mailing list - see http://electorama.com/em for list info

(Continue reading)

Jobst Heitzig | 1 Nov 20:24 2004
Picon

New criterion: Independence Of Weakly Defeating Alternatives (IWDA)

Inspired by the example I posted recently, I suggest to discuss a new
independence criterion. It is in the same spirit as IPDA and ISDA in
that it requires the winner to stay the same when an alternative is
added which is very weak in a sense. More precisely, the new alternative
is considered weak when the new defeats it brings are too weak to be
considered essential new information. Here's the definition:

INDEPENDENCE OF WEAKLY DEFEATING ALTERNATIVES (IWDA):
The winner must not change when an alternative X is added but for each
option Y which is defeated by X, already some stronger defeat against Y
is affirmed/undropped by the method.

In the current wording, IWDA only applies to methods which affirm
defeats (like Ranked Pairs, River, Kemeny) or drop defeats (like PC, SD,
SSD).

Ranked Pairs and Kemeny fail IWDA, as can be seen from the example I
posted recently. In that example, C is the "weakly defeating alternative".

Does SSD (Beatpath) fulfil IWDA?

And how does IWDA relate to IPDA and ISDA?

Jobst

----
Election-methods mailing list - see http://electorama.com/em for list info

Paul Kislanko | 1 Nov 20:35 2004
Picon

RE: New criterion: Independence Of Weakly Defeating Alternatives(IWDA)

"And how does IWDA relate to IPDA and ISDA?"

Well they all have the same number of letters, and all contain both an I, D,
and A in the same order. W is clearly < P < D.

----
Election-methods mailing list - see http://electorama.com/em for list info

Paul Kislanko | 1 Nov 20:43 2004
Picon

RE: New criterion: Independence Of Weakly DefeatingAlternatives(IWDA)

> -----Original Message-----
> From: election-methods-electorama.com-bounces <at> electorama.com 
> [mailto:election-methods-electorama.com-bounces <at> electorama.com
> ] On Behalf Of Paul Kislanko
> Sent: Monday, November 01, 2004 1:36 PM
> To: 'Jobst Heitzig'; election-methods-electorama.com <at> electorama.com
> Subject: RE: [EM] New criterion: Independence Of Weakly 
> DefeatingAlternatives(IWDA)
> 
> "And how does IWDA relate to IPDA and ISDA?"
> 
> Well they all have the same number of letters, and all 
> contain both an I, D,
> and A in the same order. W is clearly < P < D.
 Just as clearly, I meant < S 

----
Election-methods mailing list - see http://electorama.com/em for list info

Andrew Myers | 1 Nov 22:27 2004
Picon

CIVS update

Hi all,

I thought people might be interested to know about some
recent improvements to the Condorcet Internet Voting Service at
http://www5.cs.cornell.edu/~andru/civs.

* It now implements three different completion rules, including
  MAM, Beatpath Winner, and a deterministic variant of MAM. If
  others want to contribute Perl modules that implement their
  favorite completion rules I would be amenable to adding it.
  The way to do this is reasonably clear from the existing code.

* It has a nicer user interface that uses Javascript to
  make it easier to express rankings, especially when there
  are a lot of alternatives. Comments, suggestions welcome.

* The web site has a pointer to the source code so you can
  see how it works.

Cheers,

-- Andrew
----
Election-methods mailing list - see http://electorama.com/em for list info

Jobst Heitzig | 1 Nov 23:21 2004
Picon

Re: New criterion: Independence Of Weakly Defeating Alternatives (IWDA)

Some hours ago I wrote:
> INDEPENDENCE OF WEAKLY DEFEATING ALTERNATIVES (IWDA):
> The winner must not change when an alternative X is added but for each
> option Y which is defeated by X, already some stronger defeat against Y
> is affirmed/undropped by the method.
> 
> In the current wording, IWDA only applies to methods which affirm
> defeats (like Ranked Pairs, River, Kemeny) or drop defeats (like PC, SD,
> SSD).
> 
> Ranked Pairs and Kemeny fail IWDA, as can be seen from the example I
> posted recently. In that example, C is the "weakly defeating alternative".
>
> Does SSD (Beatpath) fulfil IWDA?

The following example shows that also PC, SD, and SSD (Beatpath) fail IWDA:

Sincere prefs:

	1  A>B>C>D
	33 A>D>B>C
	33 B>D>C>A
	17 C>A>B>D
	16 C>D>A>B

Defeats and winning votes: A>B>C>A>D, B>D>C

	...>... A   B   C   D
	A          67 (34) 51
	B     (33)     67  51
(Continue reading)

Alex Small | 2 Nov 09:24 2004
Picon

Successful talk on election methods

On Monday I gave a talk on the mathematics of election methods to about a dozen of my colleagues.  There's a journal club of physics grad students who normally meet to discuss topics in biophysics, solid state physics, and materials science.  This week they decided to have a talk on voting, in honor of the election.  I've been to one or two of their meetings and am the only person in my department (to the best of my knowledge) with a strong interest in the subject.
 
The talk was oriented more toward academics than activism, so I didn't hit hard on the IRV vs. approval controversy, but I gave approval voting a favorable review compared with IRV, and it was well received.  They asked some good questions.  I didn't wade into the controversy over whether IRV is worth supporting as a replacement for plurality, because I didn't think it was the right forum.  I wanted to get to subjects like Arrow's theorem, the Gibbard-Satterthwaite Theorem, my ongoing work on strong FBC, how the dimensionality of issue space affects Condorcet cycles, and the electoral college.  I also gave an overview of commonly discussed voting methods and basic issues of races with 3 or more candidates.  I gave a plug for both of the mailing lists that I'm sending this to.
 
If anybody wants to use some of my slides to give a similar talk, let me know.  It was fun putting this talk together because I realized just how much I've learned since I started exploring these issues 4 years ago, and how much even we amateurs can understand just by giving it a little thought.
 
 
 
Alex Small

__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com

----
Election-methods mailing list - see http://electorama.com/em for list info
Eric Gorr | 2 Nov 16:45 2004
Picon

Re: Successful talk on election methods


At 12:24 AM -0800 11/2/04, Alex Small wrote:
>If anybody wants to use some of my slides to give a similar talk, 
>let me know.  It was fun putting this talk together because I 
>realized just how much I've learned since I started exploring these 
>issues 4 years ago, and how much even we amateurs can understand 
>just by giving it a little thought.

I would recommend having a digital video camera any such talk so it 
can be recorded and then made available via the 'net along with PDF 
versions of any materials that are created for the talk.

If you have PDF versions of the materials you created, I would be 
happy to place them on my website and I'm sure others would like to 
have that stuff as well.

--

-- 
== Eric Gorr ========= http://www.ericgorr.net ========= ICQ:9293199 ===
"Therefore the considerations of the intelligent always include both
benefit and harm." - Sun Tzu
== Insults, like violence, are the last refuge of the incompetent... ===
----
Election-methods mailing list - see http://electorama.com/em for list info

Jobst Heitzig | 2 Nov 23:56 2004
Picon

robustness against single withdrawals in case of 4 candidates

This is an attempt to measure a kind of "robustness against withdrawals"
for the three methods Ranked Pairs, River, and Beatpath.

For any given voting situation, the method gets a score of one for each
candidate whose withdrawal does not change the winner. This score is
added for all the 52 situations with 4 candidates in which the score is
not identical for the three methods, giving a total score of 104 for RP,
81 for River, and 57 for Beatpath. This corresponds to a mean score of

	2    for Ranked Pairs,
	1.55 for River, and
	1.1  for Beatpath, compared to
	3    for Approval (the maximal score possible)

Of course, this is only a very rough indicator so far, but it suggests
that we should perhaps perform some Monte Carlo simulations in order to
estimate for various combinations of methods and candidate numbers the
median number of candidates whose withdrawal doesn't change the winner.

This would give a nice indicator for robustness. My guess is that the
robustness gap between Ranked Pairs and Beatpath will grow with the
number of candidates, and that River will be less robust than Ranked
Pairs only when the number of candidates is small.

Jobst

Here's the detailed list of examples:

Notation: XY is the strength of defeat X>Y.

Situation            Winner Score
                     RP     RP
                     | Riv  | Riv
                     | | BP | | BP
                     | | |  | | |
AB>BD>...
 CD>DA>AC>BC         A A C  2 2 1
 CD>DA>BC>AC         A A C  2 2 1
 DA>CD>AC>BC         A A C  2 2 1
 DA>CD>BC>AC         A A C  2 2 1
AB>CD>...
 BD>DA>AC>BC         A C C  2 1 1
 BD>DA>BC>AC         A C C  2 1 1

AC>BC>DA>...
 CD>AB>BD            D D B  2 2 1
AC>CD>...
 BC>DA>AB>BD         A A B  2 2 1
 DA>BC>AB>BD         A A B  2 2 1
AC>DA>...
 BC>CD>AB>BD         D D B  2 2 1
 CD>BC>AB>BD         D D B  2 2 1

BC>AC>CD>...
 DA>AB>BD            A B B  2 1 1
BC>AC>DA>...
 CD>AB>BD            D B B  2 1 1
BC>CD>...
 AC>DA>AB>BD         A B B  2 1 1
BC>DA>...
 AC>CD>AB>BD         D B B  2 1 1

BD>AB>...
 CD>DA>AC>BC         A A C  2 2 1
 CD>DA>BC>AC         A A C  2 2 1
 DA>CD>AC>BC         A A C  2 2 1
 DA>CD>BC>AC         A A C  2 2 1
BD>CD>AB>...
 DA>AC>BC            A A C  2 2 1
 DA>BC>AC            A A C  2 2 1
BD>CD>DA>...
 AB>AC>BC            B B C  2 2 1
 AB>BC>AC            B B C  2 2 1
BD>DA>...
 AB>CD>AC>BC         B B C  2 2 1
 AB>CD>BC>AC         B B C  2 2 1
 CD>AB>AC>BC         B B C  2 2 1
 CD>AB>BC>AC         B B C  2 2 1

CD>AB>...
 BD>DA>AC>BC         A C C  2 1 1
 BD>DA>BC>AC         A C C  2 1 1
CD>AC>...
 BC>DA>AB>BD         A A B  2 2 1
 DA>BC>AB>BD         A A B  2 2 1
CD>BC>...
 AC>DA>AB>BD         A B B  2 1 1
CD>BD>AB>...
 DA>AC>BC            A C C  2 1 1
 DA>BC>AC            A C C  2 1 1
CD>BD>DA>...
 AB>AC>BC            B C C  2 1 1
 AB>BC>AC            B C C  2 1 1
 AC>AB>BC            B C B  2 1 2
CD>DA>...
 AC>BD>AB>BC         B C B  2 1 2
 BD>AB>AC>BC         B C C  2 1 1
 BD>AB>BC>AC         B C C  2 1 1
 BD>AC>AB>BC         B C B  2 1 2

DA>AC>...
 BC>CD>AB>BD         D D B  2 2 1
 CD>BC>AB>BD         D D B  2 2 1
DA>BC>...
 AC>CD>AB>BD         D B B  2 1 1
DA>BD>...
 AB>CD>AC>BC         B B C  2 2 1
 AB>CD>BC>AC         B B C  2 2 1
 CD>AB>AC>BC         B B C  2 2 1
 CD>AB>BC>AC         B B C  2 2 1
DA>CD>...
 AC>BD>AB>BC         B C B  2 1 2
 BD>AB>AC>BC         B C C  2 1 1
 BD>AB>BC>AC         B C C  2 1 1
 BD>AC>AB>BC         B C B  2 1 2

(END OF LIST)

----
Election-methods mailing list - see http://electorama.com/em for list info

Paul Crowley | 4 Nov 13:44 2004
Picon

New Condorcet/RP variant

I'd like to propose another MAM/MMV/CIVS variant.  I think this one is
conceptually simpler than any of those three and has neat tiebreaking.
 The tiebreaking rule is "where all greater preferences have already
been decided and two equal preferences contradict each other, choose
the one that does best on the preferences below it".  However, the
formal expression of this rule is actually somewhat cleaner, though it
may read strangely to those more used to such rules being described
directly in terms of feasable algorithms.

Consider a potential ordering of the candidates, and show the
preference matrix with the candidates in that order.  For example,
consider the preference matrix at the bottom of this page:

http://www5.cs.cornell.edu/cgi-bin/andru/civs/results?id=E_4dcecf4df0550b93

The upper triangle of the preference matrix shows the numbers of votes
affirmed by that order for each pair, and the lower triangle shows the
numbers of votes contradicted; for example, the fact that the ordering
ranks Clark above Edwards confirms 39 votes, and contradicts 35.  The
"sorted preference list" for a given ordering is a list of all the
numbers in this upper triangle, in sorted order.  Duplicates are of
course preserved, so every list has n(n-1)/2 elements where n is the
number of candidates.

Lexicographic sorting imposes a total ordering on sorted preference
lists; the result of the election is the ordering whose sorted
preference list comes highest in this lexicographic sorted order.

In the extremely rare instance that two or more orderings have exactly
the same multiset of numbers in the upper triangle of their preference
matrix, one such maximally good ordering is chosen fairly at random. 
This is the only instance where the procedure is nondeterministic.  (I
take it that it's obvious no fully deterministic procedure can satisfy
universality, anonymity, and neutrality)

In a public election where all the numbers can be expected to differ,
this makes the same decision as MAM/MMV/CIVS, but where there are ties
I think this is the fairest and cleanest way to break them.

I've proven that this system satisfies monotonicity and the Smith
Criterion (ie it will never rank a non-member of the Smith set above a
member of the Smith set); I'm working on other proofs.  The proofs
come out quite short and neat, especially the latter one, which gives
me confidence that this method has nice properties.  It's immediately
obvious it satisfies anonymity, neutrality, and homogeneity.

Efficient implementation involves trying different possibilities where
there are ties and backtracking.  If there are many ties it could
potentially be very slow, but for any normal election it should be as
efficient as any system needs to be.

I look forward to hearing what list members think...
--

-- 
  __
\/ o\ Paul Crowley
/\__/ www.ciphergoth.org
----
Election-methods mailing list - see http://electorama.com/em for list info


Gmane