相对公平的席位分配
最后更新于:2022年6月25日 下午
“公平”的席位分配首先本来就是不可能的,公平一般是无法达到的,我们只是尽量降低不公平度,那么我们怎么衡量不公平度呢。就像评价一个人,有不同的指标,不公平度也是一样,这里介绍一种相对合理易于接受,且好判断的方法。
问题表述
某学校三个系部学生共 200 名,(甲系 100,乙系 60,丙系 40)代表会议共 20 席,按比例分配三个系分别为 10、6、4 席。但是情况变为下列情况怎样分配才是最公平的,现因学生转系三系人数为 103、63、34 。
- 问 20 席该如何分配 ?
- 若增加 21 席又如何分配 ?
显然,因为无法整除无论如何分配都不公平。下面说一下几种策略。
策略一: 按班级人数比例乘以总人数,小数点大的分得多余的一个位子。
某校 | 甲系 | 乙系 | 丙系 |
---|---|---|---|
共 200 人 | 103 | 63 | 34 |
人数比例 | 51.3 | 31.5 | 17 |
20 席位 | 10.3 | 6.3 | 3.4 |
实际分配 | 10 | 6 | 4 |
21 席位 | 10.82 | 6.62 | 3.57 |
实际分配 | 11 | 7 | 3 |
按照上述策略,会出现席位增多而 丙系的席位却减少了一个的不合理现象,说明此方法并不合理。
模型建立
假设只有 A、B 两个单位分配席位的情况,设两方人数 \(m_1,m_2\) ,分配到的席位为 \(n_1,n_2\)。
\(\frac{n_1}{m_1} = \frac{n_2}{m_2}\) 公平,但是一般是不满足的。
\(\frac{n_1}{m_1} > \frac{n_2}{m_2}\) 对 A 不公平。
\(\frac{n_1}{m_1} < \frac{n_2}{m_2}\) 对 B 不公平。
绝对不公平度 \[ d = \left| \frac{n_1}{m_1} - \frac{n_2}{m_2} \right| \] 但这样做还是有不足,例如 某两个单位的人数和席位为 \(n_1=n_2=10,m_1=120,m_2=100\) 算得 \(d=2\). 另两个单位的人数和席位为 \(n_1=n_2=10,m_1=1020,m_2=1000\) 算得 \(d=2\)。 但是显然,第二种情况更公平,但是(绝对)不公平度却是一样的不合理
相对不公平度
若 \(\frac{n_1}{m_1} < \frac{n_2}{m_2}\) 则 \[ r_A(n_1,n_2) = \frac{ \frac{n_2}{m_2} - \frac{n_1}{m_1} }{ \frac{n_2}{m_2} } = 1 - \frac{n_1 m_2}{m_1 n_2} \]
若 \(\frac{n_1}{m_1} > \frac{n_2}{m_2}\) 则 \[ r_B(n_1,n_2) = \frac{ \frac{n_1}{m_1} - \frac{n_2}{m_2} }{ \frac{n_1}{m_1} } = 1 - \frac{n_2 m_1}{m_2n_1} \] 我们的目标是让\(r_A,r_B\)(每种分配只会有一个)最小。
策略二
假设当前 \(\frac{n_1}{m_1} < \frac{n_2}{m_2}\) 对 A 不公平。新增了一个席位。
- 若 \(\frac{n_1 + 1}{m_1} \leq \frac{n_2}{m_2}\) 则 A 加 1 席
- 否则此时
- 若分配给 A,则对 B 的不公平值(相对): \[ r_B(n_1+1,n_2) = 1 - \frac{n_2 m_1}{m_2 (n_1 + 1)} \]
- 若分配给 B,则对 A 的不公平值(相对): \[ r_A(n_1,n_2+1) = 1 - \frac{n_1 m_2}{m_1(n_2 + 1)} \]
我们定义 \(Q_i = \frac{m_i ^2}{n_i(n_i+1)}\),那么分配给 B 等价于 \(r_A(n_1,n_2+1)<r_B(n_1+1,n_2)\) 等价于\(Q_1 < Q_2\)。即我们应该将席位分配给 \(Q\) 值较大者。
讲 \(Q_i\) 定义成 \(Q_i = \frac{n_i(n_i+1)}{m_i ^2}\) ,然后找最小的比较合理,不过这样会有小数点太长,所以没这么做
模型求解
先按照平均原则取整之后。分出了 19 席:\(n_1=10,n_2=6,n_3=3\),第 20 席: \[ Q_1 = \frac{103^2}{10 \times 11 } \approx 96.4 \; , \;Q_2 = \frac{63^2}{6 \times 7} \approx 94.5 \; , \;Q_3 = \frac{34^2}{3 \times 4} \approx 96.3 \] 则分配:\(n_1=11,n_2=6,n_3=3\) 第 21 席:\(Q_1=80.4, Q_2 = 94.5, Q_3 = 96.3\) 则分配:\(n_1=11,n_2=6,n_3=4\).
相对不公平度有很多变种,从而 策略二有很多变种(最后计算发现都一样)
莫非策略二就是天选之子 0.0
本文参考文库 1和文库 2,修改了其中的错误
其实作为分配者,如果你倾向 X,那你就选择让 X 收益最多的策略,反正 策略一 看上去也挺合理的,实在不行的话,再强行找花头...
由于席位分配问题确实是一个经典问题,故在此记录。