[EM] Bishop's DMD decomposition
Warren Smith
wds at math.temple.edu
Fri Nov 25 13:34:03 PST 2005
I have examined this issue before in an unpublished paper whch I can
tell you about in separate email.
Anyhow, the thing is that some, but not other, Condorcet matrices are
actually achieveable as arising from actual sets of ballots.
Which ones are achievable? Well, you can tell by solving an
"integer program." In many cases of non-achievability you can
prove it by proving no solution exists of the assciated
"linear program." If it is achievable then this IP solution will
in fact construct a set of ballots for you, that does the job.
I suspect that these IPs and LPs are in general hard to solve
(not in polynomial time) although if the number of candidates is bounded
it is in P.
Now Bishop actually suggests an algorithm (or at least sketches one)
which allegedly will find a ballot set if one exists (if one does not exist,
then what? Bishop does not say what happens then). That is an interesting conjecture.
If it is true, that is quite nice because then, for one thing, it would
disprove my non-polynomial-time difficulty-conjecture. Does Bishop's algorithm
actually work? I do not know. You could try to prove it works by proving that
removing the Bishop-vote from te Condorcet matrix cannot change the achievability
(or lack thereof) of that matrix - and you might be able to do that using my
IP and LP formulations of achievability.
Warren D Smith warren.wds at gmail.com
More information about the Election-Methods
mailing list