Hobby–Rice theorem explained

In mathematics, and in particular the necklace splitting problem, the Hobby–Rice theorem is a result that is useful in establishing the existence of certain solutions. It was proved in 1965 by Charles R. Hobby and John R. Rice;^[1] a simplified proof was given in 1976 by A. Pinkus.^[2]

The theorem

Define a partition of the interval [0,1] as a division of the interval into

n +1 subintervals by as an increasing sequence of n numbers:0= z _{0} < \underbrace{z _{1} < ... b < z _{n}} < z _{n+1} = 1

Define a signed partition as a partition in which each subinterval

i has an associated sign \delta _{i} :\delta _{1,...c,\delta} _{k+1} \in\left\{ +1 , -1 \right\}

The Hobby–Rice theorem says that for every n continuously integrable functions:

g _{1,...c,g} _{n\colon[0,1]\longrightarrowR}

there exists a signed partition of [0,1] such that:

\sum ^{n +1} _{i =1} \delta _{i\int} ^{z _{i}} ^{z _{i-1}} g _{j(z)dz=0for1\leq} j\leq n.

(in other words: for each of the n functions, its integral over the positive subintervals equals its integral over the negative subintervals).

Application to fair division

The theorem was used by Noga Alon in the context of necklace splitting^[3] in 1987.

Suppose the interval [0,1] is a cake. There are n partners and each of the n functions is a value-density function of one partner. We want to divide the cake into two parts such that all partners agree that the parts have the same value. This fair-division challenge is sometimes referred to as the consensus-halving problem.^[4] The Hobby–Rice theorem implies that this can be done with n cuts.

Notes and References

1. Hobby. C. R.. John R. Rice (professor). Rice, J. R.. A moment problem in L₁ approximation. Proceedings of the American Mathematical Society. 16. 665–670. 10.2307/2033900. 2033900. 4. American Mathematical Society. 1965.
2. Pinkus. Allan. A simple proof of the Hobby–Rice theorem. Proceedings of the American Mathematical Society. 60. 1976. 82–84. 10.2307/2041117. 2041117. 1. American Mathematical Society. free.
3. Alon. Noga. Splitting Necklaces. Advances in Mathematics. 1987. 63. 247–253. 10.1016/0001-8708(87)90055-7. 3. free.
4. . Consensus-halving via theorems of Borsuk-Ulam and Tucker . . 45 . 15–25 . 2003 . 10.1016/S0165-4896(02)00087-2 . 10419/94656 .