The costumes looked great. The bags are stuffed with goodies. But the scariest part of Halloween is just getting started: dividing the spoils of trick-or-treating.
Perhaps the family employed a divide-and-conquer strategy for the annual door-to-door candy heist, but one group came up a little light in the loot sack. Or maybe it’s an occasion for teaching the kids about teamwork and sharing. Either way, there’s a massive pile of candy that needs to be allocated to multiple goblins and ghouls.
So what’s the best way to split the stash without causing a disturbance that could raise the dead?
Vasilis Gkatzelis, PhD, a computer science professor in Drexel’s College of Computing & Informatics — who specializes in using game theory for problem solving and developing algorithms for fair resource allocation — has some tips for equitable candy allotment that could help you have a happier Halloween.
“IF THE CANDY WERE ALL OF THE SAME KIND, THEN THE PROBLEM OF DIVIDING CANDY AMONG CHILDREN IN A FAIR WAY AMOUNTS TO GIVING EVERY CHILD THE SAME NUMBER OF CANDIES,” GKATZELIS SAID. “HOWEVER, THE PROBLEM BECOMES MORE COMPLICATED WHEN THERE IS DIFFERENT TYPES OF CANDY, AND EVEN MORE DIFFICULT WHEN THE PREFERENCES OF THE CHILDREN OVER THE CANDY MAY BE DIFFERENT. A FAIR ALGORITHM FOR THIS PROBLEM NEEDS TO DECIDE HOW TO DIVIDE THE CANDY AMONG THE CHILDREN, AND THIS DECISION MAY NEED TO BE DIFFERENT, DEPENDING ON THE CHILDREN’S PREFERENCES.”
For two little monsters:
Pick a “divider” and “chooser”
This is a pretty common solution that also works well for carving up baked goods.
- Assign the roles of “divider” and “chooser” at random.
- Have the divider split the pile into two even groups.
- The chooser gets to pick the pile that he or she prefers, with the other pile going to the divider.
“If the divider values both groups equally, then both children’s value for the candy that they received is at least half as much as their value for all their candy, and also neither child envies the other. Note, however, that the chooser may get exactly half of her total value, whereas the divider may get much more than that. Therefore, to be fair, the parent should always assign these two roles at random!”
For three (or more) spirits:
Use the “method of the markers”
- First, place all the candy in a line at random.
- You will then need a set of objects that the children can use as place markers (different colored straws, pieces of string or numbered popsicle sticks all work nicely for this).
- Have each child place one marker at the end of the line, and the rest of their markers on the line with the goal of dividing the candy into equally desirable parts. The number of parts needs to be the same as the number of children, so the total number of markers that each child needs to place is also equal to the number of children. Tell the children that they are guaranteed to get at least one of these parts, so they should try to divide the candy as evenly as possible.
- Finally, to allocate the candy scan the line from left to right. When you get to the first marker, give the portion from the beginning of the line up to the marker to the child that placed that marker there. After removing the first child’s markers, keep scanning from left to right, until you have seen two markers belonging to the same child. This child gets all the candy that lies between these two markers. Remove this child’s markers, as well as all the markers that you have already scanned over, and repeat this process until all of the children have been assigned a portion of candy.
- If, after these steps, the number of leftover candy is significant, you can place it in a new line and repeat the same steps. Otherwise, just consider the leftovers your reward for taking the kids trick or treating.
If you’re a little confused, Gkatzelis offers this illustration of three children, Alice, Bob and Cindy, splitting up eight pieces of candy.
Alice gets three pink straws to use as markers, Bob gets three blue, and Cindy gets three green ones, and they place them on the line of candy as follows:
“The way Alice placed her three straws means that she would be equally happy if she received a Twix and Hershey’s bar, or a Skittles, Reese’s, and KitKat, or if she received the MilkyWay, Snickers, and Crunch.
Similarly, the straws of Bob and Cindy divide the eight candy into three parts that, based on their own preferences, are of equal value.
Starting from left to right, the first marker that we find is Alice’s, so we give Alice the Twix and Hershey’s.
Then, we remove Alice’s other straws and continue scanning from left to right until we see two of Cindy’s straws (the one after the Reese’s and the one after the MilkyWay); this means that Cindy gets the Kitkat and MilkyWay.
Finally, after removing all of Cindy’s straws, as well as the one of Bob’s straws that we have scanned over already (the one after the Skittle’s), we continue scanning until we see Bob’s two remaining markers — according to their placement, Bob should get the Crunch. And the leftovers are the Skittle’s, the Reese’s, and the Snickers — enjoy!”
Game theory, the study of mathematical models of conflict and cooperation between rational decision-makers, is particularly useful at moments like this, according to Gkatzelis, because all the participants are trying to maximize their own happiness. In these exercises, the children don’t know which portion of the candy they’ll be getting (you can even have them place their markers in secret, if you’ve tried this type of thing before, so they don’t know how the others placed their markers) so it’s in their best interest to be as fair as possible when dividing it. Though, it’s hard to say whether they will be “rational decision-makers” after a night of trick-or-treating.
Gkatzelis’ research looks at the design of computer algorithms that can be used to equitably solve problems that are even bigger than splitting the Halloween candy haul. Learn more about his work.
For media inquiries contact Britt Faulstick, bef29@drexel.edu or 215.895.2617.
This article was first published on Drexel News Blog