On Apr 13, 5:52am, Steve Eppley wrote:
> Subject: Calculating the Smith set? > Okay, computers are cheap so Condorcet's method is more viable now > than it was in the Marquis' century. It's also possible to use > parallel processing if necessary, since the voters' ballots can > easily be divvied up. (The CxC matrices can be added together at > the end.) > What about calculating the Smith set? Is this time negligible in > comparison to tallying all the pairings? What's a good algorithm? > I presume it's much quicker than the pairwise tallies, since it's > independent of the number of voters, but I want to doublecheck. >-- End of excerpt from Steve Eppley In my very limited explorations so far, I've found that there is no clear relationship between "data requirement" and "computational effort." Some voting methods, like plurality (with a most-seconds, most-thirds, etc. tie-breaker), or single-winner STV/Hare, do not require much computational effort even though (or, perhaps, because) they have high data requirements. Condorcet's method has medium data requirements and Copeland's method has low data requirements, but this seems completely irrelevant to computational effort -- they seem (to me) to be about equal to each other computationally and both would be easy to do with a suitably programmed modern computer. However, as Steve notes for Condorcet, both are, in general, very tedious to do my hand. Like Condorcet's method, Kemeny's method has medium data requirements, but, quite unlike Condorcet and Copeland, Kemeny's method can require more computational effort than can be provided by the world's currently most powerful computers when there are many (say, 20 or more) Smith winners. As Steve notes, Smith has low data requirements. (I'm using Fishburn's (1977) definitions here, for those who want to quibble.) However, I don't see an "easy" way to calculate, in general, the Smith winners. (There are some easy special cases.) Specifically, using the algorithms I am aware of, it seems easier to calculate both the Copeland winners and the Condorcet (method) winners than it is to calculate the Smith winners. Maybe that's just because I am not aware of better algorithms. But it also might be, in fact, harder to calculate Smith winners than it is to calculate winners according to some voting methods that have medium or high data requirements, even though Smith has a low data requirement. Bruce |
Free forum by Nabble | Edit this page |