Cake cutting, Dutch auctions and chit funds

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!

Cab guys’ tales

I travel to and from work in the company-provided cab. It’s a fairly convenient system, offering you flexible timings, and routings that aren’t too bad. The overhead in terms of time of traveling by cab is about 15-20 minutes for a 40-minute journey, so I take it on most days.

Given a choice, I try to sit next to the driver – maybe that’s the most comfortable seat in an Indica, and it definitely is the best seat in a Sumo. On most occasions, I chat with the driver as he drives me, but sometimes I don’t have the opportunity – since the driver is too busy chatting on his mobile phone. Yeah, company rules forbid that, but I guess no one really complains, so these guys get away with being on the phone a lot of the time.

Most of the time, the conversation is about loans, and repayment. Most of it is about informal loans that people have lent each other. The amounts these guys lend each other – seen as a percentage of their income (which I’m guessing based on what one cab guy told me last year) is humongous! They make loans to each other of the order of a few months’ salaries, and it seems like these loans are in perpetual transition – between the cabbies and their friends.

I hear them shout, strategise, pacify, ideate, about these issues. And sometimes after they’ve hung up I talk to them about this. One conversation comes to mind. So there was this cabbie whose family had lost a lot of money by “investing” it in a chit fund. It was an “informal” (i.e. unregistered fund), and in the previous “round”, his family had invested and made a good return. So in this “round”, more members of the family invested in the fund. And the fund manager decamped with the money!

I remember telling him that it was a bad strategy putting all their investments with the same guy, and tried to explain to him the benefits of diversification. He replied saying that he didn’t want to invest in the chit fund (the one he lost money in) but family members forced him to invest along with them, calling him a “traitor” when he tried to diversify!! Strange.

Back then, I didn’t know how exactly chit funds work else I would’ve also told him that it was an especially bad idea for people from the same family to invest in the same chit fund. If you think about how a chit fund works, you are basically betting on the desperation for money among the other “members” of the fund. You are betting that someone else in the pool needs money so badly that they’re willing to forego a higher “discount” which will then come into your kitty. So with members of the family all putting money in the same fund, they were just betting against each other! So even if the fund “manager” hadn’t decamped, it’s unlikely they would’ve got a particularly significant return on their investment.