! Given a set of numbers with fractional parts, we want to round
them to a set of nearby integers so that the integers sum to
a specified target. This problem might arise in preparing
a report where numbers are rounded to fewer digits, or
in choosing a number of representatives for each state
in a House of Representatives, based on population;
! Keywords: Rounding, Alabama paradox, Proportional representation,
ITEM: IDEALN, N;
! We want the integers to sum to NTOT;
NTOT = 100;
! Ideal values, with possible fractional parts;
IDEALN = 3.7 11.6 9.8 44.8 9.6 11.5 6.1 2.7 0.2;
DZ = 0.0000000001; ! Small number to avoid divide by 0 or
taking log(0). Allows some
N(i) = 0, e.g.,;
! Example 2;
! IDEALN = .21 .20 .18 .19 .22;
! NTOT = 1;
! Example 3: U.S. House, 1790;
! IDEALN =
18.3104 13.8027 12.5700 10.2657 9.6288
8.0876 6.8774 5.9887 5.2144 4.1183
2.4837 2.0569 1.9951 1.9876 1.6128;
! NTOT = 105;
! Example 4;
! IDEALN = .21 .20 .18 .19 .22 0 0;
! NTOT = 1;
N(i) = an integer close in value to IDEALN(i);
! The individual allocations must sum to the desired total;
@SUM( ITEM(i): N(i)) = NTOT;
! and be integer;
@FOR( ITEM(i): @GIN(N(i)));
! We want N(i) to be close to IDEALN(i);
! An obvious rounding objective (Alexander Hamilton's method);
! MIN = @SUM(ITEM(i): @ABS( N(i) - IDEALN(i)) );
! However, that objective may result in the Alabama
Paradox, i.e., if NTOT is increased, some N(i) may
in fact decrease;
! A better objective in this regard is...;
MIN = @SUM( ITEM(i): -IDEALN(i)*@LOG((N(i)+DZ)/(IDEALN(i)+DZ)));
A possibly more intuitive rearrangement is:
MAX = SUM(ITEM(j): IDEALN(j)*@LOG(N(j)/IDEALN(j)))
= SUM(ITEM(j): IDEALN(j)*(@LOG(N(j)) - @LOG(IDEALN(j)))) ;
! Think of @LOG(N(j)/IDEALN(j)) as the utility function for each person in group j.
It is < 0 if N(j)/IDEALN(j) < 1 and > 0 if N(j)/IDEALN(j) > 1.
It is increasing, so awarding more is better.
It is concave, so that later awards are not as valuable as earlier awards.
For group j, the utility per person in the group is weighted by IDEALN(j),
a number proportional to the number of people in group j.
It can also be shown that this objective gives solutions that are
"population monotone", i.e., avoid the Alabama paradox, i.e.,
if the total units to be allocated is increased, no N(j) will decrease.
The objective is concave in N(j) and so a greedy algorithm that starts
with NTOT = 1 and increments it until NTOT is the desired
value will find an optimum and the Alabama Paradox cannot occur.
By a similar argument it can be shown to be component monotone,
i.e., if the inputs change so that IDEALN(j) increases and IDEALN(k) decreases,
and all others stay the same, then N(j) cannot decrease and N(k) cannot increase.
If N(j) = 0, there will be a "divide by zero" numerical error.
If IDEALN(j) = 0, there will be a "log(0)" numerical error.
Therefore a small number dx is added to each in log( ) to avoid these errors.