Chapter
3.3 Equilibria via Labeled Polytopes
3.4 The Lemke--Howson Algorithm
3.7 Extensive Games and Their Strategic Form
3.8 Subgame Perfect Equilibria
3.9 Reduced Strategic Form
3.11 Computing Equilibria with the Sequence Form
3.13 Discussion and Open Problems
Chapter 4 Learning, Regret Minimization, and Equilibria
4.2 Model and Preliminaries
4.3 External Regret Minimization
4.3.1 Warmup: Greedy and Randomized-Greedy Algorithms
4.3.2 Randomized Weighted Majority Algorithm
4.3.3 Polynomial Weights Algorithm
4.4 Regret Minimization and Game Theory
4.4.1 Game Theoretic Model
4.4.2 Constant Sum Games and External Regret Minimization
4.4.3 Correlated Equilibrium and Swap Regret Minimization
4.4.4 Dominated Strategies
4.5 Generic Reduction from External to Swap Regret
4.6 The Partial Information Model
4.7 On Convergence of Regret-Minimizing Strategies to Nash
Equilibrium in Routing Games
4.7.1 Current Research Directions
Chapter 5 Combinatorial Algorithms for Market Equilibria
5.2 Fisher's Linear Case and the Eisenberg--Gale Convex Program
5.3 Checking If Given Prices Are Equilibrium Prices
5.4 Two Crucial Ingredients of the Algorithm
5.5 The Primal-Dual Schema in the Enhanced Setting
5.6 Tight Sets and the Invariant
5.7.1 Finding a Balanced Flow
5.10 Running Time of the Algorithm
5.11 The Linear Case of the Arrow--Debreu Model
5.12 An Auction-Based Algorithm
5.13 Resource Allocation Markets
5.14 Algorithm for Single-Source Multiple-Sink Markets
5.14.1 Finding the Next Cut
5.15 Discussion and Open Problems
Chapter 6 Computation of Market Equilibria by Convex Programming
6.1.1 Definitions: Models and Equilibrium
6.1.2 The Tâtonnement Process
6.1.3 Approximate Equilibria
6.1.4 Gross Substitutability
6.1.5 Special Forms of the Utility Functions
6.1.6 Equilibrium vs Optimization
6.2 Fisher Model with Homogeneous Consumers
6.3 Exchange Economies Satisfying WGS
6.3.1 Computational Results
Two Useful Transformations
The Discrete Tâtonnement Process
6.4 Specific Utility Functions
6.4.1 Convex Programs for Linear Exchange Economies
6.4.2 Convex Programs for CES Exchange Economies
6.5.1 Multiple Disconnected Equilibria
6.5.2 Hardness for the Class PPAD
6.6 Models with Production
6.6.1 Inequalities Characterizing Equilibrium
6.6.2 Convex Programs for Specific Functions
Chapter 7 Graphical Games
7.3 Computing Nash Equilibria in Tree Graphical Games
7.3.1 An Approximation Algorithm
7.3.3 Extensions: NashProp and Beyond
7.4 Graphical Games and Correlated Equilibria
7.4.1 Expected Payoff and Local Neighborhood Equivalence
7.4.2 Correlated Equilibria and Markov Nets
7.4.3 Algorithms for Correlated Equilibria in Graphical Games
7.5 Graphical Exchange Economies
7.6 Open Problems and Future Research
Chapter 8 cryptography and game theory
8.1 Cryptographic Notions and Settings
8.1.1 Security of Multiparty Computations
8.1.2 Existing Results for Multiparty Computation
8.2 Game Theory Notions and Settings
8.3 Contrasting MPC and Games
8.4 Cryptographic Influences on Game Theory
8.4.2 Removing the Mediator in Correlated Equilibrium
8.4.3 Stronger Equilibria
8.5 Game Theoretic Influences on Cryptography
8.5.1 Noncooperatively Computable Functions
8.5.2 Rational Multiparty Computation
Part II Algorithmic Mechanism Design
Chapter 9 introduction to mechanism design (for computer scientists)
9.2.1 Condorcet’s Paradox
9.2.4 The Gibbard–Satterthwaite Theorem
9.3 Mechanisms with Money
9.3.1 Vickrey’s Second Price Auction
9.3.2 Incentive Compatible Mechanisms
9.3.3 Vickrey–Clarke–Groves Mechanisms
9.4 Implementation in Dominant Strategies
9.4.1 Games with Strict Incomplete Information
9.4.3 The Revelation Principle
9.5 Characterizations of Incentive Compatible Mechanisms
9.5.1 Direct Characterization
9.5.4 Single-Parameter Domains
9.5.5 Uniqueness of Prices
9.5.6 Randomized Mechanisms
9.6 Bayesian--Nash Implementation
9.6.1 Bayesian–Nash Equilibrium
9.6.2 First Price Auction
9.6.3 Revenue Equivalence
9.7.2 Interdependent Values
9.7.3 Complete Information Models
Chapter 10 Mechanism Design without Money
10.2 Single-Peaked Preferences over Policies
10.2.2 Application to Public Good Cost Sharing
10.3 House Allocation Problem
10.4.1 A Lattice Formulation
10.4.2 The LP Formulation
10.6 Notes and References
Chapter 11 Combinatorial Auctions
11.1.3 Structure of This Chapter
11.2 The Single-Minded Case
11.2.1 Computational Complexity of Allocation
11.2.2 An Incentive-Compatible Approximation Mechanism
11.3 Walrasian Equilibrium and the LP Relaxation
11.3.1 The Linear Programming Relaxation and Its Dual
11.3.2 Walrasian Equilibrium
11.4.1 Elements of Representation: Atoms, OR, and XOR
11.4.2 Combinations of OR and XOR
11.5 Iterative Auctions: The Query Model
11.5.2 Solving the Linear Program
11.5.3 Approximating the Social Welfare
11.6 Communication Complexity
11.6.1 The Model and Statement of Lower Bound
11.7.1 Ascending Item-Price Auctions
11.7.2 Ascending Bundle-Price Auctions
Chapter 12 Computationally Efficient Approximation Mechanisms
12.2 Single-Dimensional Domains: Job Scheduling
12.2.1 A Monotone Algorithm for the Job Scheduling Problem
12.3 Multidimensional Domains: Combinatorial Auctions
12.3.1 A General Overview of Truthful Combinatorial Auctions
12.4 Impossibilities of Dominant Strategy Implementability
12.5 Alternative Solution Concepts
Chapter 13 Profit Maximization in Mechanism Design
13.2 Bayesian Optimal Mechanism Design
13.2.1 Virtual Valuations, Virtual Surplus, and Expected Profit
13.2.2 Truthfulness of Virtual Surplus Maximization
13.2.3 Applications of Myerson’s Optimal Mechanism
13.3 Prior-Free Approximations to the Optimal Mechanism
13.3.1 Empirical Distributions
13.4 Prior-Free Optimal Mechanism Design
13.4.1 Competitive Framework
13.4.2 A Competitive Digital Goods Auctions
13.4.4 The Digital Goods Auction Decision Problem
13.4.5 Reduction to the Decision Problem
13.4.6 Consensus Estimation and Truthfulness with High Probability
13.6 Conclusions and Other Research Directions
Chapter 14 distributed algorithmic mechanism design
14.2 Two Examples of DAMD
14.2.1 Distributed Implementation of VCG
14.2.2 Sharing the Cost of a Multicast Transmission
14.3.1 Networking Perspective
14.3.2 Mechanism-Design Perspective
14.3.3 A DAMD Approach: Combining the Two Perspectives
14.3.3.1 Commercial Internet Routing and the Gao–Rexford Model
14.4 Conclusion and Open Problems
15.1 Cooperative Games and Cost Sharing
15.2 Core of Cost-Sharing Games
15.3 Group-Strategyproof Mechanisms and Cross-Monotonic Cost-Sharing Schemes
15.4 Cost Sharing via the Primal-Dual Schema
15.4.2 The Facility Location Game
15.5 Limitations of Cross-Monotonic Cost-Sharing Schemes
15.6 The Shapley Value and the Nash Bargaining Solution
15.6.2 An Axiomatic Characterization of the Shapley Value
15.6.3 The Nash Bargaining Solution
Chapter 16 Online Mechanisms
16.1.1 Example: Dynamic Auction with Expiring Items
16.1.2 The Challenge of Online MD
16.2 Dynamic Environments and Online MD
16.2.1 Direct-Revelation Mechanisms
16.2.2 Remark: The Revelation Principle
16.3 Single-Valued Online Domains
16.3.1 Truthfulness for Single-Valued Preference Domains
16.3.2 Example: A Dynamic Auction with Expiring Items
16.3.3 Example: An Adaptive, Limited-Supply Auction
16.4 Bayesian Implementation in Online Domains
16.4.2 A Dynamic Vickrey–Clarke–Groves Mechanism
Part III Quantifying the Inefficiency of Equilibria
17 introduction to the inefficiency of equilibria
17.1.1 The Inefficiency of Equilibria
17.1.2 Measures of Inefficiency
17.1.3 The Price of Anarchy and the Price of Stability
17.2 Fundamental Network Examples
17.2.2 Network Design and Formation Games
17.2.4 Resource Allocation Games
17.3 Inefficiency of Equilibria as a Design Metric
17.3.2 An Example: The Proportional Sharing Mechanism
18.2.1 Nonatomic Selfish Routing
18.2.1 Nonatomic Selfish Routing
18.2.2 Atomic Selfish Routing
18.3 Existence, Uniqueness, and Potential Functions
18.3.1 Nonatomic Selfish Routing: Existence and Uniqueness
18.3.2 Atomic Selfish Routing: Existence
18.4 The Price of Anarchy of Selfish Routing
18.4.1 Nonatomic Selfish Routing: The Price of Anarchy
18.4.2 Atomic Selfish Routing: The Price of Anarchy
18.5 Reducing the Price of Anarchy
18.5.1 Marginal Cost Pricing
18.5.2 Capacity Augmentation
18.6.1 Nonatomic Selfish Routing
18.6.2 Atomic Selfish Routing
19 Network Formation Games and
the Potential Function Method
19.2 The Local Connection Game
19.2.2 Characterization of Solutions and the Price of Stability
19.2.3 The Price of Anarchy
19.3 Potential Games and a Global Connection Game
19.3.1 A Global Connection Game
19.3.2 Potential Games and Congestion Games
19.3.3 The Potential Function Method and the Price of Stability
19.3.4 Finding Nash Equilibria in Potential Games
19.3.5 Variations on Sharing in the Global Connection Game
19.4.2 Facility Location as a Potential Game
19.4.4 The Price of Anarchy for Utility Games
19.5.1 Local Connection Game
19.5.2 Potential Games and a Global Connection Game
19.5.3 Facility Location Game
20 Selfish Load Balancing
20.1.1 Load Balancing Games
20.1.2 Example of a Load Balancing Game
20.1.3 Definition of the Price of Anarchy
20.2 Pure Equilibria for Identical Machines
20.2.1 The Price of Anarchy
20.2.2 Convergence Time of Best Responses
20.3 Pure Equilibria for Uniformly Related Machines
20.3.1 The Price of Anarchy
20.3.2 Algorithms for Computing Pure Equilibria
20.4 Mixed Equilibria on Identical Machines
20.4.1 Fully Mixed Equilibria
20.5 Mixed Equilibria on Uniformly Related Machines
20.6 Summary and Discussion
21 The Price of Anarchy and the design of scalable resource allocation mechanisms
21.2.1 Price Taking Users and Competitive Equilibrium
21.2.2 Price Anticipating Users and Nash Equilibrium
21.2 The Proportional Allocation Mechanism
21.2.1 Price Taking Users and Competitive Equilibrium
21.2.2 Price Anticipating Users and Nash Equilibrium
21.3 A Characterization Theorem
21.4 The Vickrey--Clarke--Groves Approach
21.4.2 Scalar Strategy VCG Mechanisms
21.5 Chapter Summary and Further Directions
Part IV Additional Topics
22 Incentives and Pricing in Communications Networks
22.1 Large Networks -- Competitive Models
22.2.1 Pricing and Efficiency with Congestion Externalities
22.2.3 Monopoly Pricing and Equilibrium
22.2.4 Oligopoly Pricing and Equilibrium
22.2.5 Efficiency Analysis
22.2 Pricing and Resource Allocation -- Game Theoretic Models
22.3 Alternative Pricing and Incentive Approaches
22.3.1 PreviousWork on Pricing
22.3.2 Current Research on Pricing and Incentive Models
22.3.3 Areas for Future Research
23 Incentives in Peer-to-Peer Systems
23.2 The p2p File-Sharing Game
23.3.1 A Minimalist p2p Model
23.3.2 Reputation and Service Differentiation
23.4 A Barter-Based System: BitTorrent
23.6 Hidden Actions in p2p Systems
23.6.1 The Principal-Agent Model
24 Cascading Behavior in Networks: Algorithmic
and Economic Issues
24.2 A First Model: Networked Coordination Games
24.3 More General Models of Social Contagion
24.4 Finding Influential Sets of Nodes
24.5 Empirical Studies of Cascades in Online Data
24.6 Notes and Further Reading
25 incentives and information security
25.2 Misaligned Incentives
25.2.1 Applications of Game Theory
25.2.2 Network Effects and Deployment
25.3 Informational Asymmetries
25.3.1 Hidden-Action Attacks
25.3.2 Hidden Information: Measuring Software Security
25.3.3 Market-Based Approaches
25.4 The Economics of Censorship Resistance
25.4.1 Red–Blue Utility Model
25.4.2 Comparing Censorship Resistance
25.5 Complex Networks and Topology
26 Computational Aspects of Prediction Markets
26.1 Introduction: What Is a Prediction Market?
26.2.1 Setup and Notation
26.2.2 Survey of the Field
26.2.2.1 What and How: Instruments and Mechanisms
26.2.2.2 Examples and Evaluations
26.2.2.3 Theoretical Underpinnings
26.3 Combinatorial Prediction Markets
26.3.1 Compound Prediction Markets
26.3.1.2 The Matching Problem
26.3.1.3 The Computational Complexity of Matching
26.3.2 Compact Prediction Markets
26.4 Automated Market Makers
26.4.1 Market Scoring Rules
26.4.2 Dynamic Parimutuel Markets
26.5 Distributed Computation through Markets
26.5.1 Boolean Market Model
26.5.2 Bid Format and Price Formation
26.5.4 Equilibrium Price Characterization
26.5.5 Characterizing Computable Aggregates
Combinatorial Prediction Markets
Distributed Computation Through Markets
27 manipulation-resistant reputation systems
27.1 Introduction: Why Are Reputation Systems Important?
27.2 The Effect of Reputations
27.3.1 A More Dynamic Model
27.4 Eliciting Effort and Honest Feedback
27.4.2 Peer-Prediction Scoring
27.5 Reputations Based on Transitive Trust
27.5.1 Incentives for Honest Reporting
27.5.2 Sybils and Sybilproofness
27.6 Conclusion and Extensions
27.6.1 Extensions and Open Problems
28 Sponsored Search Auctions
28.2 Existing Models and Mechanisms
28.3.1 Revenue Maximization and Efficiency
28.3.2 Equilibrium Properties
28.4.1 The Online Allocation Problem
29 Computational Evolutionary Game Theory
29.1 Evolutionary Game Theory
29.1.1 The Classical Model of Evolutionary Game Theory
29.2 The Computational Complexity
of Evolutionarily Stable Strategies
29.3 Evolutionary Dynamics Applied to Selfish Routing
29.3.1 The Selfish Routing Model with Imitative Dynamics
29.3.2 Convergence to Nash Flow
29.3.3 Convergence to Approximate Equilibrium
29.4 Evolutionary Game Theory over Graphs
29.4.1 Random Graphs, Adversarial Mutations
Algorithmic Game Theory
Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.