迭代多策略对策中的零决定策略

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

英文标题：
《Zero-determinant strategies in iterated multi-strategy games》
---
作者：
Jin-Li Guo
---
最新提交年份：
2014
---
英文摘要：
  Self-serving, rational agents sometimes cooperate to their mutual benefit. The two-player iterated prisoner\'s dilemma game is a model for including the emergence of cooperation. It is generally believed that there is no simple ultimatum strategy which a player can control the return of the other participants. The recent discovery of the powerful class of zero-determinant strategies in the iterated prisoner\'s dilemma dramatically expands our understanding of the classic game by uncovering strategies that provide a unilateral advantage to sentient players pitted against unwitting opponents. However, strategies in the prisoner\'s dilemma game are only two strategies. Are there these results for general multi-strategy games? To address this question, the paper develops a theory for zero-determinant strategies for multi-strategy games, with any number of strategies. The analytical results exhibit a similar yet different scenario to the case of two-strategy games. Zero-determinant strategies in iterated prisoner\'s dilemma can be seen as degenerate case of our results. The results are also applied to the snowdrift game, the hawk-dove game and the chicken game.
---
中文摘要：
自私自利、理性的代理人有时会为了共同利益而合作。两人重复囚徒困境博弈是一个包含合作出现的模型。一般认为，不存在一个简单的最后通牒策略，玩家可以控制其他参与者的返回。最近，在重复囚徒困境中发现了一类强大的零决定策略，这一发现极大地扩展了我们对经典游戏的理解，它揭示了为有知觉的玩家提供单边优势的策略，让他们与无意中的对手对决。然而，囚徒困境博弈中的策略只有两种。一般的多策略游戏有这些结果吗？为了解决这个问题，本文发展了一个多策略博弈的零决定策略理论，该理论包含任意数量的策略。分析结果显示，两个策略博弈的情况类似但不同。迭代囚徒困境中的零决定策略可以看作是我们结果的退化情况。结果也适用于雪堆游戏、鹰鸽游戏和小鸡游戏。
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Computer Science and Game Theory        计算机科学与博弈论
分类描述：Covers all theoretical and applied aspects at the intersection of computer science and game theory, including work in mechanism design, learning in games (which may overlap with Learning), foundations of agent modeling in games (which may overlap with Multiagent systems), coordination, specification and formal methods for non-cooperative computational environments. The area also deals with applications of game theory to areas such as electronic commerce.
涵盖计算机科学和博弈论交叉的所有理论和应用方面，包括机制设计的工作，游戏中的学习（可能与学习重叠），游戏中的agent建模的基础（可能与多agent系统重叠），非合作计算环境的协调、规范和形式化方法。该领域还涉及博弈论在电子商务等领域的应用。
--
一级分类：Physics        物理学
二级分类：Physics and Society        物理学与社会
分类描述：Structure, dynamics and collective behavior of societies and groups (human or otherwise). Quantitative analysis of social networks and other complex networks. Physics and engineering of infrastructure and systems of broad societal impact (e.g., energy grids, transportation networks).
社会和团体（人类或其他）的结构、动态和集体行为。社会网络和其他复杂网络的定量分析。具有广泛社会影响的基础设施和系统（如能源网、运输网络）的物理和工程。
--
一级分类：Quantitative Finance        数量金融学
二级分类：Economics        经济学
分类描述：q-fin.EC is an alias for econ.GN. Economics, including micro and macro economics, international economics, theory of the firm, labor economics, and other economic topics outside finance
q-fin.ec是econ.gn的别名。经济学，包括微观和宏观经济学、国际经济学、企业理论、劳动经济学和其他金融以外的经济专题
--

---
PDF下载：
--> Zero-determinant_strategies_in_iterated_multi-strategy_games.pdf (100.35 KB)

2022-5-6 21:31:37 上传

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：Quantitative Environments Participants Applications Coordination

