非传递骰子游戏

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

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

立即领取

感谢您参与论坛问题回答

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

+2 论坛币

英文标题：
《A Game of Nontransitive Dice》
---
作者：
Artem Hulko and Mark Whitmeyer
---
最新提交年份：
2018
---
英文摘要：
  We consider a two player simultaneous-move game where the two players each select any permissible $n$-sided die for a fixed integer $n$. A player wins if the outcome of his roll is greater than that of his opponent. Remarkably, for $n>3$, there is a unique Nash Equilibrium in pure strategies. The unique Nash Equilibrium is for each player to throw the Standard $n$-sided die, where each side has a different number. Our proof of uniqueness is constructive. We introduce an algorithm with which, for any nonstandard die, we may generate another die that beats it.
---
中文摘要：
我们考虑一个两人同时移动博弈，其中两人各自选择任意允许的$n$边骰子作为固定整数$n$。如果一名球员的掷骰结果大于对手的结果，则该球员获胜。值得注意的是，当n美元>3美元时，纯策略中存在唯一的纳什均衡。唯一的纳什均衡是每个玩家掷标准的$n$边骰子，其中每一方有不同的数字。我们的独特性证明是建设性的。我们引入一种算法，对于任何非标准模具，我们可以生成另一个优于它的模具。
---
分类信息：

一级分类：Mathematics        数学
二级分类：Probability        概率
分类描述：Theory and applications of probability and stochastic processes: e.g. central limit theorems, large deviations, stochastic differential equations, models from statistical mechanics, queuing theory
概率论与随机过程的理论与应用：例如中心极限定理，大偏差，随机微分方程，统计力学模型，排队论
--
一级分类：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系统重叠），非合作计算环境的协调、规范和形式化方法。该领域还涉及博弈论在电子商务等领域的应用。
--
一级分类：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下载：
--> A_Game_of_Nontransitive_Dice.pdf (122.29 KB)

2022-5-31 21:26:23 上传

扫码加我 拉你入群

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

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

分享0 收藏0 回帖

关键词：Applications Quantitative SIMULTANEOUS Differential Coordination

非传递性Dicertem Hulkoand Mark Whitmeyer的游戏*2德克萨斯大学夏洛特分校北卡罗利纳大学数学与统计系德克萨斯大学经济系2018年10月23日摘要我们考虑一个两人同时移动的游戏，其中两名玩家各自选择任何允许的n边骰子作为固定整数n。如果h滚的结果大于对手滚的结果，则一名玩家获胜。值得注意的是，当n＞3时，纯策略中存在唯一的纳什均衡。独特的纳什均衡是每个球员都可以投标准的n面骰子，每一方都有不同的数字。我们的独特性证明是建设性的。我们引入一种算法，对于任何非标准模具，我们可以生成另一个优于它的模具。关键词：埃夫隆骰子，非正骰子，概率悖论，博弈论*电子邮件：mar k。whitmeyer@utexas.edu1简介如果大力士和利查斯玩骰子，谁是更好的人，掷骰子的人越大，运气越差，掷骰子的人就越容易倒下。威廉·莎士比亚，威尼斯人掷骰子的商人，是应用概率中一个引人入胜的话题。由于马丁·加德纳（Martin Gardner）[8]的一篇论文，它们首次成为人们关注的焦点，是一类更大的非及时性“悖论”（见[16]、[2]），其中也包括著名的宽恕悖论，如[7]所述。最近发表的关于非传递骰子的论文包括[1]、[4]和[15]。最近对这种情况的另一种解释是[10]，它通过投掷不公平的硬币来重新解释这种情况。此外，非传递骰子问题是最近一篇博学项目论文的主题（见[12]），实际上我们从那篇论文中获得了一些术语。可以考虑的一个问题是，在两个或多个玩家的星体游戏互动中，应该如何玩非传递骰子。

