The Gibbard-Satterthwaite result doesn't rule out Alex's SVM (Small Voting Machine) when you take into account that the voting machine is supposed to apply the OPTIMAL strategy, which is sometimes a probabilistic mixture of pure strategies requiring coin tosses, die throwing, or needle spinning.
In other words, in voting methods optimal strategies sometimes require randomization, so the G-S theorem doesn't apply to the SVM, unless Alex wanted to rule out stochastic strategies, in which case he would be ruling out optimal strategies for some of the ballot sets that could be input into his machine. Think of the scissors, rock, and paper game. The optimal strategy is to spin a needle that has equal chance of landing on each of the three possible choices. Any other "system" can be thwarted. Suppose that we had a Small Rock Scissors Paper Machine (SRSPM). What would it do? The input could be the sincere preferences of the two players say R>P>S and S>P>R. Implementing the optimal strategy the SRSPM would (unlike the SVM) ignore the inputs, throw a die, and assign R, S, or P for the first player depending on whether the die came up 0, 1, or 2 mod 3. Then it would throw the die again to determine R, S, or P for the second player. Then it would compare the two results to determine which of the two players won. Put the same input in again, and the machine will probably pick a different winner. The SVM would also give different winners sometimes when the same ballot set was used as input, though the input would generally influence the expected output (except in cases of complete symmetry like cyclic tie with equal size factions). Most voters don't like randomization in voting rules. That's one of the reasons that Lorrie Cranor's Declared Strategy Voting idea didn't appeal to polled students (or Polled Herefords, for that matter). The beauty of Cumulative Repeated Approval Balloting is that the randomness required for non-manipulability is approximated by the pseudo randomness inherent in the chaos of the cyclic patterns. So the method is absolutely deterministic, but random enough to thwart insincere voting. How can something be absolutely deterministic but approximately random? Think of "random number generators" in general; they usually implement relatively simple deterministic procedures to generate a sequence of numbers. Only the most sophisticated of them take a random number from nature (like the current temperature, humidity, or time) as a "seed" for the generator. As an aside, if you ask a mathematician how to get a sequence of random numbers, he/she will say, "Go ask a physicist, all we can do is give you pseudo random sequences based on generators of various complexity." In the days before quantuum mechanics, most physicists would reply that nothing is random in nature. Einstein's famous quote on the matter was, "God doesn't throw dice." Cumulative Repeated Approval Balloting has a kind of built in random number generator for which the seed is the set of voted CR ballots. To know how to falsify your utilities to exploit this system, you would have to know all the other CR ballots in detail, i.e. know which seed was used. Guess wrong on one rating of one candidate on one ballot by just one CR level, and you have a different seed, so the sequence goes nothing like you expect it to, so you have no chance of intelligently thwarting it by falsifying your ratings. All random number generators take advantage of this "sensitivity to initial conditions" which means that if you change the seed ever so slightly, then you change the sequence beyond recognition in a few steps. So if the repeated balloting requires winning candidates to accumulate approval of at least a dozen times the number of voters, it will take enough steps to make the sequence unpredictable for practical purposes. In any case, I believe that Alex's basic idea is true. But you just have to remember that feeding the same ballot set X into the Small Voting Machine more than once may yield different winners from time to time, because the SVM uses optimal strategies, which are in general stochastic mixtures of pure strategies. In a way this result can be thought of nature's way of giving the other members of the Smith set their due. In fact it can be thought of as a temporal version of Proportional Representation. Suppose that a group of children are trying to decide whether to play baseball, kickball, football, basketball, jumprope, etc. They are smart enough to use Paper Scissors Rock to make these kinds of decisions even when there is a majority in favor of one course of action, because it yields proportional representation over time, i.e. TPR (Temporal Proportional Represention). Forest On Thu, 2 May 2002, Rob LeGrand wrote: > Alex wrote: > > Question: Can we come up with a voting method such that you never have an > > incentive to lie to the computer? If so, then it doesn't matter if your > > assigned strategy is insincere, we still satisfy strong FBC. > > See my post on the Gibbard-Satterthwaite theorem at: > > http://groups.yahoo.com/group/election-methods-list/message/8793 > > Basically, the only way to take ranked ballots as input and choose a winner so > that no voter would ever have reason to vote insincerely is to choose the > winner according to *one* of the ballots, in effect giving dictator powers to > that voter. If it's acceptable for the election method to be that random, then > it's a perfect system. Otherwise, nothing will do. Even if a Small Voting > Machine were carefully formulated and built, it would still be possible for a > voter to gain by voting insincerely. I gave a lot of thought to a similar idea > a while ago, but I gave up on it when I realized that the G-S theorem would > still apply no matter what went on inside the SVM black box. I imagine that an > SVM or Cumulative Repeated Approval Balloting would remove incentive for > insincerity about as much as would be practical, but of course the public would > be unlikely to support such complicated systems. At least with Approval, you > never have reason not to vote for your favorite, even if you can't express > every single preference. I love Richard's explanation for why the Approval > winner could be seen as preferable to the Condorcet winner when the two are > different. > > I also like the revised Bucklin idea, the one that allows multiple levels and > multiple candidates at each level. I guess revised Bucklin is to regular > Bucklin as CR is to Borda. More investigation of this idea . . . ? > > -- > Rob LeGrand > [EMAIL PROTECTED] > http://www.aggies.org/honky98/ ---- For more information about this list (subscribe, unsubscribe, FAQ, etc), please see http://www.eskimo.com/~robla/em
