| paper | d4-conf-ecai-2010-0238 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-complete}\), even when \(m=2\tau\) and \(\mu_t=b_g=1/\tau\) for every type and category. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 7
statement extracted from the paper’s text layer
Given a finite set of categories \(G\), a finite support \(T\) of SCI-net types with strict rankings and rational masses \(\mu_t>0\) summing to \(1\), and rational per-capita stocks \(b_g\), does there exist a bundle \(B_t\subseteq G\) for each type such that \(\sum_{t:g\in B_t}\mu_t=b_g\) for every category \(g\), and for every \(t,u\), either \(B_t=B_u\) or \(B_t\succ_t B_u\), where \(\succ_t\) is the partial bundle order induced by type \(t\)'s SCI-net?
A society is a distribution \(\mu\) over complete SCI-net types. Category supplies scale with population, and each person receives an integral bundle of at most one copy of each category. The decision variables are one bundle \(B_t\) per type: necessary envy-freeness prevents positive mass of a type from receiving distinct bundles. Feasibility requires each category's allocated mass to equal its per-capita stock \(b_g\), alongside pairwise necessary-envy-freeness; there is no separate objective.
The mirror covers complete necessary-envy-free allocation and its NP-completeness result in Proposition 7. It leaves the paper's possible-envy-free results, the PPE and NPE variants, the two-agent algorithm, and other open complexity questions unaddressed.
My lead is a continuous mass version of complete necessary-envy-free allocation. The anchor is Proposition 7, proved in this paper: given \(n\) agents who report SCI-nets over \(m\) goods, deciding whether there is a complete necessarily envy-free allocation is NP-complete, even when \(m=2n\). The paper proves membership in NP using its characterization of necessary envy-freeness and proves hardness by a polynomial reduction from X3C.
Here is the mirror. Let \(G\) be \(m\) standardized good categories and \(T\) a finite set of distinct SCI-net types. Type \(t\) has mass \(\mu_t>0\), with \(\sum_{t\in T}\mu_t=1\), and a strict ranking of the categories. Let \(b_g\in\mathbb{Q}\cap[0,1]\) be the stock of category \(g\) per unit of population. Each person still receives an integral bundle \(B\subseteq G\), with at most one copy of each category; the stock of each category scales with population, and copies within a category are interchangeable.
A mass allocation can be written \(x_{t,B}\), the mass of type \(t\) receiving bundle \(B\). It must satisfy \(\sum_B x_{t,B}=\mu_t\) for every type and \(\sum_{t,B:g\in B}x_{t,B}=b_g\) for every category, so all stock is allocated. For necessary envy-freeness, whenever type \(t\) receives positive mass of \(B\), every bundle \(C\) assigned positive mass must either equal \(B\) or satisfy \(B\succ_t C\), where \(\succ_t\) is the partial bundle order induced by \(t\)’s SCI-net.
This condition forces all members of any one type to receive the same category bundle: if positive masses of type \(t\) received distinct \(B\) and \(C\), necessary envy-freeness would require both \(B\succ_t C\) and \(C\succ_t B\). Thus a prover can be given the following precise decision problem: find a bundle \(B_t\subseteq G\) for each \(t\in T\) such that \(\sum_{t:g\in B_t}\mu_t=b_g\) for every \(g\), and for every \(t,u\), either \(B_t=B_u\) or \(B_t\succ_t B_u\). The solution is this type-to-bundle assignment, representing an allocation of the whole population mass.
The hardness transfers directly. Take a hard instance from Proposition 7’s reduction with \(N\) agents and \(2N\) goods. Make each agent a distinct type, set \(\mu_t=1/N\), and set \(b_g=1/N\) for each good. Then each category must occur in exactly one assigned bundle, so feasible mass assignments correspond exactly to complete allocations in the paper’s instance; the necessary-envy conditions also agree. This gives NP-hardness even with \(\tau=N\), \(m=2\tau\), and uniform masses and stocks. The mass problem is in NP: a certificate lists one \(m\)-bit bundle per type, and the stock equalities and SCI-net dominance conditions can be checked in polynomial time. So this mirror is NP-complete, a Class B case where discrete hardness survives.
A plausible regime is a large recurring distribution program for standardized equipment or supplies. Applicants share a finite set of stable rankings over categories, and category stocks scale with the cohort. For a hard instance with \(N\) ranking types, take \(K\) applicants of each type and \(K\) interchangeable copies of each of the \(2N\) categories. The population is \(KN\), while the support remains \(N\); the normalized masses and per-capita stocks are exactly those above. The paper’s fairness criterion, incomplete ordinal information, and indivisible bundles all remain central to the question. The category-copy convention is the co-modification needed to scale supply while preserving individual indivisibility.
The main limitation is that the hard family has \(\tau=N\) and \(m=2N\): the number of preference types grows with the number of agents in the source instances. Replicating each type gives arbitrarily many people per type, but this result does not settle the case where \(\tau\) and \(m\) stay small as the population grows. That leaves useful follow-up questions: is the mass problem fixed-parameter tractable in \(\tau\) when \(m\) varies, and how does the classification change if SCI-nets allow indifferences between categories?
The only anchor raised is Proposition 7. The strongest case against its mirror is that the hardness proof carries the discrete instance across almost unchanged: each source agent becomes a separate type, with \(\tau=N\) and \(m=2N\). Replicating every type \(K\) times makes the population large, but leaves the type-to-bundle decisions and their exact-cover structure intact. Necessary envy-freeness also prevents a type’s mass from splitting across different bundles: if two bundles of positive mass went to the same type, each would have to be strictly preferred to the other. So this is a continuous population whose allocation choices remain whole type blocks.
That makes the proposed result strongest in a carefully aligned regime. The stock equalities require each \(b_g\) to be a sum of the masses of whole types assigned category \(g\). With poorly aligned supplies, complete allocation can fail for that arithmetic reason before the preference constraints do. And the hardness construction scales the number of types; it does not establish what happens in the especially compressed regime of fixed, small \(\tau\) and a growing population. Those limitations weaken the claim that this mirror opens a new continuous-optimization problem.
They do not, though, defeat the mirror. The prompt explicitly allows supply to scale with population, and the repeated cohort receiving standardized interchangeable goods is plausible. The problem remains a computational question about a continuous distribution of agents, and a Class B result is a stated goal of the programme. The source reduction’s encoding of one agent per type is therefore a limitation on what the result demonstrates, not a reason to dismiss it. I cannot make the universal negative case convincingly: the mirror survives, and the honest case against it is weak.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.