n人选数博弈的最佳策略

KeyTo9_Fans

n个人参与选数游戏，游戏规则如下：

每个人私底下秘密地选择一个正整数，选好后同时公开，然后按照下列规则判定胜负：

哪个人的数是唯一的，那个人就赢了，收益为(n-1)，其他人都是输，收益均为(-1)（例如，若3个人分别选了1、3、1，则选3的赢，选1的输）

如果有多个数都是唯一的，则在这些唯一的数中，选了最小值者赢，收益为(n-1)，其他人都是输，收益均为(-1)（例如，若4个人分别选了1、1、2、3，则选2的赢，选1、3的输）

如果所有的数都不唯一，则为平局，每个人的收益均为0（例如，若4个人分别选了1、1、2、2，则本局为平局）

假设参与者都是独立做出决定的（没有串通行为），而且这个游戏要重复N局（N趋于无穷大），每个人都希望自己N局的总收益最大

求这个博弈的纳什均衡策略。

#####

对于n=2和n=3的简单情况，我已经做出来了，答案如下：

当n=2时，我方以1的概率选1即可保持不败：若对方选1，则双方打平；若对方不选1，则我方获胜。无论哪种情况，我方都是不败的

因此，[1, 0, 0, 0, 0, ...]是n=2时的纳什均衡策略

当n=3时，三方的纳什均衡策略是以1/2的概率选1、以1/4的概率选2、以1/8的概率选3、以1/16的概率选4、以1/32的概率选5、……、依次类推直到无穷

此时，可以证明：任意一方单方面地改变他的策略，他都无法获得更高的收益（实际上，无论他选什么数，只要其余两方的策略保持不变，那么他的期望收益都是0）

因此，[1/2, 1/4, 1/8, 1/16, 1/32, ...]是n=3时的纳什均衡策略

当n>3时，我还没开始做，我感觉这个博弈的纳什均衡策略应该是一个很有趣的数列，于是发出此贴，召唤坛友们一起来解答此题。

lihpb00

应该把问题简化点，把正整数的定义域限制为不超过总人数。

KeyTo9_Fans

假设n个人都只能在{1,2,3,...,m}中任选一个数，其余规则不变，那么可以证明：

当n=3、m=2时，三方的纳什均衡策略是以1/2的概率选1、以1/2的概率选2

当n=3、m=3时，三方的纳什均衡策略是以1/2的概率选1、以1/4的概率选2、以1/4的概率选3

当n=3、m=4时，三方的纳什均衡策略是以1/2的概率选1、以1/4的概率选2、以1/8的概率选3、以1/8的概率选4

……

当n=3、m=k时，三方的纳什均衡策略是以1/2的概率选1、以1/4的概率选2、以1/8的概率选3、……、以1/2^(k-1)的概率选(k-1)、以1/2^(k-1)的概率选k

#####

如果你有精力，可以求解一下n=4、m=4的情况

KeyTo9_Fans

假设n个人都只能在{1,2,3,...,m}中任选一个数，其余规则不变，那么可以证明：

当n=4、m=2时，四个玩家的纳什均衡策略是以1/2的概率选1、以1/2的概率选2

当n=4、m=3时，四个玩家的纳什均衡策略是以1/2的概率选1、以1/2的概率选2、以0的概率选3

当n=4、m=4时，四个玩家的纳什均衡策略是以1/2的概率选1、以1/2的概率选2、以0的概率选3、以0的概率选4

……

当n=4、m=k时，四个玩家的纳什均衡策略是以1/2的概率选1、以1/2的概率选2、以0的概率选3、……、以0的概率选(k-1)、以0的概率选k

因此，[1/2, 1/2, 0, 0, 0, ...]是n=4时的纳什均衡策略

#####

到目前为止，n=2、n=3、n=4都求解完了，我还是没找到规律

可能还需要解出n=5、n=6的纳什均衡策略，才有可能找到规律

KeyTo9_Fans

n=5的纳什均衡策略是[0.371772586226221   0.337470265663412   0.197433332037597   0.083357504586568   0.009966311486202   0 0 0 0 0 0 ...]

