How to round numbers fairly

Question

There are $n$ positive numbers, $x_1+\ldots+x_n = 1$, and a number $S$.

A fair rounding is a set of $n$ integers, $s_1+\ldots+s_n = S$ such that:

$$\forall i\in\{1,\ldots,n\}:~~ \forall J\subseteq\{1,\ldots,n\}:~~ s_i \geq \bigg\lfloor \frac{x_i}{\sum_{j\in J}x_j}\cdot \sum_{j\in J}s_j\bigg\rfloor $$

In particular, $\forall i\in\{1,\ldots,n\}:~~ s_i \geq \lfloor x_i\cdot S \rfloor$.

This can be interpreted as a method for apportionment of seats in congress. In the elections to the congress, there were $n$ parties, and each party $i$ received a fraction $x_i$ of the total votes. There are $S$ seats in the congress, and we want to determine how many seats $s_i$ to allocate to party $i$. Ideally, we would give each party exactly $x_i\cdot S$ seats, but this number is not an integer, so we have to round it. Naturally, each party demands that its fraction will not be rounded 'too much', i.e, each party demands at least its fractional share $x_i\cdot S$ rounded down to the nearest integer. Moreover, this requirement should hold not only in the general population, but also when we compare each party $i$ against any other subset of parties $J$: party $i$ should get at least its fractional share of the seats of the subset $J$, rounded down to the nearest integer.

A fair rounding might not exist if some fractions are equal. For example, if $S=3$, $n=2$, $x_1=x_2=0.5$, fairness requires that $s_1=s_2$, but this is not possible since $s_1+s_2$ is odd. To prevent such edge cases, let's assume that all fractions are different, and moreover, there is no linear combination of fractions with integer coefficients that equals 0.

Under these conditions, does there always exist a fair rounding?

Answer 1

Yes.

I claim that there exists a fair rounding even under weaker conditions: if there are no identities of the kind $ax_i=bx_j$, where $i\ne j; a,b\in\mathbb Z; a,b <S+n$ (which are more likely in practice than irrational relations on the votes :).

Let us temporary forget about the condition $\sum_is_i=S$ and concentrate only on the inequalities of fairness. If we redefine fair rounding without the sum condition, the following lemma holds:

Lemma. For any positive real $C$ the numbers $s_i=\lfloor Cx_i\rfloor$ form a fair rounding.

Proof. $$\bigg\lfloor \frac{x_i\cdot \sum_{j\in J}s_j}{\sum_{j\in J}x_j}\bigg\rfloor\le\bigg\lfloor x_i\frac{\sum_{j\in J}Cx_j}{\sum_{j\in J}x_j}\bigg\rfloor=\lfloor x_iC\rfloor=s_i\ \ \ \ \ \ \ \square$$

Now consider the function $f(C)=\sum_{i=1}^n\lfloor Cx_i\rfloor,f\colon\mathbb R_+\to\mathbb Z$. Clearly, $f$ is non-decreasing, $f(S)\le S$ and $$f(S+n)>\sum_{i=1}^n((S+n)x_i-1)=S,$$ so for some $S\le C< S+n$ either $f(C)=S$ or $f$ jumps at least by two in $C$. The latter means that $$Cx_j=a\in\mathbb Z,\ Cx_i=b\in\mathbb Z$$ for two different indices $i$ and $j$. However, using $x_i,x_j\le 1$ and $C<S+n$, we obtain $a,b<S+n$ and $ax_i=ab/C=bx_j$, which contradicts my initial assumption. Thus, $f(C)=S$, and we can safely take $s_i=\lfloor Cx_i\rfloor$.

Algorithm. Calculate $L_i=\lfloor Sx_i\rfloor$ and $R_i=\lfloor (S+n)x_i\rfloor$ for every $i$ and sum $\sum_iL_i=f(S)$. Denote $k=S-f(S)$. If $k=0$, we won: $C=S$. [$O(n)$ operations by now]

Otherwise, $k>0$, and we need to find the $k$-th value of $C$ among such that $C>S$ and $Cx_i\in\mathbb Z$ for some $i$. We already know that such $C$ is somewhere between $S$ and $S+n$, so for each $i$ the relevant values include $C_i=\{(L_i+1)/x_i,(L_i+2)/x_i,\cdots,R_i/x_i\}$, since $L_i/x_i\le S$ and $(R_i+1)/x_i>S+n$. So we just form an array that is the union of all $C_i$ and pick its $k$-th (by size) element: this is the desirable value of $C$. The number of elements in $C_i$ is not greater than $x_in+1$, therefore $$|\bigcup_iC_i|\le\sum_i(x_in+1)=2n$$

Thus there are $O(n)$ elements in our array, and $k$-th largest can also be found in $O(n)$ using median of medians. Total complexity is $O(n)$, which obviously cannot be improved since the input size is $O(n)$.