Cake Cutting Algorithms for Piecewise Constant and Piecewise Uniform Valuations (d4-conf-wine-2014-0032)

Given finitely many complete piecewise-constant valuation types \(\Theta\), masses \(\mu_\theta>0\) with \(\sum_{\theta}\mu_\theta=1\), and common-refinement intervals \(J_1,\ldots,J_k\) of lengths \(\ell_r\), choose aggregate allocations \(x_{\theta r}\ge0\) satisfying \(\sum_{\theta}x_{\theta r}\le\ell_r\) to maximize \(\sum_{\theta}\mu_\theta\log U_\theta\), where \(U_\theta=\mu_\theta^{-1}\sum_r v_{\theta r}x_{\theta r}\), and provide a symmetric finite-agent realization for rational masses or its measure-valued limit, satisfying \(U_\theta\ge\mu_\phi^{-1}\sum_r v_{\theta r}x_{\phi r}\) for every pair \(\theta,\phi\).

A society is given by its support: the list \(\Theta\) of \(\tau\) valuation types with positive mass, each mass \(\mu_\theta\) a binary rational, with \(\sum_\theta\mu_\theta=1\); \(\tau\) counts supported types, not possible types.
The cake is \([0,1]\), partitioned into \(m\) common-refinement intervals \(J_r\) with positive binary-rational lengths \(\ell_r\). Type \(\theta\) has constant binary-rational density \(v_{\theta r}\ge0\) on \(J_r\), with \(\sum_r v_{\theta r}\ell_r>0\); every interval is valued positively by some type. Densities need not be normalized. Let \(L\) be the total input bit length.
Compute an exact maximizer of \(\sum_\theta\mu_\theta\log U_\theta\), where \(U_\theta=\mu_\theta^{-1}\sum_r v_{\theta r}x_{\theta r}>0\), over \(x_{\theta r}\ge0\) with \(\sum_\theta x_{\theta r}\le\ell_r\). It must satisfy \(U_\theta\ge\mu_\phi^{-1}\sum_r v_{\theta r}x_{\phi r}\) for all \(\theta,\phi\).
A symmetric finite realization has \(N\mu_\theta\) equal-claim agents of each type, for an integer \(N\) making these counts integral; their disjoint cake pieces are finite unions of intervals, each receiving length \(x_{\theta r}/(N\mu_\theta)\) from \(J_r\). A compact description indexed by agent is allowed.
Alternatively, a measure-valued realization assigns each member of type \(\theta\) the same nonnegative cake measure \(B_\theta\), with \(B_\theta(J_r)=x_{\theta r}/\mu_\theta\) and \(\sum_\theta\mu_\theta B_\theta\le\lambda\), where \(\lambda\) is Lebesgue measure; it is a weak limit of the finite realizations after multiplying each individual cake measure by \(N\).

Is computing such an exact maximizing allocation together with a symmetric finite realization or its measure-valued limit possible in time polynomial in \(m,\tau,L\), or is this problem NP-hard?

