[EM] [CES #3605] Re: Kemeny Condorcet method. Apparently not a good choice for those of us who want to know who won in our lifetimes.

[Warren Smith]

On Mon, Sep 12, 2011 at 11:00 AM, Jameson Quinn <jameson.quinn at gmail.com> 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