While waiting for my car to be worked on yesterday I pulled out a notepad and worked on the (theoretical) possibility of a machine that
1) Looks at each voter's preference order 2) Assigns each group of voters with identical preference orders an optimal (possibly mixed) strategy given the election method being used and the strategies assigned to all other voters3) Picks the winner based on the assigned strategies and the election method designated by the engineer designing the machine. The question is, do you have an incentive to submit an insincere preference order to this machine? A few months ago, some people invoked the Gibbard-Saitherwaite (sp?) Theorem to say that it's impossible to do this with a non-dictatorial machine (a "fair" but dictatorial machine would be one that conducts a lottery and the winning ballot picks the elected official, AKA Random Ballot. I say "fair" because all voters have an equal chance of being the dictator). Forest argued that since the GS Theorem doesn't consider probabilistic strategies it doesn't necessarily apply, since this machine could either include a stochastic element in its design, or assign some members of a faction to follow one strategy (the proportion being equal to the probability if we were using mixed strategies) and the rest to follow another. He further argued that if the optimal mixed strategy requires some fraction (e.g. 25%, or 1/4) of a bloc to follow a particular strategy, and that fraction of the bloc's membership is not an integer number of voters (e.g. a bloc of 17 voters, not divisible by 4), then some probabilistic method is needed to handle rounding. Here's what I came up with: In designing such a machine, the task of "assigning each faction an optimal strategy given the designated election method AND THE STRATEGIES OF THE OTHER FACTIONS" amounts to finding a Nash Equilibrium. There may be many such equilibria. This is not necessarily a problem, if all equilibria elect the same person. As a simple example, suppose that we use plurality voting and the electorate is as follows: 6% A>B>C 49% B>A>C 45% C>B>A We could have a situation where the B and C factions vote for their respective favorites, and the A faction follows a mixed strategy. As long as the mixed strategy involves the A faction giving at least 2 votes to B we have a Nash equilibrium electing B. In the above case, as long as the A faction uses the strategy of voting for B with a probability p>1/3 we have a Nash equilibrium electing B. If it is true that for any Nash equilibrium which requires pursuing strategy S with a probability p, pursuing S with a probability p+delta is also a Nash equilibrium (for delta smaller than some bound) then Forest's concern doesn't matter (for sufficiently large electorates). I don't know whether game theorists have tackled this question. However, in general we can have more than one outcome corresponding to a Nash equilibrium. In tackling that case, the machine has to use some criteria to select among the possible outcomes. Assigned strategies can't be used, since none have been assigned yet. Regardless of the method used by the machine, there will always be a faction which preferred a different Nash equilibrium, and there will always be close elections where a single unhappy faction can change the outcome by changing strategies. If we assume that they started with a sincere strategy then any strategic adjustments to protect their interests will be insincere and hence we can't design a machine that never gives you an incentive to lie (if it operates deterministically). The only remaining question is whether you can design an election method such that all equilibrium strategies give the same outcome. (The outcome cannot be the same for all electorates, but for a given electorate with a particular set of preference orders all equilibria must yield the same outcome.) This isn't quite the same as the GS theorem, since I haven't asserted that all equilibria must involve sincere strategies. We could take a method where all equilibria yield the same result, some of them using insincere strategies, and couple it to an SVM (Small Voting Machine, Super Voting Machine, Simmons Voting Machine, whatever) and make it into a method where all equilibrium strategies are sincere, since now your "strategy" is your (sincere) input to the machine, which in turns assigns a (possibly insincere) ballot. However, while I haven't thought carefully about it I suspect that such a method would be dictatorial. Once that question is answered, and the technical matter about whether pursuing the same mixed strategy with a slightly different probability is still an equilibrium, we can say goodbye to this theoretical machine. Comments? Alex Small ---- For more information about this list (subscribe, unsubscribe, FAQ, etc), please see http://www.eskimo.com/~robla/em