n=6的纳什均衡策略是[0.3347332497268076   0.3091116020527407   0.2475324310543558   0.1086227171660959   0 0 0 0 0 0 ...]

n=7的纳什均衡策略是[0.300184062196429   0.278220415848247   0.236045507468779   0.142867765777442   0.042682248709103   0 0 0 0 0 0 ...]

n=8的纳什均衡策略是[0.274658159424212   0.256081709445968   0.224484741401477   0.162807393887394   0.075778771502094   0.006189224338855   0 0 0 0 0 0 ...]

n=9的纳什均衡策略是[0.254025173368883   0.238134416197982   0.213196337967700   0.169555078292617   0.099465025506767   0.025623968666051   0 0 0 0 0 0 ...]

n=10的纳什均衡策略是[0.236876030230200   0.223100884437856   0.202679168981162   0.169624914230531   0.115666125747456   0.048134804623352   0.003918071749443   0 0 0 0 0 0 ...]

n=11的纳什均衡策略是[0.222339058609294   0.210263412037400   0.193111077377371   0.166912724179641   0.125300936854651   0.067504781227388   0.014568009714255   0 0 0 0 0 0 ...]

n=12的纳什均衡策略是[0.209864613494853   0.199187505698792   0.184524275856088   0.163113423524478   0.130318441400365   0.082529974264547   0.029065635367272   0.001396130393604   0 0 0 0 0 0 ...]

n=13的纳什均衡策略是[0.1989253643258716   0.1893952468188255   0.1766571675971236   0.1587114163600625   0.1321740500764781   0.0931372401835569   0.0440367722049508   0.0069627424331310   0 0 0 0 0 0 ...]

n=14的纳什均衡策略是[0.1893062716669423   0.1807438438201291   0.1695538415479736   0.1542445161492509   0.1323075498591642   0.1003304450177776   0.0573946494447189   0.0159434942332423   0.0001753882608011   0 0 0 0 0 0 ...]

n=15的纳什均衡策略是[0.1807093506546298   0.1729617758800387   0.1630262016699833   0.1497604248294889   0.1312697134632381   0.1047738456874560   0.0681172181859038    0.0268231971284434   0.0025582725008181   0 0 0 0 0 0 ...]

n=16的纳什均衡策略是[0.1729957447052604   0.1659462084616340   0.1570508867895068   0.1454168333150741   0.1295864820670620   0.1073419048607741   0.0762962919920366   0.0379088918706290   0.0074567559380230   0 0 0 0 0 0 ...]

n=17的纳什均衡策略是[0.1660272805918684   0.1595809429010389   0.1515600965001693   0.1412542936834500   0.1275233175131067   0.1086048060117203   0.0822838417455938   0.0479890389062938   0.0146139848316763   0.0005623973150825   0 0 0 0 0 0 ...]

n=18的纳什均衡策略是[0.1596791901543507   0.1537559830372617   0.1464758594193364   0.1372645958038875   0.1252160304283647   0.1089242670386882   0.0864703116045200   0.0564483582584582   0.0230576698937560   0.0027077343613766   0 0 0 0 0 0 ...]

n=19的纳什均衡策略还在求解中……

这些纳什均衡策略好像是一些高次方程的根，目前我只解出了上面这些数值解

解析解太复杂了，留给科技发达的后人去解吧

KeyTo9_Fans

.·.·.问4个玩家为什么不选3（.·.·.的贴子可能被删除了），回复如下：

4个玩家，如果有3个玩家以1/2的概率选1、以1/2的概率选2，有1个玩家（你）选3，

那么当所选的4个数（排序后）是
1 1 1 3 时，你赢3分，赢的概率是1/8，
2 2 2 3 时，你赢3分，赢的概率是1/8，
1 1 2 3 时，你输1分，输的概率是3/8，
1 2 2 3 时，你输1分，输的概率是3/8，

所以你选3会以2/8的概率赢3分，以6/8的概率输1分，收益的期望值是3*(2/8)+(-1)*(6/8)=0，不赢也不输