[14] 是第一个探索这一点的人：它探索了两人游戏，每个玩家可以选择一个特定的非传递对称骰子，并找到一组均衡。然后，它扩展了分析，以涵盖玩家各自选择两个骰子的情况。在这里，我们研究一个更广泛的问题：我们考虑一个两人、一杆、同时移动的游戏，其中每个玩家选择一个一般的n边骰子并掷骰子。面部表情最高的玩家赢得奖励，我们可以将其标准化为1。我们用于博弈的解决方案概念是（纯策略）纳什均衡。我们证明，对于大于3的情况，存在一个单一的、唯一的平衡，在这个平衡中，两个参与者【14】使用四个六面“埃夫隆骰子”来描述问题。注意，这个博弈是一个常数和博弈；因此，等价于零和博弈，对于两个参与者，纳什均衡的概念等价于鞍点的概念。可能有额外的混合策略eq uilibria；然而，在这一分析中，我们只考虑纯战略均衡。此后，我们所说的纳什均衡或均衡，只指那些符合标准的模具。此外，我们对唯一性的认识是有建设性的，并且包含一个算法，对于任何非标准模具，该算法都会生成一个优于它的模具。这一点的一个显著含义是，对于任何非标准模具，至少有一个模具是一个步骤的结果，这是我们算法中最基本的步骤，应用于标准模具，可以击败它。也就是说，对于任何不是标准模具的模具，都有一个与标准模具非常相似的模具可以击败它。与此最接近的一篇论文[6]也考虑了同样的问题，其中对于一些优秀的球员n，两名球员各自选择一个骰子，然后互相掷骰子。

它还表明，恨标准骰子与任何其他骰子都有着预期的联系，并且每一个非标准骰子都会输给另一些骰子。[5] 在稍微更一般的环境中探索骰子游戏，以及平衡的存在性和唯一性。在平衡中，两个玩家各自都有标准的骰子，这一点来自于论文中的命题6和命题8。我们的论文在以下关键方面与[6]和[5]有所不同。我们对博弈中纳什均衡的存在性和唯一性提供了不同的证明，并且我们能够完全使用基本的血液学来做到这一点。此外，我们的证明是建设性的，我们制定了一个简单的算法，允许我们为任何非标准模具生成一个模具。此外，我们的第一个结果——对于任何非标准模具，这里有一个比它更好的模具，它离标准模具只有一步之遥——也是一部小说。最后，骰子游戏可以放在更一般的环境中，作为布洛托上校游戏家族的一员。1921年由E.Borel开发的Fir st（见[3]），由于游戏在经济学、运筹学、政治学和其他领域的广泛应用，已经形成了一个新兴的文献。最近的一些论文包括[13]和[9]。此外，最近，[11]探索了在Interval[0，1]上玩的这个游戏的n人连续版本。对于两个参与者来说，唯一均衡是这里唯一均衡的连续模拟，即均匀分布。纯战略。[6] 虽然没有明确说明这一点，但从引理1和定理2.2可以清楚地看出，基本游戏将一般的n边骰子（以下简称“骰子”）定义为整数值随机变量，取有限集中的值1，2。。。，n, 其中分布必须满足以下条件：1。

