English

This dissertation deals with mechanism design and puts special focus on cost-sharing problems. A set of customers is interested in a specific service. This service is auctioned off by a service provider to a subset of these customers. In particular, the provider has to solve two problems:

• Which customers are given the service?
• What is the price each customer has to pay?

This dissertation considers this task under the assumption that the decisions to the above problems can solely be based on customers' bids. This problem is one of the most fundamental problems in economics and has many applications, for example in public infrastructure projects or in service supply.

The decisions of the provider are computed by a cost-sharing mechanism. However, it cannot be assumed that customers' bids correspond to their true valuations. The main task is thus to grant group-strategyproofness, i.e., to provide incentives to customers such that neither single cheating nor cooperative collusion leads to a higher profit. These incentives are naturally realized through payment computation.

Next to group-strategyproofness, there are much more desirable properties. Naturally, the cost of providing the service should be covered by the payments. On the other hand, the provider has to stay competitive and thus the surplus should be as small as possible. These requirements are summarized by the term budget-balance. Moreover, from the economic point of view, there should be a reasonable trade-off between the cost of the provider and the true valuations of the rejected customers, i.e., the mechanism should be economic efficient. Finally, practical applications demand for efficient computation of the mechanism and the solution that provides the service to the selected customers.

The main contribution of this dissertation is the extension of research in this area, in particular in the design of new mechanisms that partly improve the performance of existing mechansims. Main applications are scheduling problems and connectivity problems within networks.

Deutsch

Die Dissertation beschäftigt sich mit Mechanismen Design und legt besonderen Fokus auf Cost-Sharing Probleme. Es wird eine Menge von Kunden betrachtet, welche an einem bestimmten Service interessiert sind. Dieser Service wird von einem Anbieter (sogenannter Service Provider) mittels einer Auktion an eine Teilmenge dieser Kunden vergeben. Der Anbieter hat insbesondere zwei Probleme zu lösen:

• Welche Kunden bekommen den Service?
• Welchen Preis muss jeder Kunde zahlen?

Die Dissertation betrachtet diese Aufgabe unter der Problemstellung, dass die Entscheidungen zu diesen zwei Fragen nur anhand von Geboten getroffen werden können, welche die Kunden dem Anbieter im Vorfeld übermitteln. Dieses Problem stellt eines der fundamentalen Probleme der Ökonomie dar und hat weitreichende Anwendungen, beispielsweise in der Kostenaufteilung von öffentlichen Infrastruktur-Projekten oder im Dienstleistungsgewerbe.

Die Entscheidungen des Anbieters werden anhand eines sogenannten Cost-Sharing Mechanismus getroffen. Allerdings kann im Allgemeinen nicht davon ausgegangen werden, dass die Gebote der Kunden der Wahrheit entsprechen. Die Hauptschwierigkeit besteht nun darin, sogenannte Group-Strategyproofness zu erreichen, d.h., den Kunden Anreize zu schaffen, dass sie weder durch alleinigen Betrug noch durch gemeinschaftliche Kollaboration einen höheren Profit erzielen können. Diese Anreize werden natürlicherweise durch die Berechnung der Zahlungen realisiert.

Neben der Group-Strategyproofness-Eigenschaft existieren viele weitere erwünschte Eigenschaften. Natürlicherweise sollen die Kosten des Anbieters zur Bereitstellung des Service von den Zahlungen der ausgewählten Kunden gedeckt werden. Auf der anderen Seite möchte der Anbieter aber auch wettbewerbsfähig bleiben und kann daher nur einen relativ geringen Mehrertrag erzielen. Diese Bedingungen werden unter dem Begriff Budget-Balance zusammengefasst. Desweiteren soll aus ökonomischer Sicht ein vernünftiger Ausgleich zwischen den Kosten des Anbieters und den wahren Wertschätzungen der zurückgewiesenen Spieler erreicht werden, d.h., der Mechanismus soll ökonomisch effizient sein. Schließlich verlangen praktische Anwendungen die effiziente Berechnung des Mechanismus und einer Realisierung zur Bereitstellung des Service.

Der zentrale Beitrag der Dissertation ist die Erweiterung der Forschungsergebnisse in diesem Bereich, insbesondere im Design von neuen Mechanismen, welche die Performanz existierender Mechanismen zum Teil verbessern. Im Anwendungsbereich werden hauptsächlich Scheduling und Verbindungsprobleme in Netzwerken betrachtet.