Deutsch

Wie kann man ein System so gestalten, dass sich autonome eigennützige Spieler in "wünschenswerter" Weise verhalten werden? In dieser Dissertation betrachten wir diese Frage im Kontext von Kostenaufteilungs-Problemen, bei denen endlich viele Spieler eine unbekannte Wertschätzung für einen nicht-rivalen aber ausschließbaren Service (z.B. Netzwerk-Konnektivität) haben. Die Aufgabe besteht im Entwurf von Mechanismen, die den Spielern wahrheitsgemäße Angaben über ihre Wertschätzungen entlocken, die zu bedienende Menge von Spielern Q auswählen und die Aufteilung der entstehenden Kosten C(Q) bestimmen. Insbesondere muss den Spielern also ein Anreiz zu wahrheitsgemäßen Angaben geschaffen werden. Weitere Anforderungen bei Kostenaufteilungs-Problemen umfassen Budget-Balance (Deckung der Service-Kosten mit den erhobenen Preisen) und ökonomische Effizienz (eine sinnvolle Abwägung zwischen Service-Kosten und den Wertschätzungen der ausgeschlossenen Spieler). Praktische Anwendungen verlangen darüber hinaus, dass Kostenaufteilungs-Mechanismen in Polynomialzeit berechenbar sind.

Kostenaufteilungs-Probleme sind fundamental in der Ökonomie und haben vielfältige Anwendungen: bspw. die Weitergabe von Mengenrabatten bei elektronischem Handel, die Aufteilung von Kosten bei öffentlichen Infrastruktur-Projekten, die Umlage von Entwicklungskosten speziell angefertigter Produkte etc. Trotz dieser grundlegenden Natur gibt es nur wenige allgemeine Techniken zur Lösung von Kostenaufteilungs-Problemen. Wenn Gruppen-strategische Robustheit -- also Absprachen-Resistenz in sehr starkem Sinne -- gefordert wird, ist sogar nur eine Technik bekannt: die sogenannten Moulin-Mechanismen. Leider gibt es jedoch einige natürliche Kostenaufteilungs-Probleme, bei denen jeder Moulin-Mechanismus zwangsläufig schlechte Budget-Balance und geringe ökonomische Effizienz aufweist.

In dieser Dissertation entwickeln wir mehrere alternative Techniken für den Entwurf von Kostenaufteilungs-Mechanismen. Wir demonstrieren die Vorteile unserer neuen Techniken durch Anwendung auf verschiedene natürliche Kostenaufteilungs-Probleme, bei denen die Kosten C(Q) durch kombinatorische Optimierungsprobleme induziert sind. Außerdem erzielen wir Charakterisierungs-Resultate, welche die inhärenten Grenzen von Absprachen-Resistenz in Bezug auf die anderen gewünschten Eigenschaften von Kostenaufteilungs-Mechanismen verstehen helfen.

English

How can a system be designed so that autonomous self-interested players behave in a "desirable" way? In this thesis, we study this question in the context of cost-sharing problems, where finitely many players have an unknown valuation for some non-rivalrous but excludable service (e.g., network connectivity). The challenge is to design mechanisms that elicit truthful reports of the players' valuations, determine which set of players Q to serve, and decide how to distribute the incurred service cost C(Q). So in particular, a cost-sharing mechanism has to give players an incentive to reveal truthful information. Further constraints for cost-sharing problems include budget balance (i.e., recovery of the service cost with the prices charged) and economic efficiency (i.e., a reasonable trade-off between the service cost and the excluded players' valuations). Practical applications moreover require that cost-sharing mechanisms are computable in polynomial time.

Cost-sharing problems are fundamental in economics and have a broad area of applications; e.g., distributing volume discounts in electronic commerce, sharing the cost of public infrastructure projects, allocating development costs of low-volume built-to-order products, etc. Despite this fundamental nature, general techniques for solving cost-sharing problems are rare. When requiring group-strategyproofness--i.e., collusion resistance in a very strong sense--essentially only one technique has been known, the so-called Moulin mechanisms. Unfortunately, there are several natural cost-sharing problems for which any Moulin mechanism inevitably suffers poor budget balance and economic efficiency.

In this thesis, we devise several alternative techniques for designing cost-sharing mechanisms. We demonstrate the benefits of our novel techniques by applying them to various natural cost-sharing problems where the costs C(Q) are induced by combinatorial optimization problems. Moreover, we provide characterization results that contribute towards understanding the inherent limitations of collusion resistance with respect to the other desirable properties of cost-sharing mechanisms.