基于启发式的分布式协调博弈中的自组织

对于更高的k值，我们允许代理了解有关上一时间段餐厅入住率的更多信息，以进行比较。结果：图4显示了N=1000时该策略的仿真结果。在x轴上，我们绘制了餐厅，在y轴上，我们绘制了前往餐厅NIF或所有餐厅的代理数量，即所有i∈ N、 我们显示两个快照。图4：对称强化“事前更新”策略的模拟结果（要求成功（f=1），惩罚失败（f=0.1））。我们给出了两个快照（左栏t=5000，右栏t=10000），展示了N=1000个代理的系统可能的演变。行显示了信息集不同值的结果，k=1、k=2和k=3。很明显，随着信息集大小的增加，收敛速度会更快。时间片t=5000，另一个时间片t=10000。这三行显示了代理在三个不同信息集（k=1、2、3）下的分布。首先要注意的是，动力学变得相当缓慢。即使在10000个时间片之后（对于N=1000），也很难实现协调，如图4右侧的面板所示。然而，我们注意到收敛是有保证的。作为一种解释，考虑一个在所有餐厅中代理分布为（501499,0，…，0）的案例。根据目前的策略，只有第一家餐厅可以吸引代理，第二家餐厅只能失去代理，无论过程多么缓慢。下一个重要特征是，通过有限量地增加信息集（从k=1增加到2和3），极大地提高了协调程度，尽管动态在某一点上变得缓慢。

例如，在底部行中，我们看到分布变化非常缓慢，从t=5000到t=10000。因此，我们看到，在很长一段时间内，不同餐厅都有代理集群，然后才全部瓦解为一个巨大的集群，即发生绝对融合。这种集群行为是暂时的。3.3.2不对称更新考虑代理i在餐厅r的时间t，可能会选择另一家餐厅l。如果Alt<Art，她会留在餐厅r。否则，她会搬到餐厅l。不对称更新方案在更新概率向量{pijt}的方式上不同于对称方案。如果当前餐厅的吸引力与可能选择的餐厅之间存在差异，代理会将更高的权重分配给更具吸引力的选项，并减少其他所有餐厅的权重。形式上，如果Alt<Artpij（t+=（pijt+f（1- pijt）如果j=r（1- f）PIJT否则。如果Alt=Art，pij（t+）=pijtfor j∈ N，如果Alt>Artpij（t+）=（pijt+f（1- pijt）如果j=l（1- f）PIJT否则。最后，概率被归一化：pij（t+1）=pij（t+）/Xipij（t+）。所需信息：此策略需要与symmetricupdating策略完全相同的信息集。结果：图5显示了f=0.25时不对称更新策略的模拟结果。结果与对称更新方案相当。我们看到动力学变得缓慢。当我们将信息集从k=1扩展到2和3时，收敛在初始阶段发生得更快。但过了一段时间，所有信息集的速度都变慢了。但同样在迭代次数充足的情况下，会发生绝对收敛。因此，我们看到在很长一段时间内存在集群。但和对称更新一样，这种行为是暂时的。通过改变参数fwe研究了收敛前的动力学。

图6显示了具有多个信息集（k=1、2、3）的两个不同f值的模拟结果。为了量化收敛前的稳定性程度，我们计算了最大值的平均值。图5：具有不对称强化的“事前更新”策略的模拟结果，其中只有成功才有回报（f=0.25）。我们提供了两个快照（左栏t=5000，右栏att=10000），展示了n=1000个代理的系统的可能演变。这些行显示信息集不同值的结果，k=1、k=2和k=3。很明显，随着信息集大小的增加，收敛速度会加快，就像对称更新规则一样。图6:f=0.1和0.9以及三个信息集k=1、2和3的不对称强化的“事前更新”策略的模拟结果。我们展示了代理在所有时间片上分配给任何onerestaurant的最大概率的平均值的演化。高配筋（f=0.9）时，最大概率收敛速度比低配筋（f=0.1）时快得多。代理分配给任何餐厅的概率。对于较小的f值（f=0.1），与较大的f值（f=0.9）相比，平均概率上升得非常快。此外，对于较大的信息集，与较小的信息集相比，最大概率的平均增长速度较慢。这与以下发现一致：协调在信息集较大的情况下发生得更快，因为这需要多次切换以确保收敛。当然，随着切换频率的提高，对特定餐厅的增援也会减少。3.4通过Polya的urn模型进行强化学习我们使用Poly的urn模型（[9]）引入了一种新策略，有效地捕获强化学习。

