Fair in the Eyes of Others

The strongest positive case is a two-branch mirror built around repeated utility types. Its lead is the paper’s hardness result, Corollary 2; Proposition 9 supplies a cleaner tractable special case.

The common regime is a large population of students or households, with \(n\gg \tau\) and only \(\tau\) distinct complete utility types. A type \(t\) is the entire additive utility vector \(u_t\) over the available goods, so agents of the same type are interchangeable. Population mass is \(\mu_t\). Because an atomless population cannot share a single indivisible item, the natural co-modification is a per-capita supply \(q_o\) for each good category \(o\). Each individual still receives an integral bundle \(B\subseteq O\); only the mass of agents receiving each bundle is divisible.

A feasible continuous allocation is therefore a collection \(x_{t,B}\ge 0\), where \(x_{t,B}\) is the mass of type \(t\) receiving integral bundle \(B\), satisfying \( \sum_B x_{t,B}=\mu_t \) and \( \sum_{t,B:o\in B}x_{t,B}=q_o \). Utilities remain \(u_t(B)=\sum_{o\in B}u_t(o)\). Thus this is genuinely population continuization, not fractionalizing an individual’s bundle.

My lead problem is Continuous Unanimity-Avoidance. Given \(O,T,\mu,q\), and additive utilities \(u_t\), decide whether there exists a feasible \(x\) such that there are no two positive-mass bundles \(B,D\) with the following property: some type \(t\) receiving \(B\) strictly prefers \(D\) to \(B\), and every active type \(r\) with \(\mu_r>0\) also strictly prefers \(D\) to \(B\). In other words, no envy relation is unanimously approved by the population. A solution is the mass assignment \(x\), not merely a yes/no certificate.

This is the direct continuous analogue of the paper’s Corollary 2. The printed statement is: “Deciding whether an allocation exhibits unanimous envy is NP-Complete.” The surrounding discussion makes the intended decision problem clearer: for an add-MARA instance with additive rational utilities, decide whether an allocation avoiding unanimous envy exists, equivalently whether the instance admits a \(K\)-approval-envy-free allocation for some \(K\). Since \(K=n\) is the weakest approval requirement, this is the same as asking whether unanimous envy can be avoided. Corollary 2 is proved in the paper, using Proposition 5 and the NP-membership argument.

Proposition 5 states that when all agents have identical preferences, \((1\)-app envy)-freeness and \((n\)-app envy)-freeness coincide. Hence, on identical-preference instances, avoiding unanimous envy is exactly ordinary envy-freeness. The paper uses the known hardness of envy-free allocation to obtain Corollary 2. The continuous mirror preserves precisely this consensus-based envy question; it does not replace it with utilitarian welfare or a fractional allocation criterion.

I expect Continuous Unanimity-Avoidance to remain hard, with hardness transferring from the goods and bundle structure rather than from population multiplicity. For example, take a PARTITION instance with item weights \(w_1,\ldots,w_m\) summing to \(2W\). Use one utility type, set \(u(o_j)=w_j\), and give every item category per-capita supply \(q_{o_j}=1/2\). Since everyone has the same preferences, avoiding unanimous envy requires every bundle receiving positive mass to have the same utility. Its expected utility is \(W\), so a feasible solution exists exactly when some subset of items has total weight \(W\). A partition gives a solution by assigning mass \(1/2\) to each complementary bundle, and any solution contains a bundle of weight \(W\).

Thus the continuous population does not erase the discrete obstruction: each individual still receives an integral bundle, and the hard combinatorics live in the item set. A finite realization uses many identical agents and \(N/2\) copies of each item category, so this is a genuine high-multiplicity regime. The expected classification is therefore Class B, although the exact complexity of the general configuration problem remains a worthwhile question.

The supporting anchor is Proposition 9. It states, proved in the paper, that for every House Allocation Problem instance—where the number of agents equals the number of objects and each agent receives exactly one object—one can find an optimal \((K\)-approval envy)-free allocation in \(O(n^3\log n)\) time. The algorithm computes, for every agent-object pair, the maximum approval count generated by objects that agent prefers, builds a bipartite graph for a candidate \(K\), tests for a perfect matching, and uses dichotomous search over \(K\).

Its continuous mirror is Continuous Approval-Threshold House Allocation. The input consists of a type distribution \(\mu\), house categories \(O\) with per-capita supplies \(\rho_o\) satisfying \(\sum_o\rho_o=1\), and utilities \(u_t(o)\). A feasible solution is \(x_{t,o}\ge0\) with \( \sum_o x_{t,o}=\mu_t \) and \( \sum_t x_{t,o}=\rho_o \); every unit of population still receives exactly one integral house.

For two house categories \(o,o'\), define their approval mass by \(a(o,o')=\sum_{r:u_r(o')>u_r(o)}\mu_r\). If type \(t\) receives \(o\), its continuous approval-envy level is \(h(t,o)=\max_{o':u_t(o')>u_t(o)}a(o,o')\), with value \(0\) when \(o\) is top-ranked. The problem asks for a feasible \(x\) minimizing \( \max\{h(t,o):x_{t,o}>0\} \). This is exactly the normalized high-multiplicity version of minimizing \(K\).

I expect this problem to be Class A. For a candidate threshold \(\alpha\), simply forbid assignments \(t\to o\) with \(h(t,o)>\alpha\), then test whether the remaining type-house transportation instance is feasible. There are only finitely many candidate values \(a(o,o')\), and each feasibility test is a flow problem. The result is a polynomial algorithm in \(m,\tau\), and the encoding length of the rational masses and utilities. The paper’s matching argument survives as a type-level flow argument, while individual houses remain indivisible.

The authors should recognize both mirrors as their problems. The first retains their central notion—an agent’s subjective envy filtered through the population’s agreement—and asks whether unanimous envy can be avoided in a large repeated society. The second is their exact House Allocation problem in a natural setting such as thousands of students assigned to repeated course seats or households assigned to many equivalent housing units.

The weakest point is the inventory scaling. The original paper has a finite set of named objects, whereas a genuine atomless population requires repeated object categories or per-capita supplies. That changes the finite instance, although it is the natural co-modification forced by preserving indivisible individual bundles. There is also a wording/complement ambiguity in Corollary 2, so I would not claim that the paper itself proves the continuous hardness result. The honest claim is narrower: its named NP-complete envy result motivates a precise continuous problem, and the one-type partition restriction shows that the resulting mirror is not merely a tractable restatement.

Further questions are whether general Continuous Unanimity-Avoidance admits a configuration-LP characterization, when its bundle-pricing problem is tractable, and how its optimum approximates finite elections with \( \mu_t=n_t/n \). For House Allocation, one can also ask whether the flow solution can be rounded with bounded loss in approval mass for a finite population.