FREE ELECTRONIC LIBRARY - Thesis, dissertations, books

Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 9 |

«Contents. 1 Nash Equilibrium in Extensive Form Games 2 1.1 Selten’s Game......... 1.2 The Little Horsey....... 1.3 Giving Gifts.. ...»

-- [ Page 4 ] --

Suppose now that player 1 never offers the Star Trek manual, so s ∗ = 0, but offers the Game Theory book with positive probability, so r ∗ 0. In this case, q = 1, and player 2’s sequentially rational response is to accept for sure. However, if she accepts the offer with certainty, then player 1 would prefer to offer even the Star Trek manual: doing so would net For this reason, some authors call the strategies “partially separating” or “partially pooling.” him a payoff of 1 while not offering saddles him with 0. In other words, there can be no equilibrium of this type.

In this case, the player 1’s strategy is separating because it allows player 2 to infer what he knows with certainty. Not surprisingly, if he allowed her to do that, he would be at a disadvantage. It is not difficult to see that separating in a way that convinces player 2 that the offer contains the Game Theory book cannot be optimal: she would accept the offer given this belief but then player 1 would have an incentive to offer the Star Trek manual as well, which means player 2 cannot sustain her belief that she is offered the Game Theory book for sure.

Conversely, player 1 could induce a posterior belief that the book is the Star Trek manual for sure by playing the separating strategy (r ∗ = 0, s ∗ = 1); that is, he never offers the Game Theory book and always offers the Star Trek manual. But in this case, player 2 will always reject the offer, in which case player 1 will be strictly better off not offering the Star Trek manual. So this cannot be an equilibrium either. This game has no separating equilibria.

The final scenario to examine is r ∗ = s ∗ = 0. This leaves player 2’s information set off the equilibrium path of play, so Bayes rule cannot pin down her posterior beliefs. Can we sustain these strategies in equilibrium? To induce player 1 never to offer even the Game Theory book, it must be the case that U1 (G|GT) ≤ U1 (NT |GT) ⇒ 3α − 1 ≤ 0 ⇒ α ≤ 1/3. That is, player 2 must threaten that she will reject the offer with at least 2/3 probability. This threat will be credible if she believed the gift was bad with probability at least 1/2. In other words, if q ≤ 1/2, then player 2 can credibly reject the offer. Observe now that this is sufficient to deter player 1 from offering the Star Trek manual as well: U1 (G|ST) = 2α − 1 2( 1/3) − 1 = − 1/3 0 = U1 (NG|ST).

Therefore, we have multiple PBE that all take the same form:

r ∗ = 0, s ∗ = 0, α = 0 with q ≤ 1/2.

We have some latitude in specifying off-the-equilibrium-path beliefs here but as long as q ≤ 1/, these strategies can be sustained in PBE. Note that technically when q = 1/, any α ≤ 1/ would do the trick. However, as a knife-edge case that does not change the equilibrium path of play, we would normally ignore this.

Observe also that this PBE exists regardless of the prior. In this situation, we have multiple

equilibria. It is important to realize that the semi-separating and the other pooling equilibrium in which player 1 always makes an offer are not “multiple equilibria” in that sense:

depending on the value of the exogenous parameter p, the equilibrium takes either the partially separating or the pooling form. If it weren’t for the pooling PBE where player 1 never offers the gift, this game would have a unique solution for any value of this exogenous parameter. Unfortunately, with this second pooling PBE, this is no longer the case: the game now has at least two solutions (in terms of the equilibrium path of play) over the entire range of p, an indeterminacy that we would have to address somehow.

3 Backward Induction

Before learning how to characterize PBE in arbitrary games of imperfect information, we study how to use backward induction to compute PBE in games of complete information. In games of complete and perfect information, we can apply this technique to find the “rollback” equilibrium, which we then generalize to “subgame-perfect” equilibrium. All of these are PBE but do not require the entire belief machinery.

3.1 Rollback Equilibrium

Computing PBE in games of complete and perfect information is very easy and one does not need to introduce the machinery of beliefs at all because all information sets are singletons.

Sequential rationality will suffice (recall that the conditional beliefs would always require that the probability of being at a node in a singleton information set is exactly 1).

These games can be solved by backward induction, a technique which involves starting from the last stage of the game, determining the last mover’s best action at his information set there, and then replacing the information set with the payoffs from the outcome that the optimal action would produce. Continuing in this way, we work upwards through the tree until we reach the first mover’s choice at the initial node.

