Game Theory: An Introduction - Hardcover

Tadelis, Steven

Hardcover

ISBN 10: 0691129088 ISBN 13: 9780691129082

Publisher: Princeton University Press, 2013

Synopsis

The definitive introduction to game theory

This comprehensive textbook introduces readers to the principal ideas and applications of game theory, in a style that combines rigor with accessibility. Steven Tadelis begins with a concise description of rational decision making, and goes on to discuss strategic and extensive form games with complete information, Bayesian games, and extensive form games with imperfect information. He covers a host of topics, including multistage and repeated games, bargaining theory, auctions, rent-seeking games, mechanism design, signaling games, reputation building, and information transmission games. Unlike other books on game theory, this one begins with the idea of rationality and explores its implications for multiperson decision problems through concepts like dominated strategies and rationalizability. Only then does it present the subject of Nash equilibrium and its derivatives.

Game Theory is the ideal textbook for advanced undergraduate and beginning graduate students. Throughout, concepts and methods are explained using real-world examples backed by precise analytic material. The book features many important applications to economics and political science, as well as numerous exercises that focus on how to formalize informal situations and then analyze them.

• Introduces the core ideas and applications of game theory
• Covers static and dynamic games, with complete and incomplete information
• Features a variety of examples, applications, and exercises
• Topics include repeated games, bargaining, auctions, signaling, reputation, and information transmission
• Ideal for advanced undergraduate and beginning graduate students
• Complete solutions available to teachers and selected solutions available to students

About this title

About the Author

Steven Tadelis is associate professor and Barbara and Gerson Bakar Faculty Fellow at the Haas School of Business at the University of California, Berkeley, and a Distinguished Economist at eBay Research Labs.

From the Back Cover

"Steve Tadelis's Game Theory is an ideal textbook for advanced undergraduates, and great preparation for graduate work. It provides a clear, self-contained, and rigorous treatment of all the key concepts, along with interesting applications; it also introduces key technical tools in a straightforward and intuitive way."--Drew Fudenberg, Harvard University

"Steven Tadelis is a leading scholar in applied game theory, and his expertise shines through in this excellent new text. Aimed at intermediate to advanced undergraduates, it presents and discusses the theory remarkably clearly, at both the intuitive and formal levels. One novel feature I like is its serious consideration of the decision theoretic foundations of game theory. Another is its transparent presentation of relatively recent topics and applications, such as reputations in asymmetric information games, legislative bargaining, and cheap talk communication."--Steve Matthews, University of Pennsylvania

"Steve Tadelis has written an up-to-date, comprehensive, yet reader-friendly introductory textbook to game theory. He explains difficult concepts in an exceptionally clear and simple way, making the book accessible to students with a minimal background in mathematics. The abundance of examples and illustrations, drawing from economics, political science, and business strategy, not only shows the wide range of applications of game theory, but also makes the book attractive and fun to read. Tadelis's book will undoubtedly become a reference textbook for a first course in game theory."--Francis Bloch, école Polytechnique

"These days, game theory plays an essential role not only in economics, but in many other branches of social and engineering science, as well as philosophy, biology, psychology, even law. In all these disciplines, students and instructors alike should welcome this excellent resource for mastering the key tools of modern game theory."--Peter Hammond, University of Warwick

"It's hard to write a game theory textbook that strikes a good balance between precision and accessibility. But Steve Tadelis has accomplished this juggling act, with style and humor besides."--Eric S. Maskin, Nobel Laureate in Economics, Harvard University

"Game theory is a powerful tool for understanding strategic behavior in business, politics, and other settings. Steve Tadelis's text provides an ideal guide, taking you from first principles of decision theory to models of bargaining, auctions, signaling, and reputation building in a style that is both rigorous and reader-friendly."--Jonathan Levin, Stanford University

"Game Theory fills a void in the literature, serving as a text for an advanced undergraduate--or masters-level class. It has more detail than most undergraduate texts, while still being accessible to a broad audience and stopping short of the more technical approach of PhD-level texts. This is a valuable book, written by a meticulous scholar who is an expert in the field."--Matthew O. Jackson, author ofSocial and Economic Networks

"This is a great text, just at the right level for fourth-year undergraduates. The style is just right and the exercises are of high quality. Flow and organization are major strengths of the book--I can follow the text almost as is for the class I teach."--Luca Anderlini, Georgetown University

Excerpt. © Reprinted by permission. All rights reserved.

GAME THEORY

AN INTRODUCTIONBy Steven Tadelis

PRINCETON UNIVERSITY PRESS

Copyright © 2013 Princeton University Press
All right reserved.
ISBN: 978-0-691-12908-2

