< 上一个 | 内容 | 下一个 >

7.3.4 可分割物品的公平分配

如前文所述,对于可分割的物品在探究公平性时主要考虑的是无嫉妒分配和比例公平分配。相比于比例公平分配,无嫉妒分配的实现更加困难也更具挑战性,大量研究者致力于此方面的研究。本节主要介绍可分割物品的无嫉妒分配的研究成果。

分和选”(Divide and Choose)是一种在两个参与者之间公平分配

蛋糕等可分割资源的方法。它涉及一种异质物品或资源(“蛋糕”)和两个对蛋糕各部分有不同偏好的参与者。该方法过程如下:一人(“切蛋糕者”)将蛋糕切成两块;另一人(“选蛋糕者”)选择其中一块;切蛋糕者得到剩下的一块。这一程序自古以来就被用于在双方之间分配土地、蛋糕和其他资源。

“分和选”是无嫉妒分配:两个参与者中的每一个都能保证,根据自己的主观喜好,无论另一个参与者做什么,自己分配到的份额至少和另一个份额一样有价值。以下是每个参与者可以采取的行动:切蛋糕的人可以把蛋糕切成他们认为相等的两块。然后,无论选择者做什么,他们都会剩下一块与另一块同样有价值的蛋糕。选择者可以选择他们认为更有价值的一块。这样,即使切蛋糕的人把蛋糕切成了很不相等的两块(在选择者看来),选择者仍然没有理由抱怨,因为他们选择了在自己看来更有价值的那一块。

Selfridge-Conway Procedure 尽管两个参与者的无嫉妒分配十分自然并且可以追溯到很古早的时期,三个参与者的无嫉妒分配却一直困扰研究者们多年,直到 1960 年出现的 Selfridge-Conway 方法解

决了这一问题。[15] 该方法的简单的流程示意如下:

1)参与者 1 将蛋糕三等分(按照他自己的喜好)。

2)参与者 2 选择跳过(如果他认为至少有两块蛋糕都是他最喜欢的)。或者选择切割(将最喜欢的一块切割到与第二喜欢的一块估值相等)。如果参与者 2 选择了跳过,则按照参与者 321 的顺序依次取一块,此时分配完成。

3)如果参与者 2 选择切割,则按参与者 321 的顺序依次取一块,并且参与者 2 取走被切割的一块(如果参与者 3 没有选择这块)。此时,仅剩下被切割下去的部分还未分配。

4)参与者 2 3 中拿到没被切割的蛋糕的人作为新的切蛋糕的人将未分配的蛋糕平均分成三块。然后按照:不是切蛋糕的人,参与者 1,切蛋糕的人的顺序依次取一块。此时分配完成。

该方法通过有限次的切割实现了在三个参与者的情况下的无嫉妒分配。

Stromquist Procedure 该方法是针对三个参与者的无嫉妒分配,于 1980 年由 Walter Stromquist 提出,并以他的名字命名[16] 。该方法的简单流程示意如下:

1)一把参照刀在蛋糕上从左到右移动,将蛋糕分为左右两部分。

2)与此同时,三个参与者移动他们自己的刀将右半部分的蛋糕按他们的喜好分为相等的两部分。

3)第一个叫停的参与者拿走左半部分的蛋糕。右半部分的蛋糕被三个参与者中落在最中间的刀分成两块(X Y)。剩下的两个参与者中,如果没有一个人持有右半部分蛋糕中最中间那把刀则分别拿走右半部分蛋糕中自己刀所在一侧的一块蛋糕(X Y)。如果有人持有右半部分蛋糕中最中间的那把刀则另一个人拿走右半部分蛋糕中自己刀所在一侧的一块蛋糕(X 或者 Y),剩下的人拿走最后一块蛋糕


X 或者 Y)。

每位参与者在这个过程中要根据自己的衡量标准,其他玩家不会得到比自己更多的东西来叫停:始终握住你的刀,使其将右半部分蛋糕分成在你眼中相等的两块(因此,你的刀最初将整个蛋糕分成相等的两块,然后随着参照刀向右移动而向右移动)。当左边与你即将得到的部分相等时,叫停(即如果你的刀在最左边,则当左边等于中间时,叫停;如果你的刀在最右边,则左边等于右边时,叫停;如果你的刀在中间,如果左边等于中间等于右边时,叫停)。

尽管该方法的流程简单并且相较于Selfridge-Conway 方法更加易于理解,但该方法假设了两人同时叫停的概率为零,假设了蛋糕无限可分,在现实中不易于实现。

可分割物品的公平分配问题一直深受关注,有大量相关研究。近些年又有很大进展:例如,Aziz Mackenzie 2016 年提出了四个参与者的无嫉妒分配,并且只需 203 次切割。同年二人又提出了对于 n 个参与者,实现无嫉妒分配的操作次数的下界为𝛺(𝑛2)[17]