Algorithmic cost allocation games [Elektronische Ressource] : theory and applications / vorgelegt von Nam Dũng Hoàng

Hoang Nam Dung

Description

Algorithmic Cost Allocation Games:Theory and Applicationsvorgelegt vonDipl.-Math. Nam Du˜ng Hoa`ngaus Hanoi, VietnamVon der Fakult¨at II – Mathematik und Naturwissenschaftender Technischen Universit¨at Berlinzur Erlangung des akademischen GradesDoktor der Naturwissenschaften– Dr. rer. nat. –genehmigte DissertationPromotionsausschussVorsitzender: Prof. Dr. Fredi Tro¨ltzschBerichter: Prof. Dr. Dr. h.c. mult. Martin Gro¨tschelDr. habil. Ralf Bornd¨orferTag der wissenschaftlichen Aussprache: 6. Oktober 2010Berlin 2010D 83For my parentsAbstractDue to economy of scale, it is suggested that individual users, in orderto save costs, should join a cooperation rather than acting on their own.However, a challenge for individuals when cooperating with others is thatevery member of the cooperation has to agree on how to allocate the com-mon costs among members, otherwise the cooperation cannot be realised.Taken this issue into account, we set the objective of our thesis in inves-tigating the issue of fair allocations of common costs among users in acooperation. This thesis combines cooperative game theory and state-of-the-art algorithms from linear and integer programming in order to definefaircostallocationsandcalculatethemnumericallyforlargereal-worldap-plications. Ourapproachesoutclassetraditional costallocation methodsinterms of fairness and users’ satisfaction.

Sujets

• Mathematics

Informations

• Publié par: technische_universitat_berlin
• Publié le: 01 janvier 2010
• Nombre de lectures: 78
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Algorithmic Cost Allocation Games: Theory and Applications

vorgelegt von

Dipl.Math.NamDu˜ngHoàng

aus Hanoi, Vietnam

Von der Fakultät II – Mathematik und Naturwissenschaften der Technischen Universität Berlin zur Erlangung des akademischen Grades

Doktor der Naturwissenschaften – Dr. rer. nat. –

Vorsitzender: Berichter:

genehmigte Dissertation

Promotionsausschuss Prof. Dr. Fredi Tröltzsch Prof. Dr. Dr. h.c. mult. Martin Grötschel Dr. habil. Ralf Borndörfer

Tag der wissenschaftlichen Aussprache: 6. Oktober 2010

Berlin 2010 D 83

For my parents

Abstract

Due to economy of scale, it is suggested that individual users, in order to save costs, should join a cooperation rather than acting on their own. However, a challenge for individuals when cooperating with others is that every member of the cooperation has to agree on how to allocate the com mon costs among members, otherwise the cooperation cannot be realised. Taken this issue into account, we set the objective of our thesis in inves tigating the issue of fair allocations of common costs among users in a cooperation. This thesis combines cooperative game theory and stateof theart algorithms from linear and integer programming in order to define fair cost allocations and calculate them numerically for large realworld ap plications. Our approaches outclasse traditional cost allocation methods in terms of fairness and users’ satisfaction. Cooperative game theory analyzes the possible grouping of individuals to form their coalitions. It provides mathematical tools to understand fair prices in the sense that a fair price prevents the collapse of the grand coali tion and increases the stability of the cooperation. The current definition of cost allocation game does not allow us to restrict the set of possible coalitions of players and to set conditions on the output prices, which of ten occur in realworld applications. Our generalization bring the cost allocation game model a step closer to practice. Based on our definition, we present and discuss in the thesis several mathematical concepts, which model fairness. This thesis also considers the question of whether there exists a “best” cost allocation, which people naturally like to have. It is wellknown that multicriteria optimization problems often do not have “the optimal solu tion” that simultaneously optimizes each objective to its optimal value. There is also no “perfect” votingsystem which can satisfy all the five sim ple, essential social choice procedures presented in the book “Mathematics and Politics. Strategy, Voting, Power and Proof” of Taylor et al. Similarly, the cost allocation problem is shown to experience the same problem. In

i

particular, there is no cost allocation which can satisfy all of our desired properties, which are coherent and seem to be reasonable or even indis pensable. Our game theoretical concepts try to minimize the degree of axiomatic violation while the validity of some most important properties is kept. From the complexity point of view, it is NPhard to calculate the allo cations which are based on the considered game theoretical concepts. The hardest challenge is that we must take into account the exponential num ber of the possible coalitions. However, this difficulty can be overcome by using constraint generation approaches. Several primal and dual heuris tics are constructed in order to decrease the solving time of the separation problem. Based on these techniques, we are able to solve our applications, whose sizes vary from small with 4 players, to medium with 18 players, and 85 even large with 85 players and 2−Via computa1 possible coalitions. tional results, we show the unfairness of traditional cost allocations. For example, for the ticket pricing problem of the Dutch IC railway network, the current distance tariff results in a situation where the passengers in the central Randstad region of the country pay over 25% more than the costs they incur and these excess payments subsidize operations elsewhere, which is absolutely not fair. In contrast, our game theory based prices decrease this unfairness and increase the incentive to stay in the grand coalition for players.

ii

Acknowledgments

I would like to express my sincere gratitude to my advisor Prof. Dr. Dr. h.c. mult. Martin Grötschel for the interesting research theme and for his supervision. I am grateful to Dr. Ralf Borndörfer for his valuable supports and suggestions. I would like to express my thank to the Zuse Institute Berlin (ZIB) for providing me a KonradZuse Scholarship. I also want to thank to all my friends and colleagues at ZIB for the wonderful working atmosphere. Moreover, I am appreciative to my proof readers Carlos Cardonha, Dr. Benjamin Hiller, and Dr. Thorsten Koch for their precious comments. And last but not least, I would like to thank my parents for their care and continual supports.

iii

Contents

Abstract

Acknowledgments

1

2

3

Introduction

The Cost Allocation Problem The Cost Allocation Game . . . . . . . . Desired Properties and Conflicts . . . . . 2.2.1 Desired Properties . . . . . . . . 2.2.2 Conflicts . . . . . . . . . . . . . . 2.2.3 Some Other Desired Properties . Game Theoretical Concepts . . . . . . . 2.3.1 The Core and thef.Least Core 2.3.2 ThefNucleolus . . . . . . . . . . 2.3.3 The (f, r. . . . . . .)Least Core 2.3.4 Choosing the Weight Function . . 2.3.5 The Shapley Value . . . . . . . . 2.3.6 Another Conflict . . . . . . . . . Alternative Ansatz . . . . . . . . . . . . Nonemptiness of the Core . . . . . . . . Conclusions . . . . . . . . . . . . . . . .

2.1 2.2 2.3 2.4 2.5 2.6

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Complexity 3.1 NPHardness of Cost Allocation Game . . . . . . . . . . . . 3.2 Ellipsoid Method and Submodular Function Minimization . 3.3 Polynomial Time Algorithms for Submodular Games . . . . 3.3.1 Algorithm for thefNucleolus . . . . . . . . . . . . .

v

i

iii

1

9 11 13 14 18 21 28 28 51 66 72 73 77 78 78 87

91 91 92 94 95

CONTENTS

4

5

6

7

8

9

3.3.2

Algorithms for thefLeast Core and the (f, r)Least Core . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

Computational Aspects 107 4.1 Combinatorial Game . . . . . . . . . . . . . . . . . . . . . . 108 4.2 Constraints Generation Approaches . . . . . . . . . . . . . . 108 4.2.1 ThefLeast Core and thef108. . . . . . . Nucleolus . 4.2.2 The (f, r110)Least Core . . . . . . . . . . . . . . . . . . 4.2.3 Choosing A Good Starting Set . . . . . . . . . . . . . 112 4.2.4 The Separation Problem . . . . . . . . . . . . . . . . 121 4.2.5 Heuristics for the Separation Problem . . . . . . . . . 123

The Fairness Distribution Diagram

ASimpleRealExample

127

131

Allocating Production and Transmission Costs 137 7.1 Production and Transmission Costs . . . . . . . . . . . . . . 137 7.2 Nonlinear Multicommodity Flow Model . . . . . . . . . . . 138 7.3 Mixed Integer Model . . . . . . . . . . . . . . . . . . . . . . 140 7.4 Piecewise Linear Approximation . . . . . . . . . . . . . . . . 148 7.5 Cost Allocation in Water Resources Development . . . . . . 154 7.5.1 The Water Resources Development Cost Allocation Game . . . . . . . . . . . . . . . . . . . . . . . . . . 155 7.5.2 The Separation Problem . . . . . . . . . . . . . . . . 160 7.5.3 Computational Results . . . . . . . . . . . . . . . . . 162

Ticket Pricing Problem in Public Transport 167 8.1 The Ticket Pricing Problem . . . . . . . . . . . . . . . . . . 167 8.2 Calculating the Cost Function . . . . . . . . . . . . . . . . . 170 8.3 The Separation Problem . . . . . . . . . . . . . . . . . . . . 173 8.4 Ticket Prices for the Dutch IC Network . . . . . . . . . . . . 175

Perspectives

Bibliography

Notations

Index

vi

183

185

193

195