二人嚴(yán)格博弈的兩個(gè)等價(jià)結(jié)果

1、Two equivale nee results for two-pers on strict gamesPin gzho ng Tang, Fan gzhe n LinAbstractA game is strict if for both players, different profiles have different payoffs. Two games are best responseequivalent if their best response fun cti ons are the same. We prove that a two-pers on strict game

2、 has at most one pure Nash equilibrium if and only if it is best response equivale nt to a strictly competitive game, and that it is best resp onse equivale nt to an ordinal pote ntial game if and only if it is best resp onse equivale nt to a quasi-supermodular game.Keywords: Strictly competitive ga

3、mes; Ordinal potential games; Quasi-supermodular games Best resp onse equivale nee Strict games1. IntroductionIn this paper we prove two results about pure Nash equilibria (PNEs) for 2-pers on strict games, which are those where payoff fun cti ons are on e-to-one. The first result says that a 2-pers

4、 on strict game has at most one PNE if it is best-resp on seequivale nt (Rose nthal, 1974) to a strictly competitive game (Mouli n, 1976; Friedma n, 1983). The sec ond result says that a 2-pers on strict game is best-resp onse equivale nt to an ordinal pote ntial game (Mon derer and Shapley, 1996) i

5、f it is best-resp onse equivale nt 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 Li n, 2009). We were look ing for con diti ons that imply the uniquen ess and existe nee of the PNEs, and we

6、re using computers to run through a large set of conjectures. Give n the nu mber of all possible games, it made sense to test these con diti ons first on some special classes of games, and the class of strict games is a n atural choice as in these games, the payoff fun cti ons are on e-to-one, thus

7、easier to gen erate. As it tur ned out, some in terest ing con diti ons 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 proofsare non-trivial and had to be done manu ally.2. Basic definitionsA 2-p

8、ers on game is a tuple(A, B, ui, U2), where A and B are sets of pure strategies of players 1 and 2, respectively, anuh and U2 are fun cti ons from A XB to reals called thepayoff fun cti ons for players 1 and 2, respectively .In this paper we assume botA and B are fin ite.A game is said to bestrict i

9、f both players payoff fun cti ons are one-to-one: for any(a，b1) and (a2, b2) in A XB, if (a1, b1)豐(a2, b2) then ui(a1, bd 工52, b2), i = 1,2. A related notion in the literature is non-dege nerate gamegsee, e.gBerger, 2007): a game is non-dege nerate if for any a1,a2 A and b1, b2 B, u1(a1, b1)豐 u1(a2,

10、 b1) whenever a a2, and u2(ai, bi)工 u2(ai, b2)whenever b2. Clearly, a strict game is also non-dege nerate, but the conv erse is not true in gen eral.For each b B, let Bi(b) be the set of best responses by player one to the acti on b by player two:Bi (b)= a I a A, and for all a A, ui(a；b) ui(a, b) .S

11、imilarly, for each a A, letB2 = b I b B, and for all b N, u2(a, b ) u2(a, b).A profile (a, b) A X B is a pure Nash equilibrium (PNE) if a Bi(b) and b B2(a).In this paper we con sider only PNEs. Our in itial motivati on for this work was to capture the class of games with at most one PNE. We started

12、with strictly competitive games (see below). While every strictly competitive game can have at most one PNE, the conv erse is not true in gen eral. This led us to con sider no ti ons of equivale nee betwee n games that will preserve PNEs. The one that suits our purpose here is that of best-resp onse

13、 equivale nee (Rose nthal, 1974): two 2-pers on games=G(A,/ /B, u1, u2) and G2 = (A, B, u1 , u2 ) are said to be best-resp onse equivale nt if for each a A, B2(a) in G1 and G2 are the same, and for each B, B1(b) in G1 and G2 are the same.It is easy to see that best-resp onse equivale nt games have t

14、he 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-resp onse equivale nt to a strictly competitive game.4. Ordinal potential and quasi-supermodular gamesTheorem 2. A 2-person strict game is best-respon

15、seequivalent 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 assumpti on we made is that the best-resp onse fun cti ons are sin gle valued.For gen eral two pers on games, there are three ways to defi

16、ne a best resp onse 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-resp on ses.2. Voorneveld ysle. This definition is essentially the same to above except that it requi

17、res at least one edge in the cycle that strictly in creases 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 in creases the payoff for the deviat ing player.Three def

18、i niti ons are equivale nt whe n con sider strict games only. We now discuss the exte nsion of Theorem 2 to gen eral 2-pers on games with respect to three types of cycles.The “ on ly if ” part of Theorem 2 doteboid for gen eral 2-pers on games for normal cycle and V oorneveld s cycle btilt holds for

19、 strict cycle. For instanee, the following general game:1,12,12,21,2is a quasi-supermodular game under the ordering that orders player 1 s(row player) strategies from top to dow n and player2 s acti on from left to right. However, going counterclockwise starting in any cell will form both a normal c

