具有部署约束的负载均衡博弈分析

The load balancing game is a new research topic of algorithm game theory attracting wild attention in current decades, which is applied in network design, resource assignment, industrial management, information transmission and so on. The load balancing game with deployment constraint extends the traditional resource allocating game, and can describe more complex practical problems. In this project, we shall study inefficiency analysis of mixed Nash Equilibrium, analysis on the upper and lower bounds in the Price of Anarchy of classical coordinate mechanism of new social costs, equilibrium analysis and mechanism design for The multidimensional load balancing game with deployment constraint. The research about these problems was still in the stage of preliminary exploration. The project is expected to enrich the related research on the area of algorithm game theory and combinatorial optimization.

负载均衡博弈是近年来在算法博弈论研究中受到广泛重视的新课题，其研究成果可应用于网络设计、资源分配、工业管理及信息传播等领域。本项目拟研究具有部署约束的负载均衡博弈，它是传统负载均衡博弈的推广，能够更好地描述现实问题。研究内容包括混合策略纳什均衡的有效性分析；在新的全局目标下典型协调机制的性能分析以及机制有效性的下界研究；具有部署约束的多维负载均衡博弈的均衡有效性分析与机制设计。这些问题的研究尚处于初步探索阶段，研究成果将丰富算法博弈论和组合最优化的相关理论和应用。

负载均衡博弈是近年来在算法博弈论研究中受到广泛重视的新课题，其研究成果可应用于网络设计、资源分配、工业管理及信息传播等领域。具有部署约束的负载均衡博弈是传统负载均衡博弈的推广，能够更好地描述现实问题，但在离散优化领域中的研究并不多见，对该类问题的研究具有重要的理论与现实意义。本项目研究了具有等级、环或路等约束下的负载均衡问题，分析了一些协调机制下博弈的Price of Anarchy(POA)和Price of Stability(POS)，设计了多个负载均衡问题的多项式时间近似算法或在线算法，为未来协调机制设计奠定了理论基础。主要研究成果有：分析了等级约束下两台机器多维负载均衡问题在两个典型协调机制下博弈的POA和POS值; 设计了等级约束下两台机器在线任务包负载均衡问题的最优半在线算法; 设计了等级约束下两台机器带离散处理时间的负载均衡问题的最优半在线算法; 设计了混合环约束下带惩罚费用的离线负载均衡问题的多项式时间近似算法; 设计了两点混合环约束下在线负载均衡问题的最优在线或半在线算法; 设计了路状结构约束下在线负载均衡问题的最优半在线算法。前述具有部署约束的负载均衡问题的研究丰富了算法博弈论和离散优化的研究内容，为资源分配与调度技术提供了重要的理论依据。