让我们定义φ=mnN- m（3），其中m是可调参数，取0和N的离散值。我们用nijt表示在时间片t之前，第i个代理访问餐厅j的次数。然后，选择餐馆的概率由pijt=1+φnijtN+φPnijt给出。（4） 直观地说，这是基本无学习策略（需要pijt=1/N）的扩展，通过Polya的urnmodel嵌入强化学习。所需信息：第i个代理的所需信息集仅来自代理在不同餐厅的成功全过程。可以合理地假设代理会跟踪他们自己的访问。还要注意的是，在任何时间段，代理人都不需要从她没有去过的餐厅获得任何信息，正如早期策略所要求的那样。这是可能的，因为Ethere不涉及比较。概率策略是根据历史成功经验设计的。结果：图7显示了N=500和t=5000时不同m值（见等式3）的数值结果。在左面板中，我们显示了至少有一个代理在不同的因子m值和不同的时间段占据的餐厅数量（nocc）。显然，当m=0时，Polya的方案将如图7所示：左面板：当N=500，t=5000时，作为Polya因子m的函数，所占据的静物数量（nocc）从0演变为495。在limitm中→ N、 存在有限钢筋。我们可以分析表明，在这种情况下，入住率将为63.2%。在其他限制m中→ 0，它收敛于无学习策略，因此多数问题在线性时间内得到解决，如图2所示。

