Randomisierte Methoden im algorithmischen Mechanismen-Design

• Antragstellerin: Professorin Dr. Britta Peis, seit 11/2014
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2013 bis 2020
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 230665258

Das Gebiet des algorithmischen Mechanismen-Designs beschäftigt sich mit der Entwicklung und Analyse von effizient berechenbaren und anreizkompatiblen Verfahren. Ein Kernproblem ist die Zuteilung von Ressourcen an Agenten mit nicht-öffentlichen Nutzenfunktionen in kombinatorischen Auktionen. Insbesondere im Falle mehrdimensionaler Nutzenfunktionen sind die durch die Anreizkompatibilität gegebenen Einschränkungen an den Algorithmenentwurf besonders schwerwiegend und noch nicht hinreichend verstanden. Für verschiedene deterministische Ansätze, die diese Anforderungen erfüllen, wurde bereits nachgewiesen, dass sie keine annähernd nutzenmaximale Ressourcenzuteilung erreichen können. Neuere Arbeiten zeigen jedoch auf, dass randomisierte Mechanismen für einige grundlegende Problemstellungen gute Approximationsfaktoren garantieren können. In diesem Projekt erweitern und vertiefen wir den Stand der Forschung auf dem Gebiet des randomisierten Mechanismen-Designs. Wir erkunden neue algorithmische Ansätze für verschiedene Arten von kombinatorischen Auktionen in Online- und Offline-Modellen, und wir gehen der Frage nach, ob und inwiefern randomisierte Methoden zwingend notwendig für die Entwicklung von anreizkompatiblen Mechanismen sind.

• DFG-Verfahren: Sachbeihilfen
• Ehemaliger Antragsteller: Professor Dr. Berthold Vöcking, bis 11/2014 (†)