In 1913 Zermelo proved that chess has an optimal solution. He reasoned as follows. Since chess is a finite game (it has quite a few moves, but they are not infinite), this means that it has a set of penultimate nodes. That is, nodes whose immediate successors are terminal nodes. The optimal strategy specifies that the player who can move at each of these nodes chooses the move that yields him the highest payoff (in case of a tie he makes an arbitrary selection). Now, the optimal strategies specify that the player who moves at the nodes whose immediate successors are the penultimate nodes chooses the action which maximizes his payoff over the feasible successors given that the other player moves there in the way we just specified. We continue doing so until we reach the beginning of the tree. When we are done, we will have specified an optimal strategy for each player.

These strategies constitute a Nash equilibrium because each player’s strategy is optimal given the other player’s strategy. In fact, these strategies also meet the stronger requirements of subgame perfection, which we shall examine in the next section. (Kuhn’s paper provides a proof that any finite extensive form game has an equilibrium in pure strategies. It was also in this paper that he distinguished between mixed and behavior strategies for extensive form

games.) Hence the following result:

Theorem 4 (Zermelo 1913; Kuhn 1953). A finite game of perfect information has a pure strategy Nash equilibrium.

We can find this equilibrium by backward induction in the following way. Start with the penultimate node, and determine the sequentially rational strategy for the player who gets to move there. Replace the node with the outcome produced when that player chooses this strategy. Continue working backward until you reach the initial node. The sequentially rational strategies you now have constitute the PBE of this game, which is called a rollback equilibrium.

Since Selten’s game in Fig. 2 (p. 3) is one of complete and perfect information, we can apply backward induction to find its rollback equilibrium. At her information set, player 2 would choose L. This reduces player 1’s choices between D (which, given player 2’s strategy would yield 3) and U, which yields 2. Therefore, player 1 would choose D. The rollback equilibrium of this game is D, L. As before, this is also Nash and PBE.

Consider now the game in Fig. 10 (p. 19).

What are the Nash equilibria of this game? As usual, convert this to strategic form, as shown in Fig. 11 (p. 19). (We shall keep the non-reduced version to illustrate a point.) The Nash equilibria in pure strategies are (∼e, a), r, (∼e, ∼a), r, and (e, a), ∼r.

Applying backward induction produces the rollback equilibrium (∼e, ∼a), r illustrated in Fig. 12 (p. 19). This eliminates two of the pure-strategy Nash equilibria, and demonstrates

–  –  –

The only reason why ∼e is sequentially rational at player 1’s first information set is because player 2’s sequentially rational strategy prescribes r, which in turn is only rational because she expects player 1 to choose ∼a at his last information set, where this is the sequentially rational choice. In other words, the optimality of player 1’s initial action depends on the optimality of his action at his second information set. This is precisely why we cannot determine optimality of strategies unless they specify what to do for all information sets. Note that in this case, the second information set is not reached if the strategy (∼e, ∼a) is followed, but we still need to know the action there.

The problem with the Nash equilibrium profiles (∼e, a), r and (e, a), ∼r is that they leave information sets off the equilibrium path of play and so Nash optimality cannot pin down behavior at sets that are never reached. For example, (e, a), ∼r leaves player 1’s second information set off the path of play, which causes the strategy to miss the fact that a is not sequentially rational at that set. This incredible threat rationalizes player 2’s choice of ∼r causing her to take an action that leaves this information set off the path. Similarly, (∼e, a), r leaves both player 1’s second information set and player 2’s information set off the path of play and causes the strategies to miss two problems: player 1’s choice of a is not sequentially rational at his second information set, and given that choice, player 2’s choice of r is not rational either! In other words, since the equilibrium path of play does not reach some continuation games, Nash cannot pin down optimal behavior there.

Let’s apply backward induction to the game in Fig. 13 (p. 20). There are three penultimate information sets, all of them for player 2. For each of these sets we determine player 2’s sequentially rational strategy. Because all information sets are singletons, we do not need to specify conditional beliefs (they are trivial and assign probability 1 to the single node in the information set). So, if the (2, 0) set is ever reached, then player 2 is indifferent between accepting and rejecting. Any of these actions is plausible, so player 2’s sequentially rational strategy at (2, 0) includes both actions. In other words, player 2 will be willing to mix at this information set. On the other hand, player 2’s sequentially rational strategy at (1, 1) is unique: it is always better to accept. And so in the case of (0, 2). Therefore, player 2 has only two credible pure strategies, yyy and nyy.

(2, 0) (0, 2) (1, 1) y y y n n n 2,0 0,0 1,1 0,0 0,2 0,0

–  –  –

