On Fri, 25 Nov 2005 16:34:03 -0500 Warren Smith wrote: > 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.
That puzzles: If a Condorcet matrix is an array produced by Condorcet rules from a set of ballots, then the actual set of ballots WOULD be achievable, though other sets of ballots producing the same matrix might also be achievable. However, an array of numbers produced in some other way could be either truly (or not) achievable via Condorcet rules from some set(s) of ballots. Not clear from this distance whether it might be worth the pain. > > 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 [EMAIL PROTECTED] -- [EMAIL PROTECTED] people.clarityconnect.com/webpages3/davek Dave Ketchum 108 Halstead Ave, Owego, NY 13827-1708 607-687-5026 Do to no one what you would not want done to you. If you want peace, work for justice. ---- election-methods mailing list - see http://electorama.com/em for list info