Last night at what started off as high tea but ended up as dinner (for me, at least), Baada and I shared a cake. The cake was delivered to our table along with a (rather sharp) knife. I used the knife to cut the cake into two, and Baada chose one of the two pieces (inexplicably he chose the smaller one). That way, we had achieved the most efficient method of splitting a piece of cake between two people.
It has been an interesting mathematical problem as to how to split a piece of cake between three people, since the above algorithm doesn’t work. The problem has been solved, but is rather complicated with several cases, involving one person cutting a piece, the second person trimming it and offering it to the third, followed by further complications. I won’t bother describing it further here. And then you have the problem of extending the solution to N people sharing a piece of cake.
But then, there is an elegant solution, after all, which I found in Alex Bellos‘s excellent book Alex Through the Looking Glass a couple of days back. As Bellos describes,
One ingenious method invented in the 1960s, which can be used for any number of people, concerns a moving knife. The knife is positioned at the side of the cake and then moves very slowly across it. When someone shouts ‘STOP!’ the knife slices at that position. The person who shouted out receives the slice. The knife then continues for the remaining participants.
It is not hard to see how this works (it assumes that the players, unlike Baada last night, want the largest possible piece of cake while being fair). If you call too early, you end up with a smaller piece of cake than you’re entitled to, and so you wait. You call too late, and someone has already called for it. So with every player playing the optimal strategy, this moving knife strategy results in each person getting their fair share.
While reading this cake-cutting strategy, I got reminded of the Dutch auction. In such an auction, the house starts with a very high price, which drops slowly (represented by a clock, usually). And as the price drops, when one of the buyers is willing to pay the price at that moment, they bid for it, and the object gets sold at that price. While it is a “first price auction” and buyers may not disclose their true willingness to pay (in the hope of getting the item for a lower price), the advantage is that it’s quick, and hence used for auctioning things such as flowers.
It works the same way as the cake-cutting algorithm in that if there is a well-defined value for the object being auctioned (this is rarely the case in practice), it makes sense to bid exactly at the point when the price equals this well-defined value.
This method of cutting cakes and auctioning flowers is also similar to how chit funds work in India. In a chit fund, you have N people who invest money into a pot at N different points in time. Each time, the money thus collected is auctioned to the person who needs it the most, and the price of the auction is determined by the amount that the person is willing to “let go” of the maximum amount. This amount that is thus let go of is distributed to the other participants (with the house taking a commission).
This is exactly similar to the cake cutting case. Think about it!
So it is very interesting that a fundamental feature of Indian homegrown finance, the chit fund, draws from important concepts in maths and game theory. We’re truly great!