Hill–Beck land division problem

The following variant of the fair cake-cutting problem was introduced by Ted Hill in 1983.^[1]

There is a territory D adjacent to n countries. Each country values the different subsets of D differently. The countries would like to divide D fairly among them, where "fair" means a proportional division. Additionally, the share allocated to each country must be connected and adjacent to that country. This geographic constraint distinguishes this problem from classic fair cake-cutting.

Formally, every country C_i must receive a disjoint piece of D, marked D_i, such that a portion of the border between C_i and D is contained in the interior of C_i ∪ D_i.

Impossibility and possibility

There are cases in which the problem cannot be solved:

1. If there is a single point to which two countries assign all their value (e.g. a holy place), then obviously the territory cannot be divided proportionally. To prevent such situations, we assume that all countries assign a value of 0 to all singular points.

2. If D is a square, there are 4 countries adjacent to the 4 sides of the square, and each country assigns all its value to the border at the opposite side, then every allocation that connects, say, the northern country with its desired southern border will make it impossible to connect the eastern country with its desired western border (as long as we are in a two-dimensional plane). To prevent such situations, we assume that all countries assign a value of 0 to the boundary of D.

In 1983, Hill proved that, if each single point in D has a value of 0 for all countries, and the boundary of D has a value of 0 for all countries, then there exists a proportional division with the adjacency constraint. His proof was only existential – no algorithm was described.^[1]

Algorithm

4 years later, Anatole Beck described a protocol for attaining such a division.^[2] In essence, the protocol is an elaboration of the Last diminisher protocol. It lets the countries bid for parts of D, gives the smallest bid to its bidder and divides the remainder among the remaining n − 1 countries. Some variations are needed to guarantee that the adjacency constraint is satisfied.

Simply-connected territory

When D is simply-connected, the following algorithm is used.

1. Find a Riemann mapping h that maps D to the unit disc, such that for all countries, the value of every circle centered at the origin is 0 and the value of every radius from the origin is 0 (the existence of such an h is proved by a counting argument).

2. Ask each country to draw, on the unit disc map h(D), a disc centered at the origin with a value of 1/n. This is possible thanks to the condition that the value of all circles centered at the origin is 0.

3. Find the disc D₁ with the smallest radius, r₁.

There are two cases.

Single winner

4. If D₁ was drawn by only a single country, say C_i, then give this disc to C_i. Its value for the other countries is strictly less than 1/n, so we can give to C_i a small additional piece connecting it to its allocated disc.

To do this, draw a sector connecting D₁ to the image of the boundary between C_i and D. Let each country (other than C_i) trim this sector such that all countries value the union of the disc and the sector as at most 1/n. This is possible thanks to the condition that the value of all radii from the origin is 0. Allocate to C_i the union of D₁ and the trimmed sector.

The remainder is simply-connected and has a value of at least (n − 1)/n to the remaining n − 1 countries, so the division can proceed recursively in step 1.

Many winners

If D₁ was drawn by k>1 countries, then some more sophisticated auctions are required in order to find a country to which we can give a disc and a connecting sector.

5. pick an arbitrary winner country and call it the declarer, C₁. Let it add a sector connecting D₁ to its current territory, and let the other countries trim that sector such that:

For every non-winning country, the value of D₁ plus the trimmed sector is at most 1/n (this is possible because the value of D₁ for them is less than 1/n).
For every winning country, the value of the trimmed sector alone is less than 1/n.

6. Let each of the winning countries bid a new radius r (smaller than its first bid), such that the value of the trimmed sector plus the disc of radius r is exactly 1/n. Select the smallest such disc, D₂. Again there are two cases:

If C₁ is one of the countries bidding D₂, then just give it D₂ (which is slightly smaller than the original D₁) and the connecting sector. C₁ agreed that the value is 1/n and the other countries agreed that it is at most 1/n, so we can proceed recursively at step 1.

Otherwise, C₁ agrees that the total value of D₂ plus the connecting sector is less than 1/n. All non-winners must also agree to this since D₂ is smaller than D₁. So C₁ and all other countries that agree to this are removed from the set of winners.

7. From among the remaining winners, pick a new declarer C₂. Let it add another sector connecting D₂ to its current territory, and let the other countries trim that sector as in step 5.

Note that now D₂ is connected to two different territories – C₁ and C₂. This is a problem because it makes the remaining territory disconnected. To solve this, C₂ is allowed to take another sector, this time of length less than 1 so that it doesn't harm the connectivity.^[2] That third sector is again trimmed by all countries as in step 5. In return, C₂ is required to give up some part of the sector connecting D₂ to C₁, whose value is equal to the value of the third sector it received.

C₂'s candidate allocation now contains the following parts: D₂, a single sector of length 1 connecting D₂ to C₂, and two short sectors that do not reach the border of D. The value of this construction for C₂ is 1/n, its value for the non-winners is less than 1/n, and its value for the remaining winners is at most 1/n.

This process continues with the remaining winners, until only a single winner remains.

Finitely-connected territory

If the territory D is k-connected with a finite k, then the division can proceed by induction on k.

When k = 1, D is simply-connected and can be divided by the protocol of the previous section.

Otherwise (k > 1), mark the outer boundary of D by B₁ and its inner boundaries by B₂, ..., B_k.

Find a line L connecting the outer boundary B₁ to the inner boundary B_k, such that all countries value L as 0. This is possible by the following counting argument. There is an uncountable infinity of pairwise-disjoint lines connecting B₁ and B_k and contained in D. But the measure of D is finite, so the number of lines with a positive measure must be finite.

The set D \ L is (k − 1)-connected. Divide it recursively, then assign L arbitrarily to any country adjacent to it. This does not affect the fairness of the allocation since the value of L is 0 for all countries.

References

1 2 Hill, T. P. (1983). "Determining a Fair Border". The American Mathematical Monthly. 90 (7): 438. doi:10.2307/2975720. JSTOR 2975720.
1 2 Beck, A. (1987). "Constructing a Fair Border". The American Mathematical Monthly. 94 (2): 157. doi:10.2307/2322417. JSTOR 2322417.

For an additional solution to the problem, see: Webb, W. A. (1990). "A Combinatorial Algorithm to Establish a Fair Border". European Journal of Combinatorics. 11 (3): 301. doi:10.1016/s0195-6698(13)80129-1.

This article is issued from Wikipedia - version of the 2/10/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.