Posts Tagged ‘Fair division’

Can a computer do envy-free divison?

In Education, Interdisciplinary Science on July 28, 2012 at 10:15 PM

We have all studied division. In the world of simple mathematics, 8 divided by 2 is always 4.  But what about dividing a cake into 2 equal pieces? A computer program can always divide 8 by 2 and give 4 as answer, but can a computer program divide a cake into 2 equal pieces? Let us make it a bit more complicated. Say the cake has to be divided between persons A and B and in such a way that neither of them feels that the other person got more. This means that neither A or B will envy the share received by the other. So here the notion of equal division has to be understood in the context of the result leading to an envy-free solution. This is the subject of “Fair Division” also known as cake cutting problem. It is studied in politics, mathematics, economics and the like. Methods and algorithms have been proposed to achieve fair division but all require inputs from the parties involved in the division at different stages of the procedure. Note that these inputs need not be disclosed as these could be the feelings/assumptions/conclusions running in the minds of the parties involved. This means that different inputs at different stages can lead to different outcomes. Does it remind of “Observer Effect” in Physics? Yes. The inputs(observation of a current state of division) by a party affects the outcome of division (phenomenon being observed). It is impossible (?) for a computer to solve a problem of this type entirely on its own. Such problems arise routinely in allocation of goods, dispute resolution, negotiation of  treaties etc.

Borrowing terms from economics, a number can be treated as ‘a homogeneous good’ while a cake is essentially ‘a heterogeneous good’ as different parts of it can taste different. Hence, its envy-free division is far more complicated. If you are interested, try to read “Fair Division-From cake-cutting to dispute resolution“, an excellent book by Steven J. Brams (political scientist) and Alan D. Taylor (mathematician).