FREE ELECTRONIC LIBRARY - Thesis, dissertations, books

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

2. If 2 ever bids $3.00 she will win the auction and lose $2.00. If she bids $2.90, then 1 has to bid $3.00 in order to win. If 1’s previous bid was $2.00 or less, then 1 will not outbid 2’s $2.90 because doing so (and winning) means losing $2.00 instead of whatever 1’s last bid is, which is at most that (this is where the assumption comes into action). But the same logic applies for 2’s bid of $2.80 because 1 cannot bid $2.90 and expect to win: in this case 2 will do strictly better by outbidding him with $3.00 and losing only $2.00 instead of $2.80.

Therefore, 1 can only win by bidding $3.00 but this means losing $2.00. Therefore, if 2 bids $2.80, then 1 will pass if his last bid was $2.00 or less. In fact, any bid of $2.10 or more will beat any last bid of $2.00 or less for that very reason. So, whoever bids $2.10 first establishes a credible threat to go all the way up to $3.00 in order to win. This player has already lost $2.10, but it is worth spending $.90 in order to win the dollar.

Therefore, a bid of $2.10 is “the same” as a bid of $3.00. This means that in order to beat a $2.00 bid, it is sufficient to bid $2.10, nothing more. By a similar logic, $2.00 beats all bids of $1.10 or less. Since beating $2.00 involves bidding $2.10, if the player’s last bid was for $1.10 or less, there is no reason to outbid a $2.00 bid because doing so yields at most a loss of $1.10, which is at most equal to the player’s current bid. In fact, even $1.20 is sufficient to beat a bid of $1.10 or less. This is because once someone bids $1.20, it is worthwhile for that player to continue up to $2.10 to guarantee a victory (in which case they will stand to lose $1.10 instead of $1.20).

Therefore, a bid of $1.20 is “the same” as a bid of $2.10, which is “the same” as a bid of $3.00. By this logic, a bid of $1.10 beats bids of 20 cents or less. Because beating $1.10 involves bidding $1.20, if the player’s last bid was for 20 cents or less, there is no reason to win. Only a player who bids 30 cents has a credible threat to go up to $1.20. So, any amount down to 30 cents beats a bid of 20 cents or less. If someone bids 30 cents, no one with a bid of 20 cents or less has an incentive to challenge.

Therefore, the first player to bid should bid 30 cents and the auction should end. How does that correspond to our outcome? (Probably not too well.) Let’s look at an extensive-form representation of a simpler variant, where two players have $3.00 each but they can only bid in dollar increments in an auction for $2.00.

$3 Pass −1, 0 0, 0 $1 $2

–  –  –

−1, 0 −1, −2 We begin with the longest terminal history, ($1, $2), and consider 1’s decision there. Since 1 is indifferent between Passing and bidding $3, both are optimal (we do not use the indifference assumption as in the informal example). If he passes, then player 2 is indifferent between passing and bidding $2 at the decision node following history ($1). If, on the other hand player 1 bids $3, then player 2’s best course is to pass. So, the subgame beginning at the information set ($1) has three SPE in pure strategies: (Pass, Pass), ($2, Pass), and (Pass, $3).

At the decision node following history ($2), player 2’s unique optimal action is to pass, and so the subgame perfect equilibrium there is (Pass). Therefore, player 2’s strategy must specify Pass for this decision node in any SPE.

Consider now player 1’s initial decision. If the players’ strategies are such that they play the (Pass, Pass) SPE in the subgame after history ($1), then player 1 does best by bidding $1 at the outset. Therefore, ($1, Pass), (Pass, Pass) is an SPE of the game.

If the strategies specify the SPE ($2, Pass), then player 1’s best actions are to bid $2 or Pass at the initial node. There are two SPE: ($2, Pass), ($2, Pass) and (Pass, Pass), ($2, Pass).

If the strategies specify the SPE (Pass, $3), then player 1’s best action is again to bid $1, and so there is one other SPE: ($1, $3), (Pass, Pass).

The game has four subgame perfect equilibria in pure strategies. It only has three outcomes: (a) player 1 bids $1 and player 2 passes, yielding player 1 a gain of $1 and player 2 a payoff of $0; (b) player 1 passes and both get $0; (c) player 1 bids $2 and player 2 passes, and both get $0.

