Wer bekommt die Postkartensammlung, wer den Goldhamster? Im Falle einer Scheidung oder Erbschaft kommt es regelmäßig zu Streitigkeiten bei der Zuordnung der Habseligkeiten. Christian Klamler vom Institut für Finanzwissenschaft und Öffentliche Wirtschaft der Uni Graz hat mit den amerikanischen Koautoren Steven Brams und Marc Kilgour einen Algorithmus entwickelt, wie Güter mit ideellem Wert fair und neidfrei aufgeteilt werden können. Der wissenschaftliche Artikel dazu erscheint in der Februar-Ausgabe des Fachmagazins „Notices of the American Mathematical Society“.
Das Grundprinzip ist einfach: Zunächst reihen die beiden involvierten Personen die zur Verfügung stehenden Objekte nach ihrer persönlichen Priorität. Dann nennen sie abwechselnd die Dinge auf dieser Liste. Wollen sie verschiedene Gegenstände, erhalten sie diese jeweils. Hätten sie gerne Dasselbe, sucht eine Formel nach der fairsten Lösung. Gerechtigkeit ist dann garantiert, wenn niemand die Objekte des anderen den eigenen vorzieht. Der Vorteil des Algorithmus liegt darin, dass die maximal mögliche Anzahl an Gegenständen verteilt wird, ohne jemanden zu benachteiligen. Reiht Person A ihre Wünsche 1, 2, 3, 4 und Person B 2, 3, 4, 1, würden in einem ersten Schritt die Objekte 1 und 2 sehr einfach zugeteilt werden. Ab Nummer 3 käme es zum Konflikt. Der neue Lösungsweg schafft es, in diesem Beispiel alle Dinge zuzuordnen, ohne eineN PartnerIn schlechter zu stellen: Person A bekommt 1 und 3, Person B 2 und 4. Die Liste der Gegenstände ist natürlich beliebig erweiterbar, und zumindest eine Lösung mit maximaler Zuteilung lässt sich immer finden.
Ähnliche Algorithmen entwickelt Christian Klamler gemeinsam mit seinem Mitarbeiter Andreas Darmann auch im Rahmen des vom Österreichischen Wissenschaftsfonds FWF finanzierten Projekts „Fairness und Auswahl in der Diskreten Optimierung“. Dabei geht es unter anderem darum, Kosten für Netzwerkstrukturen wie Straßen oder Kanäle fair und effizient aufzuteilen. Zuerst werden sinnvolle Kriterien für den Aufteilungsmechanismus definiert, dadurch der geeignete Algorithmus bestimmt und gleichzeitig untersucht, ob diese Vorgangsweise auch praktikabel ist. Mit der Größe des Problems steigt nämlich auch der Berechnungsaufwand, sodass selbst leistungsstarke Computer die Ergebnisse nicht mehr in vernünftiger Zeit liefern können.
Link zur Online-Publikation: www.ams.org/notices/201402/