Optimum Pizza Slice
Three friends will be sharing three slices of pizza.
Pizza Slices:
Pizza 1: Four cheese.
Pizza 2: Chicken.
Pizza 3: Pineapple.
Three friends could share the slices in six possible ways:
Eventually answer is one of those possibilities.
How much do you want it?
Choosing a slice of pizza seems like a very basic procedure. Though, there are many factors behind this simple decision. First of all finance is involved. And obviously “preferences” is an important factor: Not everybody has the same taste for food.
Let’s add these factors to our pizza slice situation. I will assume that 6 dollars is paid in total for the pizza slices, and three friends Ali, Steve and Jane have preferences as follows:
- Ali’s first choice is four cheese. If he can’t get that, his second and third choices are chicken and pineapple in order.
- Steve’s first choice is chicken. His second and third choices are pineapple and four cheese in order.
- Jane’s first choice is also chicken. Her second and third choices are four cheese and pineapple respectively.
In such situation, how can these friends decide fairly who gets which slice for how much?
Rental Harmony Problem
Two (or more) friends decide to rent an apartment. Rooms of the apartment are different in sizes and in some other factors (getting sunlight, having its own bathroom and such). For years mathematicians showed great interest towards the problematic of this situation: How can the rent and rooms be divided?
In 2004, three Turkish scientists Atila Abdulkadiroglu, Tayfun Sönmez and Utku Ünver published a paper that had a solution for the rental harmony problem. This paper shows an ingenious auction algorithm for the solution. (In fact, a famous website that is created to solve rental harmony problems named Spliddit had used this algorithm for almost a decade.)
The Algorithm
- Roommates write their offers for every room in a closed envelope. For each roommate, total of the offers must be equal to the total rent of the apartment. (For instance, if the rent is 3000 dollars and total of the offers for each person must be equal to 3000 dollars.)
- Envelopes are opened in front of everyone. A room goes to its highest bidder.
- In the end, all the winner bids are added together. If it is equal to the rent, then winning bids are the amounts that are going to be paid. If it is exceeds or falls under the total rent, each offer gets to be corrected proportionally.
Answer to the Pizza Slices
We can use the auction algorithm in order to find a solution to the pizza slices problem. Assume that we have offers from Ali, Steve and Jane as follows:
Highest bids:
For the pizza 1 is Ali with 4 dollars.
For the pizza 2 is Steve with 4 dollars.
For the pizza 3 is Jane with 2 dollars.
Total of the winning bids is
4 + 4 + 2 = 10
which is higher than 6 dollars. Hence we have to correct the amounts that need to be paid for each of the friends:
In conclusion Steve and Ali would pay 2,4 dollars which is less than their offers. Jane would pay 1,2 dollars and it is also less than her offer. Auction algorithm helped these friends to select their pizza slices. The algorithm also helped them to pay less than what they were willing to. Hence, everyone is happy and envy-free with the conclusion.
M. Serkan Kalaycıoğlu
kmatematikatolyesi.com 