Now suppose we introduce our assumption, which states that if a player is indifferent between passing now and bidding something that will yield him the same payoff later given the other player’s strategy, then the player passes. This means that in the longest history player 1 will Pass instead of bidding $3, which further implies player 2 will Pass at the preceding node, and so this subgame will have only one SPE: Pass, Pass. But now player 1 has a unique best initial action, which is to bid $1. Therefore, the unique SPE under this assumption is ($1, Pass), (Pass, Pass). The outcome is that player 1 bids $1 and player 2 passes.

This corresponds closely to the outcome in our discussion above.

There is a general formula that you can use to calculate the optimal size of the first bid, which depends on the amount of money available to each bidder, the size of the award, and the amount of bid increments. Let the bidding increment be represented by one unit (so the unit in our example is a dime). If each player has b units available for bidding, and the award is v units, the the optimal bid is ((b − 1) mod (v − 1)) + 1. In our example, this translates to (30 − 1) mod (10 − 1) + 1 = 3 units, which equals 30 cents, just as we found.

It is interesting to note that the size of the optimal bid is very sensitive to the amount each player has available for bidding. If each player has $2.80 instead of $3.00, then the optimal bid is (28 − 1) mod (10 − 1) + 1 = 1, or just 10 cents. If, however, each has $2.70, then the optimal bid is (27 − 1) mod (10 − 1) + 1 = 9, or 90 cents.

The Dollar Auction was first described by Martin Shubik who reported regular gains from playing the game in large undergraduate classes. The game is a very useful thought experiment about escalation. At the outset, both players are trying to win the prize by costly escalation, but at some point the escalation acquires momentum of its own and players continue paying costs to avoid paying the larger costs of capitulating. The requirement that both highest bidders pay the cost captures the idea of escalation. The general solution (the formula for the size of the optimal bids) was published by Barry O’Neill.

4.3 Multi-Stage Games with Observed Actions

There is a very special but useful class of extensive form games, which have “stages” such that (a) in each stage every player knows all the actions taken by any player at any previous stage, and (b) players move simultaneously within each stage. So, “multi-stage games with observed actions” is just a fancy name for the class of extensive form games, where the players move simultaneously within each stage and know the actions that were chosen in all past stages. Most, but not all, of the games we have seen so far fall into this category.

4.3.1 Sophisticated Voting and Agenda Control Suppose there are three players, I = {1, 2, 3}, who must choose one from three alternatives

X = {x, y, z}. Their preferences are as follows:

–  –  –

They must make their choice through majority rule voting in a two-stage process. They first vote on two of the alternatives and the winner is then pitted against the remaining alternative in the second round. Players cast their votes simultaneously in each of the two rounds. Suppose player 2 controls the agenda—that is, she can decide which two alternatives are to be voted on in the first round. What is her choice?

We need to find the SPE. Clearly, player 2 will set an agenda that ensures that y is the winner if that’s possible. We have to consider the three possible situations, depending on which two alternatives are selected in the first round. To find the subgame-perfect equilibrium, we have to ensure that the strategies are optimal in all subgames. There are three generic subgames that begin with the second round: depending on the winning alternative in the first round, the second round can involve a vote on (x, y), or (x, z), or (y, z). So let’s analyze each of these subgames.

Note first that because there are only two alternatives and three players, it follows that in any PSNE, at least two players must vote for the same alternative. Observe now that casting a sincere vote—that is, voting for the preferred alternative—is weakly dominant for each player. If the other two players vote for different alternatives, then the third player’s vote is decisive, and it is strictly better to cast it sincerely. If, on the other hand, the two other players vote for the same alternative, then the third player’s vote cannot change the outcome.

Therefore, there are two possible PSNE in these subgames: either all players vote sincerely or they all vote for the same alternative. Technically, this means that when x is pitted against y, it is possible to get y to win: the strategy profile in which all players vote for y is a Nash equilibrium. However, this PSNE requires two of the players to vote against their preferred alternative and expect that they do so, which seems highly implausible. In this instance, I would rule out the PSNE involving weakly dominated strategies. Using only weakly dominant

strategies then yields a unique PSNE with sincere voting for each of the subgames, as follows:

–  –  –

In other words, we know that in SPE the second round will involve sincere voting and produce a winner accordingly.

