A few months ago we discussed the SVM and the Strong Favorite Betrayal Criterion. I haven't solved the problem of Strong FBC, but I have some thoughts on the matter that might help us answer the question.
(As a reminder, the SVM is a machine that takes each voter's preference order as input, assigns to each voter an optimal strategy given everybody else's preferences, to achieve a Nash equilibrium, where no voter has an incentive to change his strategy. The question is whether one ever has an incentive to rank somebody equal to his favorite candidate when giving input to the machine. If so then it violates the Strong Favorite Betrayal Criterion. The weak criterion is that you should have no incentive to rank another candidate above your favorite.) First, must the machine be deterministic? Yes. We already have a non-deterministic election method that satisfies strong FBC: Random ballot. If we�re going to admit non-deterministic election methods to satisfy strong FBC then there�s really no point in building the machine. However, I don�t know anybody (except maybe Alan Natapoff, who likes the Electoral College because it increases your odds of casting the deciding vote) who wants a method where you gamble on having the deciding vote. Second, in general, a game can have more than one Nash equilibrium. If for a given voting method and electorate there are two or more different outcomes that correspond to Nash equilibria the machine has a decision to make. There are two ways to resolve this: The first is to first figure out what all possible Nash equilibria are, given an electorate and election method. If more than one outcome is possible then we need to choose among those equilibria. We can�t use the strategies assigned to the voters because the machine HASN�T assigned any strategies yet. It has looked at our preferences and all possible strategies, sincere or insincere, that could be assigned to us, and figured out what the equilibria might be. The machine must therefore use some criteria to choose the winner from the set of outcomes possible with Nash equilibria. We�ve already ruled out a random selection. The criteria must therefore be based on our inputs. All that the machine has done is eliminate those candidates who can never win under the circumstances of Nash equilibria. By applying criteria based on the entire electorate, however, it no longer performs its function of assigning us strategies that are in our own best interests. It is formally equivalent to an election method without the intermediary of this machine that assigns us strategies. The other way for the machine to operate is to start from an initial condition (presumably the ballots we inputted), find a winner according to whatever method it�s using, and then modify our strategies in light of what everybody else is doing. Continue until we reach an equilibrium and then stop. (In principle it could find more than one equilibrium, but not necessarily all equilibria, and then choose among the equilibria already identified. However, that also places us in a situation formally equivalent to an election without the intermediary of the machine.) Operating by sequential adjustments may not find equilibria, but instead produce periodic behavior. (See Brams and Fishburn for a discussion of how polls can produce such outcomes in Approval Voting.) For instance, under sincere voting the winner might be candidate A. Those who dislike A might then make adjustments which result (wittingly or unwittingly) in the election of B. Those who dislike B can then make adjustments that lead to the election of C. Those who dislike C might make adjustments leading to the election of A. This periodic problem can be fixed by introducing "damping": If cyclical behavior ensues the machine could randomly assign a certain fraction of the voters to stop making adjustments after each step. (This might emulate a real-life situation, where people tire of responding to ever-changing polls during the campaign and finally decide they'll just vote sincerely on election day and take their chances). Continue until we reach a point where no voter has any incentive to change his strategy, even if he hadn't already given up in disgust. (The damping can be deterministic, since the machine can have a pre-determined rule for which fraction of voters will keep their previous strategies after each step, and for how to round numbers.) THE QUESTION: Will a machine that operates via sequential adjustments, with damping thrown in to get rid of oscillations, give voters an incentive to lie to the machine? MY ANSWER: Yes. The final outcome produced by such a voting machine depends deterministically on the initial conditions. Consider the vector (N(input 1), N(input 2).....) where each element of the vector is the integer number of voters who gave the machine each input. This vector contains all possible information on the initial state of the machine. With n candidates we can divide the input space into n regions, each region corresponding to all possible inputs that will result in the election of a particular candidate (the regions need not be connected or simply connected). If the initial condition is near the boundary of two different regions, such that there is at least one voter who can change his ballot and move to a different region of input space, then in general there can arise situations where one of those swing-voters has an incentive to vote insincerely. What I have not demonstrated is that the incentive to vote insincerely can include an incentive for a voter to rank somebody greater than or equal to his first choice. Let's assume that the input consists of cardinal utilities, with a scale that has an arbitrarily large number of levels (e.g. 0 to 10, 0 to 100, 0 to 6*10^23, whatever you like). Consider two adjacent points on opposite sides of a boundary (adjacent meaning that we can move from one to the other if a single voter changes his ballot). If at one of those points a particular voter distinguishes between his first and second choices, and at the other point the voter gives 2 candidates a tie for 1st place, AND the voter in question prefers the outcome that occurs with a tie, then strong FBC is violated. The whole problem comes down to how the input space is partitioned. The election method used by the SVM determines which strategies will improve the outcome for a voter or group of voters, and hence which strategies the machine will assign to voters and what the final outcome will be given inputs. We need to find a voting method that partitions input space in such a way that strong FBC can never be violated. I don't know whether this gets us anywhere, or whether it merely restates the problem, but it's something to think about. I do know that I�ve narrowed down the number of ways in which the machine can operate, and given a geometric criterion for strong FBC violations. Actually, if we limit ourselves to a deterministic machine, then doesn�t the Gibbard-Sitherwaite (spelling?) theorem hold? If so, then the only real question is whether it�s reasonable for me to limit the machine to a deterministic mode of operation, which amounts to asking whether I was right to argue that we might as well use random ballot once we admit non-deterministic strategies. Incidentally, if the SVM can't satisfy strong FBC then this suggests that it is impossible for parties to always give good advice to their members. By affiliating with a party you reveal by implication information on your preferences and utilities. However, the impossibility of always satisfying strong FBC means that even if the party had perfect info on the other voters (via polling) it couldn't give you good advice. Parties then have no choice but to compromise on some issues. By coming up with policies that aren't in perfect harmony with the preferences of their core supporters they essentially force their supporters to vote somewhat insincerely. However, the compromises help parties win by bringing in swing voters, similar to reeling in voters to cross from one region of input space to another. Maybe not a perfect analogy, but interesting.... Anyway, that�s all for now, folks. Alex ---- For more information about this list (subscribe, unsubscribe, FAQ, etc), please see http://www.eskimo.com/~robla/em
