10 Wahlen am Nordpol

© Frauke Jansen, MATH+

Autor*in: Emil Junker (HU Berlin)

Aufgabe

In der Geschenkeverpackungsabteilung des weihnachtlichen Verwaltungsbüros am Nordpol arbeiten die zehn Elfen Arne, Bea, Coco, Dante, Enzo, Fina, Greta, Henri, Ida und Joris.

Jedes Jahr vor Weihnachten wird aus den Reihen der Angestellten der Geschenkeverpackungsabteilung das sogenannte Verpackungskomitee gebildet. Das Verpackungskomitee ist dafür zuständig, das sachgemäße Einpacken und Verzieren aller Weihnachtsgeschenke zu überwachen. Für die Elfen ist es einerseits eine große Ehre, Teil des Verpackungskomitees zu sein. Sie dürfen dann nämlich entscheiden, welche Farben und Muster für das Geschenkpapier verwendet werden. Andererseits ist die Arbeit im Verpackungskomitee auch mit jeder Menge Stress und Überstunden verbunden, weshalb nicht alle unbedingt Lust darauf haben. Um diesem Umstand gerecht zu werden, ist ein spezielles Verfahren für die Wahl der Mitglieder des Verpackungskomitees vorgeschrieben:

Die zehn Elfen der Abteilung erhalten jeweils einen Wahlzettel, auf den sie die Namen aller Elfen schreiben, die ihrer Meinung nach im Komitee sein sollen. Alle Elfen dürfen beliebig viele Namen auf ihre Zettel schreiben – jeden Namen allerdings höchstens ein Mal. Es ist auch erlaubt, den eigenen Namen auf den Zettel schreiben, falls man selbst Mitglied des Komitees sein möchte. Nachdem alle Elfen ihre Wahlzettel ausgefüllt haben, beginnt die öffentliche Auszählung. Dabei gelten die folgenden Regeln:

• Elfen, die ihren eigenen Namen auf ihren Stimmzettel schreiben, werden genau dann ins Komitee gewählt, wenn sie noch von mindestens drei anderen Elfen vorgeschlagen werden.
• Elfen, die ihren eigenen Namen nicht auf ihren Stimmzettel schreiben, werden genau dann ins Komitee gewählt, wenn sie noch von mindestens fünf anderen Elfen vorgeschlagen werden.

Es ist ein offenes Geheimnis, dass der Weihnachtsmann nicht besonders viel von diesem Wahlverfahren hält. Am liebsten würde er allein entscheiden, aus welchen Elfen sich das Verpackungskomitee zusammensetzt. Aber es ist nun mal Vorschrift, dass die Elfen selbst darüber abstimmen. Der Weihnachtsmann will dennoch sichergehen, dass unter den Mitgliedern des Verpackungskomitees wenigstens ein paar fähige Köpfe sind. Einen Tag vor dem Wahltermin fragt er alle zehn Abteilungselfen, wen sie für das Komitee wählen werden, und erhält folgende Antworten:

1. Arne möchte, dass das Komitee aus ihm selbst, Dante, Greta und Joris besteht.
2. Bea sagt, sie wird nur sich selbst als Mitglied vorschlagen.
3. Coco hat vor Arne, Bea und Joris als Mitglieder des Komitees zu wählen.
4. Dante ist der Ansicht, dass das Komitee aus Coco, Enzo und Greta bestehen sollte.
5. Enzo sagt, er wird sich selbst, Fina, Henri und Joris wählen.
6. Fina ist der Meinung, dass Dante, Greta und Joris das Komitee bilden sollten.
7. Greta möchte das Komitee mit sich selbst, Coco, Enzo und Henri besetzen.
8. Henri hat vor sich selbst, Dante, Greta und Joris für das Komitee vorzuschlagen.
9. Ida findet, dass nur sie selbst, Coco und Joris als Mitglieder geeignet sind.
10. Joris plant Bea, Enzo, Henri und Ida für das Komitee zu wählen.

