Allocation in Networks

Description

A comprehensive overview of networks and economic design, presenting models and results drawn from economics, operations research, and computer science; with examples and exercises. This book explores networks and economic design, focusing on the role played by allocation rules (revenue and cost-sharing schemes) in creating and sustaining efficient network solutions. It takes a normative approach, seeking economically efficient network solutions sustained by distributional fairness, and considers how different ways of allocating liability affect incentives for network usage and development. The text presents an up-to-date overview of models and results currently scattered over several strands of literature, drawing on economics, operations research, and computer science. The book's analysis of allocation problems includes such classic models from combinatorial optimization as the minimum cost spanning tree and the traveling salesman problem. It examines the planner's ability to design mechanisms that will implement efficient network structures, both in large decentralized networks and when there is user-agent information asymmetry. Offering systematic theoretical analyses of various compelling allocation rules in cases of fixed network structures as well as discussions of network design problems, the book covers such topics as tree-structured distribution systems, routing games, organizational hierarchies, the “price of anarchy,” mechanism design, and efficient implementation. Appropriate as a reference for practitioners in network regulation and the network industry or as a text for graduate students, the book offers numerous illustrative examples and end-of-chapter exercises that highlight the concepts and methods presented. Cover Title Copyright Table of Contents Foreword by Hervé Moulin Preface Introduction Why Study Allocation in Networks? Motivating Examples Plan of the Book References 1 Some Basics 1.1 Graphs 1.1.1 Notation and Basic Definitions 1.1.2 Cycles 1.1.3 Trees 1.1.4 Directed Graphs 1.2 Cooperative Games 1.2.1 Notation and Basic Definitions 1.2.2 Allocation Rules 1.2.3 Monotonicity versus the Standalone Principle 1.3 Graphs and Games 1.3.1 Games with Graph Restrictions 1.3.2 From Graphs to Games 1.4 Exercises References 2 Trees 2.1 Fixed Trees 2.1.1 Chains 2.1.2 Standard Fixed Trees 2.2 Minimum-Cost Spanning Trees 2.2.1 The Model 2.2.2 Allocation in Spanning Trees 2.2.3 The MCST Problem as a Game 2.2.4 Axioms and Characterizations 2.3 Model Variations 2.3.1 Congestion 2.3.2 Individual Guarantees and Decentralized (Pricing) Rules 2.3.3 Minimum-Cost Steiner Trees 2.4 Exercises References 3 Cycles 3.1 Fixed Route 3.1.1 The Model 3.1.2 Fixed-Route Game 3.1.3 Proportional Allocation 3.1.4 Limited Cost Information 3.1.5 Limited Budgets 3.2 Traveling Salesman 3.2.1 Traveling Salesman Game 3.2.2 Practical Application 3.3 Chinese Postman 3.3.1 The Model and the Game 3.3.2 A Particular Allocation Rule 3.4 k-Connectivity and Reliability 3.4.1 k-Connectivity 3.4.2 Reliability 3.5 Exercises References 4 General Networks 4.1 Hierarchies with Joint Control 4.1.1 The Model 4.1.2 Axioms and Characterization 4.2 Networks with Redundant Connections 4.2.1 The Model 4.2.2 Cost Ratios and Liability Indices 4.2.3 Axioms for Cost-Ratio Indices 4.2.4 Characterization Results 4.2.5 Limited Reliability 4.2.6 Cost Responsibility 4.3 Capacity Networks 4.3.1 The Model 4.3.2 Allocation Rules 4.3.3 The Capacity Problem as a Game 4.4 Minimum-Cost Connection Networks 4.4.1 The Model 4.4.2 Axioms 4.4.3 Characterization Results 4.5 Network (Value) Games 4.5.1 The Model 4.5.2 Extensions of the Shapley Value 4.6 Flow Problems 4.6.1 Transmission Networks 4.6.2 Max-Flow Problems 4.7 Exercises References 5 Allocation in Decentralized Networks 5.1 Anarchy 5.1.1 PoA/PoS 5.2 Network Cost-Sharing Games 5.2.1 Strong Nash Equilibrium 5.3 Network Formation Games 5.3.1 Pairwise Stability 5.3.2 Alternative Stability Notions 5.3.3 Directed Networks 5.4 Bidding Mechanisms 5.4.1 Bargaining in Connection Networks 5.5 Strategyproofness 5.5.1 Moulin Mechanisms 5.5.2 Engineering Applications 5.6 Exercises References 6 Efficient Implementation 6.1 Truthful Reporting: Preliminary Examples 6.1.1 The MCST Model 6.1.2 Capacity Networks 6.2 Implementation: The MCST Model 6.2.1 The Game Form 6.2.2 The Setup 6.2.3 Implementation 6.3 Implementation: The MCCN model 6.3.1 The Setup 6.3.2 Implementation 6.3.3 Alternative Game Form 6.4 Welfare-Maximizing Networks 6.4.1 The Setup 6.4.2 Maskin Monotonicity 6.4.3 Implementation Results 6.5 Subscription Mechanisms 6.5.1 The Setup 6.5.2 Two Game Forms 6.5.3 Implementation Results 6.6 Exercises References Index