选址博弈和排序博弈的防策略性无支付机制设计研究

Facility games and scheduling games are important research areas in the forefront of algorithmic game theory. One of the most important objectives in the study of these games is to design appropriate mechanisms without money in order to enforce all agents to choose strategies faithfully and to achieve the overall equlibria. In this project we will conduct an in-depth study on strategy-proof mechanism design without money for facility and scheduling games by exploiting modern techniques from algorithmic game theory, the theory of approximation algorithms and the differential privacy method, and by using advanced tools from probability theory, graph theory and the theory of social choices. The overall aims of the project are: (1) to design appropriate deterministic and randomized mechanisms based on different preferences, metric spaces and social objectives, so as to optimize the overall objective in system; (2) to compute and analyze upper and lower bounds on each mechanism's approximation ratio by applying appropriate methodologies in the theory of approximation algorithms; (3) to characterize various properties of strategy-proof mechanisms without money under different models; (4) to analyze the agents' incentive under the operation of different algorithms. This is an interdisciplinary project with topics in the common part of combinatorial optimization and theoretical computer science. It is expected that the implementation of this project will significantly advance related areas in algorithmic game theory, especially the study of facility and scheduling games. On the other hand, the expected results from this project may have important applications in a few practical areas such as management science, information science, social economics, etc.

选址博弈和排序博弈是目前国际相关学术领域的两类重要前沿课题；对其进行防策略性无支付机制设计是其中重要的研究内容之一。本项目中，我们将利用算法博弈理论、近似算法设计理论及差分隐私技术，借助概率论、图论及社会选择理论等工具，对两类博弈问题的防策略性无支付机制设计进行深入研究。主要的研究内容包括：在不同个人偏好、不同度量空间、不同社会总体目标等条件下，设计相应的确定型和随机型机制，实现整体社会目标的优化；利用近似算法设计思想，计算与分析机制近似比的上界和下界；对不同模型的防策略性无支付机制进行性质刻画与分析；以及针对相应组合优化问题的精确或近似算法，对博弈者进行激励分析研究。本项目所研究的问题是组合优化和理论计算机科学的交叉学科课题，在管理科学、信息科学以及社会经济学等领域有着重要的应用，因而本项目的研究具有重要的理论意义和实际的应用价值。

算法博弈论是目前学术界十分热门的研究领域之一，作为其中重要内容之一的机制设计理论也受到众多学者的关注。本课题是以设施选址博弈和排序博弈问题为切入点来研究和探讨机制设计与分析。本课题的完成情况可从以下三个方面进行总结：1. 在选址博弈问题方面，我们研究了一般化的厌恶型选址博弈问题，在博弈者拥有单一低谷偏好且分布在线上的条件下，完整地给出了安置一个设施的防策略性和防群体策略性无支付机制的性质刻画；并且在此刻画的基础上，进一步讨论了确定型机制近似比的下界。同时，我们也研究了其他无博弈因素的设施选址优化问题-块图上的候补型2-中位问题的多项式时间的算法设计，通过构造块图的框架结构，分析块图上的最优解与其框架结构上的最优解之间的关系，设计出时间复杂度为的O(nlogn+m)多项式时间算法，其中n和m分别为图中顶点数和边数。2. 研究了较排序问题更为复杂的一类资源分配问题，即点对点网络上信息资源分配博弈问题。在此问题中，网络结构不再是特殊的二部图，而是任意的无向图结构；有边相连的节点之间可直接进行资源交换与共享。如何设计出一套全网资源分配机制，使得参与者没有动机采取策略行为，是我们研究的主要内容。我们以由“瓶颈分解”得到的分配算法作为资源分配机制，证明了该机制关于参与者的“删边”策略和“谎报权重”策略均是防策略性的，相关结果分别在计算机领域国际顶级会议IJCAI和算法博弈论重要国际会议SAGT上发表；同时我们也讨论了参与者的“拆点”策略，发现“瓶颈分解”-分配机制关于该策略不是防策略性的。为此，我们引入“激励比”概念，刻画了“拆点”策略在最坏情况下所带来的效用增加。3. 开展多项关于算法博弈论方面的推广工作，发表算法博弈论综述论文1篇；初步完成专著《互联网市场设计》，在本书中，我们从应用的角度去介绍算法博弈论，通过对互联网市场设计介绍算法博弈论中相关前沿发展方向和研究课题；合作申请获得国家自然科学基金数学天元其他项目——《算法博弈论》专题讲习班资助。