Hill–Beck land division problem

Last updated July 17, 2021

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:

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.
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.

Related Research Articles

Circle Simple curve of Euclidean geometry

A circle is a shape consisting of all points in a plane that are at a given distance from a given point, the centre; equivalently it is the curve traced out by a point that moves in a plane so that its distance from a given point is constant. The distance between any point of the circle and the centre is called the radius. This article is about circles in Euclidean geometry, and, in particular, the Euclidean plane, except where otherwise noted.

The Mandelbrot set is the set of complex numbers $for which the function does not diverge when iterated from , i.e., for which the sequence , , etc., remains bounded in absolute value. Its definition is credited to Adrien Douady who named it in tribute to the mathematician Benoit Mandelbrot, a pioneer of fractal geometry.$

In complex analysis, the Riemann mapping theorem states that if U is a non-empty simply connected open subset of the complex number plane C which is not all of C, then there exists a biholomorphic mapping f from U onto the open unit disk

A sphere is a geometrical object in three-dimensional space that is the surface of a ball.

In mathematics, mathematical physics and the theory of stochastic processes, a harmonic function is a twice continuously differentiable function f : U → R, where U is an open subset of Rⁿ, that satisfies Laplace's equation, that is,

In mathematics, a power series is an infinite series of the form

In mathematics, an analytic function is a function that is locally given by a convergent power series. There exist both real analytic functions and complex analytic functions. Functions of each type are infinitely differentiable, but complex analytic functions exhibit properties that do not generally hold for real analytic functions. A function is analytic if and only if its Taylor series about x₀ converges to the function in some neighborhood for every x₀ in its domain.

In complex analysis, a branch of mathematics, analytic continuation is a technique to extend the domain of definition of a given analytic function. Analytic continuation often succeeds in defining further values of a function, for example in a new region where an infinite series representation in terms of which it is initially defined becomes divergent.

The Gauss–Bonnet theorem, or Gauss–Bonnet formula, is a relationship between surfaces in differential geometry. It connects the curvature of a surface to its Euler characteristic.

In mathematics, a ball is the volume space bounded by a sphere; it is also called a solid sphere. It may be a closed ball or an open ball.

In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.

In mathematics, the spectral radius of a square matrix or a bounded linear operator is the largest absolute value of its eigenvalues. It is sometimes denoted by ρ(·).

In complex analysis a complex-valued function ƒ of a complex variable z:

In the mathematical field of complex analysis, a branch point of a multi-valued function is a point such that the function is discontinuous when going around an arbitrarily small circuit around this point. Multi-valued functions are rigorously studied using Riemann surfaces, and the formal definition of branch points employs this concept.

In geometry, the area enclosed by a circle of radius $r$ is $π r 2$ . Here the Greek letter $π$ represents the constant ratio of the circumference of any circle to its diameter, approximately equal to 3.1416.

Freeform surface modelling is a technique for engineering freeform surfaces with a CAD or CAID system.

In mathematics, subharmonic and superharmonic functions are important classes of functions used extensively in partial differential equations, complex analysis and potential theory.

In graph theory, a random geometric graph (RGG) is the mathematically simplest spatial network, namely an undirected graph constructed by randomly placing N nodes in some metric space and connecting two nodes by a link if and only if their distance is in a given range, e.g. smaller than a certain neighborhood radius, r.

In mathematics, a unit sphere is simply a sphere of radius one around a given center. More generally, it is the set of points of distance 1 from a fixed central point, where different norms can be used as general notions of "distance". A unit ball is the closed set of points of distance less than or equal to 1 from a fixed central point. Usually the center is at the origin of the space, so one speaks of "the" unit ball or "the" unit sphere. Special cases are the unit circle and the unit disk.

Fair cake-cutting is a kind of fair division problem. The problem involves a heterogeneous resource, such as a cake with different toppings, that is assumed to be divisible – it is possible to cut arbitrarily small pieces of it without destroying their value. The resource has to be divided among several partners who have different preferences over different parts of the cake, i.e., some people prefer the chocolate toppings, some prefer the cherries, some just want as large a piece as possible. The division should be unanimously fair - each person should receive a piece that he or she believes to be a fair share.

References

1 2 Hill, T. P. (1983). "Determining a Fair Border". The American Mathematical Monthly. 90 (7): 438–442. doi:10.2307/2975720. JSTOR 2975720.
1 2 Beck, A. (1987). "Constructing a Fair Border". The American Mathematical Monthly. 94 (2): 157–162. 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–304. doi: 10.1016/s0195-6698(13)80129-1 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[Hill-1] 1 2 Hill, T. P. (1983). "Determining a Fair Border". The American Mathematical Monthly. 90 (7): 438–442. doi:10.2307/2975720. JSTOR 2975720.

[Beck-2] 1 2 Beck, A. (1987). "Constructing a Fair Border". The American Mathematical Monthly. 94 (2): 157–162. doi:10.2307/2322417. JSTOR 2322417.

[1]

[2]