A Dictatorship Theorem for Cake Cutting (d4-conf-ijcai-2015-0214)

Given a finite catalogue \(T\) of normalized valuation densities, a population distribution \(\mu\in\Delta(T)\), an integer population scale \(N\), and \(\eta>0\), construct a succinct randomized Robertson–Webb protocol that implicitly partitions the cake into \(N\) pieces \(A_1,\ldots,A_N\), assigns them by a valuation-independent uniform random permutation, preserves individual truthfulness in expectation, and guarantees \(V_t(A_j)\in[(1-\eta)/N,(1+\eta)/N]\) for every \(t\in T\) and every \(j\), using complexity polynomial in \(|T|\), the input length, \(1/\eta\), and \(\log N\), rather than \(N\).

The cake is \([0,1]\). Each type \(t\) has an arbitrary integrable nonnegative density \(v_t\), with \(V_t(X)=\int_X v_t(x)\,dx\) and \(V_t([0,1])=1\); strict positivity is not required.
A society is given by its support: the list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu(t)\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types. Densities are accessible through Robertson–Webb oracles, rather than finite function descriptions. Also given are a binary integer \(N\ge2\) and a binary rational \(\eta>0\); \(L\) is the bit length of this finite input. There is one resource, so \(m=1\).
The query \(\operatorname{Cut}(t;\alpha)\), for \(\alpha\in[0,1]\), returns a point \(y\) satisfying \(V_t([0,y])=\alpha\); any such point is admissible. The query \(\operatorname{Eval}(t;y)\) returns \(V_t([0,y])\), only at previously generated cut points. Interior allocation endpoints must have been returned by Cut queries. Reports must remain consistent with a normalized nonnegative valuation.
An allocation partitions the entire cake into \(N\) finite unions of intervals \(A_1,\ldots,A_N\), allowing shared endpoints. A succinct output is a program specifying the recipient-piece label of each interval between consecutive queried cut points; it cannot introduce additional endpoints or defer uncharged queries. Count all queries and computation, using unit-cost exact oracle answers and real arithmetic, together with ordinary bit operations on the finite input.
The \(N\) recipient labels are virtual slots: no integrality condition is imposed on \(N\mu(t)\). Assign pieces through an independent uniform permutation \(\pi\) of these labels, drawn after reporting finishes and represented implicitly as a chance operation. Individual truthfulness in expectation means that, for every recipient's true type and every strategy of the other reporting individuals, changing its own consistent query replies cannot increase its expected value \(V_t(A_{\pi(i)})\).
Can such a randomized protocol guarantee \(V_t(A_j)\in[(1-\eta)/N,(1+\eta)/N]\) for every \(t\in T\) and \(j\in\{1,\ldots,N\}\) on every truthful execution, while preserving individual truthfulness in expectation and using total complexity and output size \(\operatorname{poly}(m,\tau,L,1/\eta,\log N)\), or is this approximation guarantee impossible within that bound?
For finite lists of \(n\) agents, a truthful-in-expectation Robertson–Webb construction guarantees \(V_i(A_j)\in[1/n-\varepsilon,1/n+\varepsilon]\); its stated query bound is \(O(n^2/\varepsilon)\), but its construction uses exhaustive enumeration. [Brânzei–Miltersen](https://www.ijcai.org/Proceedings/15/Papers/074.pdf)
An exact perfect-partition mechanism with uniform random assignment is known for nonatomic valuations, but is existential and uses direct revelation. Neither result establishes the stated support-input succinct complexity bound. [Mossel–Tamuz](https://www.tamuz.caltech.edu/papers/1003.5480.pdf)

Conclusion

The approximation guarantee is impossible within the stated complexity bound. For every \(0<\eta<1\), any successful execution requires at least \(N-1\) Cut queries. This holds already for one type with uniform density, regardless of randomization or succinct output.

1. The endpoint restriction forces many queries

Consider a completed execution making \(q\) Cut queries. Let \(c\) be the number of distinct interior points returned by those queries. Since each query returns one point, \(c\le q\).

Write these points in increasing order as \(x_1,\ldots,x_c\), and set \(x_0=0\) and \(x_{c+1}=1\). They determine \(c+1\) elementary intervals
\(I_r=(x_r,x_{r+1})\), indexed by \(0\le r\le c\).

By the output restriction, each elementary interval receives a single recipient-piece label. Consequently, every \(A_j\), apart from endpoints, is a union of elementary intervals carrying label \(j\). Every endpoint has value zero under every type, because valuations have integrable densities.

Suppose \(0<\eta<1\), and fix any \(t\in T\). The required lower bound gives
\(V_t(A_j)\ge (1-\eta)/N>0\)
for every \(j\). Thus each label must occur on at least one elementary interval of positive \(t\)-value: otherwise its piece would have value zero.

Different labels require different elementary intervals. Hence
\(N\le c+1\le q+1\),
and therefore
\(q\ge N-1\).

This argument allows disconnected pieces, repeated cut points, zero-density regions, and compressed programs. Compression cannot create additional elementary intervals.

There is also a lower bound using only the upper guarantee. Each elementary interval lies in one piece, so
\(V_t(I_r)\le (1+\eta)/N\).
The intervals cover the cake except for finitely many zero-value endpoints. Therefore
\(1=\sum_{r=0}^{c}V_t(I_r)\le (c+1)(1+\eta)/N\),
which implies
\(q\ge \lceil N/(1+\eta)\rceil-1\).
Thus any fixed positive \(\eta\), including \(\eta\ge1\), still forces a number of queries linear in \(N\).

2. Contradiction with the proposed polynomial bound

Take the admissible family of inputs with:

• \(m=1\) and \(T=\{t\}\), so \(\tau=1\);
• \(\mu(t)=1\);
• \(v_t(x)=1\) throughout the cake;
• \(\eta=1/2\);
• \(N=2^k\), encoded in binary.

All finite input data other than \(N\) have constant length, so \(L=\Theta(k)\). The proposed bound
\(\operatorname{poly}(m,\tau,L,1/\eta,\log N)\)
is therefore polynomial in \(k\).

But every successful truthful execution requires at least
\(N-1=2^k-1\)
Cut queries. Each query contributes to total complexity, and this exponential lower bound eventually exceeds every polynomial in \(k\).

The contradiction applies to randomized protocols as well: the counting argument holds separately for every successful realization of their randomness. Under the stipulated guarantee on every truthful execution, every such execution incurs the lower bound.

3. Uniform assignment does preserve truthfulness in expectation

The incentive requirement itself poses no additional obstruction.

Fix a recipient’s normalized true valuation \(V\), any reporting strategies, and any completed partition \(A_1,\ldots,A_N\). Conditional on everything determined before the independent uniform permutation \(\pi\), the recipient receives each piece with probability \(1/N\). Its conditional expected value is consequently
\(\mathbb E[V(A_{\pi(i)})\mid A_1,\ldots,A_N] =\frac1N\sum_{j=1}^{N}V(A_j)=1/N\).

The last equality follows from complete allocation and the zero value of shared endpoints. Taking expectation over the preceding execution preserves this value.

Thus changing consistent replies cannot increase expected utility, provided the protocol always terminates with a complete partition. This is also the expectation argument in [Mossel–Tamuz, Proposition 2.2](https://www.tamuz.caltech.edu/papers/1003.5480.pdf).

4. The query obstruction is sharp for one type

For a single type, exact equal-value partitioning requires only the matching \(N-1\) Cut queries: ask
\(\operatorname{Cut}(t;r/N)\)
for each \(r\in\{1,\ldots,N-1\}\).

Let the returned points be \(y_r\), with \(y_0=0\) and \(y_N=1\). The cumulative valuation is nondecreasing, and its values at successive points strictly increase, so \(y_0<y_1<\cdots<y_N\). Each consecutive interval has value
\(V_t([y_{r-1},y_r])=r/N-(r-1)/N=1/N\).

This works even when the density vanishes on intervals and Cut answers are nonunique. Uniform assignment then gives truthfulness in expectation.

Accordingly, the negative result concerns the required dependence on binary-encoded \(N\). Neither succinct labels nor uniform random assignment removes the \(N-1\) charged endpoints necessary when \(0<\eta<1\).

⟨structured verdict parsed — rendered above⟩

The prover resolves the target correctly. The endpoint restriction forces exponentially many charged queries in the binary input length, already for one uniform type. No major or minor mathematical issues were found.

• Endpoint counting is valid.

After \(q\) Cut queries, the number \(c\) of distinct interior returned points satisfies \(c\le q\). Sorting these points gives exactly \(c+1\) elementary open intervals. The output specification requires a single recipient label on each such interval and prohibits additional endpoints.

Integrable densities assign zero value to individual points. Consequently, shared endpoints cannot contribute positive value to a piece, and each piece’s value equals the sum of the values of its labeled elementary intervals.

• Both query lower bounds follow correctly.

For \(0<\eta<1\), the guarantee requires
\[ V_t(A_j)\ge \frac{1-\eta}{N}>0 \]
for every label \(j\), fixing any supported type \(t\). Each label therefore needs at least one elementary interval of positive value. Since an elementary interval has only one label, there must be at least \(N\) elementary intervals. Thus
\[ N\le c+1\le q+1, \qquad q\ge N-1. \]

The separate upper-bound argument is also valid. Nonnegativity and containment in a labeled piece give
\[ V_t(I_r)\le \frac{1+\eta}{N}. \]
Normalization and zero-valued endpoints yield
\[ 1\le (c+1)\frac{1+\eta}{N}, \qquad q\ge \left\lceil\frac{N}{1+\eta}\right\rceil-1. \]
The claim of linear growth is explicitly for fixed \(\eta\); it does not incorrectly assert a uniform linear bound when \(\eta\) grows with \(N\).

Repeated cut points, disconnected pieces, zero-density intervals, and succinct labeling programs do not invalidate either count.

• The binary-input contradiction is rigorous.

The chosen family satisfies all input requirements: one normalized uniform type, mass \(1\), \(m=1\), \(\eta=1/2\), and \(N=2^k\). Because valuations are oracle inputs, no growing finite density description is required. The finite input length is \(L=\Theta(k)\), while \(1/\eta\), \(m\), and \(\tau\) are constant.

Hence the proposed complexity bound is polynomial in \(k\), whereas every successful execution requires at least \(2^k-1\) charged Cut queries. This suffices to disprove the requested simultaneous complexity and output guarantee; a separate output-size lower bound is unnecessary.

Randomization cannot evade the argument: it holds for each completed successful execution. The stipulated guarantee on every truthful execution therefore forces the same lower bound on every such execution.

• The truthfulness calculation is correct under its stated condition.

For any complete partition produced before the independent uniform permutation, each recipient receives each piece with probability \(1/N\). For its normalized true valuation \(V\),
\[ \mathbb E[V(A_{\pi(i)})\mid A_1,\ldots,A_N] =\frac1N\sum_{j=1}^{N}V(A_j) =\frac1N. \]
This uses the true valuation, irrespective of reported valuations or other recipients’ strategies. Complete allocation and zero-valued shared endpoints justify the sum.

The proviso that the protocol always terminates with a complete partition is explicit and sufficient. The cited expectation argument matches [Mossel–Tamuz, Proposition 2.2](https://www.tamuz.caltech.edu/papers/1003.5480.pdf). The prover does not rely on that existential mechanism for computational feasibility.

• The single-type sharpness claim is correct.

The \(N-1\) queried cumulative targets are strictly increasing and lie strictly between \(0\) and \(1\). Monotonicity of the cumulative valuation forces their returned points to be strictly ordered, including between the fixed endpoints \(0\) and \(1\). Nonunique answers caused by zero-density regions do not affect this implication.

Each consecutive interval has value \(1/N\), including the first and last intervals by normalization. Uniform assignment supplies the stated expectation guarantee. This establishes sharpness of the query count for one type, without claiming the desired succinct polynomial complexity.

No repair or additional clarification is needed. The established complexity result is an unconditional oracle-query lower bound, rather than a reduction-based hardness classification.

⟨structured verdict parsed — rendered above⟩