Minimal-envy land division

Question

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.

Answer 1

If the number of citizens is large enough, such that the effect of one citizen changing his/her selection is negligible, then an envy-free division is equal to a Nash equilibrium in a congestion game.

Specifically, Igal Milchtaich's papers are relevant to this problem.

Additionally, Yonatan Aumann and Yair Dombb define several quantitative measures of unfairness: alpha-unproportionality, alpha-envy and alpha-inequitability, which may also be relevant.