Lindo Systems
! The Rounding problem. (RoundRep.lng)
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;
! Ref:
Balinski, M. and H. Young (2001), Fair Representation, Meeting
the Ideal of One Man, One Vote, 2nd ed., Brookings Institution Press.
! Keywords: Alabama paradox, Hamilton's method, Hill's method, Jefferson's method,
Multi-criteria, Proportional representation, Rounding, Webster's method,
Utility function;
SETS:
ITEM: IDEALN, N;
ENDSETS
DATA:
! 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, some group must get 0;
! IDEALN = .21 .20 .18 .19 .22;
! NTOT = 1;
! Example 3: U.S. House, 1790;
! NTOT = 105;
! 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;
! Example 4, handling of zero entitlement;
! IDEALN = .21 .20 .18 .19 .22 0 0;
! NTOT = 1;
! Example 5, may not achieve lower quota;
! IDEALN = .333 .333 .333 .333 100.668;
! NTOT = 102;
! Example 6: U.S. House of Representatives, 1900;
NTOT = 386;
IDEALN =
37.606 32.625 24.960 21.523 16.083 15.783 14.523 13.027 12.533 11.554
11.474 11.116 10.703 10.460 9.804 9.751 9.599 9.467 9.058 8.031
7.680 7.613 7.152 6.939 6.790 6.150 5.520 4.964 4.703 3.595
2.791 2.736 2.669 2.219 2.141 2.131 2.022 1.779 1.628 1.425
1.204 0.956 0.826 0.479 0.211;
! Example 7: Rounding previous numbers so they sum to exactly to 386, rather
than 386.03;
! NTOT = 386000;
! IDEALN =
37606 32625 24960 21523 16083 15783 14523 13027 12533 11554
11474 11116 10703 10460 9804 9751 9599 9467 9058 8031
7680 7613 7152 6939 6790 6150 5520 4964 4703 3595
2791 2736 2669 2219 2141 2131 2022 1779 1628 1425
1204 956 826 479 211;
ENDDATA
! Variables:
N(i) = an integer that should be 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);
! Each of the objectives below can be viewed as choosing
a utility function for each state and then maximizing
the sum of the utilities.
A particularly attractive one is a variation of the log utility;
! A)(Alexander Hamilton's method) An obvious rounding objective is;
! 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;
! B) Thomas Jefferson's method. Scale the IDEALN( i) up by
a common factor, SCALE, so that when the SCALE*IDEALN(i)
are rounded down, they sum to NTOT. Make SCALE as large
as possible;
! MAX = SCALE;
! @FOR(ITEM(i):
N(i) >= SCALE*IDEALN(i) - 0.99999;
! N(i) >= 1; ! No zeroes allowed;
! );
! C1) Daniel Webster's method;
! MIN = @SUM(ITEM(i): (N(i)^2)/(IDEALN(i)+DZ) );
! This is equivalent to:
! MIN = @SUM(ITEM(i): IDEALN(i)*(N(i)/(IDEALN(i)+DZ) - 1)^2 );
! C2) Daniel Webster's method in another way. Scale the IDEALN(i) by
a common factor, SCALE, so that when the SCALE*IDEALN(i)
are rounded to the nearest integer, they sum to NTOT. Make SCALE as large
as possible;
! MAX = SCALE;
! @FOR(ITEM(i):
N(i) >= SCALE*IDEALN(i) - 0.5;
! N(i) <= SCALE*IDEALN(i) + 0.5;
! N(i) >= 1; ! No zeroes allowed;
! );
! Joseph Hill's method;
! MIN = @SUM( ITEM(i): N(i)*((( IDEALN(i)/( N(i)+DZ)) -1)^2) );
! D) A better objective in this regard is...(Similar to Hill's method);
MIN = @SUM( ITEM(i): - IDEALN( i)*@LOG(( N(i)+ DZ)/( IDEALN( i)+ DZ)));
! Motivation:
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.
Alternatively, you might argue that any party with IDEAL( j) = 0 should be removed.