[EM] Compromise allocation of fair share

[fsimmons at pcc.edu]

The purpose of this message is to show the "proportionality" of allocation when
it is determined by maximizing the product of ballots in the form of functions
that are homogeneous of degree one in the proportion vector p.

Let  p = (p1, p2, ...) represent the proportion vector for allocation of seats
to the respective parties P1, P2, etc.  In other words, if there are N seats
distributed according to p, then the respective parties get N*p1, N*p2, etc. seats.

Hypothesis:

Suppose that p is chosen by maximizing the product  (over f in some set Beta of
ballots) of  f(p),  subject to p being an allocation vector (i.e. having
non-negative components summing to 100%).

We assume that each function f in Beta is positive homogeneous of degree one in
p, which means that for all positive t, the equation 
f(t*p)=t*f(p)
obtains, and furthermore that f is positive when all of the components of p are
positive, and also that f is non-decreasing in the components of p.

Conclusion:

If a party P1 has a fraction  n/M  of the voters, and these voters vote in
solidarity the same ballot function  f(p)=p1, then the above product
maximization will allocate to party P1 the share N*n/M of seats (up to
rounding), where N is the total number of seats.

To prove this we will make use of Euler's theorem on homogeneous functions that
says 

if  F  is homogeneous of degree m, 
then  dot(grad(F(p)),p)=m*F(p).

This theorem is easily proved by differentiating both sides of the equation that
defines homogeneity of degree m,

F(t*p)=F(p)*t^m,

with respect to t, and then setting t=1.

Now assuming that there are n+m=M voters total, and that n of these vote the
function f(p)=p1, then the product to be maximized is

F(p)*p1^n

where F is the product of the ballots of the other m voters, and hence is a
homogeneous function of degree m.

To maximize we set up the Lagrangian

L = ln(F(p)*p1^n)/M - lambda(p1+p2+...)

which simplifies to

L = (ln(F(p)) +ln(p1)*n)/M - lambda(p1+p2+..)

Taking partial derivatives w.r.t. the components of p and setting to zero, and
then taking the dot product with p we get

(dot(grad(F(p)),p)/F(p)+n)/M - lambda = 0 .

By Euler this simplifies to

(m+n)/M - lambda = 0

from which it follows that the Lagrange multiplier has a value of lambda=1.

Now that we know the value of lambda, let's go back and look at the partial
derivative of L w.r.t. p1 multiplied by p1, i.e. the first term in the dot product:

F1(p)*p1/F(p)/M + n/M -p1=0 ,

where F1 is the partial of F w.r.t. p1.

Adding p1 to both sides (and switching sides) gives

p1= n/M +F1(p)*p1/(F(p)*M), 

which is at least n/M,

since, by hypothesis,  the neglected term is a quotient of products of
non-negative values.

So the method says that party P1 should get at least n/M of the seats, i.e.
n*N/M seats up to rounding, which is what we set out to prove in the first place.