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