Re: [EM] Dodgson and Kemeny "done right"?
On Fri, Sep 16, 2011 at 5:27 PM, Warren Smith wrote: > On Fri, Sep 16, 2011 at 8:21 PM, 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"?
On Fri, Sep 16, 2011 at 8:21 PM, 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"?
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"?
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"?
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"?
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"?
"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"?
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 <> Election-Methods mailing list - see http://electorama.com/em for list info
[EM] Dodgson and Kemeny "done right"?
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
