Skip to content

10 Elections at the North Pole

© Frauke Jansen, MATH+

Author: Emil Junker (HU Berlin)

Challenge

The ten elves Arne, Bea, Coco, Dante, Enzo, Fina, Greta, Henri, Ida, and Joris work in the gift wrapping department of the Christmas administration office at the North Pole.

Every year before Christmas, from among the employees of the gift wrapping department, the so-called wrapping committee is formed. The wrapping committee is responsible for overseeing the proper wrapping and decoration of all Christmas gifts. On the one hand, it is a great honour for the elves to be part of the wrapping committee. After all, they get to decide which colours and patterns to use for the wrapping paper. On the other hand, working on the wrapping committee also involves a lot of stress and overtime, and not everyone is up for this task. Hence, the election of the members of the wrapping committee has to follow a particular procedure:

The ten elves in the department are each given a ballot on which they write the names of all the elves they think should be on the committee. Everyone is allowed to write as many names as they wish on their ballots—each name, however, not more than once. It is also allowed to write one’s own name on the ballot if one wants to be a member of the committee.

After all elves have filled out their ballots, the public count begins for which the following rules apply:

  • Elves who write their own name on their ballot will be elected to the committee if and only if they are proposed by at least three other elves.
  • Elves who do not write their own name on their ballot will be elected to the committee if and only if they are proposed by at least five other elves.

It is a well-known secret that Santa does not approve of this election process. He would prefer to choose the wrapping committee himself, but it is mandatory for the elves to vote on it themselves. Nonetheless, Santa wants to make sure that there are at least a few capable elves on the wrapping committee. Thus, one day before the election date, he asks all ten department elves who they will vote for and receives the following answers:

  1. Arne would like the committee to consist of himself, Dante, Greta, and Joris.
  2. Bea says she will propose only herself as a member.
  3. Coco plans to elect Arne, Bea, and Joris as members of the committee.
  4. Dante thinks that the committee should consist of Coco, Enzo, and Greta.
  5. Enzo says he will vote for himself, Fina, Henri, and Joris.
  6. Fina thinks Dante, Greta, and Joris should establish the committee.
  7. Greta wants the committee consist of herself, Coco, Enzo, and Henri.
  8. Henri plans to suggest himself, Dante, Greta, and Joris for the committee.
  9. Ida thinks that only herself, Coco, and Joris are suitable members.
  10. Joris plans to choose Bea, Enzo, Henri, and Ida for the committee.

“Oh no,” thinks Santa Claus after he gets the answers. “As it seems, there will be far too few competent elves on the committee. This will jeopardize the schedule of the gift deliveries! I’m going to have to intervene!”

Fortunately, Santa knows his employees very well and, in particular, how to manipulate them: he will bribe them with delicious nut cookies from the Christmas bakery. Elves who have been bribed will each vote exactly as Santa tells them to. Elves who have not been bribed will vote exactly as they have announced, i. e. as stated in the above list (a)–(j).

Santa wants the packing committee to consist of the elves Arne, Coco, Dante, Enzo, and Henri. In addition, Santa does not want the elves Bea, Fina, Greta, Ida, and Joris on the committee.

What is the minimum number of elves that Santa needs to bribe to achieve this goal?

Possible answers:

  1. The minimum number of elves that Santa needs to bribe is 1.
  2. The minimum number of elves that Santa needs to bribe is 2.
  3. The minimum number of elves that Santa needs to bribe is 3.
  4. The minimum number of elves that Santa needs to bribe is 4.
  5. The minimum number of elves that Santa needs to bribe is 5.
  6. The minimum number of elves that Santa needs to bribe is 6.
  7. The minimum number of elves that Santa needs to bribe is 7.
  8. The minimum number of elves that Santa needs to bribe is 8.
  9. Santa doesn’t have to bribe anyone. If all the elves vote as announced, the wrapping committee already consists of the members Santa wants.
  10. Santa’s goal is impossible to reach, no matter how many elves he bribes.

Saturday Bonus: For this challenge, you will get a time bonus of 48 hours.

Challenge as PDF

In the context of his master thesis, Emil Junker deals with so-called group identification problems. There, one considers a set of individuals (in our example the elves) and wants to determine which subset of them is “qualified” in a certain way. Each individual in the set has an opinion about which individuals are qualified and which are not. Subsequently, there are several different rules that one can use to evaluate. Specifically, Emil Junker is concerned with the manipulability of group identifications through bribery- or control-based attacks. Here, an outside individual (Santa) tries to achieve a certain goal; for example, that at the end of the evaluation certain individuals are classified as qualified. They may try to achieve this goal, for example, by bribing individuals or by adding additional eligible individuals. Of particular interest to Emil Junker is the feasibility and computational complexity of such attacks.