A thought that occurred to me the other day:
Say that a method is manipulable whenever it elects A and a group that prefers B to A can modify their ballots in such a way that B is elected after the modification. Then we could in principle determine the least manipulable method by minimizing the number of elections where this is possible. To put it another way, we could get something like Venzke's DNA but on a much larger scale. Consider every possible election that involves say, four voters and three candidates, with complete rankings and no equal rank. There are 3! = 6 different ways to rank and 4 voters, so 126 different elections. In the absence of ties, that would be 3^126 different methods (either A wins, B wins, or C wins for each). With ties, it would be 2^(3*126) instead (true/false: three per election as to who wins). But I think it's possible to minimize manipulability by using an integer programming formulation. Whether this is actually tractable is another matter, but it can't be worse than brute-forcing. For each election k [1...126], let election_n(k, B>A) be the number of elections where at least one of the B>A voters changed one of their ballots. Then let election(k, B>A, p) be one such election. Clearly, the number of different values of p can at most be 126. Then election k is manipulable if the assigned winner for k is A and: there exists some election(k, B>A, p) where B wins or there exists some election(k, C>A, p) where C wins (same goes for the case where B wins or C wins). Or in linear implication terms, suppose election(x)(A wins) is 0 if A doesn't win, and 1 if A does win, then: manipulable(k, if A wins) >= election(k, B>A, 0)(B wins) >= election(k, B>A, 1)(B wins) .... >= election(k, C>A, p)(C wins) manipulable(k, and A wins) >= manipulable(k, A wins) - (election(k)(B wins) + election(k)(C wins)) manipulable(k) = manipulable(k and A wins) + manipulable(k and B wins) + manipulable(k and C wins), with all free variables being binary. The second statement forces manipulable(k, and A wins) to be true if neither B nor C actually wins, and manipulable(k, if A wins) is true. The third statement then sums up manipulability over every candidate. Then the LP/IP formulation is simply: minimize sum over all k: manipulable(k) for impartial culture, and minimize sum over all k: p(k) * manipulable(k) for other election models, with p(k) being the probability of getting that election in that model. We'd probably also need some basic criteria like neutrality (of all the possible elections, A must win or be tied for first in a third of them, and same for B and C; and that in an election where every permutation of the candidates gives the same election, you must have a three-way tie). The objective function gives a bound on how unmanipulable *any* ranked system can be in this particular setting (e.g. 4 voters, 3 candidates, all voting weights integer), and would give an indication as to whether e.g. IRV is close to that bound. As a side effect, the election(k)(X wins) free variables will provide a partial election method that meets that bound. I may have been a bit sloppy in defining manipulable(k, if A wins). It should strictly speaking take ties into account: being able to go from one election where A and B are tied, to another where A and B are tied, does not constitute successful manipulation, even if (A wins) is true for the first election and (B wins) is true for the second. But accommodating ties may lead to the pathological "smartass" election method that always produces a three-way tie no matter what election it is. Perhaps there's a way to insert the reinforcement/resolvability constraint? I don't remember its actual name at the moment, but the one that says, if there's a tie, then there must exist at least one election you can get to by altering the ballots so that there's no longer a tie. Perhaps that's what forces integer programming instead of just linear. Some constraints are easy to impose as they simply say "in election X, Y must win/Z mustn't win". For these types of constraint just let election(k)(A wins) = 1, election(k)(B wins) = 0, election(k)(C wins) = 0 if A's the required winner (e.g. CW) in the kth election. A program could easily check all 126 and import the necessary forced outcomes into the linear program. Dynamic criteria like monotonicity are harder. Suppose we can go from election b (for before) to a (for after) by raising A on a ballot. Then monotonicity says that if A wins in b, then A must win in a too. If we know neither a nor b will have any ties, then it's easy to impose this constraint: election(a)(A wins) >= election(b)(A wins) will do. This forces "A wins" to be true on a if "A wins" is true on b. However, ties complicate matters more. If A wins with certainty in b, and A ties with B in a, then that's still a violation of monotonicity even if A wins in both. I can see three possible options: 1. use integer programming and "big M" constraints to force that the number of winning candidates cannot increase from b to a - but only if A is already the winner in a. 2. let the winner indicators be integers instead of binary, so that election(q)(A wins) = 6 if A wins with certainty, 3 if there's one other candidate A ties with, and 2 if A ties with both (0 if A doesn't win), with an additional constraint that the sum over all candidates for a particular election should be 6. Then the greater-than constraint above still works, because it implies that A must tie with no more candidates in a than he does in b. The problem is that the values {5, 4, 1} are undefined and have to be forced to be unassigned somehow. 3. drop integer programming and let the free variables be probabilities (that a given candidate is elected, e.g. 1/3 in a perfect three-way tie). The problem is that this allows for methods that leave too much to chance, like random ballot. As an example of the use of such a formalization: I suspect that a method that elects only from the uncovered set must by necessity be considerably more manipulable than a method that elects only from the Smith set. I have no proof of this, only a hunch from that Landau,IRV does worse than Smith,IRV. But solving the integer program for a low number of voters and for four candidates (the minimal number of candidates where someone can be in the Smith set but still be covered) could show whether that is actually the case. Without knowing what the least manipulable four-candidate uncovered and Smith-consistent methods are, the program could be used to determine how manipulable these methods are in the (limited) domain of only a few voters. From Monte-Carlo experiments, it seems that not many voters are needed to distinguish Landau,IRV's performance from Smith,IRV's. I think I found four or five sufficient. OTOH, the integer program might still be unsolvable. I wouldn't know until I try it. ---- Election-Methods mailing list - see https://electorama.com/em for list info |
Hi Kristofer, Isn't 4 voters an unfortunate number for this purpose, due to all the ties you would have? On permitted ballot types, it seems like you don't plan to allow much. My (most recent) DNA system supports more ballot types (bullet voting, equal ranking, and ranked-but-disapproved), but maybe by limiting these options, an interesting question could be answered by exhaustively analyzing DNA possibilities. The major limitations of DNA are: 1. each candidate has to be top-ranked by one of the three voting blocs. We can speculate that strict majority favorites would have to be elected, but such scenarios have no location in the DNA string. 2. DNA strings can't be uniquely determined for methods that can't be resolved knowing only the ranking of faction sizes. A scheme with four equal-sized voters would avoid that problem. So if we at least allow bullet voting, each faction has 3 ways to vote (X, X>Y>Z, X>Z>Y), there are 27 scenarios, and at least 3^27 methods (assuming no ties). I guess that is a lot. If we only allow complete strict rankings, there are only 8 scenarios and 6561 methods, and I've sort of already analyzed this. Except it's in terms of criteria, not overall manipulability. I think there are at most a dozen reasonable methods there. There is not much freedom. the cycles: A>B, B>C, C>A: A usually wins; Bucklin picks B; BPW (beats-plurality-winner cyclebreaker) picks C. A>C, B>A, C>B: A usually wins; IRV, C//IRV, and BPW pick B; some odd methods (QR) do pick C. where the plurality loser is the CW: A>C, B>C, C>A: C is more common; IRV and DAC/DSC pick A. A>C, B>C, C>B: C wins except under IRV, which picks B. where the CW is in majority coalition with the plurality winner: A>B, B>A, C>B: B usually wins; DAC/DSC picks A. MinMax is probably the least manipulable in this setting, but it would be interesting to measure it. Kevin
Le mardi 25 février 2020 à 17:24:38 UTC−6, Kristofer Munsterhjelm <[hidden email]> a écrit :
A thought that occurred to me the other day: Say that a method is manipulable whenever it elects A and a group that prefers B to A can modify their ballots in such a way that B is elected after the modification. Then we could in principle determine the least manipulable method by minimizing the number of elections where this is possible. To put it another way, we could get something like Venzke's DNA but on a much larger scale. Consider every possible election that involves say, four voters and three candidates, with complete rankings and no equal rank. There are 3! = 6 different ways to rank and 4 voters, so 126 different elections. In the absence of ties, that would be 3^126 different methods (either A wins, B wins, or C wins for each). With ties, it would be 2^(3*126) instead (true/false: three per election as to who wins). But I think it's possible to minimize manipulability by using an integer programming formulation. Whether this is actually tractable is another matter, but it can't be worse than brute-forcing. For each election k [1...126], let election_n(k, B>A) be the number of elections where at least one of the B>A voters changed one of their ballots. Then let election(k, B>A, p) be one such election. Clearly, the number of different values of p can at most be 126. Then election k is manipulable if the assigned winner for k is A and: there exists some election(k, B>A, p) where B wins or there exists some election(k, C>A, p) where C wins (same goes for the case where B wins or C wins). Or in linear implication terms, suppose election(x)(A wins) is 0 if A doesn't win, and 1 if A does win, then: manipulable(k, if A wins) >= election(k, B>A, 0)(B wins) >= election(k, B>A, 1)(B wins) .... >= election(k, C>A, p)(C wins) manipulable(k, and A wins) >= manipulable(k, A wins) - (election(k)(B wins) + election(k)(C wins)) manipulable(k) = manipulable(k and A wins) + manipulable(k and B wins) + manipulable(k and C wins), with all free variables being binary. The second statement forces manipulable(k, and A wins) to be true if neither B nor C actually wins, and manipulable(k, if A wins) is true. The third statement then sums up manipulability over every candidate. Then the LP/IP formulation is simply: minimize sum over all k: manipulable(k) for impartial culture, and minimize sum over all k: p(k) * manipulable(k) for other election models, with p(k) being the probability of getting that election in that model. We'd probably also need some basic criteria like neutrality (of all the possible elections, A must win or be tied for first in a third of them, and same for B and C; and that in an election where every permutation of the candidates gives the same election, you must have a three-way tie). The objective function gives a bound on how unmanipulable *any* ranked system can be in this particular setting (e.g. 4 voters, 3 candidates, all voting weights integer), and would give an indication as to whether e.g. IRV is close to that bound. As a side effect, the election(k)(X wins) free variables will provide a partial election method that meets that bound. I may have been a bit sloppy in defining manipulable(k, if A wins). It should strictly speaking take ties into account: being able to go from one election where A and B are tied, to another where A and B are tied, does not constitute successful manipulation, even if (A wins) is true for the first election and (B wins) is true for the second. But accommodating ties may lead to the pathological "smartass" election method that always produces a three-way tie no matter what election it is. Perhaps there's a way to insert the reinforcement/resolvability constraint? I don't remember its actual name at the moment, but the one that says, if there's a tie, then there must exist at least one election you can get to by altering the ballots so that there's no longer a tie. Perhaps that's what forces integer programming instead of just linear. Some constraints are easy to impose as they simply say "in election X, Y must win/Z mustn't win". For these types of constraint just let election(k)(A wins) = 1, election(k)(B wins) = 0, election(k)(C wins) = 0 if A's the required winner (e.g. CW) in the kth election. A program could easily check all 126 and import the necessary forced outcomes into the linear program. Dynamic criteria like monotonicity are harder. Suppose we can go from election b (for before) to a (for after) by raising A on a ballot. Then monotonicity says that if A wins in b, then A must win in a too. If we know neither a nor b will have any ties, then it's easy to impose this constraint: election(a)(A wins) >= election(b)(A wins) will do. This forces "A wins" to be true on a if "A wins" is true on b. However, ties complicate matters more. If A wins with certainty in b, and A ties with B in a, then that's still a violation of monotonicity even if A wins in both. I can see three possible options: 1. use integer programming and "big M" constraints to force that the number of winning candidates cannot increase from b to a - but only if A is already the winner in a. 2. let the winner indicators be integers instead of binary, so that election(q)(A wins) = 6 if A wins with certainty, 3 if there's one other candidate A ties with, and 2 if A ties with both (0 if A doesn't win), with an additional constraint that the sum over all candidates for a particular election should be 6. Then the greater-than constraint above still works, because it implies that A must tie with no more candidates in a than he does in b. The problem is that the values {5, 4, 1} are undefined and have to be forced to be unassigned somehow. 3. drop integer programming and let the free variables be probabilities (that a given candidate is elected, e.g. 1/3 in a perfect three-way tie). The problem is that this allows for methods that leave too much to chance, like random ballot. As an example of the use of such a formalization: I suspect that a method that elects only from the uncovered set must by necessity be considerably more manipulable than a method that elects only from the Smith set. I have no proof of this, only a hunch from that Landau,IRV does worse than Smith,IRV. But solving the integer program for a low number of voters and for four candidates (the minimal number of candidates where someone can be in the Smith set but still be covered) could show whether that is actually the case. Without knowing what the least manipulable four-candidate uncovered and Smith-consistent methods are, the program could be used to determine how manipulable these methods are in the (limited) domain of only a few voters. From Monte-Carlo experiments, it seems that not many voters are needed to distinguish Landau,IRV's performance from Smith,IRV's. I think I found four or five sufficient. OTOH, the integer program might still be unsolvable. I wouldn't know until I try it. ---- Election-Methods mailing list - see https://electorama.com/em for list info ---- Election-Methods mailing list - see https://electorama.com/em for list info |
Free forum by Nabble | Edit this page |