20、ycle as well as Voorneveld s cycle. Thus this game is not best-resp onse equivale nt to any ordinal pote ntial 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-resp onse equiva

21、le nt to it).The “ if ” part of theorem 2 does not hold for gene-pe2son games for V oorneveld s as well as strict cycles but holds normal cycles. To show this, con sider the follow ing gen eral game:2,22,12,21,11,21,21,21,21,1It has no Voorn evelds nor strict cycles. However it is not besfep onseequ

22、ivale nt to any quasi-supermodular game since there is no orderi ng of strategies under which player 2 best-responsefunction satisfies singlecross ing con diti on. On the other han d, if we assume that a game has no normal cycle, it implies that its best-response functions are single-valued. Therefo

23、re, the if part holds for no rmal cycles.二人嚴(yán)格博弈的兩個(gè)等價(jià)結(jié)果(翻譯)吳昊romTwo equivale nee results for two-pers on strict gamesby Pin gzh ong Tang, Fan gzhe n Lin摘要：若博弈對于兩個(gè)參與人是嚴(yán)格的，那么不同的情景就會(huì)有不同 的結(jié)果。若兩人的最佳反應(yīng)函數(shù)相同，則雙方就會(huì)有同樣的最佳反應(yīng)。 我們發(fā)現(xiàn)在一個(gè)嚴(yán)格的二人博弈中至多存在一個(gè)純戰(zhàn)略納什均衡，當(dāng)且僅當(dāng)它對于一個(gè)嚴(yán)格的競爭性博弈是最佳反映等價(jià)，對于一個(gè)序潛 在博弈是最佳反映等價(jià)，對

24、于一個(gè)準(zhǔn)超模博弈也是最佳反映等價(jià)。 關(guān)鍵詞：嚴(yán)格的競爭性博弈；序潛在博弈；準(zhǔn)超模博弈；最佳反映等 價(jià)；嚴(yán)格博弈1引言在本文中，我們將驗(yàn)證關(guān)于純戰(zhàn)略納什均衡(Pure Nash Equilibriums )對于二人嚴(yán)格博弈的兩個(gè)結(jié)果，這是針對那些支付函 數(shù)是一對一的博弈情況。第一個(gè)結(jié)果表明，一個(gè)嚴(yán)格的二人博弈中最 多存在一個(gè)純戰(zhàn)略納什均衡(PNE)當(dāng)且僅當(dāng)它對一個(gè)嚴(yán)格的競爭性博 弈(穆林，1976;弗里德曼，1983)是最佳反映等價(jià)(羅森塔爾，1974)。 第二個(gè)結(jié)果表明，對一個(gè)序潛在博弈( Mo nderer and Shapley 1996) 是最佳反映等價(jià)，對一個(gè)準(zhǔn)超模博弈(Topkis,

25、 1998)是最佳反映等 價(jià)。這些結(jié)果來自于我們運(yùn)用計(jì)算機(jī)發(fā)現(xiàn)博弈論定理(見，例如：唐 和林，2009)的項(xiàng)目中。我們一直在尋找純戰(zhàn)略納什均衡(PNEs)的獨(dú) 特性和存在性的隱性條件，并通過大量的猜想用計(jì)算機(jī)來執(zhí)行?？紤]到所有可能的博弈數(shù)量，有必要首先針對某些特殊種類的博弈測試這 些條件，在這些博弈中嚴(yán)格博弈的類型是一種自然選擇，其支付函數(shù)是一對一的，因而更容易產(chǎn)生。事實(shí)證明，一些有趣的條件僅在這類 博弈中成立。在這里已經(jīng)介紹了其中的一部分 (Ta ng and Li n, 2009)。 此處所說的這兩個(gè)結(jié)果，其特殊之處就在于，它們的證明過程是不平 凡的，不得不手工完成。2. 基本定義二人博弈

26、是一個(gè)元組(A, B, Ui, U2),其中A和B分別是參與人 1和2的純策略集，Ui和U2是定義在AX B上的函數(shù)，稱為參與人1 和2的支付函數(shù)。在本文中，我們假設(shè) A和B是有限的。若兩個(gè)參與人的支付函數(shù)是一對一的，則被認(rèn)為是嚴(yán)格博弈：對于任何定義在A X B上的(ai, bi)和(a2, 6)，若(ai, bi)半(a2, b2), 則Ui(ai, bi) MUi(a2, b2), i = i, 2。在文獻(xiàn)中一個(gè)相關(guān)的概念是非退化博 弈(伯杰，2007):若對于任何 和2 A and bi,B,當(dāng)ai a?時(shí)都有ui(ai, bi) m Ui(a2, bi)，當(dāng)b2 時(shí)都有 U2(ai, bi)半 U2(ai, 5)。很顯然，一個(gè)嚴(yán)格博弈也是非退化的，但通常反之則不然。對于每個(gè)b B,定義Bi(b)是參與人i對參與人2的最佳反應(yīng)行 為集：Bi (b)= a I a A, and