Fair allocation of seats

General condition

There are 200 students in the three departments (100 in Department A, 60 in Department B, 40 in Department C), and a total of 20 representative meetings are allocated proportionally. The three departments have 10, 6, and 4 seats respectively:

	A	B	C
200 in total	100	60	40
proportion	50%	30%	20%
20 seat	10	6	4

Customary allocation / Maximum surplus

When the number of people in the three lines becomes 103,63,34:

	A	B	C
200 in total	103	63	34
proportion	51.3%	31.5%	17%
20 seat	10.3	6.3	3.4
actual distribution	10	6	3+1

When the number of seats is increased to 21:

21 seat	10.815	6.615	3.57
actual distribution	10+1	6+1	3

In this way, seats are awarded to the person who has more seats, and the person who increases the least is (possibly) stripped of his or her seat. This is unfair, because there are more seats, and C gets fewer seats.

Fair allocation

Defining index

Symbolic assumption

	A	B
people	$p_1$	$p_2$
seat	$n_1$	$n_2$
people per seat	$p_1/n_1$	$p_2/n_2$

Absolute unfair value

$$if\frac{p_1}{n_1}>\frac{p_2}{n_2}$$$$Absoluteunfairvalue=\frac{p_1}{n_1}-\frac{p_2}{n_2}$$

Relative unfair value

$$r_A(n_1,n_2)=\frac{Absoluteunfairvalue}{cardinalnumber}=\frac{\frac{p_1}{n_1}-\frac{p_2}{n_2}}{\frac{p_2}{n_2}}$$

Our target is to minimize $r_A$ and $r_B$.

Definite allocation scheme

Transform one-time seat allocation into dynamic seat allocation.

Let A and B have $n_1$ and $n_2$​ seats respectively. If one more seat is added, ask whether it should be allocated to A or B?

Assume that at the beginning of allocation:

$$\frac{p_1}{n_1}>\frac{p_2}{n_2}$$

it's not fair to A.

if:

$$\frac{p_1}{n_1+1}>\frac{p_2}{n_2}$$

That is, even if one more seat is given to A, the scene is still unfair to A, then this seat should go to A.

if:

$$\frac{p_1}{n_1+1}<\frac{p_2}{n_2}$$

It's A little more complicated in this case, if the seat is given to A, it's unfair to B. It's a time to weigh who's best for the bigger picture.

if:

$$r_B(n_1+1,n_2)<r_A(n_1,n_2+1)$$$$\frac{p_2^2}{n_2(n_2+1)}<\frac{p_1^2}{n_1(n_1+1)}$$

At this point the seat should be given to A. Because it makes the relative unfair value smaller.

Q-value method

Formula

If there are only two groups of people:

$$Q_i=\frac{p_i^2}{n_i(n_i+1)},i=1,2$$

If there are m groups of people:

$$Q_i=\frac{p_i^2}{n_i(n_i+1)},i=1,2,...,m$$

At the end of the day, whoever has the highest Q value is allocated to whoever.

Apply

	A	B	C
200 in total	103	63	34

Each department is assigned a seat:

$$n_1=1,n_2=1,n_3=1$$

The next 18 seats are determined using Q values.

$${19}^{th}seat:n_1=10,n_2=6,n_3=3$$$${20}^{th}seat:$$$$Q_1=\frac{{103}^2}{10\times 11}=96.4$$$$Q_2=\frac{{63}^2}{6\times 7}=94.5$$$$Q_1=\frac{{34}^2}{3\times 4}=96.3$$$$n_1=11,n_2=6,n_3=3$$$${21}^{th}seat:$$$$Q_1=80.4,Q_2=94.5,Q_3=96.3$$$$n_1=11,n_2=6,n_3=4$$

Idealized criterion

Suppose that the number of people in m departments is $p_1,p_2,...,p_m$, the total number of seats to be allocated is N, the ideal seat allocation scheme is $n_1,n_2,...n_m$.

$n_i$ is a function of N and $p_1,p_2,...,p_m$, so that $n_i=n_i(N,p_1,...,p_m)$, assume $q_i=N{p}_i/P,i=1,2,...,m$.

If all $q_i$ are integer, $n_i=q_i$ (ideal).

If not all $q_i$ are integer:

$$\begin{array}{}\text{(i)}& [q_i{]}_{-}\le n_i\le [q_i{]}_{+},i=1,2,...,m\end{array}$$$$\begin{array}{}\text{(ii)}& n_i(N,p_1,...,p_m)\le n_i(N+1,p_1,...,p_m),i=1,2,...,m\end{array}$$

The second formula means that when the total number of seats increases, no one $n_i$ should decrease.

The general method satisfies i but does not satisfy ii, and the Q-value distribution method satisfies ii but does not satisfy i.

Particular case

First here are the python code to simulate Q value assignment:

def q_value(p, n):
    lst = []  # seats
    for i in p:
        lst.append(1)  # initial seats are all 1
    lst_ = lst[:]  # Q value
    for i in range(n - len(p)):
        for i in range(len(p)):
            lst_[i] = p[i] * p[i] / (lst[i] + 1) / lst[i]
        max_index = lst_.index(max(lst_))
        lst[max_index] += 1
    print(lst)


if __name__ == '__main__':
    p = [103, 63, 34]
    n = 21
    q_value(p, n)

Then use the following code violence to solve, you can get a special case. In fact, there are many such exceptions, and I will only ask for the first one here:

def q_value(p, n):
    lst_rate = []  # seats
    sum_ = sum(p)  # people
    for i in p:
        lst_rate.append(i / sum_ * n)
    # lst_rate存的是比例分配的小数值

    lst = []  # seats
    for i in p:
        lst.append(1)  # initial seats are all 1
    lst_ = lst[:]  # Q value
    for i in range(n - len(p)):
        for i in range(len(p)):
            lst_[i] = p[i] * p[i] / (lst[i] + 1) / lst[i]
        max_index = lst_.index(max(lst_))
        lst[max_index] += 1

    for i in range(len(lst)):
        if abs(lst[i] - lst_rate[i]) > 1:
            # 如果Q值算出来和小数值差1以上就不满足条件1，返回
            print(p, n, lst, lst_rate)
            exit(0)


if __name__ == '__main__':
    for i_1 in range(200, 1000):
        for i_2 in range(200, 1000):
            for i_3 in range(200, 1000):
                for i_4 in range(200, 1000):
                    for i_5 in range(200, 1000):
                        p = [i_1, i_2, i_3, i_4, i_5]
                        n = 243
                        q_value(p, n)

[200, 200, 200, 200, 488] 
243 
[38, 38, 38, 38, 91] 
[37.732919254658384, 37.732919254658384, 37.732919254658384, 37.732919254658384, 92.06832298136646]