凯恩斯选美的图论模型及其进化算法.doc

凯恩斯选美的图论模型及其进化算法华侨大学数量经济研究院李拉亚内容提要 本文中，我们用图论方法分析凯恩斯选美。我们发现凯恩斯选美可归结为图上的最长路径问题，并提出了一种能同步得出图上所有最长路径的进化算法。 我们还提出了存在Hamiltonian圈的一个新的必要条件，由此解释了凯恩斯选美的行为复杂性。 关键词：凯恩斯选美，算法，最长路径，Hamiltonian圈The graph model of Keynesian beauty contest and its evolutionary algorithmAbstract In this paper, we use graph theory to analyze Keynesian beauty contest. We find that Keynesian beauty contest is equal to find the longest path in a graph. We also present an evolutionary algorithm that can find all longest paths in a graph synchronously. We present a new necessary condition for Hamiltonian cycles. Based on this new necessary condition, we can explain the complicated behavior of Keynesian beauty contest.Key words: Keynesian beauty contest, Algorithm, Longest path, Hamiltonian cycle 一、导言 从众行为指群体中个体行为追随群体中大多数个体的行为。在自然界中，我们会发现许多动物具有从众行为的本能。这种普遍存在的现象表示其存在的合理性，它有助于群体的生存，是动物漫长进化过程中优胜劣淘的结果。在经济社会的一些场合，经济人也具有从众行为。通论第12章长期预期状态第五节的凯恩斯选美比喻便是一种典型的从众行为。凯恩斯指出：“或者，上述比喻稍有改变，专业投资好比报纸上的选美比赛。比赛中，评选者在100张照片中挑选出6个最美者。谁的选择结果与全体评选者平均爱好最接近，奖就授予谁。因此，每个评选者不选择他自己认为的最美者，而是选择那些他认为最可能是其他评选者挑选的最美者。而所有其他评选者也都用同样观点，不选择自己真认为的最美者，也不选一般人真认为的最美者。我们已进入第三阶段，我们用自己的智慧去预期一般人预期一般人认为的最美者。还有一些人，我相信，他们将到达第四，第五和更高的阶段。” 凯恩斯选美的本质思想是，个体选择追随群体中大多数人的选择。决定选择的关键因素是持某种选择的人数多少，而不是这个选择本身正确与否。凯恩斯选美的关键问题是，群体中大多数人的共同选择是怎样形成的。 实验经济学家设计了一种猜数游戏，用于探索凯恩斯选美中理性人的行为。如Nagel(1995)、Stahl(1996)和Ho等人(1998)提出的实验经济学案例，要求群体中每个人写下1到100间的一个数字，要求这个数字是大家所写下数字平均数再乘以p值(p小于1大于0，如p为2/3)。他们假定每一个人均认为自己会比其他人提前考虑下一阶段的情况。在第0阶段，每人均随机选择一个数，如均值50。第二阶段，每个人认为既然其他人在第一阶段选50，那么自己就选50p。如此类推，第k阶段，大家选50pk。这样，最终选值趋于0。类似方法还可见Moulin(1986)、Bosch-Domenech等人(2002)的实验分析。计算机算法中的一致算法可特别用于研究网络上所用点的状态收敛到一个一致值。该算法只要求网络上的每一点与自己相邻的点交流信息，通过一定的控制条件，达到全局的控制目标。Schmalz, Fujita和Sawodny(2009)以一致算法为基础，设计了一种新算法分析金融市场的泡沫行为等，其中也涉及到群体共识问题。 上述猜数游戏和一致算法都收敛到一个值，这与凯恩斯选美反映的投资市场的复杂行为不一致。本文中，我们以图论为基础，给出凯恩斯选美形成共识的一种新方法。该方法称之为凯恩斯选美图论模型。我们方法关于凯恩斯选美结果的唯一性和多样性，关于为提高算法的有效性而产生的不确定性，关于凯恩斯选美行为特征与混沌系统的非线性特征类似等内容，较能反映投资市场的复杂行为。 本文分为六节。第一节是导言。第六节是总结。本文的主要贡献是：第二节提出了凯恩斯选美方法可视为图上的最长路径算法；第三节设计了一种较为接近经济人实际行为并能同时得出所有最长路径的进化算法。第四节用算法的时间概念解释了不完备信息和协调预期对提高算法有效性的作用，解释了经济系统内在产生不确定性的一个原因；第五节证明了存在Hamiltonian圈的一个新的必要条件，并由此比较了凯恩斯选美特征与混沌系统的非线性特征，说明了凯恩斯选美的行为复杂性。 二、凯恩斯选美的图论模型1、关系图定义：设在一经济系统中存在N个经济人，每个经济人只认识这N个人中有限的人数。如果每个人视为一个点，两点之间的联线表示这两个人相识。这样，这N个人和他们之间的相识关系就构成一个图，称之为关系图。关系图是每边长度均为一的无向单纯图。无向指边没有方向。单纯图指图中不存在起于一个点又回到这个点的边，并且两点之间最多只存在一条边。本文说的图，均指这样定义的关系图。 v00v11v04v03v02v01v10v09v05 图 1 v08v17v18v12v13v06v14v15v19v16v07如在图1中，我们用v00, v01, v02, , v19分别表示图1的20个点。这20个点代表20个评选人。两点之间的联线表示这两个评选人相识。在图1中，每个评选人均只认识三个人。因之，每个点均只有三条联线。 2、从众原则法我们把选美过程划分为阶段。第一阶段，每个人都有自己的选择。如v00选a, v01选b, v02选c。可以有重复选择，如v00选了a, v11也可选a。这里a,b,c代表不同的选美方案。第二阶段，每个人都把自己的选择告诉自己所认识的人，并且这些所认识的人受其影响也选择同一方案，作为自己投票方案诸多选择中的一种选择。如我们用路径v00v01表示v00选择a，v01受v00的影响也选择a。这里v00表示路径的起点(也称作左端点)，v01表示路径的终点(也称作右端点)。第三阶段，由第二阶段形成的各个路径由其右端点延长到下一个相联的点(该点不在原来路径上)，得出新的更长的路径。如路径v00v01v02表示 v00、v01和v02均选a。 其余阶段可如此类推。如果群体中人数为N，则最多存在N个阶段。 关系图路径的长度用路径上的点数表示。依据投票的从众原则，影响人数最多的方案成为选美结果。由此，选美投票的从众原则可简化为在图上找出最长路径。 3、推销员法换个角度，我们可以把凯恩斯选美看作是推销员推销自己选美方案的竞赛。群体中每个人均努力推销自己的选美方案。显然，尽可能多通过图上点一次并仅一次的推销员的选美方案，其效率最高，影响的人数也最多，其选美方案成为选美结果。这一方法同样等同于在图上找出最长路径。4、选美结果唯一性或多样性 我们知道，当图存在Hamiltonian路径(即通过图上每一点一次并仅一次的路径)时，图上最长的路径是Hamiltonian路径。如果Hamiltonian路径两端的点是相邻点，那么这个路径是Hamiltonian圈。 如果图上仅存在一条最长路径，则存在一个选美结果。存在多个相同长度的最长路径时，则存在多个可能的选美结果。 如果存在至少一个Hamiltonian圈，因为每个评选人都能处在一条Hamiltonian路径的起点上，则每个评选人选择的最美者都可能成为选美结果，这导致选美结果的分散化。 三、凯恩斯选美的进化算法 在本节中，我们设计一种进化算法，用其同步找出图上的所有最长路径。 1、基本概念 (1)简单路径：一个简单路径指路径上的所有点是不相同的。换言之，简单路径不包含圈。 (2)相邻路径：如果两个简单路径有且仅有一个相同的点，并且这个相同的点是端点(端点指路径最两边的点)，那么这两条路径称之为相邻路径。 (3)种群：在图1中的所有边构成第一代种群p(1)。种群是一个集合，它的元素由简单路径构成，并且它的每个简单路径具有相同的点数，或者，具有相同的边数。下一代种群的元素由上一代种群中通过选择的的两个元素合并而成。 (4)适应条件：适应条件要求两个简单路径是相邻路径。如，第一代种群中的两个简单路径v00v01 和v01v02满足适应条件，因为这两条边相邻，它们有共同的端点v01。 (5)选择：如果种群中两个简单路径满足适应条件，即它们相邻，那么这两个简单路径被选择。 (6)合并：我们用“+”表示合并运算。如果两个简单路径s1 和s2被选择(即它们相邻)，并且s1的右端点是s2的左端点，那么我们合并这两个简单路径得到一个新的简单路径。在这个新的简单路径中，s1的右端点和s2的左端点是重合的，即这两个相同的点在新路径中只出现一次。如：v00v01 + v01v02 = v00v01v02v00v01v02 + v02v03v04v05 = v00v01v02v03v04v05 简单路径s1 和s2相邻，但是s1的右端点不同于s2的左端点。我们需要逆转一个路径或者两个路径，让s1的右端点是s2的左端点。注意一条路径的逆转仍然是同一条路径，只是将哪一个端点视为起点而已。然后这两个简单路径能被合并得到一条新的简单路径。如：v00v01 + v02v01 = v00v01 + v01v02 = v00v01v02.v01v00 + v02v01 = v00v01 + v01v02 = v00v01v02. 明显的，我们通过合并两个简单路径仍然得到一个新的简单路径。我们的合并运算便是一般进化算法的杂交或交叉运算。(7)淘汰：为限制新种群的元素数量，淘汰掉部分新种群的元素，以保证在有限的时间和有限的空间完成进化运算。这样作有极大的风险遗失最优解，从而只得到次优解。我们称之为风险淘汰。风险淘汰的条件可依具体情况而定，如随机挑选部分元素予以淘汰。如果我们加深了对问题的认识，依据我们对问题的了解，淘汰掉新种群中不会遗失最优解的元素，这种淘汰是最为可取的，但也是最为困难的。这种淘汰称之为最佳淘汰。 2、计算过程我们算法的基本思想是，每一期中，尽可能形成最长的简单路径。为了同步求得所有的最优解(即最长路径)，我们没有淘汰新种群中的元素。本文中，为节省篇幅，我们省约了该算法不淘汰新种群中的元素时不会丢掉最长路径的证明。 我们的算法存在两个过程。我们由第一个过程开始。在第一个过程，我们仅由上一个种群p(i - 1)得到新的种群p(i)。如果上一个种群中每一个元素所包含的边数是k，那么新种群中每一个元素所包含的边数是2k(这里我们假定新种群不为空)。这一过程称之为倍增过程。倍增过程是我们算法计算量的主要部分，也是我们算法的核心思想。这一过程选择种群中所有可能的两两相邻的简单路径，被选择的两个相邻简单路径被合并形成新的简单路径。新的简单路径成为下一代种群的元素。这个下一代种群在算法的下一次迭代中被用到。这一过程导致种群的进化，新的种群中简单路径的长度要长于旧种群中简单路径的长度，即更接近于解的特征。 设图中点数是N，当倍增过程继续一段时期后，当新种群中每一个元素所包含的边数是2k ，如果2k+1大于N-1，便不可能再继续下去了。此时，我们得到各个种群p(1),p(2),p(3),p(k)。p(1)的元素所包含的边数是b(1)=21-1, p(2)的元素所包含的边数是b(2)=22-1，p(3)的元素所包含的边数是b(3)=23-1，p(4)的元素所包含的边数是b(4)=24-1，p(k)的元素所包含的边数是b(k)=2k-1。我们采用如下的第二个过程。或者，这一过程任一步得到的新种群元素个数为0，则从上一步进入如下的第二个过程。 在第二个过程，我们有两个种群。一个是当前的种群。另一个是以前产生的旧种群中的一个。我们规定在合并这两个种群中每相邻的两个简单路径时，其中一个简单路径来自于当前种群，而另一个简单路径来自于被选择的旧种群。新的简单路径作为下一代种群的元素。具体计算可见下面： p(k+1)中的元素由p(k) 和p(j)的相邻简单路径合并构成。这里，设b(j)是b(1)到b(k)中与N1b(k)最接近的数，使p(k+1)的元素所包含的边数b(k+1) = b(k) + b(j) = N1。如果得到的新种群元素个数为0，设b(m)是b(1)到b(k)中与N1b(k)次接近的数，则p(k+1)中的元素由p(k)和p(m)的相邻简单路径合并构成。 p(k+2)中的元素由p(k+1) 和p(h)的相邻简单路径合并构成。这里，设b(h)是b(1)到b(j-1)中与N1b(k+1)最接近的数，使p(k+2)的元素所包含的边数b(k+2) = b(k+1) + b(h) = N1。如果得到的新种群元素个数为0，设b(n)是b(1)到b(j-1)中与N1b(k+1)次接近的数，则p(k+2)中的元素由p(k+1)和p(n)的相邻简单路径合并构成。由此类推，直到新种群中的元素所包含的边数等于N1或者b(1)被使用为止。这一过程称之为扩展过程。这一过程也导致种群的进化，新的种群中简单路径的长度要长于旧种群中简单路径的长度，即更接近于解的特征。 如果求得的最长路径为Hamiltonian路径，我们便可从中寻找Hamiltonian圈。 我们看到，在上述两个过程中，新一代种群的简单路径保存了上一代种群原来两个简单路径遗传下来的信息(即同样的点和同样的点的顺序)，没有产生变异(即有不同的点或点的顺序不一样)。3、计算结果在图1中，我们用上述进化算法发现总共有30个不同的Hamiltonian圈，有1620条Hamiltonian路径，5520条长度为18的简单路径，16140条长度为16的简单路径，2400条长度为8的简单路径, 240条长度为4的简单路径, 60条长度为2的简单路径。在图1中长度为16的简单路径数量最多，达到16140，接近16384(即214)。四、算法的时间概念及其经济理论意义1、算法的时间有效和时间无效 我们称存在多项式时间的算法为时间有效算法。简单讲，时间有效算法能在有限时间得出结果。我们称存在非多项式时间的算法为时间无效算法。该类算法不能在有限时间得出结果。在经济研究中采用传统数学方法，我们研究解的存在性，唯一性，稳定性等，并试图求出存在的解。引进算法的时间概念后，我们就需要研究，即使一个经济系统的解具有存在性，唯一性，稳定性等性能，我们还要问获得这个解的算法是时间有效的还是时间无效的。如果获得这个解的算法是时间无效的，那么这个解就没有可操作性。 在计算机算法中，存在多项式时间的算法的一类问题，称之为P类问题，如最短路径问题。在计算机算法中，也存在至今没有找到多项式时间的算法的一类问题，称之为NP类问题，如最长路径问题。NP问题到底是多项式时间，还是非多项式时间，尚无定论，是世界上六大数学难题之一。我们已把凯恩斯选美视为在图上找出最长路径。因此，按照我们的图论模型条件，凯恩斯选美是一个NP问题。 我们前面的计算结果表明，由于我们没有淘汰新种群中元素，我们的算法虽能同步找出图上的所有最长路径，但它是基于相邻简单路径两两组合的运算，这种运算不仅是非多项式时间占用，也是非多项式空间占用。但是，它较之其它寻找最长路径算法，有自己的优点，一是能同步得出所有最长路径，二是要求迭代次数少。如果图中点数是N，则保证2k = N成立的最大k便是倍增过程的迭代次数。此外，该算法还可用于求最大独立集问题，有一定的通用性。 2、风险淘汰与不完备信息假设要让上述算法变得有效，在没有加深对问题的认识前，我们可采用风险淘汰的方法，在所有可能的路径中，只采用其中一部分路径。尽管这样做会冒极大的风险丢掉最优解，但它能节省计算的时间和空间，提高算法的有效性。 风险淘汰的经济理论意义是，在实际经济中，经济人为了能在有限的时间和成本下取得结果，或在有限注意力下分析信息，他不能充分利用他可能得到的信息，只使用其中部分信息。我们的这一分析结论，支持了李拉亚(1991)和Sims(2003)关于经济人只用他可能得到的信息中的部分信息作预期和决策的思想。使用部分信息进行运算，只能得到近似结果，可能存在系统误差，从而导致不确定性。这一思想与理性预期理论假设经济人使用所有可以利用的信息(即完备信息假设)是不同的。进化算法关于选择和淘汰的各种思想方法，可供经济学家参考。这里不作论述。3、预期管理的协调预期思想在羊群中，存在一只领头羊，羊群随着领头羊走。在一些经济场合，也存在类似领头羊的行为，这便是行为经济学中的羊群效用。领头羊行为也能提高算法的有效性。凯恩斯选美中只存在从众行为，不存在领头羊行为。但是，如果在人群中有一个权威的机构或者人士起到带头羊的作用，每个经济人对带头羊的语言和行为有统一的定义和理解，这样每个经济人都能依据这一带头羊的预期调整自己的预期，他相信别人也依据带头羊的预期调整自己的预期。因此，他就不用再考虑别人的预期了，也不用考虑凯恩斯选美所指的别人预期别人的预期了，即不用考虑高阶预期了。这个带头羊起到了协调群体中预期的作用。协调预期提高了算法的有效性，导致预期较快向同一性靠拢，即导致带头羊的预期较快成为群体中大多数人的共同预期。这是预期管理理论的协调预期思想，其简要介绍可见Morris and Shin (2008)的论文。 五、凯恩斯选美的行为复杂性 如果图上出现Hamiltonian圈，则选美结果分散化。分析图上能否出现Hamiltonian圈，是凯恩斯选美分析的难点。它不仅涉及算法，更涉及图论知识。对凯恩斯选美认识的深入，必伴随对它相关数学知识认识的深入。图论中，关于Hamiltonian圈的充分条件很多，关于Hamiltonian圈的必要条件很少。在本节中，我们给出存在Hamiltonian圈的一个新的必要条件。这是本文方法上的创新。它将帮助我们认识凯恩斯选美的行为复杂性。我们还可以用这一新的必要条件设计淘汰条件，淘汰掉一些不会影响最优解的路径。这便是我们前面所说的最优淘汰。 1、基本思路如果一个图的点分别在两个不相交的集合中，该图每一条边的端点分别位于这两个集合中，这样的图称之为二分图。如果二分图两个不相交的集合有相同的点数，则这种二分图称之为平衡二分图。二分图存在Hamiltonian圈的一个必要条件，是它的两个集合必须包含相同的点数。换言之，二分图必须是平衡二分图才有可能存在Hamiltonian圈。我们的基本思路是试图在一般图中利用二分图的这一必要条件。2、怎样转换一般图到二分图 我们使用BFS(breadth first search)方法得到图G的BFS树T。让这个BFS树T有与图G同样的点与边，我们得到图GT。图GT等于图G。AEDCBHGF 图2 图 GI 如我们有图2，我们使用BFS方法得到它的图GT，见图3。图3有四个点集合，分别是A，B，H，D，C，I，G，E和F。每个点集合可视为一层。把不相邻的层上的点集合合并为一个点集合。这样可得图3的两个点集合A，C，I，G，E和B，H，D，F。它们称之为图3的两个划分集合。类似可定义一般图GT的两个划分集合。在同一层次上两点的边称为横边，如边IG和边GE。 ADGBHCF 图3 图 GTEI在图3中， 如果我们删去横边IG和GE，得图4。很明显，图4是二分图。这个二分图的两个不相交的点集合是A，C，I，G，E和B，H，D，F，即是图3的两个划分集合。但是图4不是平衡二分图。ADGBHCF 图4 EI 在图3中，如果我们收缩点I和点G为一点S，保留点I和点G的所有连接其它点的边，如果有重复的边，则只保留一条边，并删去图中其余横边，得图5。很明显，图5是二分图。并且，图5是平衡的二分图。注意，两点间有横边联接，这两点才能被收缩为一点。ADBHCF图5 收缩点后的二分图 STES3、一般图GT存在Hamiltonian圈的一个新的必要条件定理一、若一般图GT存在Hamiltonian圈， 则由一般图GT删去横边和收缩点的方式形成的二分图上也存在Hamiltonian圈。 证明： 设一般图GT存在Hamiltonian圈。Hamiltonian圈通过的横边，我们可把横边上的点收缩为一点。这是把Hamiltonian圈相邻的点收缩为一点，Hamiltonian圈仍然存在。同时，我们删去Hamiltonian圈不通过的横边。由此我们得到一个保留了Hamiltonian圈的二分图。证毕。 推论一、若一般图GT存在Hamiltonian圈， 则必可由一般图GT删去横边和收缩点的方式形成一个平衡二分图。证明：由定理一和二分图存在Hamiltonian圈的必要条件可证。证毕。易知，如果一般图GT的两个划分集合的元素个数不相等，设其差为X，但是元素个数多的集合的点所在层次上横边的个数大于或等于X，则一般图GT能由删去横边和收缩点的方式变为一个平衡二分图。这也可作为一般图存在Hamiltonian圈的必要条件。 横边还提供了一般图GT存在Hamiltonian圈的重要先验信息。如图3若存在Hamiltonian圈，则横边IG和横边GE之一必定在Hamiltonian圈上，但横边IG和横边GE不能同时在Hamiltonian圈上。由此，我们如用上述进化算法搜寻图3的Hamiltonian圈，则可在算法中加上新的选择条件，淘汰掉同时包含横边IG和横边GE的所有路径。 我们也可以把上述进化算法分为两次并行进行，一次只搜寻Hamiltonian圈包含横边IG的情况。另一次只搜寻Hamiltonian圈包含横边GE的情况。这样，在只搜寻Hamiltonian圈只包含横边IG的情况时，我们能淘汰掉同时包含横边IG和横边GE的所有路径，淘汰掉同时包含横边HG和横边GF的所有路径，淘汰掉同时包含横边HI和横边IF的所有路径，淘汰掉同时包含横边IH和横边HG的所有路径，及淘汰掉同时包含横边IF和横边FG的所有路径。4、凯恩斯选美的特征 在存在Hamiltonian圈新的必要条件中，我们能看到Hamiltonian圈对图形结构的敏感性。在图中增加一条边(一个点)或减少一条边(一个点)，Hamiltonian圈的存在与否便会出现完全不同的结果。我们也看到了即使是简单的图形，如图1，也能导致凯恩斯选美的复杂行为。我们知道混沌系统具有简单的方程，复杂的行为，及对初始条件的敏感性的特点。凯恩斯选美的这些特征与混沌系统的非线性特征类似，较能反映投资市场的复杂行为。 六、结论 本文提出了凯恩斯选美的图论模型。该模型可以归结为找出图上的最长路径。本文还设计了一种进化算法。我们用该算法同步找出图上的所有最长路径。 本文描述了经济系统存在凯恩斯选美结果的三种情况。如果关系图中仅存在一条最长路径，则存在一种选美结果。如果关系图中存在多个相同长度的最长路径时，则存在多种选美结果。如果存在一个Hamiltonian圈，则导致选美结果的分散化。 本文进一步证明了一般图上存在Hamiltonian圈的一个新的必要条件，这是本文方法上的创新。我们的这些研究，揭示了凯恩斯选美的行为复杂性。 在经济研究中引进算法分析，是经济学一个具有广阔发展前景的研究方向。算法的时间有效还是无效将成为经济理论中的一个重要概念。算法分析也将成为经济理论的一个重要部分和基本分析工具，成为数量经济学的一个新分支。 我们的研究方法也可推广到其它涉及群体从众行为的学科中，如社会学、政治学等。参考文献1李拉亚 (1991)，通货膨胀机理与预期，中国人民大学出版社。2周翼，项杨 (2001)，凯恩斯的“ 选美论”：一个网络经济学的解释，数量经济技术经济研究，第4期。3Allen, F., S. Morris, and H.S. Shin (2006), “Beauty Contests and Iterated Expectations in Asset Markets,” Review of Financial Studies 19, 719.4Bosch-Domenech, A., Montalvo, J. G., Nagel, R., and Satorra, A. (2002), “One, Two, Three, Infinity, .: Newspaper and Lab Beauty-Contest Experiments，” American Economic Review, December, Vol 92 No.5, pp1687-1701.5Ho, Teck-Hua, Colin Camerer and Keith Weigelt (1998), “Iterated Dominance and Iterated Best-Response in Experimental p-Beauty Contests,” American Economic Review 88, No. 4, 947-969.6Keynes, John Maynard (1936)，“ The general theory of employment, interest, and money.” London: Macmillan.7Morris，S. and H.S. Shin (2008)，“Coordinating Expectations in Monetary Policy，”in Central Banks as Economic Institutions, edited by.Jean-Philippe Touffut, Edward Elgar Publishing, pp.88-104. 8Moulin, Herve (1986), “Game Theory for the Social Sciences,” 2nd Ed. New York: NYU Press.9Nagel, Rosemarie (1995), “Unraveling in Guessing Games: An Experimental Study,” American Economic Review 85, 1313-1326.10Schmalz, M., Fujita, M., Sawodny, O. (2009), “Directed Gossip Algorithms, Consensus Problems, and Stability Effects of Noise Trading,” European Journal of Economic and Social Systems, Vol. 22, No. 1, pp. 43-61, 2009.11Sims, C.A.(2003)，“Implications of rational inattention,” Journal of Monetary Economics, 50(3), pp. 665-90. 12Stahl,Dahl O.(1996), Rule Learning in a Guessing Game， Games and Economic Behavior, 16(2), pp.303-30.附录一、 我们算法得出的图1所有30个Hamiltonian圈v00v01v02v03v04v13v12v11v10v09v08v07v06v16v17v18v19v15v14v05v00v00v01v02v03v04v13v14v15v16v17v18v19v12v11v10v09v08v07v06v05v00v00v01v02v03v11v10v09v08v07v06v05v14v15v16v17v18v19v12v13v04v00v00v01v02v03v11v12v19v15v16v17v18v10v09v08v07v06v05v14v13v04v00v00v01v02v09v08v07v06v05v14v13v12v19v15v16v17v18v10v11v03v04v00v00v01v02v09v08v07v06v16v17v18v10v11v03v04v13v12v19v15v14v05v00v00v01v02v09v10v11v03v04v13v12v19v18v17v08v07v06v16v15v14v05v00v00v01v02v09v10v18v17v08v07v06v16v15v19v12v11v03v04v13v14v05v00v00v01v02v09v10v18v19v12v11v03v04v13v14v15v16v17v08v07v06v05v00v00v01v02v09v10v18v19v15v16v17v08v07v06v05v14v13v12v11v03v04v00v00v01v07v06v05v14v13v12v11v10v18v19v15v16v17v08v09v0