Project 3: The Flexible Pizza Company

You run a pizza business, and are looking to make a few extra dollars from your pizza sales. You've noticed the following opportunity: Often a couple will order a pizza to share, but each person has slightly different preferences for the toppings on the pizza. For example, a pizza might have pepperoni, olives and mushrooms, with one person's ideal mix of the proportions of each topping being (0.4,0.4,0.2) and the other person's ideal mix being (0.2,0.3,0.5). You make your pizzas in advance, so you cannot take a person's exact preference into account when you make the pizza. However, you have flexibility in how you cut the pizza once the customer arrives. Your goal is to cut the pizza in such a way that both people have a better proportion according to their respective preferences than they would get with a random central division. For that service, the customer is expected to pay an extra dollar. At the same time, since some people may not pay extra for this service, your baseline pizza should distribute the toppings uniformly, and there should be an equal amount of (i.e., total area covered by) each topping. The number of toppings on the pizza is given by a parameter $n \in \{2,3,4\}$.

The pizza is modeled as a circle of diameter 12 inches. Each topping unit is a circle of diameter 0.75 inches, that cannot overlap with other ingredients, and must fall entirely within the pizza circumference. Each pizza will have 24 total units of toppings, distributed evenly over the n toppings. When a pizza is cut, the toppings are cut too, so a portion of the circle may end up on each resulting slice.

A pizza cut is a series of four cuts each angled at 45 degrees to the previous one, and sharing a common intersection point. A central pizza cut is one where the shared intersection point is the center of the pizza.

For people who don't play the extra dollar, you won't invest any extra time on cut analysis, and will just instruct the server to make a random central pizza cut. For this group of customers, we'll assume that their goal is to get as even a distribution of toppings as possible. For a particular central pizza cut, we can calculate a uniformity measure U as follows. One person is assigned the odd numbered pieces counting around the pizza, and the other person is assigned the even numbered slices. The total amount of each topping for each person is calculated. U is then the sum of the absolute differences of the actual amount and the uniform (i.e., 12/n) amount for each person. The simulator will choose 10 random central pizza cuts, at various rotational angles, and record the average U value. Lower values for U are better (i.e., more uniform).

You have ten pizzas to start the evening, and ten customers will arrive in sequence, ready to pay the extra dollar for special service. When a couple decides to utilize your cutting service, they will tell you their preferred proportions. In response, you will choose a pizza among your remaining pizzas, and a pizza cut of that pizza to achieve proportions that match the preferences of the customers. Your key insight here is that your pizza cut does not need to be central. In particular, you can use the Pizza Theorem to cut the pizza off-center, while still guaranteeing that the total area of the odd slices matches the total area of the even slices. You have flexibility in considering the position of the cut, and the rotated position of the pizza. We'll assume that the first person gets the odd slices and the other gets the even slices, counting clockwise from the reference cut (the simulator will provide details).

The person's preferred amounts can be calculated from their preferred proportions by multiplying by 12. For each person, the absolute difference between the preferred and actual amounts is calculated for each topping, and added, to get a closeness metric C. For each person, the absolute difference between the preferred and uniform (i.e., 12/n) amounts is calculated for each topping, and added, to get a baseline metric B. Your player earns a score of S=B-C, corresponding to the improvement you made by cutting the pizza in a special way.

The distribution of preferences is generated by the simulator, and is unknown to the player in advance. In fact, we'll ask groups to come up with interesting preference distributions to use for the project. Despite not knowing the distribution in advance, the player can start the game by doing some market research, obtaining 100 randomly generated preference pairs before making any pizzas. Once the game starts, the preferences will be drawn from the same distribution.

At this point, the player builds ten pizzas according to the specifications above for the provided value of n. Once all ten pizzas have been submitted to the simulator, the simulator provides ten customers, one at a time, to the player. The player responds with a pizza choice and a cut position and rotation angle. The simulator will calculate the score S for each pizza, and add them to get a total. The simulator will also identify the average uniformity U for each pizza.

The uniformity U and the score S are two dimensions of success, and there may be trade-offs involved. For example, if U is allowed to grow, S might improve. U represents a penalty applied to customers who don't pay the extra dollar, while S represents a benefit to customers who do; thus the trade-off depends on how popular the cutting feature becomes. Thus you might analyze the problem under different assumptions about the popularity.

We'll run a tournament at the end of the project, for various preference distributions and values of n.