arXiv:1409.1786v2计算机科学与博弈论；物理学与社会；经济学2014年9月30日李果迭代多策略博弈中的零决定策略(郭进利)上海科技大学商学院，上海200093，中国摘要自私自利、理性的代理人有时为了共同利益而合作。两人重复囚徒困境博弈是一个包含合作出现的模型。人们普遍认为，没有简单的最后通牒策略可以让玩家控制其他参与者的返回。最近，在重复囚徒困境中发现了一类强有力的零决定策略，这一发现极大地扩展了人们对经典游戏的理解，因为它揭示了一些策略，这些策略为有知觉的玩家在与无意中的对手较量时提供了单边优势。然而，在冒险者困境博弈中的策略只有两种。一般多策略游戏有这些结果吗？为了解决这个问题，本文发展了一个多策略博弈的零决定策略理论，其中包含任意数量的策略。分析结果显示，两个策略博弈的情况类似但不同。我们的囚徒困境策略可以看作是退化的囚徒困境结果。研究结果也适用于雪堆游戏、鹰鸽游戏和小鸡游戏。关键词：囚徒困境；零决定策略；多策略博弈；对称游戏。1导言虽然博弈论最初是作为数学的一个分支出现的，但它涵盖了人类互动的几乎所有方面，特别是包括人类行为之间的相互影响和互动、人与人之间竞争与合作的利益，以及经济学中最成功的应用。

塔克提出的博弈论中最常用的是囚徒困境，对囚徒困境的研究涉及数学、经济学、政治学、伦理学、心理学、计算机科学等领域。囚犯的斯迪莱玛（sdilemma）本身已被公认为研究合作行为出现的一种方式[1]。每个层同时提供两种选择：合作或缺陷。如果双方都合作，他们每个人都会得到相同的回报；如果两者都存在缺陷，则各自获得较低的回报P；如果一方合作而另一方存在缺陷，则脱北者获得最大可能的回报T，合作者获得最低可能的回报S。动态迭代博弈是博弈论研究的最新方向之一。在迭代博弈框架下，aarXiv的预期收益为：1409.1786v2计算机科学与博弈论；物理学与社会；经济学2014年9月30日层由其他人决定。单边参与者很难找到简单的临时策略。在PNA中，Press和Dyson[2]发现的零决定因素（ZD）策略引起了广泛关注[3-6]。它们表明，采用零决定策略的玩家能够锁定对手的预期收益。特别是，掌握这些策略的玩家α可以（i）独立于对手β的策略或反应，决定性地设定对手β的分数，或者（ii）在她和他的分数之间建立一种过分的线性关系[2]。尽管与我们的直觉不一致，但它描述了动态迭代游戏的美好前景，也引起了许多科学家的关注[3-7]。

Szolnoki和Perc[3]研究了空间囚徒困境博弈中合作的演化，其中除了无条件合作和叛逃、针锋相对、赢留输转移和勒索外，还有五种竞争策略。为了探索ZD策略对抗人类的表现，Hilbeet等人[4]设计了一个经济实验，参与者要么与一位额外参与者匹配，要么与一位慷慨的合作者匹配。他们显示，虽然勒索者成功地对抗了他们的人类对手，但勒索导致的回报低于慷慨。Stewart和Plotkin[5]探讨了重复囚徒困境中ZD策略的进化前景。Hilbeet等人[8]研究了多人社交困境中的零决定因素联盟。零决定策略也被推广到迭代公共物品博弈[9]和所有对称2x2游戏[10]。然而，如上所述，这些游戏是两种策略游戏。本文的目的之一是设计一个迭代多策略博弈中零决定策略的框架。令人惊讶的是，ZD策略仍然存在于一个在两人迭代游戏中有许多策略的玩家身上。首先，我们在迭代多策略对策中发展了ZD策略，并给出了ZD策略的可行条件。其次，我们研究了对称博弈中零决定策略的机制，以及玩家的恶作剧或勒索。第三，将结果应用于雪堆游戏、鹰鸽游戏和小鸡游戏。2.零决定策略的框架一个多策略博弈有以下两个特点：（1）让α和β分别表示参与者1和参与者2。两个玩家只有有限的策略。假设玩家α，m（nm）没有策略≤≤1）玩家的策略。

