Kevin Venzke wrote:
Hi Kristofer,
--- En date de : Mer 19.5.10, Kristofer Munsterhjelm <[email protected]> a
écrit :
Perhaps there's a way to chaff out the wrong methods before
having to evaluate them. One way of doing so would be to
relate new methods to their common old methods - if the old
tester's "DNA" is a subset of the new one, you might know
that all methods that have the first three "old DNA
characters" as A, B, and C respectively would fail
Plurality.
Yes, actually all the "static" criteria are defined this way internally.
Plurality for example is defined as "ADAADAEXEDDDDDDXXXEXEEXEEXE".
Out of curiosity (and possible interest in reproducing this), what does
that mean? I imagine "A" means "must be A at this spot" and X is
"doesn't matter what is here", but what's D and E?
For "dynamic" criteria like LNH*, mono-add-top, or burial criteria,
the logic is hard-coded, comparing the results of connected scenarios.
But if you can find the error you can also fix it (at least until you
then try to fix something else).
The huge problem is not really speed (at least with this level of
complexity) but the question of how do you represent, as concisely as
possible, a "method" and a "scenario"? Currently a method is a list of
all outcomes, which clearly won't work if a scenario is allowed to be
anything you can think of.
If the problem is not speed, it might be of interest to try all 7.6
trillion methods. While 7.6 trillion sounds like a lot, it's just 43
bits, and 40 bits crypto keys are easily cracked. The idea would be that
just checking and discarding is quicker than checking, fixing, and
checking again.
Also, if you find, say, Plurality invaluable, you'd now know you only
need to check methods starting in A and with #3, #4, and #6 set to A as
well. That cuts your space down from 3^27 to 3^23 - 37 bits.
As for the second part, that is indeed a problem. As far as I can see,
there are two solutions: either to use a small number of
scenarios/possible methods and generalize from them, or to use a large
space (perhaps the 6D space of all three candidate preferences) and some
sort of heuristic or proof mechanism to find reasonable methods. They
both have strengths and weaknesses.
One thing you could do is try to define methods in terms of metrics
(abstracted from actual ballots) that *might* be of interest, such as
pairwise contests. But it would be hard to make that very comprehensive:
I don't know how you would represent IRV this way, for instance. It
could also be difficult to be sure that you're doing justice to the
criteria you want to check.
If you can have conditionals, then you can define IRV for three
candidates. Say A > B > C in Plurality order, then
if A beats B pairwise
then A
if B beats A
then B
else tie
because C must lose (by the definition, C is eliminated), and the
ballots remaining (A vs B, B vs A) are equal to the respective pairwise
counts.
It might be possible to define methods working on the tournament matrix
as an array itself. The possible outcomes would be:
Condorcet winners:
A beats B, A beats C
B beats A, B beats C
C beats A, C beats B
Cycle:
A > B > C > A (same as B > C > A > B, C > A > B > C)
A > C > B > A (same as B > A > C > B, C > B > A > C)
thus providing a Condorcet/tournament matrix method definition of 5
ternary digits (3 for the CWs, 2 for the cycles), where the candidates
are sorted in your Plurality order. If you want to introduce strength of
preference into it, you could expand on the cycles so that the winner
with the greatest margin (WV, etc) appears first in the cycle, e.g:
A > B > C > A (A beats B more than B beats C)
A > C > B > A
B > A > C > B
B > C > A > B
C > A > B > C
C > B > A > C
giving 9 ternary digits in total (who the winner is supposed to be, base
4 if ties are possible).
A further expansion would do the same for Condorcet winners to make
non-Condorcet methods, e.g:
A beats B, A beats C (A beats B more than A beats C)
A beats C, A beats B
B beats A, B beats C
B beats C, B beats A
C beats A, C beats B
C beats B, C beats A
for a total of 6+6 = 12 "trits" - 6 for the CW case and 6 for a cycle.
To handle IRV, you'd have to add "incomplete beat parameters" that would
either decide a winner (if the DNA is set to non-tie for that position)
or just continue to the next in squence if it's set to tie; that would
expand the DNA to base-4.
The burial resistant (but nonmonotonic) "BPW" method (in 3-cand case,
elect the one who beats the Plurality winner the most) would require a
mathematical operator as well, I think.
I'm not sure how you'd determine say, the schemata for Plurality upon
such a DNA, though, since the DNA defines how the method works rather
than its results on certain scenarios. 3^9 is 15 bits so it shouldn't be
needed - you could just brute-force your way through by generating
ballot sets until either it shows a failure or the program assumes it
likely that the method passes the criterion. (3^12 is 20 bits, and 4^12,
24.)
You could also try to find particularly "discriminating"
tests for the methods and criteria by storing the examples
that show a method fails a certain criterion. Say you have a
priority queue of 1000 example ballot configurations that
have proven prior methods to fail monotonicity. Go through
all of them, increasing the count (priority) if any of them
shows the method to fail monotonicity. If none do, generate
random ballot sets, and if you find one that does show the
method to fail monotonicity, replace the lowest priority
example with this ballot set. If there are particularly
discriminating examples (like a monotonicity failure that
can be generalized to all weighted positional systems),
those examples should rise to the top.
Yes, I could see that being useful if the number of possible scenarios
got that high.
It could also be interesting as an end in itself. If some examples are
harder to break than others, these could be used in testing new methods.
Most likely, there will be some examples that cover certain classes of
methods and others that cover others - there wouldn't be a "one true
monotonicity failure example".
I think a good way to extend it would be to have a
hierarchy, so that each greater "DNA" contains the less
detailed "DNA" in it. That way, you can exclude many methods
at once, making it easier to search for needles in the
haystack.
Yes, that would be useful. The big question though is how to encode
additional scenarios into DNA. It has to be systematic for it to be
possible to write code to traverse "ballot space."
One thing I considered this morning is providing the three factions
one to three "split vote" options representing dividing the bloc in
half, each half with a different second preference or lack of. But you
have a "half of what?" problem. We only know the bloc size order, not
what combinations of half-blocs are larger than which. We could make
assumptions but the methods we'd end up with would probably not translate
very easily to the real world.
How do you get around this problem for the blocs you're already testing?
The DNA can presumably code for which bloc is larger than the others,
but not the extent to which one bloc is larger than the others. To some
extent, the problem is limited by that A is always the plurality winner,
but it wouldn't remove the problem completely.
If other approaches fail, one approach might be to try to determine what
scenarios are most common - based on what real world ballot data we do
know. I think Tideman has a database of that, as does OpenSTV for
multiwinner elections.
----
Election-Methods mailing list - see http://electorama.com/em for list info
