d4-conf-atal-2015-0049 (d4-conf-atal-2015-0049)

Given a finite support \(T\) of valuation types, rational masses \(\mu_t>0\) summing to \(1\), and normalized atomless valuation oracles \(V_t\), can a query protocol whose query count is bounded as a function of \(\tau=|T|\) find pairwise-disjoint connected intervals \(P_t\), with free disposal, such that \(V_t(P_t)\ge V_t(P_s)\) for all \(t,s\) and \(V_t(P_t)>0\) for every type?

A society is given by its support: a nonempty list \(T\) of \(\tau\) valuation types with positive binary rational masses \(\mu_t\) summing to \(1\). Here \(\tau\) is the support size, and \(L\) is the bit length of this explicit input.
The cake is \([0,1]\). Each type has a nonnegative, countably additive valuation measure \(V_t\), absolutely continuous with respect to length and normalized by \(V_t([0,1])=1\), accessed through exact Robertson–Webb queries.
An allocation assigns one connected interval \(P_t\) to each type; intervals are pairwise disjoint, with endpoint ownership immaterial. Unallocated cake may be discarded.
Require \(V_t(P_t)\geq V_t(P_s)\) for every \(t,s\in T\) and \(V_t(P_t)>0\) for every \(t\in T\). Masses impose no additional allocation or fairness requirement.
Complexity is measured by oracle query count as a function of \(\tau\); explicit-input processing depends on \(L\). There is no separate \(m\) parameter or finite encoding of the valuation measures.
Can a deterministic protocol always find such an allocation using at most \(f(\tau)\) queries for some finite function \(f\), or is no such bound possible?
Known results: for a finite list of \(n\) agents, connected envy-free allocation with free disposal and strictly positive values is computable using \(O(n2^n)\) queries. [Source](https://arxiv.org/html/1511.02599)
The stated type-based problem is already covered by that result: its allocation and fairness requirements involve only the finite list of valuation measures, so the bounded-query target is settled.

Conclusion

A deterministic bounded-query protocol exists. Its query complexity is \(O(\tau 2^\tau)\). In fact, it can guarantee \(V_t(P_t)\geq 2^{-(\tau-1)}\) for every type \(t\).

Applicable theorem

Theorem 1 of Segal-Halevi, Hassidim, and Aumann, *Waste Makes Haste*, gives an envy-free allocation among \(n\) agents with free disposal, assigning each agent a connected piece of value at least \(2^{-(n-1)}\), using \(O(n2^n)\) queries. Its valuation model consists of nonnegative, normalized measures absolutely continuous with respect to length. The paper implements its queries using Robertson–Webb evaluation and mark queries. Algorithm 1 uses a fixed agent order; finite choices can be resolved by fixed tie-breaking rules, yielding a deterministic protocol. [Source: Theorem 1, Section 2, and Section 4](https://arxiv.org/html/1511.02599).

We apply this known theorem as supplied in the task.

Reduction and verification

Enumerate the support as \(T=\{t_1,\ldots,t_\tau\}\). Construct an instance with \(n=\tau\) agents by setting \(W_i=V_{t_i}\). A query to agent \(i\) is answered by the given oracle for type \(t_i\), so this construction introduces no additional valuation queries.

All theorem hypotheses hold:

• The cake is \([0,1]\), as required.
• Each \(W_i\) is a nonnegative, countably additive measure, absolutely continuous with respect to length, with \(W_i([0,1])=1\), directly by the premises.
• Free disposal is permitted, and the required pieces are connected intervals.

Run the theorem’s protocol, obtaining pairwise disjoint intervals \(X_1,\ldots,X_\tau\), and set \(P_{t_i}=X_i\). For every pair of indices \(i,j\), its envy-freeness guarantee gives
\(V_{t_i}(P_{t_i})=W_i(X_i)\geq W_i(X_j)=V_{t_i}(P_{t_j})\).
Its value guarantee gives
\(V_{t_i}(P_{t_i})\geq 2^{-(\tau-1)}>0\).
Thus every allocation requirement in the question is satisfied. Absolute continuity implies that every singleton has value zero, so endpoint ownership does not affect these inequalities.

The masses \(\mu_t\) do not enter this construction: the stated feasibility conditions depend only on the indexed valuation measures. In particular, there is no need to expand rational masses into additional agents.

For \(\tau=1\), assign the entire cake with zero queries. For larger support sizes, the theorem provides a universal constant \(C\), enlarged if necessary to cover finitely many small sizes, such that the query count is at most \(f(\tau)=\lceil C\tau 2^\tau\rceil\). This bound is independent of the masses, their bit lengths, and the valuation measures.

⟨structured verdict parsed — rendered above⟩

The prover resolves the assigned question correctly. The reduction directly applies the supplied finite-agent theorem, and the stronger positive-value guarantee is supported by the cited source. No major or minor mathematical issues were found.

• The cited theorem is applicable. Theorem 1 guarantees an envy-free allocation with free disposal, connected pieces, value at least \(2^{-(n-1)}\) for each agent, and \(O(n2^n)\) queries. Section 2 assumes nonnegative, normalized valuation measures absolutely continuous with respect to length. These agree with the task’s hypotheses; no positive-density or finite-representation assumption is required. [Theorem 1 and Section 2](https://arxiv.org/html/1511.02599).

• The oracle model and determinism are supported. Section 4 implements Equalize operations using evaluation and mark queries. Algorithm 1 has a prescribed agent order and does not require randomization. The prover’s fixed tie-breaking convention resolves finite choices without altering the guarantees. Invoking the published protocol is sufficient here: the task explicitly supplies its bounded-query result, so reproducing its internal correctness proof is unnecessary. [Section 4](https://arxiv.org/html/1511.02599).

• The reduction preserves the instance exactly. The support is nonempty, so \(n=\tau\geq 1\). Setting \(W_i=V_{t_i}\) preserves nonnegativity, countable additivity, absolute continuity, and normalization. Forwarding a query to the corresponding type oracle introduces no additional queries. The theorem does not require different agents to have different valuation measures.

• All allocation requirements follow. The returned pieces are pairwise disjoint intervals. For arbitrary indices \(i,j\), the displayed substitution correctly transfers the theorem’s envy-freeness inequality to the required inequality between types. It covers every ordered pair, including \(i=j\). Moreover, \(2^{-(\tau-1)}>0\) for every finite support size, so the quantitative guarantee implies strict positivity for every type. Free disposal is expressly permitted.

• Endpoint ownership causes no discrepancy. Every singleton has length zero and hence value zero under every valuation by absolute continuity. Assigning a shared endpoint to either adjacent piece therefore preserves all values and inequalities.

• Ignoring masses is justified. Neither allocation feasibility nor envy-freeness involves \(\mu_t\). One agent per listed type therefore represents the task exactly. Expanding masses into additional agents would change the instance unnecessarily. The prover correctly distinguishes query complexity from explicit-input processing; it makes no unsupported running-time claim in \(L\).

• The base case and uniform bound are valid. For \(\tau=1\), assigning the entire cake uses zero queries, gives value \(1\), and satisfies envy-freeness. The stated asymptotic query bound supplies an absolute constant for sufficiently large support sizes. Enlarging it to cover finitely many smaller sizes yields the finite function claimed in the output. No explicit numerical constant is necessary for the question asked.

The established result is a uniform finite query bound. The exponential upper bound alone establishes neither polynomial query complexity nor hardness. No additional clarification is needed to verify the argument.

⟨structured verdict parsed — rendered above⟩