Contents

Preface............................................................................xiChapter 1 The Single-Person Decision Problem......................................3Chapter 2 Introducing Uncertainty and Time........................................14Chapter 3 Preliminaries...........................................................43Chapter 4 Rationality and Common Knowledge........................................59Chapter 5 Pinning Down Beliefs: Nash Equilibrium..................................79Chapter 6 Mixed Strategies........................................................101Chapter 7 Preliminaries...........................................................129Chapter 8 Credibility and Sequential Rationality..................................151Chapter 9 Multistage Games........................................................175Chapter 10 Repeated Games.........................................................190Chapter 11 Strategic Bargaining...................................................220Chapter 12 Bayesian Games.........................................................241Chapter 13 Auctions and Competitive Bidding.......................................270Chapter 14 Mechanism Design.......................................................288Chapter 15 Sequential Rationality with Incomplete Information.....................303Chapter 16 Signaling Games........................................................318Chapter 17 Building a Reputation..................................................339Chapter 18 Information Transmission and Cheap Talk................................357Chapter 19 Mathematical Appendix..................................................369References.........................................................................385Index..............................................................................389

Chapter One

The Single-Person Decision Problem

Imagine yourself in the morning, all dressed up and ready to have breakfast. You might be lucky enough to live in a nice undergraduate dormitory with access to an impressive cafeteria, in which case you have a large variety of foods from which to choose. Or you might be a less-fortunate graduate student, whose studio cupboard offers the dull options of two half-empty cereal boxes. Either way you face the same problem: what should you have for breakfast?

This trivial yet ubiquitous situation is an example of a decision problem. Decision problems confront us daily, as individuals and as groups (such as firms and other organizations). Examples include a division manager in a firm choosing whether or not to embark on a new research and development project; a congressional representative deciding whether or not to vote for a bill; an undergraduate student deciding on a major; a baseball pitcher contemplating what kind of pitch to deliver; or a lost group of hikers confused about which direction to take. The list is endless.

Some decision problems are trivial, such as choosing your breakfast. For example, if Apple Jacks and Bran Flakes are the only cereals in your cupboard, and if you hate Bran Flakes (they belong to your roommate), then your decision is obvious: eat the Apple Jacks. In contrast, a manager's choice of whether or not to embark on a risky research and development project or a lawmaker's decision on a bill are more complex decision problems.

This chapter develops a language that will be useful in laying out rigorous foundations to support many of the ideas underlying strategic interaction in games. The language will be formal, having the benefit of being able to represent a host of different problems and provide a set of tools that will lend structure to the way in which we think about decision problems. The formalities are a vehicle that will help make ideas precise and clear, yet in no way will they overwhelm our ability and intent to keep the more practical aspect of our problems at the forefront of the analysis.

In developing this formal language, we will be forced to specify a set of assumptions about the behavior of decision makers or players. These assumptions will, at times, seem both acceptable and innocuous. At other times, however, the assumptions will be almost offensive in that they will require a significant leap of faith. Still, as the analysis unfolds, we will see the conclusions that derive from the assumptions that we make, and we will come to appreciate how sensitive the conclusions are to these assumptions.

As with any theoretical framework, the value of our conclusions will be only as good as the sensibility of our assumptions. There is a famous saying in computer science—"garbage in, garbage out"—meaning that if invalid data are entered into a system, the resulting output will also be invalid. Although originally applied to computer software, this statement holds true more generally, being applicable, for example, to decision-making theories like the one developed herein. Hence we will at times challenge our assumptions with facts and question the validity of our analysis. Nevertheless we will argue in favor of the framework developed here as a useful benchmark.

1.1 Actions, Outcomes, and Preferences

Consider the examples described earlier: choosing a breakfast, deciding about a research project, or voting on a bill. These problems all share a similar structure: an individual, or player, faces a situation in which he has to choose one of several alternatives. Each choice will result in some outcome, and the consequences of that outcome will be borne by the player himself (and sometimes other players too).

For the player to approach this problem in an intelligent way, he must be aware of three fundamental features of the problem: What are his possible choices? What is the result of each of those choices? How will each result affect his well-being? Understanding these three aspects of a problem will help the player choose his best action. This simple observation offers us a first working definition that will apply to any decision problem:

The Decision Problem A decision problem consists of three features:

1. Actions are all the alternatives from which the player can choose.

2. Outcomes are the possible consequences that can result from any of the actions.

3. Preferences describe how the player ranks the set of possible outcomes, from most desired to least desired. The preference relation [??] describes the player's preferences, and the notation x [??] y means "x is at least as good as y."

