[EM] "Tablebases" and inverting proportionality models

[Kristofer Munsterhjelm]

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.