d4-conf-ecai-2023-0310

My lead is Continuum Envy-Rate, a high-multiplicity version of the paper’s computation of envy among equal-sized subgroups.

The anchor is Proposition 2, proved in this paper: the *number of envied subsets problem* is \(\#\mathrm P\)-complete. Its input is an allocation \(A\) and groups \(T_p,T_q\) with \(|T_p|\le |T_q|\); its output is the number of subgroups \(G\subseteq T_q\) of size \(|T_p|\) for which \(V_p(A_p)<V_p(A(G))\). The paper proves hardness by reducing from counting subset sum. In its construction, selecting a subgroup corresponds to selecting a subset of item values, and two counts—those above a threshold and those above a threshold shifted by one—recover the number summing exactly to the target. This is a result about the envy question itself, not about an encoding.

Here is the continuous problem. Consider two large groups \(P,Q\), with \(Q\)'s population normalized to mass \(1\) and \(P\)'s to mass \(\alpha\), where \(0<\alpha<1\). Agents have utility types: each type specifies a complete utility vector over a finite set \(J\) of item classes. The mass of each type is rational. Items within a class are interchangeable, and their supply scales with population. An allocation is a mass assignment: each unit of agent mass receives at most one item class, and each class’s allocated mass respects its supply. This scaling keeps the paper’s essential structure—indivisible items assigned at most one per agent and groups valuing bundles by optimal internal matching—while allowing type-level assignments to be fractional.

The instance includes \(P\)'s type masses \(\nu_r\), with \(\sum_r\nu_r=\alpha\), its allocated bundle \(b_j\), and \(Q\)'s joint masses \(a_{sj}\): the mass of \(Q\) with type \(s\) who receives class \(j\). Include a “no item” class so that unallocated agents are represented too. Let \(\mathcal V_\nu(z)\) be the maximum utilitarian matching value \(P\)'s population can obtain from item masses \(z_j\), subject to each type’s agent mass and each item mass being used at most once. Write \(v=\mathcal V_\nu(b)\) for \(P\)'s current value.

In finite populations approximating these masses, choose uniformly at random a subgroup of \(Q\) of size \(\alpha N\), and let \(d_N\) be the fraction of such subgroups whose assigned bundle \(P\) values above \(v\). Continuum Envy-Rate asks for the asymptotic rate \(I=\lim_{N\to\infty}-N^{-1}\log d_N\), along population sizes realizing the rational masses; if envy is impossible, the answer is \(+\infty\). A solution is an additive-\(\varepsilon\) approximation to \(I\), or a report that the envy event is impossible.

This keeps the paper’s counterfactual intact: envy is still whether \(P\) prefers its own allocation to the bundle received by a uniformly sampled equal-sized subgroup of \(Q\). What changes is the scale being computed. In a large population the degree itself often tends to zero or one; its exponential rate retains information about rare envy. If \(x_{sj}\) is the selected mass from each type-and-assignment class, the rate is given by maximizing the binary-entropy sum \(\sum_{s,j}a_{sj}H(x_{sj}/a_{sj})\), where \(H(z)=-z\log z-(1-z)\log(1-z)\), subject to \(0\le x_{sj}\le a_{sj}\), \(\sum_{s,j}x_{sj}=\alpha\), and \(\mathcal V_\nu(x_{\cdot})\ge v\). Subtract that supremum from \(H(\alpha)\), the exponential rate of all equal-sized subgroups. The weak inequality describes the closure of the strict envy event; use it only when strict envy is feasible. The matching value has a linear-program formulation, so the rate calculation becomes concave entropy optimization with linear matching constraints. I would expect this to be tractable to additive precision when the number of types and item classes is moderate.

A plausible regime is large departments assigning offices, or hospitals distributing recurring classes of equipment. Their populations can be large relative to the number of recurring preference profiles; staff and supplies both scale, and a same-size random cohort is a sensible counterfactual. Type-level averages may be fractional even though each employee in a finite realization gets at most one office or item. That is the permitted co-modification needed to make population mass meaningful. The authors have particular reason to recognize this mirror: their degree of envy is already motivated as a likelihood over equal-sized subgroups, and they explicitly study sampling methods for computing it. The mirror does not replace their utilitarian group value with a simpler average.

The scope is Proposition 2’s envy-subset count in this large-population, fixed-type regime. I am not claiming a continuous analogue of the paper’s NP-complete existence result, Proposition 1. Nor does this show that Proposition 2’s hardness disappears in general: its subset-sum reduction uses item values that can encode many distinct numbers. When the number of distinct types or item classes grows with the population, the entropy program’s dimension grows too, and hardness may remain.

The main further questions are whether the rate can be approximated with a clean polynomial bound in the type support, input bit length, and \(1/\varepsilon\); how to handle growing type support; and what refinements are needed when the rate is zero and lower-order sampling effects matter.

My weakest point is that this is the asymptotic exponent of the paper’s degree, not the finite degree the paper defines. It also assumes repeated item classes and population-scaled supply. A referee could judge that a meaningful but new large-population question rather than the authors’ continuous form of their original computation. I think the case survives because the envy event and the uniform-subgroup thought experiment remain exactly theirs; the rate is the nondegenerate quantity that remains when those subgroups become a continuum.