7.3.1 引言
公平分配是一个古老的问题，其中最广为人知的“分与选”算法最早可以在《圣经》中找到记载，有关公平分配的现代研究被认为是由 Steinhaus 于 1947 年在华盛顿特区计量经济学会的一次会议上发起的
[1] 。从那时起，经济学和数学领域的大量著作都致力于研究在参与 者之间公平分配资源的理论。最初，人们研究可分物体的公平分配问 题，并用“切蛋糕”问题来代指一系列可以分割的物品的公平分配问题。在这个问题上，公平性主要体现在“无嫉妒”和“比例公平”。人们在这 一问题上也取得了一系列的研究成果：一个可分割的蛋糕的无嫉妒分 配（也是按比例分配）总是存在的，并且可以通过有界步骤找到[Aziz 和 Mackenzie][2] 。此外，效用相等的竞争均衡同时保证了无嫉妒和 帕累托最优[Varian][3] 。最近，人们开始关注不可分割的物品，部分 原因是在一些应用中，物品的分配本身就无法以分数形式进行，例如 在云计算环境中分配计算资源，以及在学校中为教师分配课程。在过 去十年中，计算机科学为公平分配问题提供了一个全新并且实用的角 度——算法公平分配。除了设计算法，计算机科学还带来了更多的理 念，如计算和通信复杂性，以及信息假设。公平分配算法已在现实世
界中得到应用。例如，宾夕法尼亚大学沃顿商学院在课程分配中采用了“课程匹配”算法，Spliddit 和 Fair Outcomes 等网站为人们提供了公平分配算法的在线访问。
此前有许多文章从不同的视角解释公平分配理论的问题。 Moulin[4] 从经济学的角度回顾了这一理论。Aleksandrov，Walsh[5]和 Suksompong [6] 分别关注在线公平分配和受限环境。Lang 和 Rothe[7] 、Walsh[8] 和Aziz[9] 则从广义计算机科学的角度回顾了这一问题。本章节主要在以往文章的基础上加以总结梳理来介绍公平分配问题的概念，经典的公平分配算法，以及后续可以进一步研究的问题。