Given player 2’s best responses to each of his actions, player 1 can now optimize his own behavior. He knows that if he chooses (2, 0), then player 2 can either accept of reject, if he offers (1, 1) or (0, 2), then player 2 will always accept. Given these conditions, player 1 will never offer (0, 2) in equilibrium because it yields him a payoff of 0. Given these strategies, player 1 has two optimal actions, either (2, 0) if he thinks player 2 will choose the first strategy and (1, 1) if he thinks that player 2 will choose the second. Thus, we conclude that the game has only two rollback equilibria in pure strategies: (2, 0), yyy and (1, 1), nyy.4 Kuhn’s theorem makes no claims about uniqueness of the equilibrium. Indeed, as we saw in the example above, the game has two rollback equilibria. However, it should be clear that if no player is indifferent between any two outcomes, then the equilibrium will be unique.

Note that all rollback equilibria are Nash equilibria. (The converse, of course, is not true. We have just gone to great lengths to eliminate Nash equilibria that seem implausible.)

3.2 Subgame-Perfect Equilibrium

If you accept the logic of backward induction, then the following discussion should seem a natural extension. Consider the game in Fig. 14 (p. 21). Here, neither of player 2’s choices is Player 2 is indifferent between accepting and rejecting after (2, 0) offer, so she can mix after receiving it. If she accepts with probability greater than 1/2, then player 1 is better off demanding (2, 0), and we have a continuum of SPE there. If, however, she accepts with probability less than 1/2, then player 1 is better off demanding (1, 1) instead (for another continuum of SPE). If she accepts exactly with probability 1/2, then player 1 is indifferent between (2, 0) and (1, 1), so he can mix between these two strategies as well (for another continuum of SPE).

dominated at her second information set: she is better off choosing D if player 1 plays A and is better off choosing C if player 1 plays B. Hence, we cannot apply rollback.

However, we can reason in the following way. The game that begins with player 1’s second information set—the one following the history (D, R)—is a zero-sum simultaneous move game. We have seen similar games, e.g., Matching Pennies. The expected payoffs from the unique mixed strategy Nash equilibrium of this game are (0, 0). Therefore, player 2 should only choose R if she believes that she will be able to outguess player 1 in the simultaneousmove game. In particular, the probability of obtaining 2 should be high enough (in outweighing the probability of obtaining −2) that the expected payoff from R is larger than 1 (the payoff he would get if he played L). This can only happen if player 2 believes she can outguess player 1 with a probability of at least 3/4, in which case the expected payoff from R will be at least 3/4(2) + 1/4(−2) = 1. But, since player 2 knows that player 1 is rational (and therefore just as cunning as she is), it is unreasonable for her to assume that she can outguess player 1 with such high probability. Therefore, player 2 should choose L, and so player 1 should go D. The equilibrium obtain by backward induction in the game in Fig. 14 (p. 21), then, is (D, 1/2[A]), (L, 1/2[C]).

–  –  –

This now is the logic of subgame perfection: replace every “proper subgame” of the tree with one of its Nash equilibrium payoffs and perform backward induction on the reduced tree.5 For the game in Fig. 14 (p. 21), once we replace the subgame that starts at player 1’s second information set with the Nash equilibrium outcome, the game becomes the one in Fig. 2 (p. 3), which we have already analyzed and for which we found that the backwardinduction equilibrium is D, L.

Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 9 |

Similar works:

«WOMEN GROUPS HARVEST RAINWATER AND INFLUENCE NATIONAL POLICY A UGANDAN CASE STUDY Charles Rwabambari Centre for Community Solidarity P.O.Box 195 Mbarara, Uganda rwabambari_c@yahoo.com Hans Hartung, FAKT-Consult Kanalstr.23 97990 Weikersheim, Germany hansfhartung@aol.com ABSTRACT Rainwater harvesting has started in Oruchinga Valley, Southwest Uganda, in an important way after 1993. It was the participation of an NGO representative in a rainwater workshop in neighbouring Kenya that marked the...»

«Pupil Protector Personal Accident Policy We agree to give the insurance cover set out in this group policy document. We will provide cover only to those people who are shown as being insured persons as long as the appropriate premium has been paid and we have accepted it. This group policy, the schedule and any attached memoranda or endorsements show details of the cover and the terms and conditions applying to it. The group policyholder should read these documents to make sure that they...»

«Abstract SUMMARY 20th Section Fall Meeting October 10-13, 2012 Austin, TX THURSDAY, OCTOBER 10, 2012 8:30 a.m. – 10:00 a.m.PLENARY SESSION: LEGAL GUIDANCE FOR U.S. ENERGY PROVIDERS IN THE ERA OF SHIFTING NATIONAL ENERGY POLICY Legal Guidance for U.S. Energy Providers in the Era of Shifting National Energy Policy: GHG and Other Significant Regulatory Challenges Kimberly S. Bowers, Executive Vice President and General Counsel, Valero Energy Corporation, San Antonio, TX Marcus V. Brown, Senior...»

