[EM] Automatic Criterion Checking

[Jobst Heitzig]

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