摘 要

分蛋糕经常被用来比喻分配事物资源。现在已经有很多论文在讨论如何实现公平的分蛋糕的问题,也有少数的人在研究如何让其中一个有私心的参与者获得最大利益的策略,但是这些论文其实都是围绕着均衡分割和免妒忌分割来讨论的。在均衡分割的基础上让所有参与者对其他参与者都没有妒忌产生就是无妒忌分割。如何在无争议的条件下把一个蛋糕分给n人，是经典的博弈论问题，它广泛应用在经济和社会政治领域。按照分的人最后选原则，选蛋糕的人可以得到的价值超过蛋糕总价值的1/n，而分蛋糕的人只能恰好获得1/n的价值，更公平一些的做法是，是确保每个参与者都可以得到1/n多一点的价值。本课题主要内容为系统分析学习在免妒忌条件下，n个人分蛋糕协议的协议设计思想。

关键字：公平性、免妒忌性、协议

Abstract

Cake cutting is a common metaphor for the division of a heterogeneous divisible good.There are numerous papers that study the problem of fairly dividing a cake; a small number of them also take into account self-interested agents and consequent strategic issues, but these papers focus on fairness and consider a strikingly weak notion of truthfulness. It’s a classics problem in algorithmic game theory that how to divide a cake without dispute. It is widely used in the economy and social politics. It’s Envy-free division that all agents are not envious of other agents while it’s equally division. According to the rules that who divide the cake choose last, the agent who choose cake early can get more than 1/n of the cake, and the divider can only get 1/n of cake. The more fair way is make sure all agents can get more than 1/n of cake. This thesis research mainly is systematic study and analyze the Envy-free division.

Key words : Fair ,Envy-free division ,Protocols

第1章 绪论 1

1.1 研究背景及意义 1

1.2 均衡分割和免妒忌分割 3

1.3 研究内容及技术路线 7

1.4 本文章节安排 8

第2章 协议研究与分析 9

2.1 协议问题分析 9

2.2 四人情况分析 10

2.3 对ngt;4的情况分析与探讨 14

第3章 协议的分析与改进 16

3.1 对n=4的协议改进与分析 16

3.2 对分蛋糕过程的行为分析 17

3.3 协议的总结与归纳 18

3.4 对n=4时协议免妒忌情况验证 19

3.5 对n=5时协议免妒忌情况验证 22

第4章 总结与展望 24

4.1 工作总结 24

4.2 工作展望 24

参考文献 25

致谢 26

第1章 绪论

1.1 研究背景及意义

如何在无争议的条件下把一个蛋糕分给n人，是经典的博弈论问题。1994-2001年先后有Nash, Selten, Harsanyi, Mirrless, Vickrey和Stiglitz相续获得诺贝尔经济学奖，其主要贡献都与博弈论紧密相关，这标志着博弈论的应用价值获得了巨大的肯定。现阶段博弈论的应用范围日益外延，已成为自动控制，人工智能等工程领域中的重要工具。只要一个系统中，有多个可独立地选择自己行为的决策者，而且这些决策者有着相互冲突的优化目标，那么博弈论为研究这些决策者间的交互作用提供了一个合适的分析框架^[7,8]。

博弈论研究经历了三个发展阶段：

第一个阶段研究的重点是合作博弈(cooperative game）^[13,14,15]。美国数学家冯·诺依曼(John von Neumann)和摩根斯特恩(Oskar Morgenstern)于1944年出版了《博弈论与经济行为》(Game Theory and Economic Behavior），提出了“策略型”(strategic form）和“扩展型”(extensive form)等基本博弈模型，定义了最小最大解概念，构建了博弈论的基本框架。到了50年代，合作博弈发展到鼎盛期，包括了Nash和Shapley的“讨价还价”模型，Gillies和Sharpley给出的“核”(core）概念^[5,9]。
第二个阶段研究的重点是非合作博弈(non-cooperative game）。数学家Nash于1950年发表的论文提出了著名的Nash均衡(Nash equilibrium)的概念。同年Tucker定义了“囚徒困境”(prisoners' dilemma），他们的工作基本上奠定了现代非合作博弈论的基础。非合作博弈与合作博弈的区别在于当事人能否达成一个具有约束力的协议(binding agreement)，非合作博弈不需要这样一个协议，从而有更广的解释力。因为主体之间不合作关系是基本的和长期的，而合作关系是偶然的和暂时的。另外，在Nash的理论框架内，合作博弈可以作为一个特例从非合作博弈中推导出来。
第三个阶段到70年代，博弈论开始受到经济学家的重视，到80年代已成为主流经济学的一部分。近年来，博弈论的思想和建模方法已渗透到了几乎所有的经济分析领域。其中，受益最大的是微观经济学。

分蛋糕问题作为博弈论中非合作博弈的经典问题在分蛋糕人数增加的情况下难度程度呈几何倍数增加^[11]。经典的两人分蛋糕问题——为了实现免妒忌，只需要一个人切，另一个人选即可。首先，由其中一人执刀，把蛋糕切分成两块；然后，另一个人选出他自己更想要的那块，剩下的那块就留给第一个人。由于分蛋糕的人事先不知道选蛋糕的人会选择哪一块，为了保证自己的利益，他必须（按照自己的标准）把蛋糕分成均等的两块。这样，不管对方选择了哪一块，他都能保证自己总可以得到蛋糕总价值的1/2。这样就让两人双方都觉得自己得到了整个蛋糕至少1/n的价值。将这个问题延伸到n个人分蛋糕，如果有n个人分蛋糕，每个人都认为自己得到了整个蛋糕至少1/n的价值，那么实现这种情况的方法就是免妒忌条件下n人分蛋糕策略。

构造一套免嫉妒的分割方案非常困难。1960年，John Selfridge和John Conway各自独立地分析了人数为3的情况，构造出了第一个满足免嫉妒条件的三人分割方案。这种分割方案就被称为“Selfridge-Conway协议”^[6,12]。