To make things simple, let's begin with our rather trivial decision problem of choosing between Apple Jacks and Bran Flakes. We can define the set of actions as A = {a, b}, where a denotes the choice of Apple Jacks and b denotes the choice of Bran Flakes. In this simple example our actions are practically synonymous with the outcomes, yet to make the distinction clear we will denote the set of outcomes by X = {x, y}, where x denotes eating Apple Jacks (the consequence of choosing Apple Jacks) and y denotes eating Bran Flakes.

1.1.1 Preference Relations

Turning to the less familiar notion of a preference relation, imagine that you prefer eating Apple Jacks to Bran Flakes. Then we will write x [??] y, which should be read as "x is at least as good as y." If instead you prefer Bran Flakes, then we will write y [??] x, which should be read as "y is at least as good as x." Thus our preference relation is just a shorthand way to express the player's ranking of the possible outcomes.

We follow the common tradition in economics and decision theory by expressing preferences as a "weak" ranking. That is, the statement "x is at least as good as y" is consistent with x being better than y or equally as good as y. To distinguish between these two scenarios we will use the strict preference relation, x > y, for "x is strictly better than y," and the indifference relation, x ~ y, for "x and y are equally good."

It need not be the case that actions are synonymous with outcome, as in the case of choosing your breakfast cereal. For example, imagine that you are in a bar with a drunken friend. Your actions can be to let him drive home or to order him a cab. The outcome of letting him drive is a certain accident (he's really drunk), and the outcome of ordering him a cab is arriving safely at home. Hence for this decision problem your actions are physically different from the outcomes.

In these examples the action set is finite, but in some cases one might have infinitely many actions from which to choose. Furthermore there may be infinitely many outcomes that can result from the actions chosen. A simple example can be illustrated by me offering you a two-gallon bottle of water to quench your thirst. You can choose how much to drink and return the remainder to me. In this case your action set can be described as the interval A = [0, 2]: you can choose any action a as long as it belongs to the interval [0, 2], which we can write in two ways: 0 ≤ a ≤ 2 or a [member of] [0, 2]. If we equate outcomes with actions in this example then X = [0, 2] as well. Finally it need not be the case that more is better. If you are thirsty then drinking a pint may be better than drinking nothing. However, drinking a gallon may cause you to have a stomachache, and you may therefore prefer a pint to a gallon.

Before proceeding with a useful way to represent a player's preferences over various outcomes, it is important to stress that we will make two important assumptions about the player's ability to think through the decision problem. First, we require the player to be able to rank any two outcomes from the set of outcomes. To put this more formally:

The Completeness Axiom The preference relation [??] is complete: any two outcomes x, y [member of] X can be ranked by the preference relation, so that either x [??] y or y [??] x.

At some level the completeness axiom is quite innocuous. If I show you two foods, you should be able to rank them according to how much you like them (including being indifferent if they are equally tasty and nutritious). If I offer you two cars, you should be able to rank them according to how much you enjoy driving them, their safety specifications, and so forth. If I offer you two investment portfolios, you should be able to rank them according to the extent to which you are willing to balance risk and return. In other words, the completeness axiom does not let you be indecisive between any two outcomes.

The second assumption we make guarantees that a player can rank all of the outcomes. To do this we introduce a rather mild consistency condition called transitivity:

The Transitivity Axiom The preference relation [??] is transitive: for any three outcomes x, y, z [member of] X, if x [??] y and y [??] z then x [??] z.

Faced with several outcomes, completeness guarantees that any two can be ranked, and transitivity guarantees that there will be no contradictions in the ranking, which could create an indecisive cycle. To observe a violation of the transitivity axiom, consider a player who strictly prefers Apple Jacks to Bran Flakes, a > b, Bran Flakes to Cheerios, b > c, and Cheerios to Apple Jacks, c > a. When faced with any two boxes of cereal, say A = {a, b}, he has no problem choosing his preferred cereal a. What happens, however, when he is presented with all three alternatives, A = {a, b, c}? The poor guy will be unable to decide which of the three to choose, because for any given box of cereal, there is another box that he prefers. Therefore, by requiring that the player have complete and transitive preferences, we basically guarantee that among any set of outcomes, he will always have at least one best outcome that is as good as or better than any other outcome in that set.

To foreshadow what will be our premise for decision making, a preference relation that is complete and transitive is called a rational preference relation. We will be concerned only with players who have such rational preferences, for without such preferences we can offer neither predictive nor prescriptive insights.

Remark As noted by the Marquis de Condorcet in 1785, it is possible to have a group of rational individual players who, when put together to make decisions as a group, will become an "irrational" group. For example, imagine three roommates, called players 1, 2, and 3, who have to choose one box of cereal for their apartment kitchen. Player 1's preferences are given by a >₁ c >₁ b, player 2's are given by c >₂ b >₂ a, and player 3's are given by b >₃ a >₃ c. Imagine that our three players make choices in a democratic way and use majority voting to reach a decision. What will be the resulting preferences of the group, >_G? When faced with the pair a and c, players 1 and 3 will vote for Apple Jacks, hence a >_G c. When faced with the pair c and b, players 1 and 2 will vote for Cheerios, hence c >_G b. When faced with the pair a and b, players 2 and 3 will vote for Bran Flakes, hence b >_G a. As a result, our three rational players will not be able to reach a conclusive decision using the group preferences that result from majority voting! This type of group indecisiveness resulting from majority voting is often referred to as the Condorcet Paradox. Because we will not be analyzing group decisions, it is not something we will confront, but it is useful to be mindful of such phenomena, in which imposing individual rationality does not imply "group rationality."

1.1.2 Payoff Functions

When we restrict attention to players with rational preferences, not only do we get players who behave in a consistent and appealing way, but as an added bonus we can replace the preference relation with a much friendlier, and more operational, apparatus. Consider the following simple example. Imagine that you open a lemonade stand on your neighborhood corner. You have three possible actions: choose lowquality lemons (l), which imply a cost of $10 and a revenue from sales of $15; choose medium-quality lemons (m), which imply a cost of $15 and a revenue from sales of $25; or choose high-quality lemons (h), which imply a cost of $28 and a revenue from sales of $35. Thus the action set is A = {l, m, h}, and the outcome set is given by net profits and is X = {5, 10, 7}, where the action l yields a profit of $5, the action m yields a profit of $10, and the action h yields a profit of $7. Assuming that obtaining higher profits is strictly better, we have 10 > 7 > 5. Hence you should choose alternative m and make a profit of $10.

Notice that we took a rather obvious profit-maximizing problem and fit it into our framework for a decision problem. We derived the preference relation that is consistent with maximizing profit, the objective of any for-profit business. Arguably it would be more natural and probably easier to comprehend the problem if we looked at the actions and their associated profits. In particular we can define the profit function in the obvious way: every action a [member of] A yields a profit π(a). Then, instead of considering a preference relation over profit outcomes, we can just look at the profit from each action directly and choose an action that maximizes profits. In other words, we can use the profit function to evaluate actions and outcomes.

As this simple example demonstrates, a profit function is a more direct way for a player to rank his actions. The question then is, can we find similar ways to approach decision problems that are not about profits? It turns out that we can do exactly that if we have players with rational preferences, and to do that we define a payoff function.

Definition 1.1 A payoff function u : X -> R represents the preference relation [??] if for any pair x, y [member of] X, u(x) ≥ u(y) if and only if x [??] y.

To put the definition into words, we say that the preference relation [??] is represented by the payoff function u : X -> R that assigns to each outcome in X a real number, if and only if the function assigns a higher value to higher-ranked outcomes.

It is important to notice that representing preferences with payoff functions is convenient, but that payoff values by themselves have no meaning whatsoever. Payoff is an ordinal construct: it is used to order the alternatives from most to least desirable. For example, if I like Apple Jacks more than Bran Flakes, then I can construct the payoff function u(·) so that u(a) = 5 and u(b) = 3. I can also use a different payoff function [??](·) that represents the same preferences as follows: [??](a) = 100 and [??](b)=-237. Just as Fahrenheit and Celsius are two different ways to describe hotter and colder temperatures, there are many ways to represent preferences with payoff functions.

Using payoff functions instead of preferences will allow us to operationalize a theory of how decision makers with rational preferences ought to behave, and how they often will behave. They will choose actions that maximize a payoff function that represents their preferences. One last question we need to ask is whether we know for sure that this method will work: is it true that players will surely have a payoff function representing their preferences? One case is easy and worth going through briefly. In what follows, we provide a formal proposition and a formal, yet fairly easy to follow, proof.

Proposition 1.1 If the set of outcomes X is finite then any rational preference relation over X can be represented by a payoff function.

(Continues...)

Excerpted from GAME THEORYby Steven Tadelis Copyright © 2013 by Princeton University Press. Excerpted by permission of PRINCETON UNIVERSITY PRESS. All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.

Edition details

• Publisher: Princeton University Press
• Publication date: 2013
• Language: English
• ISBN 10: 0691129088
• ISBN 13: 9780691129082
• Binding: Hardcover
• Edition number: 1
• Number of pages: 416