Going back to our original question, how is player 2 to set the agenda? Clearly, if y is ever to emerge as the winner given that the 2nd round will involve sincere voting, it will have to be pitted there against z because against x it will lose. Since z defeats x in sincere voting, then perhaps choosing (x, z) as the first round agenda would work?

The answer is that it will not. Suppose player 2 set the agenda with (x, z) in the first round and everyone voted sincerely. Then the winner would be z, and in the second round the winner would be y. But players can anticipate this outcome. In particular, player 3 knows that the winner of the first comparison would go on to compete with y and if y prevails in the 2nd round, he will get his worst possible alternative. Since y will beat z with sincere voting, this means that he really does not want z to win in the first round. Of votes are cast sincerely in the first round, then player 1 is voting for x while players 2 and 3 are voting for z. However, if player 3 deviated and cast a sophisticated vote for x instead, then x will win the first round, and in the second round the sincere vote on (x, y) would leave x as the winner. Although the sophisticated vote does not enable player 3 to get his most preferred alternative, it does enable him to avoid the worst possible one.10 This now means that whatever player 2 chooses, her agenda has to be invulnerable to sophisticated voting. Well, as they say, if you can’t beat them, join them: player 2 will exploit the sophistication of the players by setting the agenda for the first round to (x, y). Observe that with sincere voting, x would defeat y. However, this would pit x against z in the 2nd round, in which case z will prevail. Player 1 can foresee this and since z is his worst possible alternative, he will cast a sophisticated vote for y against her preference for x over y. Doing so would ensure that y will go on to the 2nd round and defeat z, which gives him the secondbest outcome. Of course, our devious player 2 can now enjoy her most preferred alternative.

Therefore, the profile (y, xy), (y, z, y), (x, zz) is a subgame-perfect equilibrium when (x, y) is the pair in the first round. The strategies are specified as a triple over the (x, y) choice in the first round, and then the (x, z) and (y, z) possible subgames in the second round. In this SPE player 1 is casting a sophisticated vote (note that player 2’s manipulation pays off even though she votes sincerely). Alternative y defeats x, and then goes on to defeat z in a sincere vote in the 2nd round. Since this SPE yields player 2 her most preferred alternative, the overall SPE of the game involves her setting the agenda such that (x, y) are the two competing alternatives in the first round.

We know from McKelvey’s Chaos Theorem that if players vote sincerely using majority rule to select winners in pairwise comparisons, then any outcome is possible provided no equilibrium position exists. (That is, for any two alternatives, one can always find an agenda that guarantees that one beats the other.) With sophisticated voting, this chaos is a bit reduced: for any two alternatives, there will be an agenda that guarantees that one defeats Of course, there are also the PSNE in which two players vote sincerely and the third, whose vote is irrelevant, also votes for the same alternative. For instance, in (x, y), there is PSNE in which all players vote for x. Since player 3’s choice cannot affect the outcome, he might as well vote insincerely.

Here, as before, there are equilibria in which all three players vote for the same alternative and two of them vote against their preferences. For instance, in (x, z) this would require them all to vote for x. Coupling this with any PSNE in the 2nd round will yield an SPE, but the solution is implausible for the same reasons we discussed already.

Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |   ...   | 9 |

Similar works:

«REGULATORY ISLANDS HANNAH J. WISEMAN* Policy experimentation in the “laboratory of the states” is a frequently cited benefit of our federalist system, but a necessary condition of thoughtful experimentation is often missing. To conduct useful policy experiments, states and other subfederal actors need baseline information: In order to learn from the successes and failures of their neighbors, state actors must understand the laws and regulations that other jurisdictions have enacted. And,...»

«High school rigor and good advice: Setting up students to succeed Kasey Klepfer, Archer Graduate Fellow at the University of Texas at Austin Jim Hull, Senior Policy Analyst Center for Public Education National School Boards Association October 2012 High school rigor and good advice: Setting up students to succeed We know that around two-thirds of the future jobs in the United States will require some sort of postsecondary education. Job reports show that by 2018, there will be 47 million jobs...»

«Forum on Public Policy The Forgiveness Factor In The Lives Of Two Literary Grandmothers Geraldine Paulk DeFelix, Professor of English, Reading, and Humanities, Chipola College and Professor of English, The Baptist College of Florida Abstract The Christian principle of forgiveness plays a pivotal role in the lives of various literary characters. Having, or not having, the ability to forgive others affects the happiness and sense of fulfillment in such characters as Katherine Porter‟s title...»

