# Minimal-envy land division

There is a land divided to $D$ districts.

There are $C$ citizens.

We want to divide the land to the citizens, such that each citizen receives a single land-plot in a single district.

Each citizen prefers certain districts, however, the preference also depends on the size of plot. For example, Johnny prefers a plot of 1 dunam in the North to a plot of the 1 dunam in the South, however, he also prefers a plot of 1 dunam in the South to a plot of 0.5 dunams in the North.

Ideally, we would like to divide the land in an envy-free manner, such that no citizen thinks that the plot given to another citizen is better (according to his subjective preferences) than the plot given to him.

However, this is not always possible. For example, suppose there are 2 districts (North and South), each of size 1 dunam, and 3 citizens, all have the same preferences as Johnny. If two of them get a plot in the North and the third gets a plot in the South, then the first two get only 0.5 dunam each, and so they envy the third who gets 1 dunam. The other divisions are even worse (In the singular case where all citizens get 1/3 dunam in the North and the South remains empty, assume that it is invaded by a fourth citizen, so that all 3 citizens now envy the invader).

So, I am looking for a procedure that will minimize the envy - whatever that means.

Note that, in contrast to the standard envy-free cake-division algorithms, I am not interested in geometric cuts of the land - the division of land to districts is pre-determined, and each person can get a plot in only one district.

• Sounds like some form of assignment problem. However, you need to formalise "envy" -- "whatever that means" is a dead giveaway that you have an underspecified problem at your hands. – Raphael Mar 21 '13 at 10:34