Hannaneh Akrami nach der Verteidigung ihrer Doktorarbeit. Foto: Privat
Am 13. März 2025 hat Hannaneh Akrami erfolgreich ihre Dissertation mit dem Titel „Share-Based and Envy-Based Approaches to Fair Division of Indivisible Goods“ verteidigt. Hannaneh Akrami kam 2019 als Doktorandin an die Universität des Saarlandes und das Max-Planck-Insitutt für Infomratik und wurde von Professor Kurt Mehlhorn betreut. Sie war Mitglied der Saarbrücker Graduiertenschule für Informatik und sowie der International Max Planck Research School (IMPRS) on Trustworthy Computing. Der Doktorgrad wurde durch die Universität des Saarlandes verliehen.
Zusammenfassung der Dissertation:
Die faire Aufteilung von Ressourcen zwischen Akteuren mit individuellen Präferenzen ist ein grundlegendes Problem an der Schnittstelle von Informatik, Sozialwahltheorie und Wirtschaftswissenschaften. In dieser Dissertation werden Szenarien untersucht, in denen die zu verteilenden Ressourcen eine Reihe von unteilbaren Gütern sind. Es werden zwei Hauptkategorien von Fairnesskonzepten betrachtet: anteilsbasierte
und neidbasierte Kriterien. Jede Kategorie umfasst wünschenswerte Vorstellungen von
Fairness, die jeweils ihre eigenen Vorteile und Grenzen haben. Im ersten Teil dieser Arbeit untersuchen wir einen anteilsbasierten Fairnessbegriff, der als Maximin-Share (MMS) bekannt ist. Da MMS-Zuteilungen nicht immer existieren, untersuchen wir relaxierte MMS-Zuteilungen und zeigen positive Ergebnisse in verschiedenen Situationen. Insbesondere beweisen wir die Existenz von (3/4+3/3836) MMS-Zuteilungen
für Agenten mit additiven Bewertungen und 3/13 MMS-Zuteilungen für Agenten mit fraktionell subadditiven (XOS) Bewertungen. Zusätzlich betrachten wir ordinale Approximationen von MMS und beweisen die Existenz von 1-aus-4n/3-MMS-Zuteilungen in dem additiven Fall.
Der zweite Teil der Dissertation befasst sich mit neidbasierten Fairnesskonzepten. Für unteilbare Güter ist das bekannteste neidbasierte Kriterium die Neidfreiheit bis auf ein beliebiges Gut (EFX). Obwohl die Existenz von EFX-Zuteilungen in vielen allgemeinen Kontexten offen bleibt, leisten wir einen Beitrag zu diesem Gebiet, indem wir die Existenz von EFX-Zuteilungen für drei Agenten unter minimalen Beschränkungen ihrer Bewertungen beweisen. Darüber hinaus etablieren wir die Existenz von relaxierten Formen von EFX, einschließlich epistemischem EFX, und approximiertem EFX mit Spenden.
Im dritten und letzten Teil dieser Arbeit gehen wir über einzelne Fairnesskriterien hinaus — sei es anteilsbasiert oder neidbasiert — und beweisen die Existenz von Zuteilungen, die mehrere Fairnessgarantien erfüllen. Insbesondere beweisen wir die Existenz von (teilweisen) Zuteilungen, die gleichzeitig 2/3-MMS und EFX sind. Dieser Forschungszweig ist zwar weniger etabliert, stellt aber eine vielversprechende Richtung für zukünftige Forschung dar.
Redaktion:
Philipp Zapf-Schramm
Max-Planck-Institut für Informatik
Tel: +49 681 9325 5409
E-Mail: pzs@mpi-inf.mpg.de