重复囚徒困境的学习和响应模型  

The Learning and Response Model for Iterated Prisoner's Dilemma

作　　者：宋亦泠[1] 王秉中[2] 朱洪[1] 蔡晟[1] 

机构地区：[1]复旦大学计算机科学与工程系,上海200433 [2]南京大学计算机科学与技术系,江苏南京210093

出　　处：《计算机工程与科学》2007年第10期115-119,共5页Computer Engineering & Science

摘　　要：囚徒困境问题是博弈论的一个重要范例,对此的研究涉及经济学、社会学、生物学等广泛领域。Axelrod R在文献[1]中从进化的角度研究和探讨了经典囚徒困境的一个扩展——重复囚徒困境。这种博弈要求参与者反复进行囚徒困境的博弈,并且可以记住他们的对抗历史。Axelrod还组织了两次重复囚徒困境的计算机竞赛,最终胜出的都是简单的"以牙还牙"策略[2]。这之后有不少学者试图找到可以击败它的策略,都未能取得显著成功。本文提出了一种学习和响应的理论模型,实际中的许多重复囚徒困境的策略都可以纳入这一模型中。我们分析了实现这一模型的难点和复杂度,同时给出了一种基于树结构的实现方式,并在实验中把它和"以牙还牙"作比较。实验以及分析表明,策略在竞赛中表现的优劣主要取决于如何利用一些启发式规则来权衡学习代价和博弈的总利益,以及在此基础上如何抽取对手的关键信息。Being an important example in game theory, Prisoner＇s Dilemma （PD） has attracted widespread attention in a variety of disciplines such as economics, sociology and biology. Iterated Prisoner＇s Dilemma （IPD）was studied by Robert Axelrod in[1]to model the evolution of cooperation. In the game of IPD, two players repeatedly play PD and have the memory of the previous encounters. In the computer IPD tournaments organized by Axelrod, a simple strategy TFT （Tit for it） won twice. After that, a great mtmber of researchers sought to design new strategies to beat TFT in the tournament, but without much success. We propose a learning and response model for IPD which has many real-life strategies as its implementations. After analyzing the difficulty and complexity of implementing our model, we give a tree-based strategy and com- pare it with TFT in IPD toumaments~ Experimental results show that a strategy＇s behavior largely depends on its way to balance the trade-off between the learning cost and the overall payoff,and depends on how it investigates and utilizes its opponent＇s characteristics based on what it has learned.

关 键 词：囚徒困境 重复囚徒困境 博弈论 学习和响应 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]