[EM] Kemeny update

[Peter Zbornik]

Dear all,

a small correction to my email below (a negation was forgotten):
I wrote: "Yes, it might happen, that a good variable is eliminated, which
significantly improve the analysis, but this is very likely, since you
normally have so many other good variables."
The text should read: "Yes, it might happen, that a good variable is
eliminated, which significantly improve the analysis, but this is NOT very
likely, since you normally have so many other good variables."

My appologies and thanks for your understanding or at least patience.

Best regards
Peter Zborník

On Sat, Sep 24, 2011 at 5:52 PM, Peter Zbornik <pzbornik at gmail.com> wrote:

> Dear all,
>
> I guess there could be some simple elimination of candidates before the
> election, so that there will be a manageable set of candidates for the
> Kemeny election, like 10 to 15.
>
> I guess sometime the winner would be lost in the reduction, but I would
> expect this to be extremely rare if just the elimination would be efficient.
>
> Variable elimination is standard in multivariate data analysis with one
> response variable (the thing you like to predict) to reduce the number of
> variables, which initially can be several hundreds to something more
> manageable, like 40 variables. A common way to reduce the number of
> variables is just to do a single variable analysis with the response
> variable. The variables with a significance below a threshold are
> eliminated. Yes, it might happen, that a good variable is eliminated, which
> significantly improve the analysis, but this is very likely, since you
> normally have so many other good variables.
>
> The same thing applies for single-winner elections. There is no need to be
> afraid pr ashamed to eliminate some of the candidates using some rule of
> thumb in order to get a manageable number of them.
>
> So the question I would like to pose would be: Which rule should be used to
> reduce the number of candidates in a Kemeny election to K in the unlikely
> case we have a Smith set of candidates larger than K, i.e. a very even
> election? What should be the value of K?
>
> Here are my favorites (all rules assume that the candidates outside the
> Smith set are eliminated)
> 1) There will be a candidate threshold for first preferences, just like in
> some parliamentary election, say 5%
> 2) The K candidates with the highest first preferences will be retained
> 3) Perform a K-seat STV election
> 4) eliminate the candidates according to least preferences until the method
> finds a winner within X minutes using a fast computer
>
> Let's face it, you can crash any method, unless you have extra rules, and
> in the real world there are a lot of them and few object to them.
>
> What if every citizen of the USA would decide to run for president?
> That would be a 300 million candidate election (gasp!).
> Now those ballots would be really long, which might pose a problem if you
> have paper ballots.
> Ok, so in order to prevent that, I guess there are some rules in the US
> that decrease the number of candidates (number of signatures, money, party
> support and so on).
>
> Best regards
> Peter Zborník
>
>
>
> On Sat, Sep 24, 2011 at 4:50 PM, 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.
>>
>>
>>  5. I posed as a challenge, a certain randomized class of 27-candidate
>>> elections
>>> which I designed to be hard.
>>> It seemed plausible to me that these 27-candidate elections might be too
>>> hard
>>> for current algorithms to reliably provably find the Kemeny winner.
>>> I of course do not know the winners of my challenge elections, since if I
>>> did,
>>> then a short proof would exist, which it cannot in maximally hard
>>> elections.
>>> So far, nobody has convinced me they are able to answer the Kemeny
>>> challenge,
>>> but Kristofer Munsterhjelm has preliminarily claimed in email that
>>> he's been able to solve
>>> one election sampled from my class -- which causes
>>> him to be optimistic that he can answer the challenge.
>>> We'll see -- if that is true, I don't see why K.M. hasn't completed
>>> the job, since
>>> it seems like if he's done what he thinks he has, then he's
>>> done 99% of the programming work
>>> and the remaining 1% is for some reason holding him up.
>>>
>>
>> The thing holding me up is called employment. As you may have noticed,
>> I've been less active on the list as of late -- same reason: work is taking
>> up my time and effort.
>>
>>
>>  In the event KM or somebody else successfully
>>> answers the challenge, then I'll be reasonably impressed,
>>> but then I probably can create harder challenges
>>> with greater numbers of candidates -- the goal is to
>>> try to identify the borderline between "hard" and "easy."
>>>
>>
>> I think I solved a few instances of Warren's 27x27 matrix on [0...1
>> billion], but I can't be sure since I can't confirm that my Kemeny cost is
>> indeed the least possible. I am, however, assuming that it is, and so I'm
>> looking at larger sizes. Since these will be harder, I've thought of adding
>> an initialization step where the program tells the IP solver of a reasonably
>> low-cost guess. This could speed up the process, thus letting me solve
>> greater size matrices in about the same time I currently solve 27x27.
>> However, I have not actually implemented this initialization yet (see above
>> re what's holding me up).
>>
>>
>>  6. Richard Fobes has told me and the election methods group in emails
>>> that he's got various
>>> wonderful answers to all these issues, which he sadly has never found
>>> the time to
>>> explain, including in his privately published book on the subject.  I
>>>  (a) just don't believe him.
>>>  (b) some of his "great solutions" seem to be now to recommend a
>>> hybrid of about 3 different
>>> election methods -- which he has nowhere fully defined.   This hybrid
>>> method no longer can
>>> claim either simplicity or any attractive package of nice logical
>>> properties, but it should at least
>>> make it always feasible to compute the winner..
>>>
>>
>> Kemeny would probably be best described as an optimization problem - that
>> is, something like "the winning sequence is a transitive ordering for which
>> the sum of voters who rank each candidate above the candidate just below it
>> in the ordering is maximized". Then the actual process of optimization is an
>> implementation detail, and may be as simple or complex as needed.
>>
>>
>> ----
>> Election-Methods mailing list - see http://electorama.com/em for list
>> info
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20110924/0a376e0f/attachment-0004.htm>