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

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.