„Oh nein“, denkt der Weihnachtsmann, nachdem er die Antworten eingeholt hat. „So wie es aussieht, werden am Ende viel zu wenige kompetente Elfen im Komitee sein. Das gefährdet die rechtzeitige Auslieferung der Geschenke! Da muss ich unbedingt einschreiten!“

Zum Glück kennt der Weihnachtsmann seine Angestellten genau und weiß, wie er sie manipulieren kann – nämlich indem er sie mit leckeren Nussplätzchen aus der Weihnachtsbäckerei besticht. Bestochene Elfen werden jeweils genau so wählen, wie der Weihnachtsmann es ihnen vorschreibt. Nicht bestochene Elfen werden am Wahltag genau so wählen wie zuvor angekündigt, d. h. wie in Liste (a)–(j) angegeben.

Der Weihnachtsmann möchte, dass das Verpackungskomitee aus den Elfen Arne, Coco, Dante, Enzo und Henri besteht. Die Elfen Bea, Fina, Greta, Ida und Joris hingegen will der Weihnachtsmann nicht im Komitee haben.

Was ist die kleinstmögliche Anzahl an Elfen, die der Weihnachtsmann bestechen muss, um dieses Ziel zu erreichen?

Antwortmöglichkeiten:

1. Die kleinstmögliche Anzahl an Elfen, die der Weihnachtsmann bestechen muss, ist 1.
2. Die kleinstmögliche Anzahl an Elfen, die der Weihnachtsmann bestechen muss, ist 2.
3. Die kleinstmögliche Anzahl an Elfen, die der Weihnachtsmann bestechen muss, ist 3.
4. Die kleinstmögliche Anzahl an Elfen, die der Weihnachtsmann bestechen muss, ist 4.
5. Die kleinstmögliche Anzahl an Elfen, die der Weihnachtsmann bestechen muss, ist 5.
6. Die kleinstmögliche Anzahl an Elfen, die der Weihnachtsmann bestechen muss, ist 6.
7. Die kleinstmögliche Anzahl an Elfen, die der Weihnachtsmann bestechen muss, ist 7.
8. Die kleinstmögliche Anzahl an Elfen, die der Weihnachtsmann bestechen muss, ist 8.
9. Der Weihnachtsmann muss niemanden bestechen. Wenn alle Elfen so abstimmen wie angekündigt, besteht das Verpackungskomitee bereits aus den vom Weihnachtsmann gewünschten Mitgliedern.
10. Das Ziel des Weihnachtsmanns ist unmöglich zu erreichen, egal wie viele Elfen er besticht.

Samstagsbonus: Für diese Aufgabe gibt es eine Zeitgutschrift von 48 Stunden.

Im Rahmen seiner Master-Arbeit beschäftigte sich Emil Junker mit sogenannten Group-Identification-Problemen. Dabei betrachtet man eine Menge von Individuen (in unserem Beispiel die Elfen) und möchte ermitteln, welche Teilmenge davon auf eine bestimmte Weise „qualifiziert“ ist. Jedes Individuum in der Menge hat eine Meinung dazu, welche Individuen qualifiziert sind und welche nicht. Anschließend gibt mehrere verschiedene Regeln, die man zur Auswertung benutzen kann. Konkret beschäftigte er sich mit der Manipulierbarkeit von Group Identifications durch bribery– oder control-basierte Angriffe. Dabei versucht ein außenstehendes Individuum (der Weihnachtsmann), ein bestimmtes Ziel zu erreichen; zum Beispiel dass am Ende der Auswertung bestimmte Individuen als qualifiziert eingestuft werden. Dieses Ziel kann es etwa durch Bestechung von Individuen oder durch Hinzufügen von zusätzlichen wahlberechtigten Individuen versuchen zu erreichen. Für Emil Junker ist insbesondere die Durchführbarkeit und die Berechnungskomplexität solcher Angriffe von Interesse.