Often we have to round some numbers in such a way that the sum is correct afterwards. The most obvious case is maybe with percentage values, where a sum other than 100% is confusing for readers. But we may even have cases where a calculation becomes incorrect if the some constraint is violated. Anyway it can be useful to do some more advanced stuff behind the scenes to fulfill such a constraint. Now we could hope for the rounding operation to be an Endomorphism of the additive group, that means . At first glance it makes sense, error often compensate each other to make this true, but we can find counter examples for our usual rounding methods. Just think of the numbers . We have . Now we us a typical rounding method and we get . So it is no endomorphism, one counterexample is enough.
Is this any kind of new concept? Obviously we find printed media or web pages that are showing percentage values in such a way that they cheated for the partial values to have the anticipated sum. But it shows that such things happen officially every four years. We have events that are called „elections“ and parties or lists can be voted for. The parliament usually has a fixed number of members and if we disregard specialties that make the whole game more complex in some countries, in order to keep it accessible to logic, it is quite the same thing. Now parliament membership should be distributed according to the percentages of the popular votes. If we have seats in the parliament, we have to round the exact percentages (as fractions of long integers) to multiples of in such a way that the sum is correct. There are may established procedures for achieving this and depending on the procedure the result may differ a little bit. Did I mention the word „cheating“ above? No, we do not talk about cheating by deliberately counting wrong, off course nobody ever wanted to do something like that, but about ways to enforce an end result that uses up exactly the given number of parliament seats. Which procedure is considered to be the fairest changes almost every other year a little bit. Interestingly an equivalent issue occurs when distributing legislative seats to region. Even in the United States, where congressmen are elected by getting the plurality of votes in their district, this is applied to deciding how many congressmen will represent each state, in this case with the constraint that each state should have at least one congress seat (plus two senators).
If we do not need to write an election software, the question is often less delicate. For example a text should contain the sum of some rounded values in a reasonable accurate way. The majority of the readers will be happy. The very critical reader who knows anyway what I am writing here, will be happy as well, if it has been done well enough with inevitable cheating in the last digits. It should be observed that this seemingly trivial issues is quite involved, for example see apportionment paradox–
As described in residue class rounding, we define sets and with a metric and want to deal with maps having kept small and possibly some other constraints. But since the correction („cheating“) should be part of the mapping, we are here rather looking at a mapping
with and for all the value of is „small“. We could say, that the sum has to be rounded as well, but often it is already rounded. Think about the details of your special case when they occur and read the concepts… Purely rounding up or down will not work unless we have an exact edge case. We could desire to minimize error squares, which has the advantage that larger deviations have a larger effect, encouraging equal distribution of the corrections, for example we want
minimal. It is possible to find examples that are non-unique. In this case a rule can be defined or random numbers can be used to resolve.
Another approach would be to minimize relative errors, like
, skipping summand with because they do not create any issues if we have . Usually we do want to round to .
A good alternative is to just look at the Apportionment methods for parliaments and the underlying algorithms and adjust them for the required usage:
- D’Hondt method
- Hagenbach-Bischoff system
- Largest remainder method
- Hill-Huntington method
- Sainte-Laguë method
Often our requirements may be different and especially lower in terms of the quality of the rounding than for parliament apportionment, but it is a good idea to think twice about this prior to just doing something naïve without thinking.
Question: how are the apportionment methods behaving in terms of absolute and relative error square optimization?
If there is serious interest, I might provide an implementation in some real programming language.
Often we encounter problems similar to this that can be deduced to this. Who has ever thought that parliament apportionment is actually an act of rounding?
Here are some links to interesting pages and papers about algorithms and other topics related to this issue.
- Divisor Methods for Sequential Portfolio Allocation …
- Biproportional Sainte-Laguë: Made Simple
- Webster’s Apportionment MethodMoonwise: d’Hondt election calculations
- D’hondt in PHP
- The Hamilton Apportionment Method Is Between the Adams Method and the Jefferson Method
- Proportional Allocation in Integers
- Book: Proportional Optimization and Fairness
- A majorization comparison of apportionment methods in proportional representation
- Disproportionality indexes and robustness of proportional allocation methods
- BAZI: a free Java program
- BAZI (2)
- BAZI (Download)
- Literature List
- BAZI: Pseudo Code
- BAZI (3)
- Mathematics and Democracy: Recent Advances in Voting Systems and Collective …
von Bruno Simeone,Friedrich Pukelsheim
- Paper about BAZI
- Seat allocation distributions and seat biases of stationary apportionment methods for proportional representation
- Divisor Methods for Sequential Portfolio Allocation in Multi-Party Executive Bodies: Evidence from Northern Ireland and Denmark (second link)
- Putting citizens first: Representation and power in the European Union
- Asymptotic Equivalence of Seat Bias Models
- Why does nobody in Britain seem to pay any attention to voting rules?
- Maxmin Formulation of the Apportionments of Seats to a Parliament
- A divisor apportionment method based on the Kolm–Atkinson social welfare function and generalized entropy
- A Mathematical Exploration of Apportionment Procedures Around the World
- Divisor Methods
- Don’t let the lawyers do the math: Some problems of legislative districting in the UK and the USA
- Linear-time Algorithms for