Dear Brian! > I wish we had nice clean definitions of our favorite criteria that were > amenable to automatic checking. Then we just implement any new method in a > few lines of code, and run the checker. In most cases I believe the > computations could be completed in a few hours or a few days on any of our > common home computers.
That is a great idea indeed! Some basic criteria are certainly amenable to automatic checking, especially when they only involve one profile of preferences. Although this checking will probably be limited to 4 or 5 candidates so that the check will not bring a proof, I think that that number of candidates will still be a very good indicator for compliance. When we think of the usual counter-examples it seems that they require more than 5 candidates only in very rare cases. > Combinatorics: > For C choices and V voters. There are factorial(C) possible ranking > preferences for a voter. Multiply that by V voters and you get "any set of > voters". If you mean a preference profile by "set of voters" then that formula is wrong unfortunately: When each of the V voters can vote in C! possible ways, then the group can behave in (C!)^V and not only in C!V ways, that is, there are (C!)^V preference profiles. The number of ways a voter can vote is even larger when ties or approval cutoffs or binary preference relations are allowed. But for many combinations of method and criterion there is a much better way to test the criterion than by testing all possible preference profiles! When both the method and the criterion can be formulated in terms of defeats and precedence of defeats, then it will suffice to simulate all possible directions and precedence orders of the defeats. For c candidates X1,...,Xc, there are d:=c(c-1)/2 pairs of candidates, hence 2^d possible combinations of defeat directions. When we make use of symmetry, we can assume without loss of generality that X1>X2>...>Xc, hence we need only consider 2^(d-(c-1))=2^((c-2)(c-1)/2) many combinations of defeat direction. Multiplied with the number of possible defeat precedence orders d!, we get a total of s(c) := 2^((c-2)(c-1)/2)*(c(c-1)/2)! many combinations we must simulate, independently of the number of voters! Even for only few voters, this is much smaller than c!^v: For example: c v s(c) c!^v ----------------------------------------------------- 4 3 8*6! = 5,760 24^3 = 13,824 5 5 64*10! = 232,243,200 120^5 = 24,883,200,000 You could test the following criteria with this, I think. W always denotes the winner, DPO is the defeat precedence order: Condorcet, Smith: Run all (c(c-1)/2)! DPOs before turning to the next of the 2^((c-2)(c-1)/2) combinations of defeat directions. Then you need to determine the Smith set only once. In this way you can also test whether the winner is in any other kind of interesting set like the Uncovered Set, Banks Set, Minimal Covering Set, Tournament Equilibrium Set, Markov Set etc. Monotonicity: For each non-winning candidate X do: (i) If W>X, exchange W>X with the defeat above it in the DPO; if X>W and there is a defeat below it in the DPO, exchange them; if X>W and it is the weakest defeat, turn it around to W>X. (ii) Recompute the winner and report failure if it differs from W. Immunity from binary arguments: Apply a fast algorithm to find all strongest beatpath strengths from W to other candidates. For each X defeating W, test whether W>X is weaker than the strongest beatpath from W to X and report failure if not. Weak immunity from binary arguments: For each X defeating W, test whether W>X is weaker than the strongest defeat against X and report failure if not. ISDA, IWDA, Cloneproofness with 1 clone: For each non-winning candidate X do: Test whether X is strongly dominated, weakly dominating, or a clone of another candidate, respectively. If so, remove it, recalculate the winner, and report failure if it differs from W. 3-Consistency: Determine whether there is a candidate which wins all of its 3-wise comparisons. If so, report failure if it differs from W. In case of 4 candidates, test in this order to test only as much as necessary: 1. Test a subset {A,B,C}. Let's say A wins. 2. Test {A,B,D}. 3. If A wins in {A,B,D}, test {A,C,D}. 4. If D wins in {A,B,D}, test {A,C,D}, then if D wins there too, test {B,C,D}. In case of 5 candidates, test in this order: 1. Test a subset {A,B,C}. Let's say A wins. 2. Test {A,D,E}. 3. If A wins in {A,D,E}, test {A,B,D}, {A,B,E}, {A,C,D}, and {A,C,E}, but only as long as A wins. 4. If D wins in {A,D,E}, test {D,A,B}, {D,A,C}, {D,B,C}, {D,B,E}, and {D,C,E}, but only as long as D wins. 5. If E wins in {A,D,E}, do likewise with E and D exchanded. I'm curious how fast these implementations will be... Yours, Jobst ---- Election-methods mailing list - see http://electorama.com/em for list info