枪手射击问题，求问题的思路或解答

有n个枪手，编号依次为1~n，他们射击命中的概率分别为0<p1<p2<p3<...<pn<1.
游戏的规则是：从某个人i号开始，按照某种给定的开枪先后顺序，每个人依次开枪射击别人，被击中的人即死，退出游戏，剩下的人循环往复，直到剩下最后一人。每个人的策略集是除他自己以外的n-1个人的所有可能的排序组成的集合（即每人有(n-1)!种策略可以选择）；如此选择一个策略即等同于选择一种对剩下的所有人的排序方法，并始终射击排在最前面的的那个人（如果他还活着的话）。

问题一：若从1号开始，给定开枪的先后顺序为1,2,3...,n，那么1号有没有一个占优策略（dominant strategy）?
问题二：若从1号开始，给定开枪的先后顺序为1,2,3...,n，那么这个游戏有没有一个均衡？它是什么？
问题三：给定任意开枪先后顺序，第一个开枪的人有没有一个占优策略？ 游戏有没有均衡？
问题四：实际上，策略集合可以定义得比上面更完备；完备的策略集合应该包含对除自己以外的任意k（1<k<n）个人作出排序。在这种更复杂的情况下，问题一到问题三又该如何作解呢？

-----------------------------------------------------------------------------------------------------------------------
谢谢版主置顶。对于这个问题我想我已经了解得足够多了（请见19楼）。如果有比19楼更深或更进一步的见解，我将把它采纳为答案。

……这是高中数学竞赛题啊

Fischer 发表于 2011-7-30 11:46
……这是高中数学竞赛题啊

抱歉，这不是高中数学竞赛题

忘了一点，显然的，定义第i个人的payoff（收益）为他最终存活下来的概率。

上面四个问题中的任意一个若有想法，敬请留言。非常感谢~~
n=3的情况是很多书上的智力题，但我想考虑一般的情况：当n变大时，这个问题的结论是仍然能够简单的描述（指问题1到问题3能够肯定的作答），还是其复杂性会有根本的改变（指问题1到问题3不能肯定的作答）？

整体上来说，射击命中率是大家都知道的。目的是让自己活下来，那么就应该先杀掉枪法准的人。这样自己的存活率才会高。
1号的占优策略是开枪打n号，2号打n号（n没死），n（死了）2号打（n－1）号。依次类推。
均衡是永远开枪打枪法准的人。
给定开枪顺序第一个开枪的没有好处。命中率最低的人能进入决赛，死的几率比较大。
不管定义什么策略集，做为一个理性人，对于自己的开枪排序一定是先打危险系数最大的那个人。

duanshiliang 发表于 2011-8-1 09:49
整体上来说，射击命中率是大家都知道的。目的是让自己活下来，那么就应该先杀掉枪法准的人。这样自己的存活 ...

谢谢！但问题就在这里：有什么理由说占优策略是始终射击枪法最准的人？

对于n=3，通过穷举分析可以看出情况的确是这样。但是当n很大的时候，凭什么说射击枪法最准的人一定是占优的呢？比如说当n很大，且其他人都正常表现，但枪法第二准的那个人把你列为首要目标，有什么理由认为不该先射击他呢？

概率问题就要按照概率来办事，这里有个先后顺序我在第一轮是不可能知道n－1号那个人射击的对象的，只有在第二轮时才能。第二轮时如果我没死我可能会在第二轮选择n－2号作为目标，这个是报复不是均衡。
如果不先解决掉命中率高的人，在那些人行动时自己死亡的概率就上升了。每个人都知道的。参与者没有人有动机去偏离这个动机。
假如我射击n－1号，n－1的概率是P（n－1），n的概率是Pn，后者大。那么对于我来说n号更具有威胁性，我不知道他们两个会射击谁（可能n－1号射击我，或者n号射击我，或者都不射击我），但是从我出发，我一定会将潜在的威胁最小化。
就算里面可以交谈那也是不可信的，你不可能把神枪手留到最后和你对决吧！所有人都希望最后和自己对决的人的命中率无限接近零。那么自己活着的希望就大一点。

概率问题就要按照概率来办事，这里有个先后顺序我在第一轮是不可能知道n－1号那个人射击的对象的，只有在第二轮时才能。第二轮时如果我没死我可能会在第二轮选择n－2号作为目标，这个是报复不是均衡。
如果不先解决掉命中率高的人，在那些人行动时自己死亡的概率就上升了。每个人都知道的。参与者没有人有动机去偏离这个动机。
假如我射击n－1号，n－1的概率是P（n－1），n的概率是Pn，后者大。那么对于我来说n号更具有威胁性，我不知道他们两个会射击谁（可能n－1号射击我，或者n号射击我，或者都不射击我），但是从我出发，我一定会将潜在的威胁最小化。
就算里面可以交谈那也是不可信的，你不可能把神枪手留到最后和你对决吧！所有人都希望最后和自己对决的人的命中率无限接近零。那么自己活着的希望就大一点。
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

谢谢你的建议，我想我明白你想说的意思。

