Consensus-halving via theorems of Borsuk-Ulam and Tucker

TL;DR

The paper gives a constructive proof that any object can be divided into two portions that all \(n\) players regard as exactly equal, using at most \(n\) parallel cuts, via Tucker’s lemma and the Borsuk-Ulam theorem. It also derives applications to team-splitting, the Law of the Sea Treaty, and necklace splitting, while noting that only approximate solutions are constructible by finite discrete procedures.

Key findings

• For any object \(A\) and \(n\) continuous bounded preference measures, there exists a consensus-halving partition \(A_1,A_2\) with \(\mu_i(A_1)=\mu_i(A_2)\) for all \(i\); \(n\) cuts by parallel planes are sufficient, and in some cases best possible.
• A constructive proof of Tucker’s lemma yields an algorithm for locating an arbitrarily close approximate solution to any pre-specified error tolerance \(\varepsilon\), using at most \(n\) cuts rather than a number growing as \(\varepsilon\) decreases.
• The team-splitting theorem shows that \(2n\) explorers with two of each specialty can be divided into two teams of \(n\) (one of each type) and the territory divided so each explorer is satisfied, using no more than \(n\) straight cuts.
• Applications include replacing divide-and-choose in the Law of the Sea Treaty and giving a constructive solution to necklace splitting; for necklace splitting, choosing \(\varepsilon=1\) jewel lets the simplicial algorithm find an exact division.

Methods

• Theoretical/combinatorial-topology design: the object is modeled as a measurable bounded set in \(\mathbb{R}^2\) or \(\mathbb{R}^3\), infinitely divisible, with each player’s preferences given by a bounded continuous measure; additivity and positivity are not required.
• Existence is proved by applying the Borsuk-Ulam theorem to a function \(f:S^n\to\mathbb{R}^n\) whose \(i\)-th coordinate is player \(i\)’s measure of portion \(A_1\); constructive approximation uses Tucker’s lemma on a centrally symmetric triangulation of \(S^n\).
• The algorithm assigns labels to vertices according to the most distressed player and her preferred portion, then uses simplicial path-following algorithms (e.g., Freund-Todd) to find adjacent vertices with opposite labels.

Limitations

• Stated: no finite discrete procedure can produce an exact equal division, so the method gives approximate solutions up to a pre-specified tolerance; the measures must be continuous and bounded, forbidding point masses.
• Stated: the team-splitting result assumes no coalitions and continuous, not necessarily additive, measures; strategic manipulability and Pareto-efficiency are not meaningful when players are not assigned either resulting piece.
• Evident: the paper is purely theoretical and does not report empirical tests; the simplicial algorithms are not reviewed in detail, and implementation depends on interactive polling or fully specified preferences.