02.05.2011 · Wege zu gerechten Teilungsverfahren: Mathematiker haben für ein Alltagsproblem zwar nicht die optimale, aber doch eine zufriedenstellende Lösung gefunden.
Von Heinrich Hemme
© Bildagentur-online/Tetra
Gerecht zu teilen ist eine Kunst, die immer wieder gefragt ist - etwa, wenn zwei Söhne ihren Vater beerben oder zwei Jungen einen Teller voller Süßigkeiten bekommen. Dabei darf sich keiner vom anderen übervorteilt fühlen. Probleme dieser Art gibt es zuhauf im Wirtschafts- und Alltagsleben, und es ist eine Kunst, ein gerechtes Teilungsverfahren zu finden. Anfang April haben die beiden amerikanischen Mathematiker Lionel Levine vom Massachusetts Institute of Technology (MIT) in Cambridge und Katherine E. Stange von der Stanford University in Kalifornien ein neuartiges Verfahren veröffentlicht, mit dem sich solche Teilungsprobleme schnell und für beide Parteien zufriedenstellend lösen lassen.
Zwei Geschäftsleute A und B wollen sich eine bestimmte Anzahl Güter teilen, wobei sie vereinbaren, dass sie immer abwechselnd eines wählen dürfen. Die Güter sind nicht alle gleich, und außerdem haben sie für die beiden Geschäftsleute unterschiedliche Werte. Beide können nun jedem Gut einen persönlichen Wert zuordnen, der sich durch eine Punktzahl ausdrücken lässt. In der Regel ist die Verteilung der Punkte bei den beiden Geschäftsleuten nicht gleich. So kann es beispielsweise sein, dass A ein bestimmtes Gut unbedingt haben will und ihm deshalb eine hohe Punktzahl gibt, während es für B nicht besonders wichtig ist und darum von ihm nur mit einer kleinen Zahl bewertet wird. Die Geschäftsleute haben über die Güter die vollständigen Informationen, sie kennen also auch die Bewertungen ihres Konkurrenten. Ziel beider Geschäftsleute ist es, bei der Teilung eine insgesamt möglichst hohe Punktzahl zu erreichen. Nach welcher Strategie müssen die beiden vorgehen, um dieses Ziel zu erreichen?
Mit Streichstrategie
Will man die für beide Geschäftsleute optimale Strategie finden, muss man alle Reihenfolgen, in denen sie die Güter wählen können, durchprobieren und die dazugehörigen Gesamtpunktzahlen berechnen. Bei n zu verteilenden Gütern sind dies 1·2·3·...·(n-2)·(n-1)·n mögliche Strategien. Das Produkt, das man auch kurz als n! (lies: n Fakultät) schreibt, wächst mit größer werdendem n rasant an. Schon bei nur 60 Gütern gibt es mehr verschiedene Strategien als Atome im gesamten Universum, und kein Computer der Welt wird wohl jemals in der Lage sein, sie alle durchzuprobieren. Deshalb sucht man nach einer Strategie, die vielleicht nicht optimal, aber schnell zu finden ist und für beide Parteien zu einem zufriedenstellenden Ergebnis führt.
Das Verfahren, das Levine und Stange entwickelt haben, bezeichnen sie als Streichstrategie. Deren Grundprinzip besteht darin, dass der Letzte, der noch ein Gut wählen kann, bevor alles verteilt ist, das vom Konkurrenten am geringsten geschätzte Gut nimmt. Was aber bedeutet das? Angenommen, B ist derjenige, der den letzten Zug macht, und z das Gut, das von A am geringsten geschätzt wird. A wird dieses Gut z natürlich bis zum Schluss übriglassen, da die Wahl aller anderen Güter ihm eine höhere Punktzahl bringt. Wenn B sich an die Streichstrategie hält, wird auch er z erst bei seinem letzten Zug nehmen. Da sich dies sowohl A als auch B überlegen können, ist damit beiden von Anfang an völlig klar, dass B das Gut z mit seinem letzten Zug bekommt.
Das Teilen lässt sich aus diesem Grunde auch vereinfachen. Das Gut z wird von vornherein von der Liste gestrichen und B zum Schuss automatisch zugesprochen. Es gibt somit ein Gut weniger zu verteilen, und A ist jetzt der Letzte, der wählt. Wenn das Gut y dasjenige ist, was von den restlichen Gütern von B am geringsten geschätzt wird, dann wird B es bis zum Schluss übrig lassen. A wird es dann getreu der Streichstrategie mit seinem letzten Zug nehmen. Auch dies können sich beide Parteien von vornherein überlegen, so dass auch das Gut y von der Liste gestrichen werden kann und A automatisch bei seinem letzten Zug zugesprochen wird. Auf diese Art und Weise können sich die beiden Geschäftsleute vom letzten Zug aus Schritt für Schritt bis zum ersten Zug zurückhangeln.
Im Nash-Gleichgewicht
Ein Beispiel soll die Streichstrategie verdeutlichen. A und B wollen sich die vier Güter a, b, c und d teilen und haben sie mit a = (3, 3), b = (1, 2), c = (4, 1), d = (2, 4) bewertet. Dabei gibt die erste Zahl in jeder Klammer die Bewertung von A und die zweite die von B an. A darf zuerst wählen; folglich macht B den letzten Zug. Das Gut b wird von A am schlechtesten bewertet, also bekommt B es mit seinem letzten Zug und streicht es aus. Beim vorletzten Zug der Teilung bekommt A das Gut c, da es von B am schlechtesten bewertet wird, und streicht es aus. Auf der Liste stehen nun noch die Güter a und d. B ist jetzt am Zug und nimmt d, da es von den beiden Gütern auf der Liste von A schlechter bewertet wird. Somit bleibt für A im ersten Zug nur noch das Gut a. Insgesamt erhält A bei dem Verfahren 7 und B 6 Punkte.
Wenn schon eine Strategie nicht optimal sein kann, so sollte sie doch zumindest gut sein. In der Sprache der Spieltheorie, der Disziplin der Mathematik, die sich mit Verfahren zur Entscheidungsfindung in Konfliktsituationen befasst, heißt das, die Strategien der beiden Geschäftsleute sollten ein Nash-Gleichgewicht bilden. Dies besagt, dass beide Geschäftsleute solche Strategien verfolgen sollten, dass es keinem der beiden einen Vorteil bringt, wenn er einseitig von seiner Strategie abweicht. Der Anreiz zum einseitigen Abweichen von den Strategien ist im Nash-Gleichgewicht also außerordentlich gering und bietet deshalb beiden Mitspielern ein recht hohes Maß an Sicherheit. Ein Spiel kann mehrere Nash-Gleichgewichte haben, aber in den meisten Fällen ist es nicht möglich, dasjenige zu finden, das für beide Mitspieler den höchsten Gewinn bringt.
Levine und Stange konnten nun beweisen, dass das Streichverfahren, wenn es von beiden Geschäftsleuten angewendet wird, ein Nash-Gleichgewicht bildet. Die Methode ist sogar besonders robust. Macht einer der beiden Geschäftsleute einen "Fehler" und weicht für einige Züge vom Streichverfahren ab, kann der andere dennoch getrost mit dem Streichverfahren weitermachen, denn auch für den Rest des Teilens bildet es für beide ein Nash-Gleichgewicht.
