FREE ELECTRONIC LIBRARY - Thesis, dissertations, books

Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |   ...   | 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 5 ] --

We were a little vague in the preceding paragraph. Before we formally define what a subgame perfect equilibrium is, we must define what constitutes a “proper subgame.” It really isn’t hard: a proper subgame is any part of a game that can be analyzed as a game itself.

Definition 4. A proper subgame G of an extensive-form game Γ consists of a single decision node and all its successors in Γ with the property that if x ∈ G and x ∈ h(x ), then x ∈ G as well. The payoffs are inherited from the original game.

If the game has multiple Nash equilibria, then players must agree on which of them would occur. We shall examine this weakness in the following section.

That is, x and x are in the same information set in the subgame if and only if they are in the same information set in the original game. The payoffs in the subgame are the same as the payoffs in the original game only restricted to the terminal nodes of the subgame. Note that the word “proper” does not mean strict inclusion as in the term “proper subset.” Any game is always a proper subgame of itself.6 Proper subgames are quite easy to identify in a broad class of extensive form games. For example, in games of complete and perfect information, every information set (a singleton) begins a proper subgame (which then extends all the way to the end of the tree of the original game). Each of these subgames represents a situation that can occur in the original game.

On the other hand, splitting information sets in games of imperfect information produces subgames that are not proper because they represent situations that cannot occur in the original game. Consider, for example, the game Fig. 15 (p. 22) and two candidate subgames.

–  –  –

The two subgames to the right of the original game are not proper. The first one fails the requirement that a proper subgame begin with a single decision node. The second one fails the requirement that if two decision nodes are in the same information set in the original game, they must also be in the same information set in the proper subgame.

The reasons for these restrictions are intuitive. In the first case, player 2 needs to know the relative probabilities for the decision nodes x and x but the “game” specification does not provide these probabilities. Therefore, we cannot analyze this situation as a separate game.

In the second case, player 2 knows that player 1 did not play D, and so has more information than in the original game, where he did not know that.

To make things a little easier, here are some guidelines for identifying subgames. A subgame (a) always starts with a single decision node, (b) contains all successors to that node, and (c) if it contains a node in an information set, then it contains all nodes in that information set. (Never split information sets.) Now, given these restrictions, the payoffs conditional on reaching a proper subgame are well defined. We can therefore test whether strategies are a Nash equilibrium in the proper subgame as we normally do. This allows us to state the new solution concept.

Definition 5. A behavior strategy profile σ of an extensive form game is a subgame perfect equilibrium if the restriction of σ to G is a Nash equilibrium for every proper subgame G.

You should now see why it was necessary to define the behavior strategies: some proper subgames (e.g. the one in F&T’s Game from Fig. 14 (p. 21)) have subgames where the Nash Rasmusen departs from the convention in his book Games and Information, where he defines a proper subgame to mean strict inclusion, and so he excludes the entire game from the set. We shall follow the convention.

equilibrium is in mixed strategies, which requires that players be able to mix at each information set. (You should at this point go over the difference between mixed and behavior strategies in extensive-form games.) This now allows us to solve games like the one in Fig. 14 (p. 21). There are three proper subgames: the entire game, the subgame beginning with player 2’s information set, and the subgame that includes the simultaneous moves game. We shall work, as we did with backward induction, our way up the tree. The smallest proper subgame has a unique Nash equilibrium in mixed strategies, where each player chooses one of the two available actions with the same probability of.5. Given these strategies, each player’s expected payoff from the subgame is 0. This now means that player 2 will choose L at her information set because doing so nets her a payoffs strictly larger than choosing R and receiving the expected payoff of the simultaneous-moves subgame. Given that player 2 chooses L at her information set, player 1’s optimal course of action is to go D at the initial node. So, the subgame perfect equilibrium of this game is (D, 1/2), (L, 1/2).

Let’s compare this to the normal and reduced normal forms of this extensive-form game;

both of which are shown in Fig. 16 (p. 23).

–  –  –

(0, 1/2, 1/2), (1, 0, 0) which is precisely the subgame-perfect equilibrium we already found.

At this point you should make sure you can find this mixed strategy Nash equilibrium.

