Re: [EM] Dodgson and Kemeny done right?
Kemeny is precinct summable, all it needs is the pairwise matrix. Dodgson also is precinct summable: for each (candidate, rank) 2-tuple, you keep track of the count. Re my/Simmons' Kemeny done right based on ratings-style ballots, I think it is highly debatable whether this is really a good analogue to Kemeny. I think it's a bad analogue. The analogy is much better for Dodgson than for Kemeny. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Dodgson and Kemeny done right?
You're right, I forgot that Kemeny only needed the pairwise matrix. And according to Warren Dodgson is summable. I don't see how. - Original Message - From: Kristofer Munsterhjelm Date: Thursday, September 15, 2011 12:14 pm Subject: Re: [EM] Dodgson and Kemeny done right? To: fsimm...@pcc.edu Cc: Warren Smith , election-methods fsimm...@pcc.edu wrote: A fourth common problem with Dodgson and Kemeny that I failed to mention is their common lack of efficient precinct summability. Is that true? My implementation of Kemeny uses a variant of integer program #3 from Improved Bounds for Computing Kemeny Rankings, and this integer program only needs access to the graph itself to find the minimum feedback arc set. In voting terms, that means that the integer program only needs the Condorcet matrix to determine who the winner is. In optimization terms, the problem consists of finding the transitive sequence C_1 beats C_2 beats ... beats C_n so that the sum of [C_1 beats C_2] + [C_2 beats C_3] + ... + [C_(n-1) beats C_n] is maximized. (Equivalently, one could phrase it as minimizing the number of upsets - sum of C_k beats C_(k-1).) Thus, unless I'm wrong, the precinct summability is the same as any other Condorcet method, except to the extent that Kemeny is not summable because it doesn't give the winners in polytime. However, Kemeny can't give the winners in worst case polytime, not even if you have the ballots themselves, unless P = NP. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Dodgson and Kemeny done right?
On Fri, Sep 16, 2011 at 8:21 PM, fsimm...@pcc.edu wrote: You're right, I forgot that Kemeny only needed the pairwise matrix. And according to Warren Dodgson is summable. I don't see how. --if Dodgson minimizes the total travel distance for all candidates on all ballots to travel from their current position to the output-permutation's position, and position means rank then all you need to know is the total number of times candidate X is in rank Y on any input ballot, for all (X,Y). That count-info is publishable by each precinct. For N candidates this is N^2 different counts published by each precinct. Right? Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Dodgson and Kemeny done right?
On Fri, Sep 16, 2011 at 5:27 PM, Warren Smith warren@gmail.com wrote: On Fri, Sep 16, 2011 at 8:21 PM, fsimm...@pcc.edu wrote: You're right, I forgot that Kemeny only needed the pairwise matrix. And according to Warren Dodgson is summable. I don't see how. --if Dodgson minimizes the total travel distance for all candidates on all ballots to travel from their current position to the output-permutation's position, and position means rank then all you need to know is the total number of times candidate X is in rank Y on any input ballot, for all (X,Y). That count-info is publishable by each precinct. For N candidates this is N^2 different counts published by each precinct. Right? I think we just have to find the minimal travel distance to make someone a Condorcet winner. We don't have to make all of the ballots identical. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Dodgson and Kemeny done right?
Borda done right is detailed here:
http://lists.electorama.com/pipermail/election-methods-electorama.com/2011-July/028043.html
Dodgson done right was sketched here:
http://lists.electorama.com/pipermail/election-methods-electorama.com/2011-July/027888.html
The version of Dodgson I was addressing does not attempt to output a social
order like Kemeny does. (I agree with your treatment of Kemeny below.)
The usual version of Dodgson modifies the ballots minimally to create a
pairwise beats-all candidate without saying who came in second, etc.
My versions of {ranked method} done right also include the clone free
conversion of ordinal ballots to cardinal ballots, as detailed most thoroughly
in the first link above.
A fourth common problem with Dodgson and Kemeny that I failed to mention is
their common lack of efficient precinct summability. In my done right
versions this is taken care of by faction
amalgamation which is easy to do with cardinal ballots, but requires two
rounds in the case of ordinal ballots; the first round sums all of the first
place preferences to make this information available for
the clone free conversion of ordinal ballots to cardinal ballots. Then the
second round can also go forward summably by making use of the cardinalized
ballots.
In the case of Dodgson, once the factions have been amalgamated, if there is no
pairwise beats-all candidate, all interested parties can submit modifications
of these faction scores. The minimal
modification that yields a beats-all candidate determines the winner.
- Original Message -
From: Warren Smith
Date: Tuesday, September 13, 2011 5:29 pm
Subject: Dodgson and Kemeny done right?
To: electionscie...@googlegroups.com, election-methods , fsimm...@pcc.edu
Dodgson and Kemeny done right (F.W.Simmons)
-Warren D. Smith, Sept 2011--
Simmons claims he had posted something called Dodgson done right
which gets around the problem that with Dodgson voting it is NP-hard
to find the winner, and supposedly Kemeny has a similar fix.
I failed to find his post, but reading between the lines am attempting
to try to determine what Simmons probably had in mind by reverse
engineering, and/or the fact I had similar thoughts of my own a long
time back.
DODGSON:
votes are rank-orderings of the N candidates.
Output ordering: the one such that the smallest total
candidate motion (distance moved, summed over all
candidates on all ballots) is required to convert the input orders
into the output order.
KEMENY:
votes are rank-orderings of the N candidates.
Output ordering: the one with the fewest total number of
disagreements with the input orders about candidate-pairs
(summed over
all candidate-pairs on all ballots)
ATTEMPT TO REPAIR/REDEFINE:
Make the ballots instead be range-voting style RATINGS ballots.
Output now also is a ratings-style ballot.
For ratingified Dodgson, output is a ballot with
minimum total candidate motion required to convert all
the input ballots into the output ballot (total distance traveled
along the ratings axis, summed over all candidates and all ballots).
For ratingified Kemeny, output is the ballot with
minimum total 2-candidate travel distance summed over all
candidate-pairs on all input ballots, where that candidate pair
has to
travel along the ratings axis so instead of their original directed
separation, they now have the same separation (in same
direction) as
the output ballot.
THEOREM:
Ratingified Dodgson is no longer NP-hard to find, in fact it is easy,
in fact it is just this: each candidate's output score is the median
of his input scores.
PROOF: Easy.
REMARK:
If instead we were minimizing the sum of the SQUARES of the travel
distances, then ratingified Dodgson would just become average-based
range voting, the output score is the mean of that candidate's input
scores.
THEOREM:
Ratingified Kemeny is by this definition the same thing as
ratingified Dodgson.
--
Warren D. Smith
http://RangeVoting.org -- add your endorsement (by clicking
endorse as 1st step)
Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Dodgson and Kemeny done right?
fsimm...@pcc.edu wrote: A fourth common problem with Dodgson and Kemeny that I failed to mention is their common lack of efficient precinct summability. Is that true? My implementation of Kemeny uses a variant of integer program #3 from Improved Bounds for Computing Kemeny Rankings, and this integer program only needs access to the graph itself to find the minimum feedback arc set. In voting terms, that means that the integer program only needs the Condorcet matrix to determine who the winner is. In optimization terms, the problem consists of finding the transitive sequence C_1 beats C_2 beats ... beats C_n so that the sum of [C_1 beats C_2] + [C_2 beats C_3] + ... + [C_(n-1) beats C_n] is maximized. (Equivalently, one could phrase it as minimizing the number of upsets - sum of C_k beats C_(k-1).) Thus, unless I'm wrong, the precinct summability is the same as any other Condorcet method, except to the extent that Kemeny is not summable because it doesn't give the winners in polytime. However, Kemeny can't give the winners in worst case polytime, not even if you have the ballots themselves, unless P = NP. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Dodgson and Kemeny done right?
On 9/15/2011 12:14 PM, Kristofer Munsterhjelm wrote: fsimm...@pcc.edu wrote: A fourth common problem with Dodgson and Kemeny that I failed to mention is their common lack of efficient precinct summability. Is that true? My implementation of Kemeny uses a variant of integer program #3 from Improved Bounds for Computing Kemeny Rankings, and this integer program only needs access to the graph itself to find the minimum feedback arc set. In voting terms, that means that the integer program only needs the Condorcet matrix to determine who the winner is. ... The Condorcet-Kemeny method only needs the pairwise counts from each precinct. Those are summed at any location, and the calculations begin. (Will reply to other messages as I have time) Richard Fobes Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Dodgson and Kemeny done right?
On 7/22/64 2:59 PM, Warren Smith wrote: Dodgson and Kemeny done right (F.W.Simmons) -Warren D. Smith, Sept 2011-- Simmons claims he had posted something called Dodgson done right which gets around the problem that with Dodgson voting it is NP-hard to find the winner, and supposedly Kemeny has a similar fix. I failed to find his post, but reading between the lines am attempting to try to determine what Simmons probably had in mind by reverse engineering, and/or the fact I had similar thoughts of my own a long time back. DODGSON: votes are rank-orderings of the N candidates. Output ordering: the one such that the smallest total candidate motion (distance moved, summed over all candidates on all ballots) is required to convert the input orders into the output order. Dodgson, by the way, is not merely NP-hard. It is higher in the polynomial hierarchy and has been shown to be complete for P^NP (parallel access to NP oracles). Probably worse than Kemeny! -- Andrew attachment: andru.vcf Election-Methods mailing list - see http://electorama.com/em for list info
