若干排序博弈问题的协调机制研究

项目名称： 若干排序博弈问题的协调机制研究

项目编号： No.11201439

项目类型： 青年科学基金项目

立项/批准年度： 2013

项目学科： 数理科学和化学

项目作者： 农庆琴

作者单位： 中国海洋大学

项目金额： 22万元

中文摘要： 排序博弈问题的协调机制设计与分析是计算机理论与博弈理论交叉领域"算法博弈理论"所研究内容的一部分，该领域是近十年的热点研究领域。本项目首先探讨若干排序博弈模型的协调机制的近似纳什均衡问题，包括：（1）探讨近似纳什均衡的存在性；（2）探讨收敛到近似纳什均衡的时间复杂性；（3）分析近似无秩序代价、近似稳定代价；（4）近似纳什均衡的求解算法。其次给机器是并行分批处理机的排序博弈问题设计协调机制，研究相应排序博弈问题的纳什均衡存在性问题，求出无秩序代价、稳定代价或估计它们的上界和下界，分析收敛到纳什均衡的时间复杂性。本项目的研究争取为排序博弈问题的协调机制设计与分析提供一些新的思想、新的研究方法和理论结果，促进该领域进一步发展。

中文关键词： 博弈；排序；装箱；协调机制；无秩序代价

英文摘要： Designing and analysing coordination mechanisms for scheduling games is a part of the content studied in Algorithmic Game Theory，a new and hot area that is an interface of theoretical computer science and game theory and that has been exploded over the past ten years. In this project we first research on problems related to approximate Nash equilibrium in some models of scheduling games, including the existence of approximate Nash equilibrium, the time complexity of the players of a scheduling game converge to an approximate Nash equilibrium, the price of approximate anarchy, the price of approximate stability and the algorithms to compute an approximate Nash equilibrium. We then concentrate on designing coordination mechanisms for scheduling games with parallel-batching machines. We will theoretically analyze the coordination mechanisms designed by studying the existence of Nash equilibrium and the time complexity of convergence to a Nash equilibrium, and evaluating the price of anarchy and the price of stability. We try to explode some new ideas and new approaches and provide some new results for coordination mechanisms of scheduling games.

英文关键词： game；scheduling；bin packing；coordination mechanism；price of anarchy