Networked Fairness in Cake Cutting (d4-conf-ijcai-2017-0328)

Given a finitely typed measured treeing \(\mathcal G\), type masses \(\mu_t\), valuation densities \(v_t\), a globally consistent edge mass-transport law, and one normalized cake copy per finite replica, compute a distribution \(\Lambda\) over finite-cut allocation patterns such that for \(\mathcal G\)-almost every directed edge \(i\to j\), \(V_{\operatorname{type}(i)}(A_i)\ge V_{\operatorname{type}(i)}(A_j)\); output an exact finite-cut certificate or an \(\varepsilon\)-accurate certificate whose support and cut complexity depend on the role and type description and \(\log(1/\varepsilon)\), not on the number of replicated agents.

A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Masses sum to \(1\).
The measured treeing is specified by finitely many explicitly listed, nonempty rooted tree templates \(T_k\), vertex type labels \(t(k,u)\), and positive binary-rational weights \(p_k\) summing to \(1\). Its agents are \((k,y,u)\), with \(y\in[0,1]\) and \(u\in V(T_k)\); edges join template neighbors with the same \((k,y)\), and each vertex fiber has measure \(p_k/|V(T_k)|\) times Lebesgue measure. Let \(R=\sum_k|V(T_k)|\).
Require \(\mu_t=\sum_k p_k|\{u:t(k,u)=t\}|/|V(T_k)|\). Directed-edge measure is obtained by integrating counting measure on neighbors against agent measure; this specifies the globally consistent, reversal-invariant mass-transport law.
Each replica \((k,y)\) has its own cake \([0,1]\). Each type has a nonnegative piecewise-constant density \(v_t\), with binary-rational heights on a common partition into \(m\) intervals with binary-rational endpoints; its integral is either \(0\) or \(1\). Write \(V_t(S)=\int_S v_t(x)\,dx\), and let \(L\) be the total input bit length.
A pattern consists of one complete partition \((A_{k,u})_{u\in V(T_k)}\) of the cake for each template, with every share a finite union of intervals with rational endpoints. It is reused in every replica of that template; interval endpoints may be assigned arbitrarily.
A certificate is a finitely supported distribution \(\Lambda\), with binary-rational probabilities, over patterns. For every supported pattern and both orientations of every template edge \(u\to w\), require \(V_{t(k,u)}(A_{k,u})+\varepsilon\ge V_{t(k,u)}(A_{k,w})\). Thus fairness holds almost everywhere in each realization, rather than only in expectation. The rational input \(\varepsilon\in[0,1)\) allows exact certificates when \(\varepsilon=0\); set \(h=0\) then, and otherwise \(h=\lceil\log_2(1/\varepsilon)\rceil\).

Is this certificate-construction problem polynomial-time solvable in \(m,\tau,R,L,h\), with polynomial support size and total cut complexity independent of the number of replicated agents, or is it NP-hard?

