二人严格博弈的两个等价结果.doc

Two equivalence results for two-person strict gamesPingzhong Tang, Fangzhen LinAbstractA game is strict if for both players, different profiles have different payoffs. Two games are best response equivalent if their best response functions are the same. We prove that a two-person strict game has at most one pure Nash equilibrium if and only if it is best response equivalent to a strictly competitive game, and that it is best response equivalent to an ordinal potential game if and only if it is best response equivalent to a quasi-supermodular game.Keywords: Strictly competitive games；Ordinal potential games；Quasi-supermodular games；Best response equivalence；Strict games朗读Yux j sh yng de, rgu du ling mng qiyun, btng cmin yu btng de hubo. Ling chng bsi sh zu ho de hud dng ji de, rgu tmen de zu ji fnyng hnsh sh xingtng de. Wmen zhngmng lio y ling grn zi zu yng de yux yg chn n shn jnhng de, dng qi jn dng t sh zu ho de hud xingdng y yg yng de jngzhng yux, zh sh zu ho de hud xingdng y yg x qinzi de yux, dng qi jn dng t sh zu ho de Fnyng xingdng y yg zhn cho m yux字典 - 查看字典详细内容1. IntroductionIn this paper we prove two results about pure Nash equilibria (PNEs) for 2-person strict games, which are those where payoff functions are one-to-one. The first result says that a 2-person strict game has at most one PNE if it is best-response equivalent (Rosenthal, 1974) to a strictly competitive game (Moulin, 1976; Friedman, 1983). The second result says that a 2-person strict game is best-response equivalent to an ordinal potential game (Monderer and Shapley, 1996) if it is best-response equivalent to a quasi-supermodular game (Topkis, 1998).These results came out of our project on using computers to discover theorems in game theory (see, e.g. Tang and Lin, 2009). We were looking for conditions that imply the uniqueness and existence of the PNEs, and were using computers to run through a large set of conjectures. Given the number of all possible games, it made sense to test these conditions first on some special classes of games, and the class of strict games is a natural choice as in these games, the payoff functions are one-to-one, thus easier to generate. As it turned out, some interesting conditions hold only for this class of games. We have described some of them in Tang and Lin (2009). The two results that we report here are special in that their proofs are non-trivial and had to be done manually.2. Basic definitionsA 2-person game is a tuple (A, B, u1, u2), where A and B are sets of pure strategies of players 1 and 2, respectively, and u1 and u2 are functions from A B to reals called the payoff functions for players 1 and 2, respectively. In this paper we assume both A and B are finite.A game is said to be strict if both players payoff functions are one-to-one: for any (a1, b1) and (a2, b2) in A B, if (a1, b1)(a2, b2) then ui(a1, b1)ui(a2, b2), i = 1, 2. A related notion in the literature is non-degenerate games (see, e.g. Berger, 2007): a game is non-degenerate if for any a1,a2A and b1, b2B, u1(a1, b1)u1(a2, b1) whenever a1a2, and u2(a1, b1)u2(a1, b2) whenever b1b2. Clearly, a strict game is also non-degenerate, but the converse is not true in general.For each bB, let B1(b) be the set of best responses by player one to the action b by player two:B1 (b)=aa A, and for all aA, u1(a,b)u1(a, b).Similarly, for each aA, letB2 (a) =bb B, and for all bN, u2(a, b)u2(a, b).A profile (a, b)AB is a pure Nash equilibrium (PNE) if aB1(b) and bB2(a).In this paper we consider only PNEs. Our initial motivation for this work was to capture the class of games with at most one PNE. We started with strictly competitive games (see below). While every strictly competitive game can have at most one PNE, the converse is not true in general. This led us to consider notions of equivalence between games that will preserve PNEs. The one that suits our purpose here is that of best-response equivalence (Rosenthal, 1974): two 2-person games G1= (A, B, u1, u2) and G2 = (A, B, u1, u2) are said to be best-response equivalent if for each aA, B2(a) in G1 and G2 are the same, and for each bB, B1(b) in G1 and G2 are the same.It is easy to see that best-response equivalent games have the same sets of PNEs.3. Strictly competitive games and at most one PNETheorem 1. A strict 2-person game has at most one PNE if and only if it is best-response equivalent to a strictly competitive game.4. Ordinal potential and quasi-supermodular gamesTheorem 2. A 2-person strict game is best-response equivalent to a quasi-supermodular game if and only of it has no best-response cycle.DiscussionsTheorem 2 still holds for non-degenerate games, since the only assumption we made is that the best-response functions are single valued.For general two person games, there are three ways to define a best response cycle:1. Normal cycle. In this definition, as long as any best-response function is multi-valued, there is always a trivial cycle in which one player deviates among multiple best-responses.2. Voornevelds cycle. This definition is essentially the same to above except that it requires at least one edge in the cycle that strictly increases the payoff for the deviating player. In this way, it rules out the trivial cycle in our original definition.3. Strict cycle. In this definition, every edge in the cycle must strictly increases the payoff for the deviating player.Three definitions are equivalent when consider strict games only. We now discuss the extension of Theorem 2 to general 2-person games with respect to three types of cycles.The “only if” part of Theorem 2 does not hold for general 2-person games for normal cycle and Voornevelds cycle but still holds for strict cycle. For instance, the following general game:1,12,12,21,2is a quasi-supermodular game under the ordering that orders player 1s (row player) strategies from top to down and player 2s action from left to right. However, going counterclockwise starting in any cell will form both a normal cycle as well as Voornevelds cycle. Thus this game is not best-response equivalent to any ordinal potential game. However, according to Theorem 3 in Kukushkin et al. (2005), there is no strict cycle if a game is quasi-supermodular (therefore no strict cycle for a game that is best-response equivalent to it).The “if” part of theorem 2 does not hold for general 2-person games for Voornevelds as well as strict cycles but holds for normal cycles. To show this, consider the following general game:2,22,12,21,11,21,21,21,21,1It has no Voornevelds nor strict cycles. However it is not best-response equivalent to any quasi-supermodular game since there is no ordering of strategies under which player 2s best-response function satisfies single crossing condition. On the other hand, if we assume that a game has no normal cycle, it implies that its best-response functions are single-valued.Therefore, the if part holds for normal cycles.二人严格博弈的两个等价结果唐平中，林方正摘要：若博弈对于两个参与人是严格的，那么不同的情景就会有不同的结果。若两人的最佳反应函数相同，则双方就会有同样的最佳反应。我们发现在一个严格的二人博弈中至多存在一个纯战略纳什均衡，当且仅当它对于一个严格的竞争性博弈是最佳反映等价，对于一个序潜在博弈是最佳反映等价，对于一个准超模博弈也是最佳反映等价。关键词：严格的竞争性博弈；序潜在博弈；准超模博弈；最佳反映等价；严格博弈1引言在本文中，我们将验证关于纯战略纳什均衡（Pure Nash Equilibriums）对于二人严格博弈的两个结果，这是针对那些支付函数是一对一的博弈情况。第一个结果表明，一个严格的二人博弈中最多存在一个纯战略纳什均衡(PNE)当且仅当它对一个严格的竞争性博弈（穆林，1976；弗里德曼，1983）是最佳反映等价（罗森塔尔，1974）。第二个结果表明，对一个序潜在博弈（Monderer and Shapley，1996）是最佳反映等价，对一个准超模博弈（Topkis，1998）是最佳反映等价。这些结果来自于我们运用计算机发现博弈论定理（见，例如：唐和林，2009）的项目中。我们一直在寻找纯战略纳什均衡(PNEs)的独特性和存在性的隐性条件，并通过大量的猜想用计算机来执行。考虑到所有可能的博弈数量，有必要首先针对某些特殊种类的博弈测试这些条件，在这些博弈中严格博弈的类型是一种自然选择，其支付函数是一对一的，因而更容易产生。事实证明，一些有趣的条件仅在这类博弈中成立。在这里已经介绍了其中的一部分(Tang and Lin, 2009)。此处所说的这两个结果，其特殊之处就在于，它们的证明过程是不平凡的，不得不手工完成。2基本定义二人博弈是一个元组（A，B，u1, u2），其中A和B分别是参与人1和2的纯策略集，u1和u2是定义在AB上的函数，称为参与人1和2的支付函数。在本文中，我们假设A和B是有限的。若两个参与人的支付函数是一对一的，则被认为是严格博弈：对于任何定义在A B上的（a1, b1）和（a2, b2），若（a1, b1）（a2, b2），则ui(a1, b1)ui(a2, b2), i = 1, 2。在文献中一个相关的概念是非退化博弈（伯杰，2007）：若对于任何a1,a2A and b1, b2B,当a1a2时都有u1(a1, b1)u1(a2, b1)，当b1b2时都有u2(a1, b1)u2(a1, b2)。很显然，一个严格博弈也是非退化的，但通常反之则不然。对于每个bB，定义B1(b)是参与人1对参与人2的最佳反应行为集：B1 (b)=aa A, and for all aA, u1(a,b)u1(a, b)同理，对于每个aA，定义B2 (a) =bb B, and for all bN, u2(a, b)u2(a, b)若aB1(b) 且bB2(a)，则数据分布(a, b)AB是一个纯战略纳什均衡（PNE）。在本文中我们只考虑纯战略纳什均衡(PNEs)。我们这项工作的最初动机是为了得到最多具有一个纯战略纳什均衡(PNE)的博弈类型。我们从严格的竞争性博弈开始（见下文）。虽然每一次严格的竞争性博弈最多只有一个纯战略纳什均衡(PNE)，但通常反之则不然。这促使我们考虑博弈之间保持纯战略纳什均衡(PNEs)的等价概念。这里正合我意的是最佳反映等价(罗森塔尔，1974）：若对于每个aA，G1和G2中的B2(a)是相同的，且对于每个bB，G1和G2中的B1(b)也是相同的，则这两个二人博弈G1= (A, B, u1, u2)和G2 = (A, B, u1, u2)被认为是最佳反映等价。很显然，最佳反映等价博弈有相同的纯战略纳什均衡集(PNEs)。3严格竞争性博弈和至多有一个纯纳什均衡集(PNE)定理1. 严格的二人博弈至多有一个纯战略纳什均衡(PNE)当且仅当它对一个严格的竞争性博弈是最佳反映等价4有序的潜在和准超模博弈定理2. 二人严格博弈对于准超模博弈是最佳的反应等价当且仅当它没有最佳反应周期小结讨论由于我们做出的唯一假设是，最佳的反应函数是单值的，因此定理2仍然适用于非退化博弈。对于通常的二人博弈，有三种方法来确定最佳反应周期：1.正常周期在这个定义中，只要任何最佳反应函数是多值，总有一个参与人的小周期，在多个最佳反应中偏离。2. Voorneveld周期这个定义在本质上与上述概念是相同的，只是它至少需要一个绝对增加偏离参与人的回报的周期边界。这样，它排除了我们初始定义中的小周期。3.严格周期在这个定义中，每个周期边界都必须绝对地增加偏离参与人的回报。当只考虑严格博弈时，三个定义是等价的。我们现在讨论由定理2扩展到一般二人博弈的三个周期类型。定理2的“仅当”部分并不适用于一般二人博弈的正常周期和Voorneveld周期，但是仍然适用于严格周期。例如，下面有一个常见的博弈：1,12,12,21,2上图是一个在命令参与人1（一排参与人）执行自上而下的策略和参与人2从左至右的行动的情景下的一个准超模博弈。然而，任何单元的逆时针方向的开始将产生一个正常的周期以及一个Voorneveld周期。因此，这个博弈对于任何序潜在博弈不再是最佳反映等价。不过，根据Kukushkin等人(2005)的定理3，如果博弈是一个准超模博弈（因此一个博弈没有严格的周期就是最佳反映等价），则它没有严格的周期定理2的“如果”部分并不适用于一般二人博弈的Voorneveld周期和严格的周期，但并不适用于正常周期。为了说明这一点，考虑以下常见的博弈：2,22,12,21,11,21,21,21,21,1它没有Voorneveld周期也没有严格的周期。由于没有参与人2的最佳反应函数满足单一交叉条件下的策略序，它对于任何准超模博弈并不是最佳反映等价。另一方面，如果我们假设一个博弈没有正常的周期，这就意味着其最佳反应函数是单值的。因此，“如果”部分适用于正常周期。述评本文验证了关于纯纳什均衡（Pure Nash Equilibriums）对于二人严格博弈且支付函数是一对一的两个结果，最终得到两个结论：(1)一个严格的二人博弈中至多存在一个纯战略纳什均衡(PNE)当且仅当它对于一个严格的竞争性博弈是最佳反映等价；(2)一个严格的二人博弈中至多存在一个纯战略纳什均衡(PNE)当且仅当它对于一个序潜在博弈和准超模博弈是最佳反映等价。众所周知，现代博弈理论由匈牙利大数学家冯诺伊曼（John von Neumann）于20世纪20年代开始创立，1944年他与经济学家奥斯卡摩根斯特恩（Oskar Morgenstern）合作出版的巨著博弈论与经济行为，标志着现代系统博弈理论的初步形成。对于非合作、纯竞争型博弈，诺伊曼所解决的只有二人零和博弈，比如两个人打乒乓球，一方赢则另一方必输，两个人获利的总和为零。在这里能否且如何找到一个理论上的“解”或“平衡”，也就是对参与双方来说都最“合理”或者是最优的具体策略？怎么样的策略才是“合理”？应用传统决策论中的“最小最大”准则，即博弈的每一方都假设对方的所有策略的根本目的是使自己最大程度地失利，并据此最优化自己的对策，诺伊曼从数学上证明，通过一定的线性运算，对于每一个二人零和博弈，都能够找到一个“最小最大解”。用通俗的话说，这个著名的最小最大定理所体现的基本思想是“抱最好的希望，做最坏的打算”。虽然二人零和博弈的解决具有重大的意义，但作为一个理论来说，它应用于实践的范围是极其有限的。二人零和博弈主要的局限性在于：一是在各种社会活动中，常常有多方参与而不是只有两方；二是参与各方相互作用的结果并不一定有人得利就有人失利，整个群体可能具有大于零或小于零的净获利。纳什均衡(Nash Equilibrium)：所谓纳什均衡