Algorithmen für faire Zuweisung unteilbarer Güter

• Antragsteller: Professor Dr. Martin Hoefer
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2020 bis 2024
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 431465915

Die Zuweisung von unteilbaren Gütern an verschiedene Nutzer ist ein grundlegendes Problem in vielen modernen Systemen, z.B. bei der Vergabe von Studienplätzen, von Zugriffsrechten auf Ressourcen einer Rechner- oder Verkehrsinfrastruktur, bei der Konfliktlösung (Scheidung, Erbe), usw. Der Entwurf von guten Allokationsalgorithmen für diese Probleme spielt eine wichtige Rolle in der Forschung. Insbesondere die Einhaltung von Gerechtigkeits- und Fairnesskriterien durch effiziente Algorithmen ist eine wichtige Herausforderung in der Forschung und ein aktuelles Thema in der öffentlichen Diskussion.In diesem Projekt betrachten wir Entwurf und Analyse von effizienten Approximationsalgorithmen für faire Zuweisung von unteilbaren Gütern. Das Ziel sind neue Verfahren und beweisbare Gütegarantien für Fairness in Systemen mit aussagekräftigen Bewertungsfunktionen der Nutzer. Wir untersuchen dabei eine Reihe von neuen und attraktiven Fairnesskriterien (z.B. Varianten der Envy-Freeness), die algorithmisch und strukturell noch nicht gut verstanden sind. Daneben betrachten wir faire Zuweisung auch unter strategischen und spieltheoretischen Gesichtspunkten. Das Ziel ist der Entwurf von Mechanismen, die Garantien an die (approximative) Fairness der Zuweisungen im Gleichgewicht ermöglichen.

• DFG-Verfahren: Sachbeihilfen