右图：在N=500、t=500至5000的情况下，作为多因子m的函数，餐厅的分形（fractionof restaurants，focc）的演变从5到495。很明显，对于小规模的m，占用的餐厅数量非常少，而在另一个极端，占用率接近63.2%(≈ 这证实了早期的结果。收敛到无学习情况，出现绝对收敛。这意味着只有一家餐厅会被占用。这可以从图中看出，在不同时间段的条形图上，通过fixingm=0。在另一个极端，m=N-5（对于模拟，我们无法设置m=N），我们看到500家餐厅中约有318家餐厅被占用。这与将factorm设置为非常接近N的概念相一致，这意味着如果一个代理去一家餐厅，她会在剩余的时间里一直呆在那里。因此，第一次切片中的选择本身就决定了代理在餐厅中的分布，因为这种分布永远不会因为内部信息而改变。很容易证明，由于代理从均匀分布的概率开始（piuj0=1/N），在第一时间，63.2%的代理将被占用。我们跳过这个分数的导数。感兴趣的读者可以参考[？]。我们可以很容易地验证318/500接近63.5%，因此这验证了我们的结果。同一图中的右侧面板显示了占用的静物比例，即focc=nocc/N。结果与左侧面板完全一致。我们还注意到，Polya方案中的m=N（即有限钢筋）与非对称更新策略中的assumingf=1相同。

因此，在极限范围内，这两种策略完全相同。该策略允许我们通过改变因子m在强化的广谱之间进行插值。特别是，它允许我们覆盖对称和非对称更新策略分别完成的相同范围。3.5事后知识如果是Sec的事前知识。3.3、westudied策略，即代理人可以获得新选择餐厅的吸引力信息，并对chosenrestaurant和当前餐厅的吸引力进行比较。然而，在实际参观另一家餐厅之前，了解其吸引力可能是一项代价高昂的活动。在本节中，我们研究了一组相同的策略，在这些策略中，代理人只有在搬到所选餐厅后才能获得关于吸引力的信息。与早期案例的一个重要区别是，目前的策略允许后悔。在经纪人搬到一家新餐厅后，她开始了解它的吸引力，因此在换餐厅之前无法进行比较。根据相对吸引力的不同，更新概率向量的方式与inSec相同。3.3.3.5.1对称更新考虑代理i，其中i∈ N，在任何通用时间段t。假设她在餐厅r，并给定她的概率向量{pijt}，她概率地选择了餐厅l。在了解Altand Art之后，概率向量pijt的更新方式与秒完全相同。3.3.1。为了避免重复，我们跳过了概率更新方案。所需信息：所需信息来自代理访问过的餐厅。因此，没有获得外部信息。结果：图8显示了f=1和f=0.1时顶部面板中的模拟结果。我们显示了两个时间片的结果，分别为t=5000和t=10000。

与前面的案例一样，这种策略也相当缓慢，但最终会收敛到有限的一家餐厅。当然，这比事前的knowledgecase要慢。图8：对称（顶部面板，f=1和f=0.1）和非对称（底部面板，f=0.5）钢筋的“事后更新”策略的模拟结果。在x轴上，我们绘制餐厅的标识。对称更新导致餐厅更拥挤。3.5.2非对称更新与上述类似，考虑代理i∈ N、 在任何一般时间段t。假设她在餐厅r，并给出她的概率向量{pijt}，她概率选择餐厅l。在了解Altand Art之后，概率向量pijt的更新方式与秒中的更新方式完全相同。3.3.2。所需信息：所需信息仅来自她访问的餐厅，因此没有获得外部信息。结果：模拟结果已在图8和图9的下部面板中报告。我们发现，餐厅代理分布的结果在质量上与对称更新的结果相似，只是协调性较差，因为许多餐厅代理数量较少。我们研究了图9中形成的瞬态团簇的稳定性程度。对于较高的off值，与较低的f值相比，平均过最大概率上升了很多，尽管最终他们的行为是相似的。图9：系统规模N=1000时，f=0.1和0.9的不对称强化“事后知识”策略的模拟结果。我们展示了代理分配给任何一家餐厅的所有时间片的最大概率的平均值的演变。

在高强化（f=0.9）情况下，最大概率的收敛速度远远快于低强化（f=0.1），类似于“事前更新”策略的情况。4自组织与协调在本节中，我们讨论了在解决协调问题的多agent系统中，自组织发生的程度。4.1协调的出现我们已经看到，一些策略，特别是那些需要事先信息或知识的策略，原则上可以被认为需要支付一些成本才能获得信息。同样现实的是，代理可能会在收敛到解决方案的速度与解决方案的效率之间进行权衡。也就是说，他们可能会发现在较短的时间内获得多数，而不一定是绝对多数，以达成解决方案是有用的。一个平行的主题是，最初所有的餐厅都是相同的。但在绝对趋同的情况下，其中只有一个胜利者。这可以解释为一种特定的社会规范是如何从多种可能性中产生的，这些可能性在先验上是同等可能的。因此，绝对协调的出现有两个潜在代价高昂的因素。第一个问题显然是缺乏合作的代价图10：“事前”和“暴露”策略的模拟结果，对于系统尺寸N=1000的非对称强化，f=0.5和0.5。顶部面板显示了“事前知识”和底部面板显示的“事后知识”在各代理之间的协调演变。dination。第二个问题是等待协调的成本。这可以在集群行为中最清楚地看到，在集群行为中，当代理以合理的速度实现部分协调时，多个选择仍然存在。4.2集群形成我们已经看到，集群行为可能是暂时的，但在几乎所有情况下，它们都在缓慢演化。

这意味着我们在很长一段时间内观察不同餐厅的代理集群。图11显示了集群的概率密度函数的四个实例。我们在t=10000个时间片上跟踪了n=1000个代理的选择。我们假设所有四种情况（事前、事后和对称）都有前面提到的参数值。所得到的概率密度函数已在O（10）次模拟中平均。使用symmetricupdating规则的事前和事后（面板（a）和（c））均显示出较强的聚类行为，而其他两种情况显示出非常中等分布的聚类（面板（b）：参数值为4.8564的指数分布；面板（d）：拟合伽马分布，参数值为2.7103，1.3834）。图11：簇的大小分布（N=1000，T=10，在O（10）个平行模拟上的平均值）。面板（a）：具有对称更新的事前知识（插图：对数-对数图中的幂律fit），面板（b）：具有不对称更新的事前知识，具有指数分布，面板（c）：具有对称更新的公开知识（插图：对数图显示分布的不连续性），小组（d）：事后知识与不对称更新（插图：采用伽马分布）。4.3效率和等待成本正如前面所讨论的，代理可能会有执行策略的成本，因此，如果有需要很长时间才能达到绝对收敛状态的策略，代理可能会选择效率较低的解决方案，即较小的集群，如果这很快就能实现的话。我们在图12中研究了这种权衡，图中绘制了平均超过最大概率达到至少0.8所需的时间片数量与餐厅占用率的对比。y轴中的变量表示等待时间方面的成本。

x轴中的变量表示解决方案效率方面的成本（占用率越小效率越高）。我们通过使用Polya更新方案（m=50、75、100、…、475、495）模拟N=500个代理的系统来绘制权衡。X轴上的值显示<Pmax>达到0.8时时间片的占用率。从成本最小化的角度来看，这种权衡是显而易见的。较低的等待成本会导致较高的入住率，从而提高效率，反之亦然。这是模型的一个非常有用的特性，可以了解到达分析地点的等待成本和分配的准确性之间的权衡。图12:Polya更新方案的效率权衡和收敛时间。模拟结果表明，对于N=500.5的总和，存在明显的单调衰减。本文研究了多agent、多选项系统中的分布式协调模型。我们考虑一个具有多重纳什均衡的博弈，所有这些均衡都具有相同的可能性。基本问题是，如果主体参与重复交互，将实现哪种平衡，以及它们收敛到平衡的速度有多快。本质上，我们通过分布式协调算法解决了均衡选择问题。我们根据不同类型的自然学习提出了一些策略。特别是，通过Polya的urn模型进行强化学习提供了非常有用的基准。我们证明了系统以非常慢的动力学和瞬态集群自组织。最后，我们描述了实现分配的等待成本和分配的准确性之间的权衡。