策略集分别表示为：}，，，，{321 nSαL=，}，，，，{321 mSβL=（2）在每一轮游戏中，如果玩家α和玩家β分别使用策略iα和策略jβ，则形成一个游戏（jiβα）。假设玩家α收到payffija，玩家β收到payffijib，则玩家α的支付矩阵为nijaa×=[，玩家β的支付矩阵为nmijbb×=]【arXiv:1409.1786v2计算机科学与博弈论；物理学与社会；经济学2014年9月30日有限双人博弈的数据可以用两个矩阵来概括。具有有限多个选择的双人博弈，如上面的一个，也被称为矩阵博弈，因为它们可以用两个矩阵来表示。通常，这些矩阵被写成一个矩阵，每个位置有两个数字因此，这种游戏通常被称为“双矩阵游戏”。正式定义如下。双矩阵对策是一对n×m矩阵（A，B），其中==×），（），（），（），（），（），（），（），（），（），（），（），（），（），（nmnmnnmmmnijigbababababababababababababalmll.（1）在迭代博弈中，对于玩家α，每个阶段博弈的可能结果可以表示为：mnji×），（βα。对于玩家α，在下一个博弈策略中，给定当前博弈，kα出现的条件概率），（jiβα已发生表示为）（kjipβα。因此，条件概率向量的形式如下：对于玩家β，每个阶段游戏的可能结果可以表示为：nmij×），（αβ。对于玩家β，给定当前游戏，下一个游戏策略中kβ发生的条件概率，（ijαβ已经发生）表示为（kijqαβ）。因此，条件概率矩阵的形式如下Mkqqqqqqqqkkkkkkkkkmnn，2,1），，，，，，，（）（）（）（llll==αβαβαβαβαββ）。

（3） 我们让q分别表示）1（p）和）1（q）（kp和）（kq表示一个马尔科夫矩阵，其平稳概率向量v与相应的支付矩阵相结合，使每个参与者的预期结果都是一致的。矩阵的行和列按α的顺序排列，马尔科夫转移矩阵（qpP）从一个移动到下一个移动如图1所示。arXiv:1409.1786v2计算机科学与博弈论；物理学与社会；经济学2014年9月30日=)()()()()1()()1()()()2()2()2()1()2()()2()2()2()1()2()()1()2()1()1()1()()1()2()1()1()1()()()()()()()1()()1()()1()()()2()2()2()1()2()()2()2()2()1()2()()2()2()2()1()2()()1()2()1()1()1()()1()2()1()1()1()()1()2()1()1()1()()()()()()()1()()1()()1()()()2()2()2()1()2()()2()2()2()1()2()()2()2()2()1()2()()1()2()1()1()1()()1()2()1()1()1()()1()2()1()1()1【中国英语常用常用金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属金属n n n n n nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn n n n n n n n n n n n n n n n n n n n n n n n n n nαββαββαββαββββαααααααββββββββββββββββαααβββββββββββββββββαααααααααβββββββββββββββββββββββββββββββββββββββββββββββαααααααββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ好啦好啦好啦好啦好啦好啦好啦好啦好啦好啦好啦llmlmlmlmmlllmmllmllmlmlmlmlmmlllmmllfig。1.马尔可夫转移矩阵（qpP）。因为作为一个单位特征值-≡\' 是单数，因此行列式为零。马尔可夫矩阵的平稳向量v，或与其成比例的任何向量，满足vvp=或0\'=vP。（4） “Pis”的附加矩阵如下=nmnmnmnmppppppppppadjlmmll）“（，（5）0”=-≡ IPP表示0\'\'）\'（==IPPPAdj。

（6） 根据附加矩阵的性质和平稳概率，每一行（PAdj）都与v成正比。选择最后一行，我们可以看到v的分量是（直到asign）nm×nm矩阵的行列式，这些行列式由\'P\'的前nm-1列形成，依次去掉每一个nm行。如果将\'Pis\'的第一列添加到第二列，并将第三列添加到第一列，则这些行列式不变。这些操作的结果是任意nm向量f与马尔可夫矩阵的静止向量v的点积公式，），，（fqpDfv≡·, 式中，，（fqpD是以下行列式（见图2）。arXiv:1409.1786v2计算机科学与博弈论；物理学与社会；4.mnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmnmmmmll）1（）（）1()()()2()2()2()1()2()()2()2()2()1()2()3()1()1()1()3()1()1()1()1()()1()()1()()()2()2()2()1()2()()2()2()2()1()2()()2()2()2()1()2()3()1()1()1()3()1()1()1()3()1()1()1()1()()1()()1()()()2()2()2()1()2()()2()2()2()1()2()()2()2()2()1()2()3()1()1()1()3()1()1()1()3()1()1()1()1()()1()()1()()()2()2()2()1()2()()2()2()2()1()2()()2()2()2()1()2()3()1()1()1()3()1()1()1()3()1()1()1(---+++---++-------++++++++++++++++++++++++++++++++++++--------------------αββααββααββααββααββααββααββααββααββαβααβαββαβααβαββααββααββααββααββααββααββααββααββααββααββααββααββαβααβαββαβααβαββαβααβαββααββααββααββααββααββααββααββααββααββααββααββααββαβααβαββαβααβαββαβααβαββααββααβαβαβαβαββαβαβαβαβαβαβαβαβαβαβαβαβααβαβαβαβαβαβαβαβααβαβαβαβαβαβαββαβ图2。

