Jump to content

Hobby–Rice theorem

From Wikipedia, the free encyclopedia

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

[edit]

Define a partition of the interval [0,1] as a division of the interval into subintervals by as an increasing sequence of numbers:

Define a signed partition as a partition in which each subinterval has an associated sign :

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

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

(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

[edit]

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.

References

[edit]
  1. ^ Hobby, C. R.; Rice, J. R. (1965). "A moment problem in L1 approximation". Proceedings of the American Mathematical Society. 16 (4). American Mathematical Society: 665–670. doi:10.2307/2033900. JSTOR 2033900.
  2. ^ Pinkus, Allan (1976). "A simple proof of the Hobby–Rice theorem". Proceedings of the American Mathematical Society. 60 (1). American Mathematical Society: 82–84. doi:10.2307/2041117. JSTOR 2041117.
  3. ^ Alon, Noga (1987). "Splitting Necklaces". Advances in Mathematics. 63 (3): 247–253. doi:10.1016/0001-8708(87)90055-7.
  4. ^ F.W. Simmons and F.E. Su (2003). "Consensus-halving via theorems of Borsuk-Ulam and Tucker" (PDF). Mathematical Social Sciences. 45: 15–25. doi:10.1016/S0165-4896(02)00087-2. hdl:10419/94656.