对于Dn，di的每个可能值，其发生的概率pdi是1/n.2的倍数。Ep（Dn）=nXi=1dipdi=n+1对于给定的n，用Dn表示所有n边骰子的集合。然后，一个标准的n面模具Sn就是一个模具，其中每个值的出现概率为1/n∈ Dn。我们可以表示任何n面模具，Dn∈ Dn，作为一个（离散的）均匀分布随机变量，它在大小为n的多集中取值，元素在1，2。。。，n和和等于吨（n+1）：Dn=[d，d，…，dn]（1） 示例1。五个四面骰子是S=[1, 2, 3, 4], X个=[1, 1, 4, 4], Y型=[2, 2, 2, 4],[1, 3, 3, 3,[2, 2, 3, 3].2.1游戏考虑两个玩家，艾米（A）和鲍勃（B）。他们玩下面的一杆游戏。Fixn、Amy和Bob各自独立地选择任意n面模具An、Bn∈ 然后将它们相互滚动。他们的预期收益是其下一卷的实现高于对手卷的实现的概率。如果掷骰结果相同，则由（公平的）硬币决定胜利者。Amy（和Bob类似）的一个策略就是选择∈ Dn。对于任何一对策略，（An，Bn），Amy的预期收益，UA（An，Bn），isUA（An，Bn）=Pr（An>Bn）+Pr（An=Bn）示例2。假设n=4，让Amy和Bob分别从示例1中选择骰子X和Y。然后UA（X，Y）=7/16，UB（X，Y）=9/16。本文的主要结果是以下定理。定理1。对于任何n，两人博弈的唯一纳什均衡是当重新选择玩家时的标准值。也就是说，唯一的纳什均衡是策略对（Sn，Sn）。我们将通过证明两个命题来证明这个定理：命题1，（Sn，Sn）是纳什均衡；命题2，（Sn，Sn）是唯一平衡≥ 4） 。提案1。（Sn，Sn）是纳什均衡。证据

首先，我们展示了∈A、 B类对于所有Dn∈ Dn，Ui（Sn，Dn）=Ui（Dn，Sn）=。假设玩家B选择标准模具，而玩家A选择任意模具=[d，d，…，dn]. 如果实现Dnis di；也就是说，掷骰子Dn“lands”显示面di，然后用概率（di-1） /n，dn击败标准模具，并且概率为1/n，Dnties标准模具。因此，UA（Dn，Sn）=nXi=1ndi公司- 1n+n·=nE[Dn-=由于（Sn，Sn）给参与者B的收益为1/2，因此没有可预测的偏差。对于任何模具Dn∈ Dn和任何i和j，使得i 6=j，di6=1，dj6=n，由Φi，j（Dn）定义的DnisΦi，j（Dn）的一个步骤=[d，…，di-1，di- 1，di+1，dj- 1，dj+1，dj+1，dn]显然，Φi，j（Dn）满足等式1中的条件，因此Φi，j（Dn）是一个模具。我们可以作如下评论：评论1。任何模具都可以从任何其他模具一步一步到达。这当然意味着，任何模具都可以从标准模具Sn开始，通过一系列的电子步骤到达。对于任意两个骰子An，Bn∈ Dn，如果ai>bj的对数（ai，bj）超过ai<bj的对数，我们说AnBeats bn。它仍然需要显示唯一性，我们在下面的引理中实现了这一点。提案2。纳什均衡（Sn，Sn）对于n是唯一的≥ 4.证明。显然，对于任何策略对，当且仅当有一个骰子击败了她的对手时，玩家i就有一个可预测的偏差。我们的证明是有建设性的，我们证明了对于任何模具Bn6=Sn，我们都可以构造一个优于它的模具Gn。为此，让Bn=【b，b，…，bn】, 和（召回）序号=[1，2，…，n]. 我们引入γk，定义为γk=|bi | bi=k|对于k=1，2，n、 请注意，每个γ都是一个非负整数，每个满足度nxk=1γk=nnXk=1kγk=n（n+1），然后，对于k=1，2。

n- 1定义ξkasξk=γk+γk+1要构造优于Bn的模具GN，我们只需找到一对（ξi，ξj），其中ξi>ξj（显然j 6=i），i 6=j+1。然后，只需向SiA中添加1，并从Sj+1中删除1（因此需要i 6=j+1），得到的模具将超过Bn。示例3。假设PLAY yer A choos es die XFORM o ur p re v i ous Example，X=[1, 1, 4, 4]. 我们有γ=2，γ=γ=0，γ=2，所以ξ=2，ξ=0，ξ=2，ξ=2。显然ξ>ξ，1=i 6=j+1=2+1=3。因此，我们将1加上沙子，再从s中减去1，得到直径=[2, 2, 2, 4], 确实，如果球员B选择Y，他将获得9/16>1/2的回报。显然，如果对于某些a，b，ξa6=ξbf，那么一定存在一些i，j，ξi>ξj。因此，我们建立了以下引理：引理1。如果n≥ 4，则对于任何非标准n-侧面模具 a对a、b∈1，2。。。，n,其中ξa6=ξb.Proof。显然ξa=ξba、 b类∈1，2，n当且仅当γ+γ=γ+γ=γ+γ=···=γn-当且仅当γ=γ=····=γk时，1+γN成立 奇数整数k∈1，2，nγ=γ=···=γj 偶数整数j∈1，2，n（2） 我们还有以下两个关系：nXk奇γk+nXj偶γj=n（3）和nXk oddkγk+nXj evenjγj=n（n+1）（4）我们可以将方程2和3结合起来得到n+1γ+n- 1γ=n（5）表示奇数n。对于偶数n，方程2和3 yieldnγ+nγ=norγ+γ=2（6）。此外，从方程2和4中，我们得到了γ+n（n+2）γ=n（n+1）或γ+n+2γ=n+1（7）表示偶数n。现在观察，我们不能同时得到两个γ≥ 1和γ≥ 1因为如果一个等于1，另一个大于1，这将违反3；如果两者都等于1，那么Bn=Sn，这是一个矛盾。因此，γ或γ必须等于0。假设n是奇数，γ=0。根据方程5，我们得到（n- 1） γ=2n，其中没有整数n的解，γ表示n>3。接下来，假设n是奇数，γ=0。

从方程5中，我们得到（n+1）γ=2n，它在积分n中没有解，当n>1时，γ。因此，我们得出结论，n不可能是奇数。假设n为偶数且tγ=0。从方程6和7中，我们必须得到γ=2和n+2=n+1，这显然是一个矛盾。最后，假设n是γ=0的偶数nda。从方程6和7中，我们必须有γ=2和n=n+1，这也是一个矛盾。因此，我们证明了引理1。为了总结命题2的证明，我们需要验证，当i=j+1时，不能存在满足ξi>ξjoccurs的唯一对ξi，ξj的情况。为此，假设ξi>ξji，因为i=j+1。首先，让j 6=1。那么，如果ξj- 1.≤ ξj，relabel j- 1 asj′，当i 6=j′+1时，产生ξi>ξj′。如果ξj- 1> ξj，relabel j- 1 asi′，意味着对于i′6=j+1，ξi′>ξj。接下来，让j=1。如果ξi+1≥ ξi，将i+1重新标记为i′，当i′6=j+1时，ξi′>ξj。相反，如果ξi+1<ξi，则将i+1重新标记为j′，因此对于i 6=j′+1，我们有ξi>ξj′。我们也可以写出下面的推论，我们已经在这一过程中证明了这一点。推论1。让n≥ 4、然后，对于任何模具Bn6=Sn， a die GN是aone stepΦi的图像，jon是击败Bn的标准模具SN。请注意，给定一些模具Bn6=Sn，我们在证明中开发的算法会产生eve RYWINING模具（即一个超过Bn的模具），该模具距离m Sn只有一步之遥。此外，很容易看出，通过“flipping”算法，我们还可以获得一步之遥的丢失骰子集。此外，该算法还使我们能够找到“最佳”（和“最差”）的骰子，与Snto与Bn相比，只差一步。一步中净收益最大的骰子击败Sn的可能性最大。同样，一步净损失最大（绝对值）的骰子击败Sn的可能性最低。参考文献【1】L.Angel，M。

Davis，“非传递骰子集的直接构造”，ArXive prints 1610.085952016。https://arxiv.org/pdf/1610.08595[2] C.Blyth，“随机选择中的一些概率悖论”，《美国统计协会杂志》，67:366-3731972。[3] E.Borel，“La Theorie du Jeu et les Equations integrations a Noyan Symetrique”，Comptes Rendus de l\'Academic des Sciences，173:1304-13081921；L.Savage的英文翻译，“游戏理论和具有斜对称核的积分方程”，《经济学》，21:97-1001953年。[4] B.Conrey，J.Gabbard，K.Grant，A.Liu，K.Morrison，“不及物骰子”，《数学杂志》，89（2）：133-1432016年。[5] B.De Schuymer，H.De Meyer，B.De Baets，“等额骰子游戏的最优策略”，离散应用数学，154:2565-25762006年。[6] M.Finkelstein，E.O.Thorp，“具有同等手段的非传递骰子”，《最佳游戏：游戏和赌博的数学研究》（S.N.Ethier和W.R.Eadington编辑），雷诺：赌博和商业游戏研究所，2007年。https://www.math.uci.edu/~mfinkels/dice9。pdf[7]P.C.Fishburn，S.J.Brams，“优先投票的悖论”，《数学杂志》，56（4）：207-2141983年。[8] M.Gardner，“非传递骰子的悖论”，《科学美国人》，223:110-1111970年。[9] S.Hart，“离散的布洛托上校和洛托将军博弈”，载于《国际博弈论杂志》，36（3-4）：441-4602008年。[10] G.Hetyei，“埃夫隆的货币和临床排列”，离散数学，339（12）：2998-30042016。[11] A.Hulko，M.Whitmeyer，“随机变量的名称”，Mimeo，2017年。https://arxiv.org/abs/1712.08716[12] D.H.J.Polymath，“骰子的随机三元组是可传递的”，Mimeo，2017年。https://gowers.files.wordpress.com/2017/07/polymath131.pdf[13] B。

罗伯逊，《布洛托上校的游戏》，经济理论，29（1）：1-242006年。[14] C.伦普，“埃夫隆掷骰子的策略”，数学杂志，74（3）：212-216，2001年。[15] R.P.萨维奇，“非传递骰子的悖论”，《美国数学月刊》，101（5）：429-436。[16] R.L.Tenney，C.C.Foster，“非过渡统治”，《数学杂志》，49（3）：115-120，1976年。