The cake-cutting game is usually played between individuals. What if we try to play it between groups?
A certain land has to be divided between two states. There are $n$ citizens in each state. Each citizen in each state has a subjective continuous value measure over the land. How can the land be divided such that each citizen, in each state, believes that his/her state received at least $1/2$ of the land value?
Some simple observations:
- A solution with a single cut (giving each state a single connected piece) is not always possible. For example, if in each state there are citizens who want only the east and citizens who want only the west, then every single-cut division (using a north-south line, at least) will leave some citizens unsatisfied, feeling that their state has got no value at all. So we must allow multiple cuts (this is in contrast to cake-cutting between individuals, where a single-cut solution is always possible).
- If the valuations are piecewise-constant, i.e. the land can be partitioned to $k$ districts such that each citizen has a constant value measure over each district, then an easy solution is to give each state $1/2$ the area of each district. Every practical continuous value measure can be regarded as approximately piecewise-constant for sufficiently small pieces, so this can be regarded as a sufficient solution. The problem with it is that it gives each state $k$ disconnected pieces, and $k$ may be very large (even larger than the number of citizens).
So the interesting question is: how to divide the land fairly, such that each state receives only a small number of disconnected pieces? (e.g. a constant, or a function of the number of citizens).
Initially I thought of a variant in which only half of the citizens in each state should feel that the division is fair. This makes sense in democratic states, since the suggested division may be brought to a referendum in each state, and if at least half vote in favor of it, it is implemented. Under this assumption, it is possible to divide the land in a single cut (a single piece per state). But this does not generalize well to 3 or more states.