UID:
edoccha_9961574143902883
Format:
1 online resource (779 pages)
Edition:
Second edition.
ISBN:
9783031600999
Series Statement:
Classroom Companion
Note:
Intro -- Foreword -- Foreword by Michael Wooldridge for the Second Edition -- Foreword by Matthew O. Jackson and Yoav Shoham for the First Edition -- Preface -- Contents -- List of Figures -- List of Tables -- Chapter 1 Playing, Voting, and Dividing -- 1.1 Playing -- 1.1.1 Noncooperative Game Theory -- 1.1.2 Cooperative Game Theory -- 1.2 Voting -- 1.2.1 Preference Aggregation by Voting -- 1.2.2 Manipulative Actions in Single-Peaked Societies -- 1.2.3 Multiwinner Voting -- 1.2.4 Judgment Aggregation -- 1.3 Dividing -- 1.3.1 Cake-cutting: Fair Division of Divisible Goods -- 1.3.2 Fair Division of Indivisible Goods -- 1.3.3 A Brief Digression to Single-Item Auctions -- 1.3.3.1 Classification -- 1.3.3.2 English Auction -- 1.3.3.3 Dutch Auction -- 1.3.3.4 Vickrey Auction -- 1.3.3.5 American Auction -- 1.3.3.6 Expected Revenue -- 1.4 Some Literature Pointers -- 1.5 A Brief Digression to Computational Complexity -- 1.5.1 Some Foundations of Complexity Theory -- 1.5.1.1 Turing Machines and Complexity Measures -- 1.5.1.2 The Complexity Classes P and NP -- 1.5.1.3 Upper and Lower Bounds -- 1.5.2 The Satisfiability Problem of Propositional Logic -- 1.5.2.1 Definitions -- 1.5.2.2 Upper Bounds for SAT -- 1.5.2.3 How to Prove Lower Bounds: Reducibility and Hardness -- 1.5.2.4 Some Background on Approximation Theory -- 1.5.3 A Brief Compendium of Complexity Classes -- 1.5.3.1 Polynomial Space -- 1.5.3.2 The Polynomial Hierarchy -- 1.5.3.3 DP: The Second Level of the Boolean Hierarchy over NP -- 1.5.3.4 Probabilistic Polynomial Time -- 1.5.3.5 And Now, Finally, . . . -- Part I Playing Successfully -- Chapter 2 Noncooperative Game Theory -- 2.1 Foundations -- 2.1.1 Normal Form, Dominant Strategies, and Equilibria -- 2.1.1.1 The Prisoners' Dilemma -- 2.1.1.2 Noncooperative Games in Normal Form -- Definition 2.1 (normal form). -- 2.1.1.3 Dominant Strategies.
,
Definition 2.2 (dominant strategy). -- Definition 2.3 (Pareto dominance and Pareto optimality). -- 2.1.1.4 Nash Equilibria in Pure Strategies -- Definition 2.4 (Nash equilibrium in pure strategies). -- 2.1.1.5 Relations between Solution Concepts -- 2.1.2 Further Two-Player Games -- 2.1.2.1 The Battle of the Sexes -- 2.1.2.2 The Chicken Game -- 2.1.2.3 The Penalty Game -- 2.1.2.4 The Paper-Rock-Scissors Game -- 2.1.2.5 The Guessing Numbers Game -- 2.2 Nash Equilibria in Mixed Strategies -- 2.2.1 Definition and Application to Two-Player Games -- 2.2.1.1 Definition of Nash Equilibria in Mixed Strategies -- 2.2.1.2 The Penalty Game -- 2.2.1.3 The Paper-Rock-Scissors Game -- 2.2.1.4 The Battle of the Sexes -- 2.2.1.5 The Chicken Game -- 2.2.1.6 The Prisoners' Dilemma -- 2.2.1.7 Overview of Some Properties of Some Two-Player Games -- 2.2.2 Existence of Nash Equilibria in Mixed Strategies -- 2.2.2.1 Definition of Some Notions from Mathematical Topology -- 2.2.2.2 Sperner's Lemma and Brouwer's Fixed Point Theorem Lemma 2.1 (Sperner's lemma). -- 2.2.2.3 Nash's Theorem Theorem 2.3 (Nash [729, 730]). -- 2.3 Checkmate: Trees for Games with Perfect Information -- 2.3.1 Sequential Two-Player Games -- 2.3.1.1 Game Trees -- 2.3.1.2 Tic-Tac-Toe -- 2.3.1.3 Nim -- 2.3.1.4 Geography and the Hardness of Finding Winning Strategies -- 2.3.2 Equilibria in Game Trees -- 2.3.2.1 Edgar's Sequential Campaign Game -- 2.3.2.2 Nash Equilibria in Edgar's Sequential Campaign Game -- 2.3.2.3 Subgame-Perfect Equilibria -- 2.4 Full House: Games with Incomplete Information -- 2.4.1 The Monty Hal l Problem -- 2.4.1.1 Intuitive Solutions to the Monty Hall Problem -- 2.4.1.2 Solution of the Monty Hall Problem Using the Law of Total Probability -- 2.4.2 Analysis of a Simple Poker Variant -- 2.4.2.1 Von Neumann's Simplified Poker Variant.
,
2.4.2.2 Analyzing a Simplified Variant of von Neumann's Poker -- 2.5 How Hard Is It to Find a Nash Equilibrium? -- 2.5.1 Nash Equilibria in Zero-Sum Games -- 2.5.2 Nash Equilibria in General Normal Form Games -- 2.5.2.1 Issues to Deal with -- 2.5.2.2 Four Types of Nonconstructive Proof Steps -- 2.5.2.3 The Polynomial Pigeonhole Principle -- 2.5.2.4 Polynomial Local Search -- 2.5.2.5 The Polynomial Parity Argument for Graphs -- 2.5.2.6 The Polynomial Parity Argument for Directed Graphs -- 2.5.2.7 Relations Among These Complexity Classes -- 2.5.2.8 Complexity of Computing Mixed Nash Equilibria -- Chapter 3 Cooperative Game Theory -- 3.1 Foundations -- 3.1.1 Cooperative Games with Transferable Utility -- 3.1.1.1 Coalition Structures, Characteristic Functions, and Payoff Vectors -- 3.1.1.2 Superadditivity -- 3.1.2 Special Subclasses of Cooperative Games -- 3.1.2.1 Convex Games -- 3.1.2.2 Simple Games -- 3.2 Stability in Cooperative Games -- 3.2.1 Imputations -- 3.2.2 The Core of a Cooperative Game -- 3.2.2.1 The Core of a Convex Game -- Theorem 3.1 (Shapley [858]). -- Proof. -- 3.2.2.2 The Core of a Simple Game -- Theorem 3.2. -- Proof. -- 3.2.3 Further Stability Concepts in Cooperative Games -- 3.2.3.1 The -- Core and the Least Core of a Cooperative Game -- 3.2.3.2 The Cost of Stability -- 3.2.3.3 Stable Sets in a Cooperative Game -- 3.3 Fairness in Cooperative Games -- 3.3.1 The Shapley-Shubik Index and the Shapley Value -- 3.3.1.1 Definitions and an Example: Simple Games -- 3.3.1.2 Beyond Simple Games: The Shapley Value -- 3.3.1.3 Properties and Axiomatic Characterization -- 3.3.1.4 Shapley Value versus Core -- 3.3.2 The Banzhaf Indices -- 3.4 Counting and Representing Cooperative Games -- 3.4.1 A Universal Representation for Simple Games -- 3.4.2 Cooperative Games on Graphs -- 3.4.2.1 Induced Subgraph Games -- 3.4.2.2 Network Flow Games.
,
3.4.2.3 Path Disruption Games -- 3.5 Computational Complexity of Identifying Good Outcomes -- 3.5.1 An Oracle-Based Approach: Core-Stable Outcomes in Convex and Simple Games -- 3.5.2 Complexity of Problems for Weighted Voting Games -- 3.5.2.1 Complexity of Stability-Related Solution Concepts for Weighted Voting Games -- 3.5.2.2 Complexity of Power Indices in Weighted Voting Games -- Computing and Comparing Power Indices -- Beneficial Merging and Beneficial Splitting of Players -- Control by Deleting or Adding Players -- Manipulating the Quota -- Unary Weights and Approximation -- Graph-Restricted Weighted Voting Games -- 3.5.3 Complexity of Problems for Induced Subgraph Games -- 3.6 Hedonic Games -- 3.6.1 Stability in Hedonic Games -- 3.6.2 Representation Formalisms -- 3.6.2.1 Anonymous Hedonic Games -- 3.6.2.2 Additively Separable Hedonic Games -- 3.6.2.3 Further Classes of Hedonic games -- 3.6.3 Complexity of Stability in Hedonic Games -- 3.6.3.1 Existence and Verification for Stability in Hedonic Games -- 3.6.3.2 Anonymous Hedonic Games -- 3.6.3.3 Additively Separable Hedonic Games -- Stability Concepts Based on Single-Player Deviations -- Core Stability, Strict Core Stability, Perfectness, and Wonderful Stability -- 3.6.4 Dynamics in Hedonic Games -- 3.6.5 Other Important Concepts for Hedonic Games -- 3.6.5.1 Altruistic Hedonic Games -- 3.6.5.2 Solution Concepts Beyond Stability -- 3.6.5.3 Quantifying Social Welfare Loss -- 3.6.5.4 Online Hedonic Games -- Part II Voting and Judging -- Chapter 4 Preference Aggregation by Voting -- 4.1 Some Basic Voting Systems -- 4.1.1 Scoring Protocols -- 4.1.1.1 Plurality Voting -- 4.1.1.2 Veto (Antiplurality) -- 4.1.1.3 k-Approval and k-Veto -- 4.1.1.4 Borda Count -- 4.1.2 Voting Systems Based on Pairwise Comparisons -- 4.1.2.1 Condorcet Voting -- 4.1.2.2 The Family of Llull and Copeland Voting Systems.
,
4.1.2.3 Dodgson Voting -- 4.1.2.4 Simpson Voting (Maximin) -- 4.1.2.5 Young Voting -- 4.1.2.6 Kemeny Voting -- 4.1.2.7 Ranked Pairs, Schwartz Voting, Schulze's Rule, etc. -- 4.1.3 Approval Voting and Range Voting -- 4.1.3.1 Approval Voting -- 4.1.3.2 Range Voting and Normalized Range Voting -- 4.1.4 Voting Systems Proceeding in Stages -- 4.1.4.1 Plurality with Run-Off and Veto with Run-Off -- 4.1.4.2 Single Transferable Vote (STV) -- 4.1.4.3 The Cup Protocol -- 4.1.4.4 Bucklin Voting -- 4.1.4.5 Nanson and Baldwin Voting -- 4.1.5 Hybrid Voting Systems -- 4.1.5.1 Black Voting -- 4.1.5.2 Fallback Voting -- 4.1.5.3 Sincere-Strategy Preference-Based Approval Voting -- 4.1.6 Overview of Some Fundamental Voting Systems -- 4.2 Properties of Voting Systems and Impossibility Theorems -- 4.2.1 The Condorcet and the Majority Criterion -- 4.2.1.1 The Condorcet Criterion -- 4.2.1.2 The Majority Criterion -- 4.2.2 Nondictatorship, Pareto Consistency, and Consistency -- 4.2.2.1 Nondictatorship -- 4.2.2.2 Pareto Consistency -- 4.2.2.3 Consistency -- 4.2.3 Independence of Irrelevant Alternatives -- 4.2.4 Resoluteness and Citizens' Sovereignty -- 4.2.4.1 Resoluteness -- 4.2.4.2 Citizens' Sovereignty -- 4.2.5 Strategy-Proofness and Independence of Clones -- 4.2.5.1 Strategy-Proofness -- 4.2.5.2 Independence of Clones -- 4.2.6 Anonymity, Neutrality, and Monotonicity -- 4.2.6.1 Anonymity -- 4.2.6.2 Neutrality -- 4.2.6.3 Monotonicity -- 4.2.7 Homogeneity, Participation, and Twins Welcome -- 4.2.7.1 Homogeneity -- 4.2.7.2 Participation Criterion -- 4.2.7.3 Twins-Welcome Criterion -- 4.2.8 Overview of Properties of Voting Systems -- 4.3 Complexity of Voting Problems -- 4.3.1 Winner Determination -- 4.3.1.1 Unique versus Nonunique Winners -- 4.3.1.2 Scoring Protocols, Copeland, and Other Voting Systems -- 4.3.1.3 Dodgson, Young, and Kemeny Voting.
,
4.3.2 Possible and Necessary Winners.
Additional Edition:
ISBN 9783031600982
Language:
English
Bookmarklink
