考虑资源相关性的最大化最小公平分配问题研究

论文总字数：27279字

摘 要

资源的最大化最小公平分配问题是经济学与计算机科学中的经典问题，其应用场景包括遗产分割与计算资源共享等等。已有的研究工作通常假设待分配资源是可以任意划分组合的，然而在现实生活中待分配资源并不总是可以任意组合划分的。例如在办公室分配中，一个项目组通常希望获得相邻的办公室以方便交流。因此本文考虑如何对具有相关性约束的资源进行最大化最小分配（即最大化收益最小的Agent的效用）。本文考虑采用图结构来表示资源之间的相连关系，并要求每个Agent获得的资源集合在资源关系图中必须是连通的。

针对这个问题，本文提出了一种启发式算法。该方法首先利用贪心分配先将资源进行预分配，其次通过局部变换，将效用值较大的Agent的资源分配给效用值最小的Agent，过程中保证资源子图的连通性。实验结果表明本文提出的算法效果比单纯贪心分配和随机分配效果要好。

关键词：资源分配；最大化最小公平；连通性约束；启发式算法。

Abstract

The max-min fair allocation of resources is a classical problem in economics and computer science. Its application scenarios include inheritance settlements and computing resource sharing. The existing work usually assumes that the resources to be allocated can be divided and combined arbitrarily, but in real life, the allocated resources can not always be divided and combined arbitrarily. For example, in office assignment, an agent usually wants to get adjacent offices to facilitate communication. Therefore, this paper considers how to fairly allocate the resources with relativity constraints to maximize the minimum utility of any agent. This paper considers adopting a graph structure to represent the dependency relationship between resources, and requires that the set of resources obtained by each agent must be connected in the resource relationship graph.

To solve this problem, a heuristic algorithm is proposed in this paper. In this method, a greedy allocation is used to pre-allocate resources firstly, and then a local transformation is used to allocate resources of agents with larger utility value to agents with the smallest utility value, while ensuring the connectivity of resource subgraphs. The experimental results show that the proposed algorithm outperforms the greedy allocation and random allocation.

Keywords: Resource allocation；Max-min fair ; Connectivity constraints; Heuristic algorithms

目 录

摘要 I

Abstract II

1. 绪论 1
   1. 研究背景 1
   2. 相关工作 1
   3. 研究内容与研究思路 5
   4. 论文结构 6

第二章 问题模型 7

2.1 问题建模 8

第三章 启发式方法 10

3.1 贪心初始化 10

3.2 局部变换调整 13

3.3 局部交换再调整 14

3.4 实例分析 17

第四章 实验验证与分析 19

4.1 实验设计 19

4.2 实验结果 20

4.3 实验结论 22

第五章 总结与展望 24

5.1 全文工作总结 24

5.2 研究展望 24

参考文献 25

致谢 27

1. 绪论

1.1研究背景

资源的最大化最小公平分配问题是经济学与计算机科学中的经典问题，其应用场景包括遗产分割，边界争端处理与计算资源共享等等。例如，在土地分配中，每个继承人通常希望获得相互紧邻的地块。在办公室分配中，一个Agent通常希望获得相邻的办公室以方便交流。

资源公平分配的关键在于资源的存在形式以及分配指标。目前已有的关于资源公平分配问题的研究工作通常关注可分割资源与不分割资源的无嫉妒分配，比例分配，最大化最小公平分配和最大化最小份额保证分配。而且，已有工作还探究了不可分割资源的最小化嫉妒公平分配。尽管不可分割资源的最大化最小公平分配已被广泛研究，但是已有研究工作通常假设资源可以任意组合分配。然而，在现实生活中待分配资源并不总是可以任意组合划分的。例如在办公室分配中，一个项目组通常希望获得相邻的办公室以方便交流。因此

本文考虑如何对具有相关性约束的资源进行最大化最小分配（即最大化收益最小的Agent的效用）。本文采用图结构来表示资源之间的依赖关系，并要求每个Agent获得的资源集合在资源关系图中必须是连通的。由于该问题是NP难的，本文考虑设计了高效的启发式方法来寻找近似最优分配策略。

1.2相关工作

资源的分配问题是经典的，并且在生活中应用十分广泛的问题。而研究这一问题的目标是使得每个Agent都能尽可能的提高自己的收益。资源分配问题很早之前就有人开始了相关的研究。

切蛋糕问题是资源分配问题中最经典的之一。很多学者研究资源分配问题是绕不开切蛋糕问题的。Steinhaus [1]在1948年提出了一篇关于公平分配的文章，这篇文章是蛋糕切割问题的最早研究工作。Stromquist[2]在1980年提出了“如何公平切割蛋糕”的文章，文中证明了蛋糕可以在n个人之间公平分配，即使每个人对蛋糕的不同部位有不同的喜好。对于这个问题，有一个简单的版本，只要满足每个人至少收到1/n价值的蛋糕，则这个方案就是公平的。Brams和Taylor[3]在1996年发表了一篇关于资源分配的文章，从对著名的蛋糕切割问题的分析开始，“我切割，你选择”已经成为了一种公平分配的标准。切蛋糕，分割房地产，在国际争端中确定边界——这种公平划分的问题无处不在，作者展示了公平分配问题在多个领域中是如何得到应用的，然后分析了需要分配适用于一方或两方以上的利益的情况下的公平分配问题，特别是，他们专注于提供“无嫉妒”分配的算法，在这些程序中，每个人都认为他或她获得了最大的份额，因此不会妒忌任何其他人。对于“无嫉妒”分配，Brams和Taylor[4]在1995年发表了一篇关于“无嫉妒”蛋糕分配协议的文章，讲述了n个Agent分配蛋糕的方案，并满足每个人至少得到一块1/N大小（按本人的标准）的蛋糕。Brams和Jones[5]等学者在2006年研究了切割蛋糕的更好的方法，其介绍的分配标准不是“无嫉妒”，而是比例性。

不仅仅是切割蛋糕问题，其他关于资源分配的问题也陆续有学者开始深入研究。Woeginger [6]在1997年研究了一个最大化最小机器完成时间的多项式时间近似方案。这一问题与本文研究的最大化最小资源分配概念近似。他们考虑将一组中n个作业分配给m个完全相同的并行机器系统，目标是达到最大化最早的机器完成时间（不使用空闲时间）。该问题在组合式燃气涡轮飞机发动机维修行动的排序中有应用。到目前为止，只知道最坏情况比严格远离一的近似算法，他们给出了该问题的第一个多项式时间近似方案。算法的时间复杂度是，其中是一个常数，取决于所需的精度。

剩余内容已隐藏，请支付后下载全文，论文总字数：27279字