基于经济效益与社会平等准则的资源分配计算问题研究

Problem of allocating resources among multiple self-interested agents has been a well-established research theme in economics. A “good” allocation must look after both economy efficiency and social equality. In economics, most work in this area has focused on existence of good allocations in mathematical models. However, little attention has been paid to the realistic problems of how to find such good allocations in a procedural way and whether the computation task is tractable. On another hand, resource allocation for multiple self-interested agents recently becomes an emerging research topic in Artificial Intelligence. Much recent work has been done to design procedural mechanisms for allocating resources efficiently, and to analyze agents' strategical behavior in terms of computational complexity. It is not only promising but also challenging to consider computation tractability, economy efficiency, and social equality in designing allocation mechanisms. In this project, we will study characteristics of good allocations from the point of view of computational efficiency. Then we will design procedural mechanisms (including designing and testing some specific protocols for resource allocation), which can efficiently compute allocations that can look after both economy efficiency and social equality. To corroborate the reliability and rationality of relevant mechanisms, we also plan to analyze computational complexity of agents' strategical behavior in these mechanisms.

面向多个自利Agent的资源分配问题是经济学里的一个重要研究内容。一个“好” 的分配方案往往须要兼顾经济效益与社会平等。在经济学中，大多数相关的研究侧重于在数学模型上探讨“好”的分配方案的存在性问题。而另一方面，多Agent 资源分配问题近年来也成为了人工智能领域里的研究热点。许多相关的工作旨在设计具有高执行效率的程序化资源分配制度，并从计算复杂性的角度分析智能Agent 的策略性行为。因此从计算效率、经济 效益和社会平等这三个维度综合研究面向多个自利 Agent 的分配制度设计问题，是现代经济学和人工智能在其核心研究方向上交叉发展的趋势和挑战。本课题将从计算效率的角度研究 理想分配方案的性质；设计能以高的计算效率得到兼顾经济效益与社会平等的分配方案的程序化制度(包括实现和测试具体可执行的分配协议)，并通过分析在其下进行策略性行为的计 算复杂性来证明相关制度的可靠性与合理性。

面向多个自利Agent的资源分配问题是经济学里的一个重要研究内容。一个“好” 的分配方案往往须要兼顾经济效益与社会平等。在经济学中，大多数相关的研究侧重于在数学模型上探讨“好”的分配方案的存在性问题。而另一方面，多Agent 资源分配问题近年来也成为了人工智能领域里的研究热点。许多相关的工作旨在设计具有高执行效率的程序化资源分配制度，并从计算复杂性的角度分析智能Agent 的策略性行为。因此从计算效率、经济 效益和社会平等这三个维度综合研究面向多个自利 Agent 的分配制度设计问题，是现代经济学和人工智能在其核心研究方向上交叉发展的趋势和挑战。. 目前，本项目的主要工作与成果包括：.（1） 我们提出了一种对于参与者身份不敏感的并行资源分配机制。在参与分配的各个Agent相互独立且其估值函数满足可加性的前提下，我们比较了并行资源分配机制和传统的串行资源分配机制在社会福利中的平均(和最坏)情况，理论和实验结果表明并行资源分配机制比串行资源分配机制更具有优势。在这一并行资源分配机制下，我们还研究了若干个相关的操弄问题，以及两个Agent在信息完备情形下的子博弈完美纳什均衡。.（2） 我们对近似公平分配做了进一步研究，首先定义了设计新的近似公平分配概念EQL，给出近似公平分配EQL的存在性定理并给出相关证明。接着在可加估值函数的前提下，我们证明了满足帕累托最优（PO）以及EQL的分配存在，并且给出了可在多项式时间内找到这种分配的算法。