d4-conf-ijcai-2009-0244

The anchor is Theorem 3.1, proved in this paper: in the Robertson–Webb model, achieving an envy-free cake allocation has query complexity \(\Omega(n^2)\). The bound is against algorithms with no restriction beyond that query model; the counted queries are cuts and evaluations. This is a concrete query lower bound, not an NP-hardness result or a running-time lower bound. It is the one anchor I would use.

My lead mirror is Mass-RW Envy-Free Cake Cutting. A plausible regime is a large public resource allocation—say, many beneficiaries dividing a heterogeneous pool—where complete valuation profiles recur because beneficiaries fall into a modest number of standardized classes. Let \(N\) be the population mass, with \(N\gg\tau\), and let \(\mu\) give the fractions of that mass in the \(\tau\) types. A type \(t\) is the complete valuation \(v_t\): an additive, nonatomic valuation of cake intervals, normalized by \(v_t([0,1])=1\). The application only fits this regime if people within a type really share that valuation, not merely a rough label.

Here is the problem precisely. Take \(N\in\mathbb N\), rational masses \(\mu_t\) summing to \(1\), and, for definiteness, instances with \(N\mu_t\in\mathbb N\). Each type has a Robertson–Webb oracle for its valuation. The algorithm may ask that oracle for an interval’s value or for a cut attaining a specified value. It must output a finite list \((t_j,q_j,X_j)_{j=1}^S\): mass \(q_j>0\) of type \(t_j\) receives the actual piece \(X_j\), a finite union of intervals. Require \(\sum_{j:t_j=t}q_j=N\mu_t\) for every type, and require \(\sum_{j:x\in X_j}q_j=1\) for almost every cake point \(x\), so the cake is fully allocated. Envy-freeness is ex post: for every two positive-mass cohorts \(j,k\), \(v_{t_j}(X_j)\ge v_{t_j}(X_k)\). In particular, this does not replace each person’s bundle with an expected bundle; \(\lambda\), or equivalently the list, records population mass assigned to each actual piece. The computational question is the worst-case number of type-oracle queries needed to produce such a list, as a function of \(N,\tau\), the mass bit length \(L\), and the output support \(S\).

This is a mass population version of the paper’s allocation problem: it retains the cake, the type valuations, full resource use, and the same envy comparisons. It changes named agents into divisible cohorts that can be split across pieces. That is the high-multiplicity move. A natural setting is a large allocation program with many beneficiaries but relatively few recurring, complete valuation templates. The discrete bridge is explicit when \(N\mu_t\) are integer counts; the relaxation comes from allowing a type’s mass to divide into subcohorts.

For the intended regime \(N\gg\tau\), I expect the quadratic \(N\) dependence to weaken: cut and evaluation information can be reused across everyone sharing a type. My tentative prediction is an output-sensitive algorithmic result—Class A—with query cost governed roughly by the number of cohorts produced and \(\tau\), rather than by \(N^2\) independent agent-type interactions. I am not claiming that bound follows from Theorem 3.1. The paper’s theorem motivates the question; it does not settle it. Further questions are whether \(S\) can be bounded by \(O(N+\tau)\), whether a succinct output avoids a population-sized list, and whether the query complexity can be polynomial in \(\tau\) and \(L\) when \(N\) is binary encoded.

The weakest point is that the anchor’s lower bound relies on separately queryable valuations for named agents, while the mirror deliberately shares one oracle across a type and lets its mass split. The proof therefore does not transfer as a lower bound, and an explicit output may itself require many cohorts. The case survives as a precise, author-recognizable question about whether their envy-free allocation barrier comes from population size or from the number of distinct valuation types; it does not claim that this paper already answers that question.