求解社区项目博弈的一种改进贪婪算法研究

Study on an Improved Greedy Algorithm Applied in Benefit Allocating of the Community

针对社区项目博弈的一般模型,应用贪婪算法求解项目博弈的近似社会最优指派,给出参与者重加权分配机制,证明贪婪算法求得的指派恰好是非合作项目博弈的一个纳什均衡.定义控制参数,给出边际效益后悔值定义,利用后悔值改进了贪婪算法,证明基于后悔值贪婪算法求得的指派是非合作项目博弈的一个纳什均衡.通过数值仿真实验发现,与模拟退火算法比较,贪婪算法能够得到更好的社会效益,而且基于后悔值贪婪算法比贪婪算法得到更好的社会效益.

Greedy algorithms can be used to solve the general model for project game in the community. The obtained assignment approximates social optimality. In this paper, we present a mechanism to reweight the players, and proved that the assignment obtained using greedy algorithm is Nash equilibrium with the given weights. In addition, after defining regret value and two scale parametersσand/β, we propose advanced greedy algorithm based on regret value. Numerical experiment results show that the presented algorithm can get better results.