«The Student Handbook Warren Wilson College 2011-2012 About the Student Handbook Warren Wilson College publishes a Student Handbook each year to help students understand how the College is structured and to inform them of what is expected of them as members of the College community. The Student Handbook provides information about the organization of the College and campus policy. This Handbook should be used in tandem with the Warren Wilson College Catalog. Both publications should be read...»

«Thinking Differently: CSOs’ alternative contribution to global processes Jean-Pierre Cassarino There can be no question that regional consultative processes (RCPs) on migration and development have contributed to opening dialogues between countries of destination, of transit and of origin. The need for enhanced communication between the representatives of these countries has been addressed and policy networks among officials have been created. At the same time, however, such global...»

«Frequently Asked Questions Updated: September 2015 For The Office of Management and Budget’s Uniform Administrative Requirements, Cost Principles, and Audit Requirements for Federal Awards At 2 CFR 200 The following are frequently asked questions presented by the COFAR on OMB’s Uniform Guidance at 2 CFR 200. Please note that in case of any discrepancy, the actual guidance at 2 CFR 200 governs. If there is a question pertaining to the application of the guidance to a particular Federal...»

«CR:511E Acoustic Caliibrator User Manual Page 1 User Manual for the CR:511E Acoustic Calibrator This manual, the software to which it relates, the program code and drawings are all: © Copyright Cirrus Research plc 1989-2012 Page 2 CR:511E Acoustic Caliibrator User Manual The content of this manual, any illustrations, technical information and descriptions within this document were correct at the time of going to print. Cirrus Research plc reserves the right to make any changes necessary,...»

«Please cite this paper as: Tothova, M. (2009), The Trade and Trade Policy Implications of Different Policy Responses to Societal Concerns, OECD Food, Agriculture and Fisheries Working Papers, No. 20, OECD Publishing, © OECD. doi:10.1787/221782147025 OECD Food, Agriculture and Fisheries Working Papers No. 20 The Trade and Trade Policy Implications of Different Policy Responses to Societal Concerns Monika Tothova* JEL Classification: Q01, Q10, Q17, Q18, Q19, Q5 * OECD, France THE TRADE AND TRADE...»

«Data and dogma: the great Indian poverty debate Angus Deaton Research Program in Development Studies Princeton University Valerie Kozel World Bank September 2004 This paper contains material from the introduction to a volume of the same name. We are grateful to T. N. Srinivasan for comments and suggestions, as well as to many of the people whose papers are cited in this review. However, the views expressed here are those of the authors alone. ABSTRACT What happened to poverty in India in the...»

«Vol. 10 (2016), pp. 243–252 http://nflrc.hawaii.edu/ldc http://hdl.handle.net/10125/24693 Revised Version Received: 13 Feb 2016 Endangered Language Research and the Moral Depravity of Ethics Protocols George van Driem University of Bern At the 2nd International Conference on Endangered Languages in Kyōto in December 2001, a field linguist from Siberia and I both independently warned an international audience of linguists and policy makers about the perils of ethics protocols for endangered...»

«Reducing the Cost and Headache of e-Discovery with a Comprehensive Retention Plan for Electronically Stored Information By Fernando A. Bohorquez Alberto Rodriguez Table of Contents I.  INTRODUCTION II.  THE BENEFITS OF A ROBUST ESI RETENTION POLICY A.  A Comprehensive ESI Plan Significantly Reduces e-Discovery Litigation Costs B.  A Well-Prepared ESI Retention Plan Can Reduce the Burdens on InHouse Counsel III.  HALLMARKS OF AN EFFECTIVE ESI RETENTION POLICY A.  An ESI Retention Policy...»

«The Magenta Book Magenta Book Background Papers The Magenta Book: guidance notes for policy evaluation and analysis Government Social Research Unit HM Treasury 1 Horse Guards Road London SW1A 2HQ Magenta Book Background Papers Contents Contents Introduction Objectives, format and uses 1 What is policy evaluation? 1.1 The demand for policy evaluation 1.2 What is evaluation? 1.3 What types of evaluation are used in government? 1.4 How does policy evaluation relate to project management? 1.5...»

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