«Transboundary river basin management in Europe Legal instruments to comply with European water management obligations in case of transboundary water pollution and floods Andrea M. Keessen, Jasper J.H. van Kempen & Helena F.M.W. van Rijswick* 1. Introduction Modern water policy is shaped by geographical areas in the context of which water courses are divided into river basins. This is reflected on an international level by treaties such as the 1992 Convention on the Protection and Use of...»

«TENNESSEE DEPARTMENT OF REVENUE LETTER RULING # 11-58 WARNING Letter rulings are binding on the Department only with respect to the individual taxpayer being addressed in the ruling. This presentation of the ruling in a redacted form is information only. Rulings are made in response to particular facts presented and are not intended necessarily as statements of Department policy. SUBJECT The application of the Tennessee sales and use tax to a customer relationship management software...»

«ICS-ACI Policy Series ICS-ACI-P020 Data Protection and Retention This is part of a series of documents that make up the formal policies adopted by the Institute for CyberScience at the Pennsylvania State University. Last Updated: July 9, 2015 1.0 Overview The purpose of this document is not to impose restrictions that are contrary to the Pennsylvania State University’s established culture of openness, trust and integrity. The Institute for CyberScience Advanced Cyber Infrastructure (ICSACI)...»

«Boosting Open Innovation and Knowledge Transfer in the European Union Appendix Independent Expert Group Report on Open Innovation and Knowledge Transfer Research and Innovation EUROPEAN COMMISSION Directorate-General for Research and Innovation Directorate B — Innovation Union and European Research Area Unit B1 — Innovation Union Policy E-mail: RTD-Innovation-Policy-B1@ec.europa.eu RTD-PUBLICATIONS@ec.europa.eu Contact: Peter Dröll European Commission B-1049 Brussels EUROPEAN COMMISSION...»

«EXCERPTED FROM Decentralization in Uganda: Explaining Successes and Failures in Local Governance Gina M. S. Lambright Copyright © 2011 ISBN: 978-1-935049-32-6 hc FIRSTFORUM PRESS A D I V I S I O N O F LY N N E R I E N N E R P U B L I S H E R S, I N C. 1800 30th Street, Ste. 314 Boulder, CO 80301 USA telephone 303.444.6684 fax 303.444.0824 This excerpt was downloaded from the FirstForumPress website www.firstforumpress.com Contents List of Tables and Figures ix List of Abbreviations and...»

«Finno Ugorskii Martirolog Zhertv Finno-Ugorskii Martirolog Zhertv Politicheskikh Repressii V SSSR Politicheskikh Repressii V SSSR And not do on report in there must be existing jobs for a integrity, online loans, more fee increased for also increased. Of they offer paid for mortgage and was their mergers, you is license to become up, be your quality and take having out your product underwriters. By there do still one real buyer dollars of your document for 4 meetings, valuables do his good...»

«July 2016 The changing relationship between government and policy scholarship: Challenges to nonpartisan research in Brookings’ second century William A. Galston INTRODUCTION O ver the past half-century, the relationship between research centers and governing authorities in the United States has undergone a profound transformation. Increasing polarization between the political parties has reduced demand for nonpartisan research while sparking a William A. Galston proliferation of think tanks...»

«The Implications of Devolution for England Presented to Parliament by the First Secretary of State and Leader of the House of Commons by Command of Her Majesty December 2014 Cm 8969 -2© Crown copyright 2014 This publication is licensed under the terms of the Open Government Licence v3.0 except where otherwise stated. To view this licence, visit nationalarchives.gov.uk/doc/open-government-licence/version/3 or write to the Information Policy Team, The National Archives, Kew, London TW9 4DU, or...»

«Bob Dylan’s 116th Dream: Reflections on the Lyrics1 Louis A. Renza “Don’t get up gentlemen, I’m only passing through.” Bob Dylan, “Things Have Changed” (1999) Not a few critics of Bob Dylan’s songs think one ought to discuss them primarily as songs, which is to say not as the equivalent of written poems.2 The Dylan “text” clearly comprises a perpetually interchangeable complex of verbal lyric, musical arrangement, and vocal performancehis in particular. Moreover, not a few...»

<<  HOME   |    CONTACTS
2016 www.dis.xlibx.info - Thesis, dissertations, books

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.