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. Each citizen in each state has a subjective 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 half 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$ of each district. This gives each state up to $k$ disconnected pieces.

So the interesting question is: how to divide the land fairly, such that each state receives a minimum number of disconnected pieces?