[EM] Proportionality vs utility: Droop quota and feasible points

[Kristofer Munsterhjelm]

I added a method to determine the feasible regions of proportionality vs 
VSE for methods that elect from certain sets, to my simulator.

This works by taking the convex hull of the boundary of the set so far, 
and then creating a set of new points by, for each convex hull point, 
and for each possible outcome inside the set for that round, adding the 
proportionality and utility values for that outcome to that convex hull 
point. Doing so produces a new point set, and the convex hull is set to 
the convex hull of the new point set.

As long as the model space isn't too small,[1] the convex hull should 
then characterize the region of every nondeterministic method that could 
be designed that elects from the set in question.

By using the set of all outcomes (all possible councils), the region 
shows what tradeoffs are possible. Every point outside the region is 
infeasible - it's impossible to make a method that good (or that bad).

By using the set of every outcome compatible with the Droop 
proportionality criterion, the region shows what results a method that 
passes the DPC can get. And at least for this model, it's surprisingly 
large: the Droop proportionality criterion doesn't seem to be a very 
strong constraint.

I've added some graphs showing these regions for the same parameters as 
in my previous post. Getting gnuplot to work properly is kind of a pain, 
so excuse the lower effective resolution (thicker lines). The blue 
region is for methods passing the Droop proportionality criterion, while 
the green is what's feasible at all. (The white areas are impossible to 
reach.)

-km

[1] For the technical details, the convexity only approximately holds. 
Suppose we have a model where there are only two possible elections, 
call them eA and eB, and two candidates (A and B). Sometimes, electing A 
in eA is the best, other times, electing B in eA is the best; and the 
same for eB.

If we only consider deterministic methods, then disregarding ties, there 
are only four possibilities:
	method W: elect A in eA, B in eB
	method X: elect A in eA, A in eB
	method Y: elect B in eA, A in eB
	method Z: elect B in eA, B in eB.

Suppose these are at the edges of the chart, i.e. these solutions 
correspond to (-1, -1) for W, (1, -1) for X, (1, -1) for Y, and (1, 1) 
for Z. There's no way to get, say (0, 0), although this is a convex 
combination of the four possible outcomes. But it is possible if we're 
nondeterministic: then a method that behaves like W 50% of the time and 
Z the other 50% of the time would have an expected result of (0, 0).

But if the model is very small (there are few elections), then what can 
happen is that the edges are too optimistic. In the example above, every 
time an eA election favors A, the convex hull will be updated with 
(among others) the results of a method that somehow guesses A; and every 
time it favors B, the convex hull will be updated with (among others) 
one that guesses B. So it not only contains nondeterministic methods, 
but "improbably lucky" ones.

If the model's election space is large, then the chance that the same 
election will occur more than once during a simulation should be small 
enough that this shouldn't be a problem. Since the binary model has 
5..260 voters, I don't think this "improbably lucky" scenario is going 
to be a problem... but I might just add a test for elections that have 
been seen in the past, just to be sure, later.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: droop_far_out.png
Type: image/png
Size: 21735 bytes
Desc: not available
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20240911/3ae829ca/attachment.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: droop_full_plot.png
Type: image/png
Size: 20130 bytes
Desc: not available
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20240911/3ae829ca/attachment-0001.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: droop_detailed.png
Type: image/png
Size: 21690 bytes
Desc: not available
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20240911/3ae829ca/attachment-0002.png>