论文部分内容阅读
如何分一块蛋糕？你可能会认为答案非常简单。根据人数，把蛋糕切成相应的分数，只要大小差不多，不就可以了？
其实，这个问题非常复杂。例如，分糕的本意是让大家都吃得开心，但总有一些意外情况会让有些人不欢而散，比如，有的人非常讨厌草莓，但你按照上述分糕方法，很有可能恰恰给他们分了有草莓的那一块，还有的人可能会觉得自己手中分到的蛋糕小，感觉很不公平。说到这里，也许现在你已经明白了，我们不只是在谈论蛋糕，而是在谈论公平分配的问题。
在生活的许多方面，都涉及到“分糕”，比如如果在学校住宿，你会遇到分配宿舍床位的问题。在家里，家务也需要分配，再大一点，在法律政治领域，法官该如何判刑，税收该收多少，高考政策该如何向贫困地区倾斜，这些也可以简化为一个“分糕”问题。当我们弄懂了一个蛋糕该如何分配，这些问题其实都可以解决。然而，到底该怎么分配呢？为了简化，我们不妨先从如何科学地分一块蛋糕或者一个宿舍开始。
我分，你选择
现在我们假想一个简单的情形，假如两个孩子都要吃一块蛋糕，蛋糕只有一块，妈妈该如何分配，让这两个孩子都不觉得自己拿得太少？
聪明的你可能很快想到答案，只需使用一种“我分，你选择”的方法就可以解决。这种情况下，妈妈可以让一个孩子分糕，另一个孩子挑。切糕的人知道选择的人会挑两半中的最好的一半，所以他会尽可能均匀地切割蛋糕。双方都能得到一块他们认为是至少和别人一样好的蛋糕。
该方法非常巧妙，不仅在于它的操作性很强，而且它产生的结果至少在某些情况下是直观公平的。因此，经济学家和数学家们将这种分割模式称为“无嫉妒”模式。
“我分，你选择”的方法在实际生活中应用得非常广泛，比如家务也可以公平地分配，只要一个人列出家务清单，另一个人选择自己的那一份。
在商业领域，这种方法也应用于企业并购。如果一个企业要并购另外一个企业，往往是强势一点的企业提出收购价格，而另一个企业考虑是不是采纳。类似的，跟终止关系有关的离婚协议或者公司之间的合同终止也利用了这种方法。
《国际海事法》甚至也运用了这种方法。在20世纪70年代，各国开始考虑到，海底开采将成为一大产业，发展中国家担心在自己有能力建立科学的测量方法之前，技术先进的发达国家的企业将买走最有价值的海底所有权。《海洋法公约》解决了这个问题。现在，如果一家公司希望在海底开采，他们必须首先将开采区域划分成两部分，由主权国选择一个。
N块蛋糕的切分模式
然而，这些只是两个人之间的分割模式，假如蛋糕现在是三个人一起吃，又该如何分配呢？
20世纪40年代，一个名为胡果·斯坦豪斯的教授是第一个用数学的严谨性来解决这些问题的。他思考的是是否在三个或三个以上的人之间，可以运用“我分，你选择”的方法，他最终想出了现在所谓的“孤分法”。
想象一下，现在一块蛋糕由三个人分。其中一个被随机抽为切糕者，他的任务是将蛋糕切成三块。此时，切糕者不知道他会得到哪一块，所以他试图切出三个同样大小的蛋糕块。剩下的两个人，会选择哪块蛋糕他们愿意接受，然后他们会做比较，如果两个选择的人都宣称自己愿意接受不同的蛋糕，游戏结束，这两块蛋糕由他们拿走，切糕的人拿到第三块。
然而，如果两个选择者都想要同一块，切糕者拿走没有人抢的两块中的一块，剩下的两块蛋糕可以重新制作成一块蛋糕，然后两个饥饿的竞争对手来重新进行“我分，你选择”的游戏。
胡果的“孤分法”很简单，可扩展到三个以上的玩家，但它不能保证结果是高效率的。如果要高效率地分配，我们需要更复杂的数学。
三角形蛋糕
20世纪90年代后期，弗朗西斯·苏在哈佛大学获得了他的数学博士学位，一天，他在剑桥大学上学的朋友布拉德·曼找上了他，告诉了他一个关于住宿问题的烦恼。像在剑桥上学的大多数学生一样，曼将与一些室友共用一个小的套间。当涉及到谁该住什么房间，又该花费多少时，大家的意见不统一，曼想知道如何打破僵局。
虽然我们大多数人会用一个简单的经验方法回应，比如采用抽签或者直接平分房租等的方法，但苏（现在是美国数学协会的主席）和我们不一样，他告诉曼这是一个数学问题，而且还是一个有关公平分配的问题。作为一个“古老切蛋糕的问题”的实际应用，特别启发苏的是20世纪20年代一个不起眼的数学论证——斯波纳引理。这个定理其最基本的版本，无关房间或蛋糕分配，相反，它与三角形有关。这个引理是这样的，有一个大三角形，其顶点分别用红、绿、黄着色，大三角形里有奇数个小三角形，每个小三角形的三个顶点也随机用红、绿、黄三种不同的颜色着色，不管你怎么随机选择颜色，最终会至少得到一个小三角形，它的三个顶点是分别用红、绿、黄来着色。
那么，这与租金有什么关系呢？
苏将这个三角形的顶点重新定位为房间价格分配模式。例如，苏将从三角形外面的一个顶点开始，并问其所有者以下问题：“如果租金是按照这个定价方案分配，你会选择哪个房间？”取决于这些人的回答，这一点将会标上一个字母（A、B或C，这些字母代表着这个人愿意支付的价格，以及选择的房间）。然后，同样的问题会被提出，三个人的回答将组成一个三角形，该方法将不断重复下去，直到一个房间定价机制被发现，其中每一个人愿意支付不同的价格。根据计算，这样的三角形是一定存在的，这个时候在租金方面实现了“无嫉妒，无争吵”。
撇开数学论证细节不谈，该方法在实际应用中取得了巨大成功。2014年，纽约时报用这种方法成功地计算了三个人租用一个3000美元的房间时该如何分配。
存在的问题
苏的算法有效，不过只达到了“无嫉妒”效果，并不一定是最公平的。想象一个极端的例子，一个有三间卧室的套间月租金共为3000美元，第一个室友只想住在第一个卧室，第二个室友仅对第二个感兴趣，第三个室友也只喜欢第三个卧室。每个室友都愿意为他或她喜欢的房间支付全部的3000美元。 用苏的方法，一个可能的分配方案将是把每一个室友放在他们选择的房间，第一个房间的人承担全部租金。第二和第三个房间的人不用交任何费用，第一个房间的人也没有理由反对。他支付的3000美元完全和他愿意支付的房间的价格一样多，他也对其他房间没兴趣。这虽然是一个“无嫉妒”的解决方案，但它显然是不公平的，公平的方案应该是给大家分配到他们想要的房间，并且让每个人支付相应的租金。
在“我分，你选择”模式中，也存在这样的弊端。再来回顾下蛋糕的例子。想象一下，如果蛋糕是一块水果蛋糕，比方说蛋糕的中间有几个草莓，两个小孩有不同的食物偏好，有一个非常喜欢吃草莓，另外一个并不喜欢。如果草莓迷主持切糕，他可能会将蛋糕平均分割，在任何一边，都会留下相同数量的草莓，这会保证在另外一个小孩选择任何一块蛋糕时，他的那一块都有一定数量的草莓。
这次分配结果再次达到了“无嫉妒”模式。这样的结果是有效的，双方都没有任何理由要交换自己的那一块，从理论上讲，这两个人也没有什么好嫉妒的，但不喜欢草莓的小孩对结果很不满意。草莓爱好者其实可以给那个不想要草莓的人分一块没有草莓的、更大的蛋糕，而自己得到所有的草莓，这时大家可以双赢。
然而，上述解决方案可能在数学意义上达到了“无嫉妒”模式，但它并不符合我们的基本公平感。草莓爱好者为了几颗草莓，只能吃到一小块，而蛋糕爱好者拿到了一大块，这公平吗？
一个更公平的算法
来自卡内基梅隆大学的研究者们想解决这种问题，让分配的结果不仅符合“无嫉妒模式”，还要让每个人都能感觉到公平，他们发明了Spliddit算法。首先，这个算法会最大化每个室友愿意为那个房间支付的房租，以及他最终支付的钱的差异。这种方法可以衡量每一个交易者获利多少，保证每个室友的获利比他在其他房间里的获利高。这满足了“无嫉妒”的条件，没有人愿意交换房间。随后，研究者还试图找到一个“直觉公平”的解决方案，计算器会最小化每个室友实际获利的差异，然后根据计算的价格分配房间。
简单地说，算法将保证每个人都得到一个很好的交易，但没有一个人比起其他室友得到更好的交易。Spliddit算法自发布以来，已经应用于租车费用计算、工作信用分配、任务分配等等。
然而，虽然数学家们的公平算法已经越来越进步，但具体地运用到现实社会时，情形又会变得复杂许多。例如，一个兄弟分割父母财产时，也许算法可以为他们找到一个很平等的分割方案，但其中一个子女在父母患病期间付出最多，是不是应该分得更多呢？这类问题，Spliddit算法也没法解决。
看来，关于如何“切糕”让每个人觉得公平，这一个复杂的问题还会像幽灵一样，与学者们纠缠不清。
其实，这个问题非常复杂。例如，分糕的本意是让大家都吃得开心，但总有一些意外情况会让有些人不欢而散，比如，有的人非常讨厌草莓，但你按照上述分糕方法，很有可能恰恰给他们分了有草莓的那一块，还有的人可能会觉得自己手中分到的蛋糕小，感觉很不公平。说到这里，也许现在你已经明白了，我们不只是在谈论蛋糕，而是在谈论公平分配的问题。
在生活的许多方面，都涉及到“分糕”，比如如果在学校住宿，你会遇到分配宿舍床位的问题。在家里，家务也需要分配，再大一点，在法律政治领域，法官该如何判刑，税收该收多少，高考政策该如何向贫困地区倾斜，这些也可以简化为一个“分糕”问题。当我们弄懂了一个蛋糕该如何分配，这些问题其实都可以解决。然而，到底该怎么分配呢？为了简化，我们不妨先从如何科学地分一块蛋糕或者一个宿舍开始。
我分，你选择
现在我们假想一个简单的情形，假如两个孩子都要吃一块蛋糕，蛋糕只有一块，妈妈该如何分配，让这两个孩子都不觉得自己拿得太少？
聪明的你可能很快想到答案，只需使用一种“我分，你选择”的方法就可以解决。这种情况下，妈妈可以让一个孩子分糕，另一个孩子挑。切糕的人知道选择的人会挑两半中的最好的一半，所以他会尽可能均匀地切割蛋糕。双方都能得到一块他们认为是至少和别人一样好的蛋糕。
该方法非常巧妙，不仅在于它的操作性很强，而且它产生的结果至少在某些情况下是直观公平的。因此，经济学家和数学家们将这种分割模式称为“无嫉妒”模式。
“我分，你选择”的方法在实际生活中应用得非常广泛，比如家务也可以公平地分配，只要一个人列出家务清单，另一个人选择自己的那一份。
在商业领域，这种方法也应用于企业并购。如果一个企业要并购另外一个企业，往往是强势一点的企业提出收购价格，而另一个企业考虑是不是采纳。类似的，跟终止关系有关的离婚协议或者公司之间的合同终止也利用了这种方法。
《国际海事法》甚至也运用了这种方法。在20世纪70年代，各国开始考虑到，海底开采将成为一大产业，发展中国家担心在自己有能力建立科学的测量方法之前，技术先进的发达国家的企业将买走最有价值的海底所有权。《海洋法公约》解决了这个问题。现在，如果一家公司希望在海底开采，他们必须首先将开采区域划分成两部分，由主权国选择一个。
N块蛋糕的切分模式
然而，这些只是两个人之间的分割模式，假如蛋糕现在是三个人一起吃，又该如何分配呢？
20世纪40年代，一个名为胡果·斯坦豪斯的教授是第一个用数学的严谨性来解决这些问题的。他思考的是是否在三个或三个以上的人之间，可以运用“我分，你选择”的方法，他最终想出了现在所谓的“孤分法”。
想象一下，现在一块蛋糕由三个人分。其中一个被随机抽为切糕者，他的任务是将蛋糕切成三块。此时，切糕者不知道他会得到哪一块，所以他试图切出三个同样大小的蛋糕块。剩下的两个人，会选择哪块蛋糕他们愿意接受，然后他们会做比较，如果两个选择的人都宣称自己愿意接受不同的蛋糕，游戏结束，这两块蛋糕由他们拿走，切糕的人拿到第三块。
然而，如果两个选择者都想要同一块，切糕者拿走没有人抢的两块中的一块，剩下的两块蛋糕可以重新制作成一块蛋糕，然后两个饥饿的竞争对手来重新进行“我分，你选择”的游戏。
胡果的“孤分法”很简单，可扩展到三个以上的玩家，但它不能保证结果是高效率的。如果要高效率地分配，我们需要更复杂的数学。
三角形蛋糕
20世纪90年代后期，弗朗西斯·苏在哈佛大学获得了他的数学博士学位，一天，他在剑桥大学上学的朋友布拉德·曼找上了他，告诉了他一个关于住宿问题的烦恼。像在剑桥上学的大多数学生一样，曼将与一些室友共用一个小的套间。当涉及到谁该住什么房间，又该花费多少时，大家的意见不统一，曼想知道如何打破僵局。
虽然我们大多数人会用一个简单的经验方法回应，比如采用抽签或者直接平分房租等的方法，但苏（现在是美国数学协会的主席）和我们不一样，他告诉曼这是一个数学问题，而且还是一个有关公平分配的问题。作为一个“古老切蛋糕的问题”的实际应用，特别启发苏的是20世纪20年代一个不起眼的数学论证——斯波纳引理。这个定理其最基本的版本，无关房间或蛋糕分配，相反，它与三角形有关。这个引理是这样的，有一个大三角形，其顶点分别用红、绿、黄着色，大三角形里有奇数个小三角形，每个小三角形的三个顶点也随机用红、绿、黄三种不同的颜色着色，不管你怎么随机选择颜色，最终会至少得到一个小三角形，它的三个顶点是分别用红、绿、黄来着色。
那么，这与租金有什么关系呢？
苏将这个三角形的顶点重新定位为房间价格分配模式。例如，苏将从三角形外面的一个顶点开始，并问其所有者以下问题：“如果租金是按照这个定价方案分配，你会选择哪个房间？”取决于这些人的回答，这一点将会标上一个字母（A、B或C，这些字母代表着这个人愿意支付的价格，以及选择的房间）。然后，同样的问题会被提出，三个人的回答将组成一个三角形，该方法将不断重复下去，直到一个房间定价机制被发现，其中每一个人愿意支付不同的价格。根据计算，这样的三角形是一定存在的，这个时候在租金方面实现了“无嫉妒，无争吵”。
撇开数学论证细节不谈，该方法在实际应用中取得了巨大成功。2014年，纽约时报用这种方法成功地计算了三个人租用一个3000美元的房间时该如何分配。
存在的问题
苏的算法有效，不过只达到了“无嫉妒”效果，并不一定是最公平的。想象一个极端的例子，一个有三间卧室的套间月租金共为3000美元，第一个室友只想住在第一个卧室，第二个室友仅对第二个感兴趣，第三个室友也只喜欢第三个卧室。每个室友都愿意为他或她喜欢的房间支付全部的3000美元。 用苏的方法，一个可能的分配方案将是把每一个室友放在他们选择的房间，第一个房间的人承担全部租金。第二和第三个房间的人不用交任何费用，第一个房间的人也没有理由反对。他支付的3000美元完全和他愿意支付的房间的价格一样多，他也对其他房间没兴趣。这虽然是一个“无嫉妒”的解决方案，但它显然是不公平的，公平的方案应该是给大家分配到他们想要的房间，并且让每个人支付相应的租金。
在“我分，你选择”模式中，也存在这样的弊端。再来回顾下蛋糕的例子。想象一下，如果蛋糕是一块水果蛋糕，比方说蛋糕的中间有几个草莓，两个小孩有不同的食物偏好，有一个非常喜欢吃草莓，另外一个并不喜欢。如果草莓迷主持切糕，他可能会将蛋糕平均分割，在任何一边，都会留下相同数量的草莓，这会保证在另外一个小孩选择任何一块蛋糕时，他的那一块都有一定数量的草莓。
这次分配结果再次达到了“无嫉妒”模式。这样的结果是有效的，双方都没有任何理由要交换自己的那一块，从理论上讲，这两个人也没有什么好嫉妒的，但不喜欢草莓的小孩对结果很不满意。草莓爱好者其实可以给那个不想要草莓的人分一块没有草莓的、更大的蛋糕，而自己得到所有的草莓，这时大家可以双赢。
然而，上述解决方案可能在数学意义上达到了“无嫉妒”模式，但它并不符合我们的基本公平感。草莓爱好者为了几颗草莓，只能吃到一小块，而蛋糕爱好者拿到了一大块，这公平吗？
一个更公平的算法
来自卡内基梅隆大学的研究者们想解决这种问题，让分配的结果不仅符合“无嫉妒模式”，还要让每个人都能感觉到公平，他们发明了Spliddit算法。首先，这个算法会最大化每个室友愿意为那个房间支付的房租，以及他最终支付的钱的差异。这种方法可以衡量每一个交易者获利多少，保证每个室友的获利比他在其他房间里的获利高。这满足了“无嫉妒”的条件，没有人愿意交换房间。随后，研究者还试图找到一个“直觉公平”的解决方案，计算器会最小化每个室友实际获利的差异，然后根据计算的价格分配房间。
简单地说，算法将保证每个人都得到一个很好的交易，但没有一个人比起其他室友得到更好的交易。Spliddit算法自发布以来，已经应用于租车费用计算、工作信用分配、任务分配等等。
然而，虽然数学家们的公平算法已经越来越进步，但具体地运用到现实社会时，情形又会变得复杂许多。例如，一个兄弟分割父母财产时，也许算法可以为他们找到一个很平等的分割方案，但其中一个子女在父母患病期间付出最多，是不是应该分得更多呢？这类问题，Spliddit算法也没法解决。
看来，关于如何“切糕”让每个人觉得公平，这一个复杂的问题还会像幽灵一样，与学者们纠缠不清。