On Mon, Sep 12, 2011 at 11:00 AM, Jameson Quinn <[email protected]> wrote: > I wonder if there aren't also Kemeny optimizations similar to IRV's > multiple-elimination, which would work well for real data.
--there definitely are. If there is a condorcet winner (or loser) we can place him at the top (bottom) of the ordering, then reduce the election to the remaining N-1 candidates and solve it recursively More generally if there is a subset of candidates that are above all the others (by majority votes on all pairs) i.e the "Smith set" then we can split into two subproblems. [I'm taking wikipedia's word for it that Kemeny satisfies the Smith criterion...] In this way we can quickly reduce the problem down to "irreducible" hard Kemeny elections, i.e. those without any Condorcet winner, Condorcet loser, or nontrivial Smith set. Large random elections are (with high probability) irreducible... but for small or medium elections this reduction often should be a big time savings. But in bad cases it saves you nothing since already irreducible. You can see why it is the that runtimes of algorithms vary tremendously depending on the election... -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step) and math.temple.edu/~wds/homepage/works.html ---- Election-Methods mailing list - see http://electorama.com/em for list info