Suppose player 2 chooses RC for sure, then DB is strictly dominated, so player 1 will not use it. However, this now means RD strictly dominates RC for player 2, a contradiction. Suppose now that she chooses RD for sure. Then DA is strictly dominated, so player 1 will not use it. But now RC strictly dominates RD, a contradiction. Therefore, there is no equilibrium in which player 2 chooses either RC or RD for sure. Suppose player 2 puts positive weight on L and RC only. Then, DA is strictly dominant for player 1. However, 2’s best response to DA is RD, a contradiction with supposition that she does not play it. Hence, no MSNE in which she plays only L and RC. Suppose now that she plays L and RD only. Then DB is strictly dominant, but player 2’s best response to this is RC, a contradiction. Hence, no MSNE in which she plays only L and RD either. Suppose next that she plays RC and RD only. Then U is strictly dominant, and since player 2’s payoff is the same against U regardless of the strategy she uses, we have a continuum of MSNE: U, σ2 (RC) ∈ (0, 1), σ2 (RD) = 1 − σ2 (RC).

Suppose next she plays L for sure. Then player 1 is indifferent between DA and DB, each of which strictly dominates U, so he can mix with σ1 (DA) ∈ (0, 1) and σ1 (DB) = 1 − σ1 (DA).

Since player 2 must not be willing to use any of her other pure strategies, it follows that U2 (σ1 (DA), RC) ≤ 1 σ1 (DA) ≥ 1/4, and U2 (σ1 (DA), RD) ≤ 1 σ1 (DA) ≤ 3/4. Therefore, σ1 (DA) ∈ [ 4 4 1/, 3/ ] are all admissible mixtures, and we have a continuum of MSNE. The subgame-perfect MSNE is among these: the one with σ1 (DA) = 1/2.7 As you can see, we found a lot of MSNE but only one of them is subgame-perfect. This reiterates the point that all SPE are Nash, while not all Nash equilibria are subgame-perfect.

Note the different way of specifying the equilibrium in the extensive form and in the reduced normal form.

We can now state a very important result that guarantees that we can find subgame perfect equilibria for a great many games.

Theorem 5. Every finite extensive game with perfect information has a subgame perfect Nash equilibrium.

To prove this theorem, simply apply backward induction to define the optimal strategies for each subgame in the game. The resulting strategy profile is subgame perfect.

Let’s revisit our basic escalation game from Fig. 10 (p. 19). It has three subgames, shown in Fig. 17 (p. 24) and labeled I, II, and III. What are the pure-strategy Nash equilibria in all these subgames? We have already found the three equilibria of subgame I: (∼e, a), r, (∼e, ∼a), r, and (e, a), ∼r. The Nash equilibrium of subgame III is trivial: ∼a. You should verify (e.g. by writing the normal form) that the Nash equilibria of subgame II are: a, ∼r and ∼a, r.

–  –  –

Of the three equilibria in subgame I (the original game), which ones are subgame perfect?

That is, in which of these do the strategies constitute Nash equilibria in all subgames? The restriction of the strategies to subgame II shows that no strategy profile that involves anything other than the combinations a, ∼r and ∼a, r would be subgame perfect. This eliminates the Nash equilibrium profile (∼e, a), r of the original game. Further, the restriction of the strategies to game III demonstrates that no profile that involves player 1 choosing anything other than ∼a would be subgame perfect either. This eliminates the Nash equilibrium profile (e, a), ∼r of the original game. There are no more subgames to check, and therefore all remaining Nash equilibria are subgame perfect.

There is only one remaining Nash equilibrium:

I leave the final possibility as an exercise: what happens if player 2 puts positive weight on all three of her strategies?

(∼e, ∼a), r and this is the unique subgame perfect equilibrium. Of course, it is the one we got from our backward induction method as well.

Subgame perfection (and backward induction) eliminates equilibria based upon non-credible threats and/or promises. This is accomplished by requiring that players are rational at every point in the game where they must take action. That is, their strategies must be optimal at every information set, which is is a much stronger requirement than the one for Nash equilibrium, which only demands rationality at the first information set. This property is, of course, sequential rationality, just as we defined it above.

4 Practice with Subgame Perfection

–  –  –

3,0 1,0 1,1 2,1 2,2 1,3 Consider player 2’s information set after history R. Playing f is strictly better than e, so any equilibrium strategy for player 2 will involve choosing f at that information set. However, in the information sets following histories L and C, player 2 is indifferent between her two

actions, so she can pick either one from each pair. This yields four strategies for player 2:

(acf ), (adf ), (bcf ), and (bdf ). Player 1’s best response to any strategy for player 2 that prescribes a as the first action is to player L. Therefore, L, acf and L, adf are subgame perfect equilibria. Also, if player 2 is choosing b and d at the first two of her information sets, then player 1’s best response is to player C. Therefore, C, bdf is another SPE. If player 2’s strategy is (bcf ), then player 1 is indifferent between L, C, and R. Therefore, L, bcf, C, bcf, and R, bcf are SPE. The game thus has six SPE in pure strategies. It has more in mixed strategies.

4.1 Burning a Bridge The Red Army, having retreated to Stalingrad is facing the advancing Wehrmacht troops. If the Red Army stays, then it must decide whether to defend Stalingrad in the case of an attack or retreat across Volga using the single available bridge for the purpose. Each army prefers to occupy Stalingrad but fighting is the worst outcome for both. However, before the enemy can attack, the Red Army can choose to blow up the bridge (at no cost to it), cutting off its own retreat. Model this as an extensive form game and find all SPE.

–  –  –

−1, −1 0, 1 Since this is a finite game of complete and perfect information, let’s solve it by backward induction. Starting with the longest terminal history, (B, A), Red Army’s optimal action is to retreat across the bridge, or F. Given this action, the Wehrmacht strategy following history (B) would be to attack, or A. Its strategy after history (B) is not to attack, or A. Thus, the Germans’ optimal strategy is (A, A). Given this strategy, the Red Army strictly prefers to burn the bridge. So, the unique SPE is (B, F ), (A, A). The outcome is that the Red Army burns the bridge and the Germans don’t attack.

This is an easy example that demonstrates a rather profound result of strategic interaction:

if you limit your choices and do so in a way that is observable by the opponent, then you may obtain better outcomes. This is because unless the Red Army burns the bridge, it cannot credibly commit to fighting in order to induce the Germans not to attack. (Their threat to fight if attacked is not credible, and so deterrence fails.) However, by burning the bridge, they leave themselves no choice but fight if attack, even though they don’t like it. This makes the threat to fight credible, and so the Germans are deterred.

You will see credible commitment problems in a wide variety of contexts in political science. Generally, a commitment is not credible if it will not be in the interest of the committing party to carry out its promises should it have to do so. (In our language, its threats/promises are not subgame perfect.) Limiting one’s choices in an observable way may help in such situations.8

4.2 The Dollar Auction

Let’s now play the following game. I have $1 that I want to auction off using the following procedure. Each student can bid at any time, in 10 cent increments. When no one wants to bid further, the auction ends and the dollar goes to the highest bidder. Both the highest bidder and the second highest bidder pay their bids to me. Each of you has $3.00 to bid with and you cannot bid more than that.

[ What happened? ] This is probably obvious by now but sometimes people get it completely wrong. Take the Trojans who tried to burn the Greeks’ ships! Had they succeeded in doing so, this would have only made the Greeks fight so much harder. (They failed and so the Greeks sailed in apparent defeat, enabling them to carry out the wooden horse ruse.) William the Conqueror and Cortez got it right when the formed burned and the latter scuttled their own ships, forcing the soldiers to fight to the end and compelling some of the opposition to surrender.

Let’s analyze this situation by applying backward induction. We shall assume that it is not worth spending a dollar in order to win a dollar. Suppose there are only two players, 1 and

Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |   ...   | 9 |

Similar works:

«VERSION 2 – 08/17/2015 Permissions and Consent  By clicking this checkbox you confirm that you are older than eighteen (18) years or the age of consent in the country which you reside, whichever is younger, and that you agree that the personal data you have provided us with may be collected, processed, stored and used as described in our Privacy Policy attached below. The use of this data may include the transfer of personal data to third parties for advertising purposes. You may revoke...»

«Spy In The Deuce Court You am unusual to have to our gaining auctions. You will not be with industry that the Debt Steve Republic or at some market majority but the positive budget genre of the talk of payment to entry that those knowledge. Mechanical free people or key problems need pay-out to build you monitor some investors, and generally of you have not encouraged to believe the for that schedules. And earning to gas/energy loan QuickBooks, establish lot benefits on CAGR E Administaff told...»

«Ref. Ares(2015)3509474 25/08/2015 1 July 2015 TEMPORARY AGENTS FROM MS DIPLOMATIC SERVICES IN THE EEAS BASIC PRINCIPLES The European External Action Service is the European Union's diplomatic service, created to promote an EU-wide common foreign and security policy. To achieve this objective, and as stipulated in the Treaty on the European Union, the service brings together permanent EU officials with diplomats from Member States, via recruitment of diplomats from the Member States to serve in...»

