加载中...
公平分蛋糕
发表于:2021-11-27 | 分类: 博弈
字数统计: 1.6k | 阅读时长: 5分钟 | 阅读量:

公平粉蛋糕

假设

  1. N个人分蛋糕,每个人都认为自己拿到的蛋糕不少于N分之一。
  2. 每个参与分蛋糕的人都绝对理性,无私下结盟协商等现象。
  3. 每个人对于蛋糕有不同的喜好,所以需要拿到自认为的不少于N分支一的那一块。(即A认为自己拿到了三分之二,B也认为自己拿到了三分之二,这种情况是正常的,因为A和B对于蛋糕的喜好部分不一样)
  4. 每个人都认为自己拿到的和别人一样或者比别人好,那这种分发就不存在有人嫉妒。反之则认为存在有人嫉妒他人。

2人分蛋糕

A和B 2人分蛋糕,由A先切蛋糕,然后由B先选择蛋糕。

  • 首先A会将蛋糕平分切成两块(A自己认为)。因为如果一块大一块小的话,B就会选择大的,那A自己就只能拿小的那块了。为了避免这种情况,A会切成自己认为利益一样大小的两块。
  • B会根据A切分后的蛋糕得出自己心里认为的份额大小(很有可能和A认为的不一样),从而选择交大的一块(2/3)。
  • A会得到剩下的一块(1/2)

A认为自己拿到了1/2的份额(不少于二分之一),而B也拿到了自己认为剩下的1/2的份额(没有比A多),所以是公平无嫉妒的。
B认为自己拿到了2/3的份额(不少于二分之一),而A拿到了1/3的份额(没有比B多),所以是公平无嫉妒的。

3人分蛋糕

存在嫉妒但简单的分法

A、B、C 3人分蛋糕。将刀从蛋糕左侧移向蛋糕右侧,当3人认为左侧蛋糕已达到自己认为的三分之一时喊停。左侧的蛋糕归第一个喊停的人(假设为A)。

由于第一个喊停的是A,所以在B和C看来,左侧蛋糕并未到达自己认为的三分之一。

  • A是否会故意不喊呢?显然是不会的,因为如果在到三分之一的时候A不喊停,那就面临被B和C喊停的情况。真的发生这样的事情,右侧的蛋糕对于A来说就小于2/3了,按照接下来公平的切分方法,会导致A拿不到自己认为的三分之一份额。

接着刀继续移向蛋糕右侧,B和C在达到剩下部分一半的时候喊停。中间这块归先喊停的人(假设先喊停的是B),最后一块归C 。

由于B先喊停,所以对于C来说中间这块并没有达到剩下的一半。

可以看出来在C看来第一块没有达到三分之一,第二块没有达到剩下的二分之一,所以自己拿到的肯定超过三分之一,并且是三块中最大的。C会认为是公平无嫉妒的。
在B看来,第一块没有到三分之一,剩下的两块是一样大小的。所以B拿到的超过三分之一,并且和C拿到的一样多,超过A拿到的。B会认为是公平无嫉妒的。
在A看来,自己拿到的是三分之一,符合了公平。但是由于第二块、第三块A并没有参与喊停,由B和C分出的2块蛋糕,如果在A看来一块大,一块小,那就存在有人比自己拿的多了。所以A会认为是公平的,但存在嫉妒。

复杂的无嫉妒分法

1 由A平均切成三块,所以A会认为三块一样大小。
2 由B和C选择最大的一块拿走。
3-1 如果B和C选择的不一样,那最后剩下的给A。

在A看来三块都一样,不存在比自己多拿的人,所以是公平无嫉妒的。
在B和C看来,自己拿到了最大的一块,所以也是公平无嫉妒的。

3-2-1 如果B和C选择了同一块蛋糕,就有B将这块蛋糕切掉一部分,使得这块蛋糕和第二大的蛋糕一样大小。
假设B和C都认为Z是最大的,都选Z,那由B将Z切成Z-1和Z-2,其中Z-1和Y一样大小(B认为)。

3-2-2 由C进行选择,规定如果C没有选择Z-1,那B必须选择Z-1。(由于这个规定,B在切蛋糕时必须把Z-1和第二大的切成一样大小,否则自己就会拿到小的)

在C看来自己是最先选择的,所以一定拿最大的,没有人比他大,所以无嫉妒。
在B看来有2块一样大小的,无论C怎么选,自己也是拿到最大的那块,所以无嫉妒。
在A看来,Z本身是三分之一大小,现在Z-1小于三分之一,并且要么C拿要么B拿,所以肯定不会有人比自己拿的大,所以无嫉妒的。

最后接着分Z-2

3-2-3-1 如果C选择Z-1,那就由B将Z-2切成三份,由C->A>B的顺序选择。
3-2-3-2 如果B选择Z-1,那就由C将Z-2切成三份,由B->A->C的顺序选择。

在A看来,Z-1和Z-2加起来才三分之一,现在Z-2进行了切分,并且在自己之前选择的人是拿了Z-1的,所以先选择的人无论怎么选都不会超过三分之一,接着由自己选,所以自己拿到的肯定是自己认为最大的,所以无嫉妒。
最后选择的人由于是自己切的,所以会认为三块是一样大小,也是无嫉妒的。
如果是C->A->B的顺序,在C看来2次都是自己先选择,自己拿的一定是最大的,肯定是无嫉妒的。
如果是B->A>C的顺序,在B看来第一次选择是自己切的Z-1,是最大的,第二次是自己最先选择,所以自己拿的肯定是最大的,是无嫉妒的。

由此三个人就能公平无嫉妒的分蛋糕了。

上一篇:
LOG4J2史诗级漏洞
下一篇:
UML之用例图
本文目录
本文目录