[EM] Bishop's DMD decomposition

[Dave Ketchum]

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   warren.wds at gmail.com

-- 
  davek at clarityconnect.com    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.