行列式），，（fqpdn这个结果来自于在第nm列上用次列展开行列式，并注意到nm-1×nm-1行列式与每个f相乘就是上面描述的那些。对于v·f，这个公式值得注意的是，它是一个行列式，其第二列，，，，，，，，，，，，，1，，（1122111111毫米毫米毫米pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp+--=,    （7） 完全受α控制；其第一列，），，，，，，，1，，，，1（）1（）1（）1（）1（）1（）1（）1（）1（）1（）1（）1（）1（）1（）1（）1（）1（21212111112111 NMNMNMMMqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq---=+++.  （8） 完全受β的控制；我们将支付矩阵playerα改写为向量形式，，，，，，，，，，，，（21222111211 nmnnmmaaaaaaaaaa LLLL=αω，（9）我们也将支付矩阵playerβ改写为向量形式，，，，，，，，，，（2122211111 mnmmnnbbbbbb LLLL=βω。（10）在静止状态下，他们各自的预期分数是1，，（），（1 qpDqpDvvαω）=··= ,                      （11） ）1，，（），（1 qpDqpDvvββωωπ=··= ,                      （12） arXiv:1409.1786v2计算机科学与博弈论；物理学与社会；经济学2014年9月30日，其中1是所有成分的向量1。分母是必需的，因为v之前没有被标准化，使其分量和为1（如平稳概率向量所需）。由于等式（11）和等式（12）中的分数与相应的支付矩阵P呈线性关系，因此对于分数的任何线性组合也是如此，给出了）1，，（）1，，（qpDcbaqpDcba++=+++βαβαωω（13），其中，b和c是常数。这个等式（13）揭示了参与者预期收益之间可能存在的线性关系。回想一下，在矩阵的p中，存在一个由1（p）决定的列p，或者存在一个完全由1（q）决定的列q。

如果α选择的策略满足1CBAP++=βαω，（14）或如果β选择的策略满足1CBAQ++=βαω，（15），则行列式消失，且两个预期分数之间存在线性关系，=++cbaβαω，（16）。由于矩阵\'P是奇异的，因此导致等式（16）的上界线的策略是游戏者α的多策略零行列式策略。可行条件。并非所有的零决定策略都是可行的，概率和q都在[0,1]范围内。它们在任何特定情况下是否可行取决于应用程序的特定部分。多策略对策的可行零决定策略的一个充分条件如下：≠∑=nmiinmP和nmiPinm，2,1,0 L=≥  奥米平，2,1,0升=≤ .α单方面设定β的分数。等式（13）允许通过选择值A、b、c来进行更多的破坏，该值保持了等式（14）中定义的策略p。在可能性向量领域，α可以单方面对迭代游戏的预期分数施加某些约束。从上面可以看出，α可以选择设置0=a，屈服强度bc-=βπ. 通过这样做，她可以单方面确定β的预期回报。arXiv:1409.1786v2计算机科学与博弈论；物理学与社会；《经济学》2014年9月30日α要求并获得了过高的份额。有趣的是，α和β之间的线性关系可以抵消α和β之间的线性关系。通过设置Δ+-= )（bac，对于任何偏移Δ，（17）α强制）（Δ-=Δ-βαπλπ.

（18） 对于λ>1的值，这种策略可以被描述为对α强制执行“不公平的”支付份额。3对称博弈的零行列式策略对称博弈的定义如下：参与者α的支付矩阵是NNIJAA×=[，而帕耶β的支付矩阵是A的转置，即nnjiTaAB×=[，然后==如果我们假设Njiaaaijjijij，2,1，（issymmetric。这也是我们称之为对称博弈的原因。例如，囚徒困境、猎鹿和鸡的博弈都是对称博弈，这意味着它们都可以用对称22×支付矩阵表示（见等式（20））),让我们来看一看=+-+-++,),,,,,,,,,,,,（2）1（1）1（1）1（1）1（1）1（2）1（1）1=+-+-++.我们将支付矩阵游戏者α改写为向量形式，，，，，，，，，，，（21222111211 nnnn aaaaaaaaaaa LLLL=αω，（21）arXiv:1409.1786v2计算机科学与博弈论；物理学与社会；经济学2014年9月30日我们将支付矩阵玩家β改写为以下向量形式，，，，，，，，，，，（2122111 nnnnnn aaaaaaaaaaa LLLL=βω。（22）假设NNAA≥, 博弈），（βα是相互充分合作，博弈），（nnβα是完全不合作。恶作剧和勒索。