设施选址博弈问题的无支付机制设计与分析

设施选址博弈问题，是目前国际学术领域前沿的研究课题之一。如何利用算法博弈理论，设计一个恰当的机制，使得博弈者在自身利益驱动下选择设计者期望的策略，从而达到符合设计目标的系统总体均衡态，是其重要的研究内容之一。本项目将从近似算法设计与分析的角度，利用算法博弈理论，借助图论和概率论工具，分别对经典和厌恶型设施选址博弈问题进行无支付机制设计与分析。研究的主要内容为：(1) 在不同的设施类型、设施个数、社会费用、网络结构等条件下，设计具有防护策略性质的确定型和随机型机制；(2) 针对设计出的各类机制，对其竞争比的上界和下界进行讨论与分析。在研究方法上，充分结合近似算法的设计与分析方法，着重网络的结构性质的分析，力争在理论上有所突破。本项目所研究的是组合优化、选址科学和理论计算机科学的交叉学科课题，具有重要的理论意义和实践意义。

设施选址博弈和优化问题，是目前国际学术领域前沿的研究课题之一。在设施选址博弈问题中，如何利用算法博弈理论，设计一个恰当的机制，使得博弈者在自身利益驱动下选择设计者期望的策略，从而达到符合设计目标的系统总体均衡态，是其重要的研究内容之一。本项目从近似算法设计与分析的角度，利用算法博弈理论，借助图论和概率论工具，首次对厌恶型设施选址博弈问题进行无支付机制设计与分析。我们主要研究了在线段、圈、树及一般网络上的各种模型，针对不同网络结构设计出确定型、随机型防策略性的无支付机制，并分析各机制的结果与最优解之间的近似比，得到了一些有意义的结果：当所有博弈者分布在线段、圈及树上时，我们分别设计出近似比为3的确定型机制；当博弈者分布在线段时，我们设计出一个随机型机制，其近似比为3/2。同时，我们研究了其他无博弈因素的设施选址优化问题——块图上的候补型2-中位问题的多项式时间的算法设计，通过构造块图的框架结构，分析块图上的最优解与其框架结构上的最优解之间的关系，设计出时间复杂度为的O(nlogn+m)多项式时间算法，其中n和m分别为图中顶点数和边数。