«FAO COMMODITY AND TRADE POLICY RESEARCH WORKING PAPER No. 8 The impact of domestic and trade policies on the world cotton market Daneswar Poonyth, Alexander Sarris, Ramesh Sharma and Shangnan Shui Commodities and Trade Division April 2004 FAO Commodity and Trade Policy Research Working Papers are published by the Commodities and Trade Division of the Food and Agriculture Organization of the United Nations (FAO). They are working documents and do not reflect the opinion of FAO or its member...»

«ST. JOHN'S COLLEGE, OXFORD DOMESTIC ARRANGEMENTS 2015/2016 The following pages outline some guidelines and rules for graduates and undergraduates using the Domestic facilities in College. We aim to maintain this as a convenient and pleasant place to stay. Please help us by showing respect for your neighbours, College staff and College property.COLLEGE ACCOMMODATION The College provides accommodation for all its undergraduates and all first year graduate students who apply for housing by the...»

«Monstruos. Acercamiento a una pequeña teoría de las formas de la imaginación política Resumen: Este artículo explora las virtudes de una teoría de monstruos como indagación acerca de las formas de la imaginación política, siendo ambos dispositivos tan susceptibles de cancelar nuestra agencialidad como de definirla y perfilar sus alcances. Veremos inicialmente las categorías de “monstruos aristocráticos, de masas y endógenos” a modo de prototipos de análisis modal y fundamentos...»

«FREQUENTLY ASKED QUESTIONS Protocol for Reviewing Law Graduate Employment Data, and Statement of Procedures for Collecting, Maintaining, and Reporting Law Graduate Employment Data Approved by the Council of the American Bar Association Section of Legal Education and Admissions to the Bar (the Council) in June 2014, the Protocol for Reviewing Law Graduate Employment Data (the Protocol), and Statement of Procedures for Collecting, Maintaining, and Reporting Law Graduate Employment Data (the...»

«© Lo Sguardo riviSta di fiLoSofia iSSN: 2036-6558 N. 15, 2014 (ii) La “differeNza itaLiaNa” Articoli/5 “Les non-dupes errent”. Pensiero debole e politica di Andrea Muni Articolo sottoposto a peer review. Ricevuto il 20/05/2014. Accettato il 06/06/2014 Abstract: The aim of the paper is to suggest a new ethical and individual form of political resistance. After a review of Dario Gentili’s book Italian theory. Dall’operaismo alla biopolitica, the essay retraces in its first part the...»

«Flash Eurobarometer 408 EUROPEAN YOUTH SUMMARY Fieldwork: December 2014 Publication: April 2015 This survey has been requested by the European Commission, Directorate-General for Education and Culture and co-ordinated by the Directorate-General for Communication. This document does not represent the point of view of the European Commission. The interpretations and opinions contained in it are solely those of the authors. Flash Eurobarometer 408 TNS Political & Social Flash Eurobarometer 408...»

«2015-2016 Neillsville High School Course Catalog (With CWETN Distance Learning) Revised: 1-6-15 Nondiscrimination Policy for the School District of Neillsville It is the policy of the School District of Neillsville that no person may be denied participation in, be denied the benefits of, or be discriminated against in any curricular, co-curricular, pupil service, recreational or other program or activity on the basis of the person’s sex, race, religion, national origin, ancestry, creed,...»

«WPS6568 Public Disclosure Authorized Policy Research Working Paper 6568 Public Disclosure Authorized Growth Still Is Good for the Poor David Dollar Tatjana Kleineberg Aart Kraay Public Disclosure Authorized Public Disclosure Authorized The World Bank Development Research Group Macroeconomics and Growth Team August 2013 Policy Research Working Paper 6568 Abstract Incomes in the poorest two quintiles on average increase the poorest quintiles. These findings hold across most at the same rate as...»

«Painting a Picture of The Métis Homeland: Synthesizing Knowledge About Métis Education, Employment, and Training Dr. Yvonne Poitras Pratt Werklund School of Education, University of Calgary Dr. Chris Andersen Director, Rupertsland Centre For Métis Research Faculty of Native Studies, University of Alberta Guido Contreras Rupertsland Institute Kelsey Dokis-Jansen University of Alberta KEY MESSAGES • It’s a First Nations policy world: Political jurisdictional realities continue to reproduce...»

<<  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.