For finitely many agents, MEA computes a Pareto-optimal, envy-free allocation in polynomial time; its variable-claims extension optimizes a claim-weighted logarithmic utility objective and satisfies claim-adjusted envy-freeness. [Aziz–Ye](https://arxiv.org/pdf/1307.2908)
Exact equilibrium computation for finite linear Fisher markets with rational budgets and utilities is polynomial-time solvable; this result does not formulate the population realization requirement above. [Devanur et al.](https://ics.uci.edu/~vazirani/market.pdf)

Result

The problem is polynomial-time solvable in \(m,\tau,L\) under the permitted compact output representation. One can compute an exact rational maximizing allocation, a symmetric finite realization, and a measure-valued realization satisfying the stated weak-limit requirement.

The construction uses \(\tau\) Fisher-market buyers. It never explicitly expands the population into its potentially exponentially many members.

1. Reduction to an exact linear Fisher market

Define the aggregate utility of type \(\theta\) by

\(\displaystyle w_\theta(x)=\sum_r v_{\theta r}x_{\theta r}=\mu_\theta U_\theta(x).\)

A feasible allocation with every utility positive exists: take \(x_{\theta r}=\mu_\theta\ell_r\). Then

\(\displaystyle U_\theta(x)=\sum_r v_{\theta r}\ell_r>0.\)

Construct a Fisher market with one buyer for each supported type \(\theta\), budget \(\mu_\theta\), and one unit-supply good for each interval \(J_r\). Its utility coefficients are

\(\displaystyle a_{\theta r}=v_{\theta r}\ell_r.\)

Writing \(y_{\theta r}=x_{\theta r}/\ell_r\), the market feasibility constraints are precisely

\(\displaystyle y_{\theta r}\ge 0,\qquad \sum_\theta y_{\theta r}\le 1.\)

We use the following established theorem: a linear Fisher market with rational positive budgets and rational nonnegative utility coefficients, in which every buyer values some good and every good has an interested buyer, admits an exact rational equilibrium computable in polynomial time in its binary input length. Prices and a corresponding allocation have polynomial bit length. This is the exact algorithm of [Devanur, Papadimitriou, Saberi, and Vazirani, especially Section 2, Lemma 7.1, and Theorem 8.12](https://ics.uci.edu/~vazirani/market.pdf).

All hypotheses hold here:

• Each budget \(\mu_\theta\) is positive.
• Each buyer values some good because \(\sum_r v_{\theta r}\ell_r>0\).
• Every good has an interested buyer by the interval-positivity hypothesis.
• Products \(v_{\theta r}\ell_r\) are rational, and the transformed input has polynomial bit length.

Compute an exact equilibrium allocation \(y\) and prices \(p\), and set

\(\displaystyle x_{\theta r}=\ell_r y_{\theta r},\qquad \pi_r=p_r/\ell_r.\)

Here \(\pi_r\) is the price per unit of cake length on \(J_r\).

2. A rational certificate of optimality and envy-freeness

We derive the required properties directly from equilibrium.

Every price \(p_r\) is positive. Indeed, some buyer has \(a_{\theta r}>0\); if \(p_r=0\), that buyer could obtain arbitrarily large utility by demanding arbitrarily much of this free good, contradicting utility maximization at a finite equilibrium bundle.

Define

\(\displaystyle \alpha_\theta=\max_r\frac{a_{\theta r}}{p_r}=\max_r\frac{v_{\theta r}}{\pi_r}>0.\)

For any bundle affordable with budget \(\mu_\theta\), its utility is at most \(\alpha_\theta\mu_\theta\). This bound is attainable by spending the entire budget on a good attaining the maximum ratio. Consequently, equilibrium utility equals that bound, and equilibrium expenditure equals the entire budget. Thus

\(\displaystyle w_\theta(x)=\mu_\theta\alpha_\theta,\qquad U_\theta(x)=\alpha_\theta,\qquad \sum_r\pi_r x_{\theta r}=\mu_\theta.\)

In particular, for all \(\theta,r\),

\(\displaystyle v_{\theta r}\le U_\theta(x)\pi_r.\)

Market clearing gives \(\sum_\theta x_{\theta r}=\ell_r\). Summing expenditures therefore yields

\(\displaystyle \sum_r\pi_r\ell_r=\sum_\theta\mu_\theta=1.\)

These are all exact rational identities or inequalities.

Optimality

Let \(z\) be any feasible allocation with every \(U_\theta(z)>0\). The inequality \(\log t\le t-1\), valid for every \(t>0\), gives

\(\displaystyle \sum_\theta\mu_\theta\log U_\theta(z)-\sum_\theta\mu_\theta\log U_\theta(x) \le \sum_\theta\frac{w_\theta(z)-w_\theta(x)}{U_\theta(x)}.\)

The negative terms sum to

\(\displaystyle \sum_\theta\frac{w_\theta(x)}{U_\theta(x)}=\sum_\theta\mu_\theta=1.\)

For the positive terms, the coefficient inequalities and feasibility imply

\(\displaystyle \sum_\theta\frac{w_\theta(z)}{U_\theta(x)} =\sum_{\theta,r}\frac{v_{\theta r}}{U_\theta(x)}z_{\theta r} \le\sum_r\pi_r\sum_\theta z_{\theta r} \le\sum_r\pi_r\ell_r =1. \)

Hence the objective difference is nonpositive. Therefore \(x\) is an exact global maximizer.

Required envy inequalities

For any pair \(\theta,\phi\),

\(\displaystyle \frac{1}{\mu_\phi}\sum_r v_{\theta r}x_{\phi r} \le \frac{U_\theta(x)}{\mu_\phi}\sum_r\pi_r x_{\phi r} =U_\theta(x). \)

This proves precisely the required claim-adjusted envy-freeness.

3. Symmetric finite realization with polynomial-size description

Write each mass in lowest terms as \(\mu_\theta=c_\theta/d_\theta\), and choose

\(\displaystyle N_0=\operatorname{lcm}_\theta d_\theta,\qquad n_\theta=N_0\mu_\theta.\)

Each \(n_\theta\) is a positive integer, and \(\sum_\theta n_\theta=N_0\). Moreover,

\(\displaystyle \log_2 N_0\le\sum_\theta\log_2 d_\theta\le L,\)

so \(N_0\) is computable and representable with polynomially many bits.

Fix an ordering of the types. Write \(J_r=[a_r,a_r+\ell_r]\), with a consistent convention assigning boundary points to only one piece, and define

\(\displaystyle s_{\theta r}=\sum_{\psi<\theta}x_{\psi r}.\)

For agent \(h\) of type \(\theta\), where \(1\le h\le n_\theta\), assign within \(J_r\) the interval whose endpoints are

\(\displaystyle a_r+s_{\theta r}+\frac{(h-1)x_{\theta r}}{n_\theta} \quad\text{and}\quad a_r+s_{\theta r}+\frac{h x_{\theta r}}{n_\theta}. \)

Zero-length intervals are omitted. The agent’s piece is the union of these intervals over \(r\).

For each \(J_r\), consecutive type blocks have lengths \(x_{\theta r}\), and consecutive agents partition their type’s block. Since \(\sum_\theta x_{\theta r}=\ell_r\), these pieces partition the cake, up to the boundary convention. Every individual receives exactly

\(\displaystyle \frac{x_{\theta r}}{n_\theta}=\frac{x_{\theta r}}{N_0\mu_\theta}\)

from \(J_r\), as required.

Each agent of type \(\theta\) receives utility \(U_\theta(x)/N_0\). Their valuation of any type-\(\phi\) agent’s piece is

\(\displaystyle \frac{1}{N_0\mu_\phi}\sum_r v_{\theta r}x_{\phi r}\le\frac{U_\theta(x)}{N_0}.\)

Thus the finite realization is envy-free among its equal-claim agents.

The endpoint formula is a compact description indexed by \((\theta,h)\). Its tables and parameters have polynomial size; any indexed agent’s at most \(m\) intervals can be computed in polynomial time.

4. Measure-valued realization and its weak-limit construction

Define the nonnegative measure \(B_\theta\) by its constant density on each refinement interval:

\(\displaystyle \frac{dB_\theta}{d\lambda}(t)=\frac{x_{\theta r}}{\mu_\theta\ell_r} \qquad\text{for }t\in J_r. \)

Then

\(\displaystyle B_\theta(J_r)=\frac{x_{\theta r}}{\mu_\theta}.\)

Furthermore, on every \(J_r\),

\(\displaystyle \sum_\theta\mu_\theta\frac{dB_\theta}{d\lambda} =\frac{\sum_\theta x_{\theta r}}{\ell_r}=1. \)

Consequently,

\(\displaystyle \sum_\theta\mu_\theta B_\theta=\lambda.\)

Its own and cross-type utilities are exactly the quantities already proved envy-free.

It remains to establish the requested weak-limit property.

A sequence of symmetric finite realizations

For each positive integer \(k\), let

\(\displaystyle N_k=kN_0,\qquad n_\theta^{(k)}=N_k\mu_\theta.\)

Partition each \(J_r\) into \(k\) consecutive cells of equal length. Within each cell, allocate a consecutive block of length \(x_{\theta r}/k\) to type \(\theta\), in the fixed type order, and divide that block equally among its \(n_\theta^{(k)}\) agents.

Explicitly, agent \(h\) of type \(\theta\) receives, in cell \(t\), where \(0\le t<k\), the interval with endpoints

\(\displaystyle a_r+\frac{t\ell_r+s_{\theta r}}{k} +\frac{(h-1)x_{\theta r}}{k n_\theta^{(k)}} \quad\text{and}\quad a_r+\frac{t\ell_r+s_{\theta r}}{k} +\frac{h x_{\theta r}}{k n_\theta^{(k)}}. \)

Let \(A_{\theta h}^{(k)}\) denote the union of these intervals. These are disjoint finite unions, and every agent receives total length

\(\displaystyle \frac{x_{\theta r}}{n_\theta^{(k)}}=\frac{x_{\theta r}}{N_k\mu_\theta}\)

from \(J_r\).

Proof of weak convergence

Define the rescaled individual measure

\(\displaystyle \eta_{\theta h}^{(k)}=N_k\,\lambda|_{A_{\theta h}^{(k)}}.\)

On every cell \(C\subseteq J_r\), both \(\eta_{\theta h}^{(k)}\) and \(B_\theta\) have the same mass:

\(\displaystyle \eta_{\theta h}^{(k)}(C)=\frac{x_{\theta r}}{k\mu_\theta}=B_\theta(C). \)

For a continuous function \(f:[0,1]\to\mathbb R\), let

\(\displaystyle \omega_f(\delta)=\sup_{|s-t|\le\delta}|f(s)-f(t)|.\)

Every cell has diameter at most \(1/k\). Two nonnegative measures with equal mass on a cell have integrals of \(f\) differing by at most that mass times the oscillation of \(f\) on the cell. Summing over cells gives

\(\displaystyle \left|\int f\,d\eta_{\theta h}^{(k)}-\int f\,dB_\theta\right| \le B_\theta([0,1])\,\omega_f(1/k). \)

Uniform continuity implies \(\omega_f(1/k)\to0\). The bound is independent of \(h\), so convergence holds uniformly over all agents of type \(\theta\):

\(\displaystyle \eta_{\theta h}^{(k)}\Longrightarrow B_\theta.\)

This proves the population realization requirement.

5. Complexity conclusion

The exact market computation has polynomial bit complexity in \(m,\tau,L\). All subsequent quantities—allocation lengths, population counts, endpoint parameters, and measure densities—are obtained by polynomially many rational arithmetic operations on polynomial-length numbers.

Thus either requested realization can be output in polynomial time. An explicit listing of every agent could have exponential length, but the task expressly permits the compact indexed description constructed above.

⟨structured verdict parsed — rendered above⟩

The prover’s claim is proved. The argument establishes an exact polynomial-time algorithm under the compact output representation permitted by the task. I found no mathematical errors or gaps requiring clarification.

All mathematical notation below follows the final formatting instruction to use \( \) delimiters.

1. Reduction and applicability of the equilibrium theorem

The proposed positive-utility allocation is feasible: \(x_{\theta r}=\mu_\theta\ell_r\) gives \(\sum_\theta x_{\theta r}=\ell_r\), and its utility is \(U_\theta=\sum_r v_{\theta r}\ell_r>0\).

The change of variables \(y_{\theta r}=x_{\theta r}/\ell_r\) is valid because every \(\ell_r>0\). It preserves nonnegativity and converts each supply constraint into \(\sum_\theta y_{\theta r}\le1\). With \(a_{\theta r}=v_{\theta r}\ell_r\), market utility equals aggregate cake utility: \(\sum_r a_{\theta r}y_{\theta r}=w_\theta(x)\).

The cited exact Fisher-market result applies. Budgets are positive rational numbers, coefficients are nonnegative rational numbers, each buyer values some good, and each good has an interested buyer. The cited paper explicitly accommodates rational inputs through scaling, establishes polynomial-size rational equilibrium outputs, and gives a polynomial-time exact algorithm. The prover’s theorem statement and its application are supported by [Devanur et al., Sections 2, 7, and 8](https://ics.uci.edu/~vazirani/market.pdf).

Forming the products \(v_{\theta r}\ell_r\) increases their bit lengths only polynomially. The reduction therefore preserves polynomial input size.

2. Equilibrium identities

The proof that every price is positive is valid under the standard Fisher demand definition: individual utility maximization is over nonnegative affordable bundles, without individual supply caps. A positively valued free good would make that optimization unbounded.

Consequently, \(\alpha_\theta=\max_r a_{\theta r}/p_r\) is finite and positive. The affordable-utility bound \(\alpha_\theta\mu_\theta\) and its attainability follow directly from linear utility. Because prices and \(\alpha_\theta\) are positive, a maximizing bundle exhausts the budget.

Thus all three displayed identities hold:

• \(w_\theta(x)=\mu_\theta\alpha_\theta\).
• \(U_\theta(x)=\alpha_\theta\).
• \(\sum_r\pi_r x_{\theta r}=\mu_\theta\).

The coefficient inequalities \(v_{\theta r}\le U_\theta(x)\pi_r\) follow from the definition of \(\alpha_\theta\). Positive-price market clearing gives \(\sum_\theta x_{\theta r}=\ell_r\), and summing expenditures correctly yields \(\sum_r\pi_r\ell_r=1\).

3. Exact global optimality

The logarithmic comparison is correct. Applying \(\log t\le t-1\) to \(t=U_\theta(z)/U_\theta(x)>0\) gives precisely the displayed upper bound, because \(w_\theta=\mu_\theta U_\theta\).

The negative terms sum to \(1\). The positive terms are at most \(1\), using the coefficient inequalities, nonnegativity of \(z\), feasibility, and the price normalization established above.

Therefore every feasible allocation in the stated positive-utility domain has objective value at most that of \(x\). This proves exact global optimality. No numerical evaluation of logarithms is required.

4. Required envy inequalities

For every ordered pair \((\theta,\phi)\), the coefficient inequalities bound type \(\theta\)’s valuation of type \(\phi\)’s allocation. Dividing by the positive mass \(\mu_\phi\) and using type \(\phi\)’s expenditure identity gives exactly the required inequality.

This argument covers all pairs, including \(\theta=\phi\), without any normalization assumption on densities.

5. Symmetric finite realization

The least common multiple construction makes every \(n_\theta=N_0\mu_\theta\) a positive integer, with total population \(N_0\).

The bit-length bound is valid: the least common multiple is at most the product of the denominators, whose total encoding length is bounded by the input length. Polynomial-time integer arithmetic therefore suffices to compute \(N_0\) and the counts.

The endpoint formulas correctly partition each type block into \(n_\theta\) equal portions. Their lengths are exactly \(x_{\theta r}/(N_0\mu_\theta)\). Omitting zero-length intervals and assigning boundaries consistently handles zero allocations and disjointness.

The individual utility and cross-type valuation formulas are correct, so the finite realization is envy-free. The compact indexed description has polynomial size; computing one agent’s endpoints uses polynomially many operations on polynomial-length rational numbers. An exponentially large population therefore does not invalidate the output-time claim.

6. Measure-valued realization

The specified densities are nonnegative and finite. Integrating on \(J_r\) gives \(B_\theta(J_r)=x_{\theta r}/\mu_\theta\).

The weighted density sum equals \(1\) almost everywhere, so \(\sum_\theta\mu_\theta B_\theta=\lambda\). Boundary conventions do not affect these absolutely continuous measures.

The own-type and cross-type utility expressions agree with those already verified.

7. Weak-limit construction

The sequence uses integral type counts because \(N_k=kN_0\). Each cell contains a type block of length \(x_{\theta r}/k\), divided among all \(n_\theta^{(k)}\) agents. Summing an agent’s portions over the \(k\) cells gives exactly \(x_{\theta r}/n_\theta^{(k)}\), as required.

After multiplication by \(N_k\), each individual measure has cell mass \(x_{\theta r}/(k\mu_\theta)\), equal to the corresponding mass of \(B_\theta\). All scaling factors in this calculation are correct.

The oscillation estimate also has the correct constant: equal-mass nonnegative measures supported on a cell have integral difference at most their common mass times the oscillation there. Cell diameters are at most \(1/k\), so summing yields the stated bound.

The measure \(B_\theta\) has finite total mass, and every continuous test function on \([0,1]\) is uniformly continuous. The bound therefore tends to zero. Its independence from the agent index verifies convergence uniformly across each type’s changing finite population.

8. Complexity and scope

The exact equilibrium output has polynomial bit length. The subsequent finite tables, endpoint parameters, counts, and measure densities involve polynomially many rational or integer arithmetic operations with polynomial-size operands.

The weak-limit sequence is supplied by an explicit parameterized construction; the proof does not require outputting infinitely many realizations or listing every agent. Both permitted output alternatives are therefore addressed.

No repair or additional clarification is needed.

⟨structured verdict parsed — rendered above⟩