Monday, August 13, 2012

Dubins-Spanier Moving-knife Method

This is one of the classic proportional procedures. It is proposed by L. E. Dubins and E. H Spanier back in 1961.

Given a group of \(n\) agents and a bar cake, a referee holds a knife parallel to edge of the cake and moves slowly across the whole cake from left to right. When an agent calls "cut", he will get the piece to the left of the blade. The claim is, in this way, the best strategy for agents is to call cut exactly at \(\frac{1}{n}\) position based on their own utility functions. For the last two agents, we do a cut-and-choose. This will give us a proportional allocation.

This procedure is based on one key assumption, that the agents are maximum risk averse. In other words, the agent care only about the maxmin value. Given this assumption, it is not hard to see that calling cut at \(\frac{1}{n}\) gives us the highest maxmin value.

As we can see earlier, the last two agents who call "cut" will get a piece larger than \(\frac{1}{n}\). Therefore, it is possible that all agents may wait for others to call "cut" at the same time, and thus it ends up no one calls throughout the whole procedure. To avoid this, we can simple make a random allocation if no one calls. Since agents are maximum risk averse, this will drive them to call "cut" in order to guarantee a \(\frac{1}{n}\) maxmin value.

Reference: L. E. Dubins, E. H. Spanier, 1961, How to Cut A Cake Fairly, The American Mathematical Monthly.

4 comments:

  1. Nice blog. Thank you for sharing. ASHOKA PACKERS AND MOVERS is well established reputed and professionally managed company having own branches and network all over India.
    Packers and Movers Hyderabad
    Packers and Movers Gurgaon
    Packers and Movers Pune
    Packers and Movers Delhi
    Packers and Movers Bangalore

    ReplyDelete
  2. تكثر عمليات نقل العفش بالرياض و بالمملكة داخل المدن وخارجها نظرا ً لكثرة تنقل المواطنين بين الوظائف أو لرغبتهم في تغيير المسكن لذلك يبحث الجميع عن أفضل شركة نقل عفش داخل الرياض أو شركة نقل عفش خارج الرياض إذا كان هذا عملائنا ما تبحثون عنه نحن نقدم لكم أرقي الخدمات وبأفضل الأسعار:
    شركة نقل اثاث بالدمام
    شركة نقل اثاث بالمدينة
    شركة نقل اثاث بالطائف
    شركة نقل عفش جدة

    ReplyDelete