Cost Sharing, Capacity Investment and Pricing in Networks

Description

Anja Schedel analyzes two models in the field of algorithmic game theory which both constitute bilevel problems in networks. The first model is a game-theoretic variant of the well-known Steiner forest problem, and one is interested in an optimal sharing of the cost of the Steiner forest. The author provides (and partially exactly characterizes) network structures which allow for cost-minimal pure Nash equilibria. The second model is motivated from privatized public roads, in which private, selfishly acting firms build roads, and as compensation for their investment, are allowed to set prices for using the roads. For a basic model of this situation, the author shows existence and uniqueness of pure Nash equilibria. The existence result requires a non-standard proof approach since techniques like Kakutani’s fixed point theorem cannot be applied directly.    Acknowledgements Contents 1 Introduction [DELETE] 1.1 Cost Sharing in Networks 1.2 Capacity and Price Competition in Networks 1.3 Thesis Organization 2 Preliminaries [DELETE] 2.1 Graphs 2.2 Games 2.3 Correspondences 3 Cost Sharing in Networks 3.1 Introduction 3.1.1 Problem Description 3.1.2 Main Results and Proof Techniques 3.1.3 Discussion of the Model and Related Work 3.2 An LP-Characterization of Enforceability 3.3 Results for Two Player Games 3.3.1 Connection to Steiner forests 3.3.2 The Set of Bad Configurations and some Intuition 3.3.3 Proof Sketch of Theorem[theoremrobust]3.3.1 3.3.4 ([Thm3.3.1.3]3) implies ([Thm3.3.1.1]1) of Theorem[theoremrobust]3.3.1 3.3.5 ([Thm3.3.1.1]1) implies ([Thm3.3.1.2]2) of Theorem[theoremrobust]3.3.1 3.3.6 Discussion of the Result 3.4 Results for n-Player Games 3.4.1 The Algorithm n-SePa 3.4.2 Analysis of Algorithm n-SePa 3.4.3 Main Results 3.4.4 Discussion of the Results 3.5 Bibliographic Notes 4 Capacity and Price Competition in Networks 4.1 Introduction 4.1.1 Problem Description 4.1.2 Main Results and Proof Techniques 4.1.3 Discussion of the Model and Related Work 4.2 Continuity of Profit Functions 4.3 Characterization of Best Responses 4.3.1 The Case z-i=0 4.3.2 The Case z-ineq0 4.3.3 The Characterization 4.3.4 Discussion 4.4 Existence of Equilibria 4.5 Uniqueness of Equilibria 4.6 Quality of Equilibria 4.7 Bibliographic Notes 5 Conclusion [DELETE] Bibliography Bibliography