[EM] Kemeny update

[Jameson Quinn]

2011/9/24 Warren Smith <warren.wds at gmail.com>

> On Sat, Sep 24, 2011 at 10:50 AM, Kristofer Munsterhjelm
> <km_elmet at lavabit.com> wrote:
> > Warren Smith wrote:
> >>
> >> To reiterate and/or answer some questions:
> >>
> >> 1. there is no way to find the Kemeny winner that is much faster than
> >> finding the full Kemeny ordering. More precisely, both are NP-complete
> >> tasks
> >> so there is no poly-time algorithm for either unless P=NP.
> >>
> >> 2. Even if some benificent God helpfully informs you of the name of
> >> the Kemeny winner,
> >> or the full Kemeny ordering, then there is no easy way for you
> >> to confirm or deny that claim.   No matter how much supporting
> information
> >> God provides to you (if it is only a polynomially-bounded number of
> >> bits) -- such
> >> as a proof -- there remains no way to confirm or deny either claim that
> >> runs in
> >> polynomial time, unless NP=coNP.  In other words, no short proofs exist.
> >>
> >> 3. It IS possible to find both the Kemeny
> >> ordering and Kemeny winner, in any election, if you are willing to
> >> devote enough compute time to it.  But the amount of time needed will
> >> exceed any polynomial in the #candidates.  Every currently known
> >> algorithm in the papers I cited fails for easy-to-generate and fairly
> >> natural
> >> 40-candidate elections, no matter how much time they devote to it
> >> within the limits of their finances.
> >>
> >> 4. The hardest elections have got Smith set = the full set of
> candidates.
> >> This is asymptotically not a great restriction since random elections
> have
> >> Smith set = full set, with probability -->1 in the limit as
> >> #candidates --> infinity.
> >
> > Is Kemeny independent of Smith-dominated alternatives? Toby said he
> thought
> > he was. If it is, then Kemeny is feasible for practical elections because
> > you can just restrict it to the Smith set (and the Smith set won't be
> very
> > large in practice). That is, of course, unless the existence of advanced
> > voting methods will make the public vote in ways that will lead to a
> greater
> > Smith set (e.g. candidates who otherwise didn't want to split the vote
> now
> > feel bold enough to show up). Still, even so, I can't imagine there would
> be
> > a 27-member Smith set.
>
> --seems to me, KM is correct; if the Smith Set has less than about 20
> members (and if this also is true recursively upon removing it), then
> it always will be feasible to find the Kemeny order.
>
> How often will a (>=20)-member Smith set arise in practice?
>
> I do not know.   KM "can't imagine" it will happen, but that's his guess.
> I think if you take a 100-candidate election with random-uniform
> votes, it'd happen pretty often. Such elections have Condorcet winners
> about 9-12% of the time (says my computer), which leads me to guess
> that they have (>=20)-member Smith sets about 10% of the time.  See
> also puzzles
> 25 and 26 here for some theorems about the closely related problem of
> random "round robin tournaments" rather than random "elections":
>   http://www.rangevoting.org/PuzzlePage.html
>
> But it could be argued/hoped that 100-candidate elections, when they
> occur, will have vote distributions quite dissimilar to
> random-uniform.
> It could be counterargued that humanity's experience with
> 100-candidate elections is small, and with 100-candidate
> rank-order-ballot
> elections is even smaller, so there is little basis for KM's guess.
>
> Tideman in his book has got a statistical semiempirical model, based
> on real election statistics, of rank-order ballot elections.  His
> model is described/corrected/recalculated here:
>    http://rangevoting.org/TidemanElModel.html
> and it finds the probability, in a 100-canddt election,that a
> Condorcet Winner exists, is 27%, and for a 200-canddt
> Tideman-statistics election this probability is 5.6%.
>

At a very, very rough estimate, the average size of the Smith set should be
about 1/prob(CW). That is, take the prob(CW) as the recursive probability
that the Smith set "stops at size n" for any n. (This is obviously very
rough, because for instance a 2-member Smith set is impossible. But I'm just
going for generalities here)

So, a 100-candidate election in Tideman's model would have a Smith set
around 4 members, and 95% of the time (1/e^3), would have a smith set under
12. In this model, a 20-member Smith set would happen about once per 150
elections.

I'd say that this is (extremely) weak evidence that Kemeny could handle a
100-member election. I'd also guess that Tideman's model is probably
"pessimistic" for such very-large elections in that it overestimates the
strength of non-top-tier candidates. So in this sense, I would be inclined
to give Kemeny the benefit of the doubt.

Also note that it is extremely probable that a 5-25 member Smith set would
happen at least once before any >25-member Smith sets ever happened. That
would give much stronger data from which to evaluate the "risk" of an
irresolvable Kemeny election, before such a crisis occurred.

hoping-that-someone-else-is-better-with-beta-functions-than-I-am-ly y'rs,
JQ
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20110924/089d9d32/attachment-0003.htm>