I think I have found a way to help the design of multiwinner methods.
As you may know, I've been using a proportionality measure to find the
degree to which multiwinner methods give proportional representation,
and along with Bayesian regret, to define the current Pareto front of BR
versus disproportionality for multiwinner methods that we know of. Some
of these tradeoff results are given at
http://munsterhjelm.no/km/elections/multiwinner_tradeoffs/ .
Some time ago, I was playing with numbers, trying to figure out how many
distinct ranked ballot sets exist for a given number of voters and
candidates. Because we would expect any reasonable voting method to obey
neutrality and symmetry (invariance under permutations of voter and
candidate orders), the number of distinct ranked ballot sets turn out to
be much smaller than I expected.
If we consider ranked ballots without equal rank or truncation, then the
number is (n + k - 1) choose k, where k is the number of voters - 1, and
n is the factorial of the number of candidates.
For 3 candidates, we have, for instance:
num voters = 10, num ballot sets = 2002 (11 bits)
num voters = 25, num ballot sets = 118 755 (17 bits)
num voters = 50, num ballot sets = 3 162 510 (22 bits)
num voters = 100, num ballot sets = 91 962 520 (27 bits)
So with a small number of voters, we could store the mean
disproportionality and regret for all possible ballot sets, and if each
set has a sufficient number of samples, we could look up any given
ballot set and simply see how disproportional each outcome is, on average.
What does that give us? My proportionality metric works by giving each
candidate and voter a certain binary issue profile, where a given voter
is either for or against a given issue. Then it constructs ballots that
are consistent with this: voters rank candidates with like issue
positions ahead of those with dissimilar positions; and the
proportionality per issue of the outcome picked by a multiwinner method
can be compared in terms of how many of the council members are in favor
of issue one (two, n) versus how many of the voters are so.
However, that metric starts from issue profiles and generates ballot
sets. It can't go in the other direction by itself. Yet with the
"tablebase" - a map from ballot sets to sets of performance numbers - we
can do so easily. By noting the disproportionality of every outcome for
the ballot sets as we encounter those ballot sets, we can build a record
of the function so as to invert it afterwards.
And how does that help in mechanism design? Usually, for two-of-three
elections, the pattern is that one outcome is dominated by the other two
(i.e. the other two have both lower regret and disproportionality), and
then one outcome is more proportional but has more regret, and the last
outcome has less regret but is less proportional also. By looking at
these ballot sets and outcomes, we can try to come up with rules that
keep the dominated solutions from being picked.
Inverting the proportionality metric would also make it possible to
determine the Pareto front for all ranked methods within the binary
issue model given (and the constraints on number of candidates and
voters). A brute-force approach would simply note that each possible
decisive method has to give an outcome for all (or most of) the ballot
sets, and plot the Pareto front of the performance of every possible
outcome combination. But if there are 1000 ballot sets and 3 possible
outcomes for each, that's 3^1000, which is clearly infeasible. Dynamic
programming can probably make it feasible again.
Regarding criteria, the map could be used to find out how much a certain
criterion constrains outcomes. That could be done directly as well
(without the need for storage), but using a map could give some idea of
how passing a criterion limits the Pareto front, too.
Finally, one could use the tablebase to make a Yee diagram for an
"optimal" method (again, given the constraints and model). Just define
an indifference function (how much disproportionality people are willing
to accept for lowered majoritarian regret), then when given a certain
ballot set by the Yee generator, determine which outcome is best
according to the indifference function and respond as if the (unknown)
method chose that outcome. It isn't trivial, though: Yee drawing usually
involves having hundreds if not thousands of voters. Perhaps one could
use some sort of repeated sampling or antialiasing to get a conclusive
result even with <100 voters per sample.
----
Election-Methods mailing list - see http://electorama.com/em for list info