红字的不完整性在于：如果你允许射击者每轮改变射击对象的先后顺序话，那么第二轮的时候我也不可能知道别人的射击对象，因为他们可以改变；反之，如果你不允许射击者改变射击的对象的先后顺序（如同我定义的策略那样），那么你即使知道了别人的射击对象，第二轮也无法改变自己射击的先后顺序。

蓝字：Pn大代表Pn对我来说更具威胁性。那么什么叫做“威胁性”？ 如果Pn“威胁性大”就是选择射击P(n-1)比选择射击Pn降低我存活的概率的话，那么这等于循环论证了；至少没有给出令人信服的理由。寻求“潜在威胁最小化”的思路也是一样的道理，觉得跳跃太大！




         

让我来说说我到现在为止的思路和结论吧，我只能想到4个人那么远。基本想法是递归。欢迎挑刺~

策略集合按照问题四里的来定义，即可以根据所剩人数多少来改变射击的先后顺序。

首先，对于n=3的情况是容易分析出来的。此时正如dushiliang所言，对于任何开枪顺序，1,2,3号的（严格）占有策略分别是（3,2）,(3,1) 和 (2,1)，它们组成唯一的均衡。

现在需要定义些记号和做些准备工作。定义P(i|a,p1,p2,p3)为开枪顺序为a、三人命中概率分别为p1,p2,p3 时i号幸存的概率. 则下面的命题成立：

命题一：若 p3'>p3, 则P(i|a,p1,p2,p3)>P(i|a,p1,p2,p3'), 对于i=1,2 和任意开枪顺序a.
               若 p2'>p2, 则P(i|a,p1,p2,p3)>P(i|a,p1,p2',p3), 对于i=1,3 和任意开枪顺序a.

证明略.

现在，考虑n=4的情况. 先考虑a=(1,2,3,4)的情况：

给定其他人的任意策略，若1首先射击枪法最准的4号，则由条件概率展开：P(1|(1,2,3,4))=p1P(1|(2,3,1))+(1-p1)P(1|(2,3,4,1))  

若1首先射击2号或3号，则由条件概率展开： P(1|(1,2,3,4))=p1P(1|(3,4,1))+(1-p1)P(1|(2,3,4,1)) 或 P(1|(1,2,3,4))=p1P(1|(2,4,1))+(1-p1)P(1|(2,3,4,1))。

现在来看等式的右边第二项，它是1号没有射中目标且最终获胜的概率。我们按照上面的方法把P(1|(2,3,4,1))也按条件概率展开，然后把展开后的第二项继续按条件概率展开，依次进行下去。这样做了3次之后我们又会回到P(1|(1,2,3,4))，它前面的系数是(1-p2)(1-p3)(1-p4). 所以3次展开以后：

P(1|(2,3,4,1))=(1-p2)(1-p3)(1-p4)P(1|(1,2,3,4))+C，回顾我们展开条件概率过程，我们可以看出C的值与1号选择谁做他最先射击的对象是无关的 (理由是，C中的所有条件概率都是只对三个人而言的，所以1号在四个人的时候选择最先射击谁于它们无关).

所以，若1首先射击4号，则 P(1|(1,2,3,4))=（p1P(1|(2,3,1))+(1-p1)C）/ (1-(1-p1)(1-p2)(1-p3)(1-p4))
          若1首先射击2号，则  P(1|(1,2,3,4))=（p1P(1|(3,4,1))+(1-p1)C）/ (1-(1-p1)(1-p2)(1-p3)(1-p4))
           若1首先射击3号，则 P(1|(1,2,3,4))=（p1P(1|(2,4,1))+(1-p1)C）/ (1-(1-p1)(1-p2)(1-p3)(1-p4))
         由命题一，P(1|(2,3,1)>P(1|(3,4,1)  且 P(1|(2,3,1)>P(1|(2,4,1)
          所以，1首先射击4号时，他最终幸存的概率最大。所以此时1号的占优策略为（4,3,2）

         类似的思路，展开P(2|(1,2,3,4))得2号的占优策略为(4,3,1);  展开P(4|(1,2,3,4))得4号的占优策略为(3,2,1).

         但是，当我们展开P(3|(1,2,3,4)) 时，却发现3号没有在任何概率下都占优的策略。若3号选择最先射击4号，那么P(3|(3,4,1,2))=p3P(3|(1,2,3))+(1-p3)P(3|(4,1,2,3)) ; 但若3号最先射击2号，那么P(3|(3,4,1,2))=p3P(3|(4,1,3))+(1-p3)P(3|(4,1,2,3)).  实际上，我们可以选择某组p1<p2<p3<p4满足P(3|(1,2,3))>P(3|(4,1,3)), 也可以选择另一组p1<p2<p3<p4满足P(3|(1,2,3))<P(3|(4,1,3)).  所以，3号选择最先射击2号还是最先射击4号，依赖于四个人命中的概率。

所以在n=4的时候，对于问题三的回答是：任意开枪顺序下第一个人没有占优策略（这种开枪顺序是3,4,1,2）；但是游戏依然有均衡。
在n=4的时候，对第一问和第二问的回答是肯定的；但因为第三个人的占优策略不固定，均衡的时候他可能不会首先射杀4号。其他人的表现均正常。