Muutke küpsiste eelistusi

Course in Networks and Markets: Game-theoretic Models and Reasoning [Kõva köide]

(Cornell University)
  • Formaat: Hardback, 264 pages, kõrgus x laius x paksus: 229x203x22 mm, 40 color illus., 3 b&w illus.; 43 Illustrations
  • Sari: The MIT Press
  • Ilmumisaeg: 16-Apr-2019
  • Kirjastus: MIT Press
  • ISBN-10: 0262039788
  • ISBN-13: 9780262039789
Teised raamatud teemal:
  • Formaat: Hardback, 264 pages, kõrgus x laius x paksus: 229x203x22 mm, 40 color illus., 3 b&w illus.; 43 Illustrations
  • Sari: The MIT Press
  • Ilmumisaeg: 16-Apr-2019
  • Kirjastus: MIT Press
  • ISBN-10: 0262039788
  • ISBN-13: 9780262039789
Teised raamatud teemal:
A graduate-level, mathematically rigorous introduction to strategic behavior in a networked world.

A graduate-level, mathematically rigorous introduction to strategic behavior in a networked world.

This introductory graduate-level text uses tools from game theory and graph theory to examine the role of network structures and network effects in economic and information markets. The goal is for students to develop an intuitive and mathematically rigorous understanding of how strategic agents interact in a connected world. The text synthesizes some of the central results in the field while also simplifying their treatment to make them more accessible to nonexperts. Thus, students at the introductory level will gain an understanding of key ideas in the field that are usually only taught at the advanced graduate level.

The book introduces basic concepts from game theory and graph theory as well as some fundamental algorithms for exploring graphs. These tools are then applied to analyze strategic interactions over social networks, to explore different types of markets and mechanisms for networks, and to study the role of beliefs and higher-level beliefs (beliefs about beliefs). Specific topics discussed include coordination and contagion on social networks, traffic networks, matchings and matching markets, exchange networks, auctions, voting, web search, models of belief and knowledge, and how beliefs affect auctions and markets. An appendix offers a “Primer on Probability.” Mathematically rigorous, the text assumes a level of mathematical maturity (comfort with definitions and proofs) in the reader.

