d4-conf-ijcai-2016-0063

My lead is Three-Type Continuous Envy-Free Feasibility. It mirrors Theorem 4, proved in this paper: deciding whether a complete envy-free allocation exists is NP-complete when there are three agents. The paper proves this by reducing from NOT-ALL-EQUAL 3SAT.

Here is a continuous-population version. Let \(J\) be a finite set of item categories, and let the three types \(A,B,C\) have masses \(\mu_A=\mu_B=\mu_C=1/3\). Each type has a strict ranking of \(J\). Copies within a category are homogeneous, and each person receives an integral bundle \(S\subseteq J\), with at most one copy of each category. The supply of each category \(j\in J\) is mass \(1/3\): enough for every member of one cohort to receive one copy.

A solution is a collection of masses \(\lambda_{t,S}\geq 0\), where \(\lambda_{t,S}\) is the mass of type \(t\) receiving bundle \(S\). It must satisfy \(\sum_S\lambda_{t,S}=1/3\) for each type and \(\sum_{t,S:j\in S}\lambda_{t,S}=1/3\) for each category \(j\). It must also be envy-free: whenever \(\lambda_{t,S}>0\) and \(\lambda_{t',S'}>0\), type \(t\) weakly prefers \(S\) to \(S'\) under the paper’s responsive set extension. In that extension, every item in \(S'\) must be matchable to an equally or more preferred item in \(S\). The question is whether such an allocation exists; a solution can be given as the bundle masses, or as one bundle per type.

The latter representation is enough here: two people with the same strict category ranking cannot receive different bundles in an envy-free allocation, since each would have to weakly prefer its bundle to the other’s. Thus each category’s supply, exactly \(1/3\), must go to exactly one cohort. Given any three-agent instance from Theorem 4, make each original agent a cohort, each original item a category, and give that category supply \(1/3\). Assigning the category to a cohort is then exactly assigning the original item to its agent, and the envy comparisons are the same. This is an exact embedding of the paper’s problem into the continuous one, so the mirror is NP-hard; in this restricted formulation it is also in NP, with the three bundles as a certificate.

The regime is a large allocation program with three stable preference cohorts and many people in each cohort—for example, households choosing among replicated categories of standardized aid or equipment. With \(r\) people per cohort, there are \(3r\) people but only \(\tau=3\) preference types, and each category has \(r\) copies. The number of categories varies with the instance. This is a plausible high-multiplicity regime, and the hardness lives in the item and preference agenda, not in the number of distinct population types. I would expect Class B: hardness transfers.

The mirror asks the paper’s own question about complete itemwise envy-freeness, with integral bundles for individuals and the society represented by type masses. The needed co-modification is the per-capita supply of item categories. I would not claim it covers the paper’s two-agent algorithms or its item-addition and deletion results; it emphatically covers Theorem 4’s three-agent feasibility result.

The main weakness is that the paper assumes strict rankings over distinct items, whereas the high-multiplicity scenario treats copies in a category as identical. Preferences remain strict across categories, but copies are tied. I think this is a natural way to model replicated goods and the population scaling the mirror requires; still, a demand that every physical copy receive a distinct strict rank could break the exact three-type embedding.

This mirror also raises useful follow-ups: how complexity changes for unequal rational cohort masses and supplies; whether the paper’s item-addition or deletion hardness survives when the chair can change item mass fractionally; and how to state the finite-clone to continuous-allocation dictionary precisely.