| paper | d4-conf-ecai-2016-0310 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given finitely many agent types \(i\) with masses \(\mu_i\), item types \(j\) with per-capita supplies \(q_j\) summing to \(1\), ordinal utilities \(u_{ij}\in L\), and a succinct coordinatewise monotone capacity ν on mass vectors, find a feasible mass plan \(x_{ij}\ge 0\) satisfying \(\sum_j x_{ij}=\mu_i\) and \(\sum_i x_{ij}=q_j\) that maximizes \(\max_{\lambda\in L}\min\{\lambda,\nu(r^\lambda)\}\), where \(r_i^\lambda=\sum_{j:u_{ij}\succeq\lambda}x_{ij}\). Each individual receives one indivisible item; atomlessness allows a type cohort to be partitioned to realize its mass flows. What is the complexity of this optimization problem as a function of the type counts, |L|, rational bit lengths, and capacity-circuit size?
Use an atomless population of agent types with masses \(\mu_i\) and item types with per-capita supplies \(q_j\). Decision variables \(x_{ij}\) are the masses of type \(i\) assigned item type \(j\); each person receives one indivisible item, while cohorts can be split measurably. A monotone capacity ν evaluates the mass vector receiving at least each utility threshold, and the objective is its Sugeno integral.
The hardness witness needs \(3m\) role types and a knife-edge capacity that rewards complete variable groups at exactly a specified mass, so it does not establish hardness for a small stable type set or ordinary aggregate capacities.
fatal: False
The mirror covers Theorem 2’s general-capacity hardness question. It leaves the special-case algorithms in Theorem 1, the MIP formulation, and the numerical experiments unmirrored.
My strongest case is the paper’s general hardness result: it has a direct atomless mirror, and the reduction appears to carry over even when agents can be divided into fractional cohorts. The mirror keeps the paper’s assignment question and Sugeno objective; it continuizes the population and the supplies.
Consider a large school district assigning residents to service slots, where each resident gets one indivisible slot and residents rank the service categories on a qualitative scale. A type records a resident’s complete utility profile and any group attribute used by the district’s importance policy. A plausible regime has hundreds of thousands of residents but only dozens or hundreds of types. The mass \(\mu_i\) of type \(i\) is its share of residents; each service category \(j\) has a rational per-capita supply \(q_j\), with \(\sum_j q_j=1\).
The lead question is Atomless Sugeno Assignment. Its instance contains a finite ordinal scale \(L\), agent types \(i\in I\) with masses \(\mu_i\), item types \(j\in J\) with supplies \(q_j\), and utilities \(u_{ij}\in L\). It also contains a capacity \(\nu\) on coalition compositions: for \(z_i\in[0,\mu_i]\), \(\nu(z)\in L\), with \(\nu\) coordinatewise monotone, \(\nu(0)=\bot\), and \(\nu(\mu)=\top\). To make this a finite computational problem, give \(\nu\) as a circuit of rational affine comparisons and Boolean gates, with monotonicity promised. A solution is a nonnegative mass plan \(x_{ij}\) satisfying
\[
\sum_j x_{ij}=\mu_i,\qquad \sum_i x_{ij}=q_j.
\]
It represents a measurable assignment of indivisible items to individuals: atomlessness lets each type cohort be partitioned to realize its flows.
For each utility threshold \(\lambda\in L\), let \(r_i^\lambda=\sum_{j:u_{ij}\succeq\lambda}x_{ij}\), the mass of type \(i\) receiving utility at least \(\lambda\). The plan’s value is
\[
S_\nu(x)=\max_{\lambda\in L}\min\{\lambda,\nu(r^\lambda)\}.
\]
The problem asks for a feasible plan maximizing this value, with complexity measured in \(|I|\), \(|J|\), \(|L|\), the rational bit lengths, and the capacity-circuit size. Crucially, the objective preserves the distribution of people’s qualitative utilities; it does not substitute a type’s average utility for its members’ utilities.
The anchor is Theorem 2, proved in this paper. It says that finding an assignment maximizing the Sugeno integral of individual utilities is NP-hard, even when \(|L|=2\). In context, the capacity is succinctly specified so its value on a coalition can be computed in polynomial time. The theorem’s proof reduces from monotone 1-in-3-SAT: every clause must have exactly one true variable. That is the content I am relying on; the theorem does not itself state a result about continuous populations.
There is a concrete way to carry its reduction to Atomless Sugeno Assignment. For a formula with \(m\) clauses, make one agent type for each of its \(3m\) literal occurrences, each of mass \(1/(3m)\). Give each clause item type supply \(1/(3m)\), and give a filler item type supply \(2/3\). An occurrence type gets \(\top\) only from its own clause item; every other assignment gives \(\bot\). The occurrence types are distinguished by their variable-group membership, since that is relevant to the capacity.
Define \(\nu(z)=\top\) if either \(\sum_i z_i>1/3\), or \(\sum_i z_i=1/3\) and the selected types form a union of complete variable groups, with every selected coordinate equal to its full mass and every unselected coordinate zero. Set \(\nu(z)=\bot\) otherwise. This capacity is monotone: a strict increase from a top-valued vector at mass \(1/3\) moves above the threshold, where the capacity is also top. Its circuit has polynomial size.
At most \(1/3\) of the population can receive \(\top\), because only clause items provide it and their total supply is \(1/3\). Thus a plan has Sugeno value \(\top\) exactly when it assigns the full supply of every clause item to top-utility occurrence types, selecting exactly one occurrence per clause, and those occurrences comprise whole variable groups. That is exactly a satisfying 1-in-3 assignment. Fractional splitting does not defeat the reduction: the capacity makes partial occurrence cohorts insufficient at the threshold. The types can each be replicated \(R\) times, for arbitrarily large \(R\), while keeping \(|I|=3m\); the finite population then has \(N=3mR\) people and the same type masses. This gives a direct hardness-transfer argument for the continuous problem, rather than merely an analogy to the discrete theorem.
This is a plausible mirror of the authors’ underlying problem. It keeps one-to-one assignment at the individual level, ordinal utilities, coalition importance, and Sugeno aggregation. Its capacity depends on coalition composition rather than personal names, which is consistent with high multiplicity when type membership includes all features the problem uses. The hardness comes from the assignment and agenda structure in the reduction, not from needing a small population. I would expect this mirror to be hard because discrete hardness transfers.
My weakest point is the capacity in the reduction. It is deliberately engineered, and its exact-threshold rule for whole cohorts may be less natural in an applied district than a simpler policy based only on total satisfied mass. That limits what the anchor says about ordinary applications. It does not undo the worst-case mirror: the paper studies general succinct capacities, and this continuous formulation gives such capacities a coherent mass-based domain. The central further question is whether hardness persists for simpler, more anonymous capacity families, and which of those admit a tractable optimization or separation method. This case covers Theorem 2 alone; I would not use Theorem 1 as an additional anchor, since its fixed \(k\)-maxitivity condition needs a separate choice of how \(k\) should scale in a continuum.
The only anchor the proponent raises is Theorem 2: NP-hardness of maximizing a Sugeno integral for a general capacity. The strongest case against its mirror is that the hardness construction keeps the combinatorics in a type-level capacity that distinguishes nearly every agent role. In the reduction, there are \(3m\) occurrence types for \(3m\) agents. Replicating each type creates large cohorts, but the formula is still encoded across \(3m\) distinct types.
That matters if the claimed payoff is a population limit with a small, stable set of types. For a generic capacity in the paper, an agent’s role can depend on how that agent interacts with every coalition; preserving it may require making each agent its own type. If we instead require a capacity that treats agents anonymously within a fixed set of demographic or preference types, Theorem 2 does not establish hardness for that restricted model. The proposed reduction’s capacity also gives top value at a knife-edge mass only when the selected cohorts are whole and form complete variable groups. That is a valid monotone capacity, but it is a contrived policy whose logical structure does the work.
This is a real limit on what the anchor demonstrates: it does not show that the continuous model gains a tractable high-multiplicity regime, or that the hardness persists for ordinary aggregate capacities. But it does not defeat the mirror. The proposed model has per-capita supplies, type masses, a mass-transfer assignment, and a normalized monotone capacity computable from a polynomial-size circuit. Replicated members of each type are indistinguishable under both utilities and the capacity. The unusual capacity is still within the paper’s general model, and hardness surviving in a continuous population is a meaningful possible result under ChoCo’s stated scope.
A stronger, more applied mirror would ask about a restrained family of capacities on type proportions—for example, capacities based on a fixed number of group shares—and characterize which families make Sugeno assignment tractable. The paper does not answer that question, but neither does its hardness theorem rule it out. So the negative case is weak: it can show that the proponent’s reduction is not evidence of a broad tractability gain for compact-type societies, but it cannot honestly establish that no worthwhile continuous mirror exists.
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.