4
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ $J$ must be nonempty for the condition to make sense. $\endgroup$
    – ccorn
    Jan 28, 2017 at 20:48
  • $\begingroup$ @ccorn you are right. $\endgroup$ Jan 28, 2017 at 21:08
  • $\begingroup$ Let $S=3,n=2,x_1=0.159155\pi$ (approximately 0.500000179). I doubt that fair rounding would exist in this case too. It seems like there are more edge cases than you think. $\endgroup$
    – guest
    Feb 9, 2017 at 10:11
  • $\begingroup$ @guest Actually, $s_1=2, s_2=1$ is a fair rounding in this case, which coincides with intuitive answer. $\endgroup$
    – Wolfram
    Feb 9, 2017 at 22:34

1 Answer 1

5
+50
$\begingroup$

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)$.

$\endgroup$
3
  • $\begingroup$ Beautiful. So there is even a simple algorithm for finding the number of seats per party. Let $C := S$. If $f(C) = S$ then return $s_i := \lfloor x_i C \rfloor$; else let $C := C+1$ and repeat. Your proof shows that this algorithm must return after at most $n$ steps. right? $\endgroup$ Feb 10, 2017 at 13:26
  • 1
    $\begingroup$ @ErelSegal-Halevi Not quite. The jumps of $f$ occur not in integer values of $C$, but for such $C$ that one of $x_iC$ is an integer. When you increase $C$ by $1$, you can jump too high if for several $x_i$ holds $\lfloor(C+1)x_i\rfloor>\lfloor Cx_i\rfloor$. I'll add the correct simple algorithm to the post in a while. $\endgroup$
    – Wolfram
    Feb 10, 2017 at 15:27
  • $\begingroup$ How can I cite you in a paper? $\endgroup$ Dec 27, 2018 at 7:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.