Introduction xi
I Games and Graphs
1(50)
1 Game Theory
3(14)
1.1 The Prisoner's Dilemma Game
3(1)
1.2 Normal-form Games
4(2)
1.3 Dominant Strategies
6(1)
1.4 Iterated Strict Dominance (ISD)
7(2)
1.5 Nash Equilibria and Best-Response Dynamics
9(4)
1.6 A Cautionary Game: The Traveler's Dilemma
13(1)
1.7 Mixed-strategy Nash Equilibrium
14(3)
2 Graphs
17(8)
2.1 Basic Definitions
18(1)
2.2 Connectivity and Reachability
19(1)
2.3 Breadth-first Search and Shortest Paths
20(5)
3 Analyzing Best-Response Dynamics
25(8)
3.1 A Graph Representation of Games
25(1)
3.2 Characterizing Convergence of BRD
26(3)
3.3 Better-response Dynamics
29(2)
3.4 Games without PNE
31(2)
4 Coordination in Social Networks
33(12)
4.1 Plain Networked Coordination Games
33(2)
4.2 Convergence of BRD
35(2)
4.3 Incorporating Intrinsic Values
37(3)
4.4 The Price of Stability
40(2)
4.5 Incorporating Strength of Friendship
42(3)
5 Contagion in Social Networks
45(6)
5.1 Cascades
45(1)
5.2 Characterizing Cascades
46(2)
5.3 Strong Cascades
48(1)
5.4 Dealing with Subjective Thresholds
49(2)
II Markets on Networks
51(46)
6 More on Graphs: Flows and Matchings
53(12)
6.1 The Max-Flow Problem
53(3)
6.2 The Max-Flow Min-Cut Duality
56(2)
6.3 Bipartite Graphs and Maximum Matchings
58(2)
6.4 Perfect Matchings and Constricted Sets
60(5)
7 Traffic Network Games
65(8)
7.1 Definition of a Traffic Network Game
65(1)
7.2 Braess's Paradox
66(2)
7.3 Convergence of BRD
68(1)
7.4 Price of Stability
69(4)
8 Matching Markets
73(12)
8.1 Definition of a Matching Market
74(1)
8.2 Acceptability and Preferred Choices
75(1)
8.3 Social Optimality of Market Equilibria
76(3)
8.4 Existence of Market Equilibria
79(2)
8.5 Emergence of Market Equilibria
81(1)
8.6 Bundles of Identical Goods
82(3)
9 Exchange Networks
85(12)
9.1 Definition of an Exchange Network
85(1)
9.2 Stable Outcomes
86(3)
9.3 Existence of Stable Outcomes
89(1)
9.4 Applications of Stability
90(2)
9.5 Balanced Outcomes
92(5)
III Mechanisms for Networks
97(78)
10 Mechanism Design and Auctions
99(20)
10.1 The Mechanism Design Model
100(2)
10.2 Goals of Mechanism Design
102(4)
10.3 The VCG Mechanism
106(3)
10.4 VCG and Matching Markets
109(3)
10.5 Generalized Second-price (GSP) Auctions
112(2)
10.6 Applications to Sponsored Search
114(5)
11 Voting: Basic Notions
119(6)
11.1 Social-choice Contexts
119(1)
11.2 Voting Rules and Strategy-proofness
120(1)
11.3 Condorcet Voting
121(1)
11.4 The Problem with Nonbinary Elections
122(3)
12 Voting: Barriers and Ways around Them
125(14)
12.1 The Gibbard Satterthwaite Theorem
125(1)
12.2 Proof of the Gibbard-Satterthwaite Theorem [ Advanced]
126(6)
12.3 Single-peaked Preferences and the Median Voter Theorem
132(3)
12.4 Voting with Payments
135(2)
12.5 Summarizing the Voting Landscape
137(2)
13 One-sided Matchings: House Allocation Problems
139(8)
13.1 (One-sided) Matching Contexts
139(1)
13.2 Strategy-proof Matching Rules: Serial Dictatorship
140(2)
13.3 Uniqueness of Serial Dictatorship [ Advanced]
142(1)
13.4 Proof of the Uniqueness Theorem [ Advanced]
143(4)
14 Two-sided Matchings: Stable Marriages
147(14)
14.1 Two-sided Matching Problems
147(1)
14.2 The Stable Marriage Theorem
148(3)
14.3 Optimality of Stable Outcomes
151(2)
14.4 Strategy-proofness of Two-sided Matching Rules
153(4)
14.5 Strategy-proofness vs. Stability
157(4)
15 Web Search
161(14)
15.1 Weighted Voting and PageRank
162(4)
15.2 Scaled PageRank
166(5)
15.3 Impossibility of Non-manipulable Web Search
171(4)
IV The Role of Beliefs
175(44)
16 The Wisdom and Foolishness of Crowds
177(8)
16.1 The Wisdom of Crowds
177(4)
16.2 The Foolishness of Crowds: Herding
181(4)
17 Knowledge and Common Knowledge
185(16)
17.1 The Muddy Children Puzzle
185(1)
17.2 Kripke's "Possible Worlds" Model
186(5)
17.3 Common Knowledge
191(2)
17.4 Can We Agree to Disagree? [ Advanced]
193(2)
17.5 The "No-Trade" Theorem [ Advanced]
195(2)
17.6 Justified True Belief and the Gettier Problems
197(4)
18 Common Knowledge of Rationality
201(10)
18.1 Knowledge and Games
201(2)
18.2 An Epistemic Characterization of ISD
203(2)
18.3 An Epistemic Characterization of PNE
205(1)
18.4 Knowledge vs. Belief: Explaining Bubbles in the Market
206(5)
19 Markets with Network Effects
211(8)
19.1 Simple Networked Markets
211(4)
19.2 Markets with Asymmetric Information
215(4)
V Appendix
219(2)
A A Primer on Probability 221(14)
A.1 Probability Spaces
221(2)
A.2 Conditional Probability
223(1)
A.3 Bayes' Rule
224(4)
A.4 Random Variables
228(1)
A.5 Expectation
229(6)
Bibliography 235(8)
Index 243