For finite trees with \(n\) agents, a moving-knife protocol produces a complete locally envy-free allocation using \(O(n^2)\) cuts; this is a cut bound, not a polynomial bit-time guarantee. [Source](https://arxiv.org/pdf/1707.02033)
For finite trees of depth at most two, a Robertson–Webb protocol uses \(O(n^3\log n)\) cuts. [Source](https://arxiv.org/abs/2205.12559) No result establishing complexity for this precise measured, replica-independent certificate formulation was located.

Result

The problem is polynomial-time solvable, including when \(\varepsilon=0\). A deterministic certificate suffices: its support has size \(1\), and its total cut complexity is at most \(mR\).

The key is the explicitly given common partition: splitting each of its intervals equally among a template’s vertices makes every type value all shares equally. This construction applies to every admissible instance and uses the permitted finite unions of intervals.

Construction

Write the common partition endpoints as
\(0=b_0<b_1<\cdots<b_m=1\).
For each type \(t\), let \(c_{t,j}\) be its constant density on the interior of \([b_{j-1},b_j]\).

Let \(K\) be the number of templates. For template \(T_k\), put \(n_k=|V(T_k)|\), and enumerate its vertices as
\(u_{k,1},\ldots,u_{k,n_k}\).

For every partition interval \(j\), define
\[ \]
\(q_{k,j,i}=b_{j-1}+\dfrac{i}{n_k}(b_j-b_{j-1}),\qquad 0\leq i\leq n_k.\)

Give vertex \(u_{k,i}\) the share
\(A_{k,u_{k,i}}=\displaystyle\bigcup_{j=1}^{m}[q_{k,j,i-1},q_{k,j,i}).\)
Include the endpoint \(1\) in the final vertex’s share.

For each \(j\), these subintervals partition \([b_{j-1},b_j)\). Consequently, the shares partition the entire cake. Every endpoint is rational, and every share is a union of at most \(m\) intervals.

Proof of exact fairness

Fix a template \(k\), a type \(t\), and a vertex index \(i\). Endpoint assignments do not affect integrals because finite sets have Lebesgue measure zero. The portion assigned to vertex \(i\) within partition interval \(j\) has length \((b_j-b_{j-1})/n_k\). Therefore,
\(V_t(A_{k,u_{k,i}}) =\displaystyle\sum_{j=1}^{m}c_{t,j}\frac{b_j-b_{j-1}}{n_k} =\frac{V_t([0,1])}{n_k}.\)

This expression is independent of \(i\). Thus every type assigns equal value to all shares within a template. In particular, for every directed template edge \(u\to w\), taking \(t=t(k,u)\) gives
\(V_{t(k,u)}(A_{k,u})=V_{t(k,u)}(A_{k,w}).\)

Hence the required fairness inequality holds with \(\varepsilon=0\), and therefore with every permitted \(\varepsilon\). This calculation also covers types whose integral is \(0\).

Let \(P\) be the single pattern containing these allocations for all templates, and define the certificate by
\(\Lambda(\{P\})=1\).
Its probability is binary rational. Reusing \(P\) in every replica makes fairness hold for every replica and every edge, which implies the required almost-everywhere fairness under the specified directed-edge measure. The construction preserves the given type labels, agent measures, and mass-transport law.

Cut and bit complexity

Within template \(k\), the construction subdivides the cake into \(mn_k\) consecutive elementary intervals. Thus at most \(mn_k-1\) internal cut locations suffice. Summing over templates gives at most
\(\displaystyle\sum_{k=1}^{K}(mn_k-1)=mR-K\leq mR\)
cuts. The total number of listed interval components is at most \(mR\).

It remains to verify that these cuts have polynomial encoding length. Write two consecutive input endpoints as \(b_{j-1}=a/d\) and \(b_j=c/e\), with positive denominators. Then
\(q_{k,j,i} =\dfrac{(n_k-i)ae+icd}{n_kde}.\)

The integers encoding input endpoints have at most \(L\) bits, and \(i\leq n_k\leq R\). The displayed numerator and denominator therefore have \(O(L+\log R)\) bits. Computing them, and reducing the fraction if desired, takes polynomial bit time. Although these endpoints need not be dyadic, the task explicitly permits rational endpoints.

There are at most \(mR\) interval components to output. Consequently, the complete certificate has encoding length
\(O\!\left(mR(L+\log R)\right)\)
and can be constructed in time
\(O(L)+O\!\left(mR\,\operatorname{poly}(L+\log R)\right)\).
This is polynomial in the requested parameters and does not depend on \(h\) or on the number of replicated agents.

The cited [moving-knife](https://arxiv.org/pdf/1707.02033) and [Robertson–Webb](https://arxiv.org/abs/2205.12559) protocols are unnecessary for this explicit piecewise-constant input model: equal subdivision within each common partition interval already provides an exact certificate.

⟨structured verdict parsed — rendered above⟩

The prover resolves the task correctly. The construction gives an exact deterministic certificate for every admissible input, with polynomial encoding length and at most \(mR\) cuts. No mathematical gaps or false steps were found.

• Applicability of the construction. Every template is explicitly listed and nonempty, so \(1\leq n_k\leq R\). Dividing a partition interval into \(n_k\) equal pieces is therefore well-defined. The common partition ensures that every type’s density is constant on each interval being subdivided. The task allows disconnected shares and arbitrary rational endpoints, so the resulting shares meet its representation requirements.

• Completeness and disjointness. For fixed \(k,j\), the endpoints \(q_{k,j,i}\) increase strictly with \(i\), with

\[ q_{k,j,0}=b_{j-1},\qquad q_{k,j,n_k}=b_j. \]
The half-open subintervals therefore partition \([b_{j-1},b_j)\). Taking their unions over \(j\) partitions \([0,1)\), and assigning \(1\) to the final vertex completes the partition of the cake. Each share has at most \(m\) interval components. Endpoint assignments are explicitly permitted by the task.

• Exact fairness. The displayed valuation calculation is correct:

\[ V_t(A_{k,u_{k,i}}) =\sum_{j=1}^{m}c_{t,j}\frac{b_j-b_{j-1}}{n_k} =\frac{V_t([0,1])}{n_k}. \]
The finitely many endpoints have zero Lebesgue measure, so their assignments do not affect this identity. Its right-hand side is independent of \(i\), for every type \(t\). Consequently, each agent values its own share and every neighboring share equally. Both orientations of every edge satisfy the required inequality, including when \(\varepsilon=0\). Types with integral zero are also covered.

• Certificate and replica requirements. The allocations for all templates form one pattern \(P\). The distribution assigning probability \(1\) to \(P\) has finite support and a binary-rational probability. Because the fairness identity holds on every template edge and the same allocation is reused in each replica, fairness holds in every replica, hence almost everywhere under the specified directed-edge measure. The construction changes neither agent measures nor edges, so it does not require any additional mass-transport argument. The prescribed consistency of the society masses remains an input condition.

• Cut and component bounds. For template \(k\), there are \(mn_k\) consecutive elementary intervals. Their internal boundaries number \(mn_k-1\). Summing over templates gives

\[ \sum_{k=1}^{K}(mn_k-1)=mR-K\leq mR. \]
Some boundaries may be unnecessary after adjoining components assigned to the same vertex; that only decreases the required count. Listing the elementary pieces uses at most \(mR\) interval components across the pattern.

• Rational encoding and running time. The endpoint formula is algebraically correct:

\[ q_{k,j,i}=\frac{(n_k-i)ae+icd}{n_kde}. \]
With input integers of at most \(L\) bits and \(i,n_k\leq R\), both numerator and denominator have \(O(L+\log R)\) bits. Integer arithmetic and optional fraction reduction take polynomial bit time. The output has at most \(mR\) components, so the stated polynomial encoding and construction bounds follow. Template and vertex indexing also fit within these bounds. No approximation is needed, so independence from \(h\) is justified.

The cited protocols are not used to establish any step of the argument. Their bit-time guarantees therefore need not be supplied or verified for this proof.

Required clarification: None. The output establishes polynomial-time solvability under the exact representation and certificate rules in the task.

⟨structured verdict parsed — rendered above⟩