Cake cutting: Explicit examples for impossibility results
Pith reviewed 2026-05-25 13:19 UTC · model grok-4.3
The pith
In the BSS-RW model there exist explicit measures where no algorithm outputs an equitable connected cake division or a utilitarian welfare maximum.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
In the BSS-RW model there exist explicit couples of measures for which no algorithm outputs an equitable fair division with connected parts. There also exist explicit sets of measures for which no algorithm outputs a fair division which maximizes the utilitarian social welfare function. The proofs rely on Galois theory to establish the non-existence of the required algebraic solutions.
What carries the argument
The BSS-RW model of computation, which allows Robertson-Webb queries but limits operations to those of the Blum-Shub-Smale model, together with Galois theory applied to the minimal polynomials of candidate division points.
If this is right
- No procedure in the BSS-RW model can guarantee an equitable connected division for every possible pair of measures.
- Maximization of utilitarian social welfare is impossible in the BSS-RW model for certain explicitly described collections of measures.
- Because every known Robertson-Webb algorithm can be rewritten inside the BSS-RW model, the new impossibility statements apply to all such algorithms.
- Galois theory supplies a systematic way to construct further explicit counterexamples for other fairness notions inside the same computational model.
Where Pith is reading between the lines
- The results indicate that certain fairness properties may require computational operations outside the algebraic closure, such as solving irreducible polynomials of degree five or higher.
- The same Galois-theoretic technique could be used to produce explicit impossibilities for other allocation problems that combine queries with algebraic operations.
- If the model were enlarged to permit a broader class of operations, the identified barriers for these particular measures might no longer hold.
- The approach links algebraic computability directly to the existence of fair divisions, opening a route to classify which fairness criteria remain tractable under restricted arithmetic.
Load-bearing premise
The BSS-RW model correctly captures the computational power available to any mediator and that Galois theory applies directly to prove non-existence of the required algebraic solutions for the chosen explicit measures.
What would settle it
An explicit algorithm expressed in the BSS-RW model that produces an equitable connected division for one of the paper's example measure pairs, or a direct computation of the Galois group of the associated polynomial showing that the extension degree is solvable by radicals.
read the original abstract
In this article we suggest a model of computation for the cake cutting problem. In this model the mediator can ask the same queries as in the Robertson-Webb model but he or she can only perform algebraic operations as in the Blum-Shub-Smale model. All existing algorithms described in the Robertson-Webb model can be described in this new model.We show that in this model there exist explicit couples of measures for which no algorithm outputs an equitable fair division with connected parts.We also show that there exist explicit set of measures for which no algorithm in this model outputs a fair division which maximizes the utilitarian social welfare function.The main tool of our approach is Galois theory.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces a BSS-RW computational model for cake cutting that augments the standard Robertson-Webb query model with Blum-Shub-Smale algebraic operations (+, *, /, sign tests). It claims to exhibit explicit pairs of measures on [0,1] for which no algorithm in this model produces an equitable division into connected pieces, and explicit collections of measures for which no algorithm maximizes utilitarian social welfare; Galois theory is the central tool used to establish these non-existence results.
Significance. If the central claims are correct, the work supplies the first explicit, concrete counterexamples to algorithmic existence inside a natural hybrid model that already contains all known RW procedures. The emphasis on explicit measures and the deployment of Galois theory to obtain non-computability results would constitute a genuine technical contribution to the literature on fair-division complexity, provided the reduction from Galois non-solvability to the absence of any finite adaptive BSS-RW procedure is fully rigorous.
major comments (2)
- [Section 3 (equitable division) and Section 4 (utilitarian welfare)] The manuscript does not supply a self-contained argument showing why a non-solvable Galois group on an auxiliary polynomial precludes every possible finite adaptive sequence of RW queries followed by field operations. Because each RW query can return a value that enlarges the base field in a query-dependent way, it is not immediate that the fixed polynomial considered in the Galois-theoretic step captures all reachable extensions; this step is load-bearing for both main theorems.
- [Definition of the explicit couples (around the statement of Theorem 1)] The explicit measures are introduced only after the model is defined, yet the text does not verify that the chosen density functions lie outside every possible BSS-RW-computable cut; a concrete walk-through of one query sequence that would be required (and why it is blocked) is missing.
minor comments (2)
- [Abstract] The abstract contains several grammatical issues ('there exist explicit set of measures', 'no algorithm outputs an equitable fair division') that should be corrected for readability.
- [Preliminaries] Notation for the value functions and the cut points is introduced without a consolidated table or list of symbols; readers must hunt through the text to recall whether v_i denotes a measure or a density.
Simulated Author's Rebuttal
We thank the referee for the thorough review and for identifying points where the rigor of the Galois-theoretic reduction and the verification of the explicit measures can be strengthened. We address each major comment below and will incorporate the suggested clarifications in a revised manuscript.
read point-by-point responses
-
Referee: [Section 3 (equitable division) and Section 4 (utilitarian welfare)] The manuscript does not supply a self-contained argument showing why a non-solvable Galois group on an auxiliary polynomial precludes every possible finite adaptive sequence of RW queries followed by field operations. Because each RW query can return a value that enlarges the base field in a query-dependent way, it is not immediate that the fixed polynomial considered in the Galois-theoretic step captures all reachable extensions; this step is load-bearing for both main theorems.
Authors: We agree that the current text leaves the reduction from Galois non-solvability to the non-existence of any finite adaptive BSS-RW procedure somewhat implicit. In the revision we will insert a new lemma (placed before the main theorems) that proves the following: every value returned by an RW query (whether a cut point or an evaluation) is algebraic over the base field generated by the density functions, and its minimal polynomial divides the fixed auxiliary polynomial whose Galois group is shown to be non-solvable. Consequently, any finite adaptive sequence of queries and BSS operations remains inside a field extension whose Galois group is a quotient of the original non-solvable group, preserving the impossibility. This makes the argument self-contained for both theorems. revision: yes
-
Referee: [Definition of the explicit couples (around the statement of Theorem 1)] The explicit measures are introduced only after the model is defined, yet the text does not verify that the chosen density functions lie outside every possible BSS-RW-computable cut; a concrete walk-through of one query sequence that would be required (and why it is blocked) is missing.
Authors: We accept that an explicit walk-through would make the claim more transparent. In the revised version we will add, immediately after the definition of the first explicit couple, a short subsection that considers a hypothetical algorithm attempting to compute an equitable connected division. We will enumerate the first few possible RW queries (e.g., an Eval query at a rational point, followed by a Cut query whose returned value would have to satisfy a quadratic or cubic equation), show that each such query forces the cut point to lie in an extension whose degree is incompatible with the non-solvable Galois group, and conclude that no finite sequence can succeed. The same style of verification will be sketched for the utilitarian-welfare example. revision: yes
Circularity Check
No circularity; Galois-theoretic non-existence proof is self-contained
full rationale
The paper defines the BSS-RW model, states that existing RW algorithms fit inside it, and invokes Galois theory on explicitly chosen measures to prove that no finite sequence of RW queries plus BSS operations can produce the required cut points for equitable connected divisions or utilitarian optima. No step reduces a claimed prediction to a fitted parameter by construction, no self-citation chain is load-bearing, and the impossibility argument does not rename a known result or smuggle an ansatz. The derivation therefore stands or falls on the correctness of the Galois application to the query-extended field, which is an external mathematical claim rather than a definitional loop.
Axiom & Free-Parameter Ledger
axioms (2)
- standard math Galois theory can be applied to demonstrate that required cut points are not algebraic for the chosen measures
- domain assumption The BSS-RW model accurately represents the computational restrictions relevant to cake-cutting algorithms
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.