| paper | d4-journals-jair-2009-0003 |
| 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: NP-hard · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given a finite support \(T\) of one-attribute profiles with rational supply masses \(\mu_t>0\) summing to \(1\), choose selected masses \(x_t\in[0,\mu_t]\). Replace each paper-style count property on \(\phi\) by a quota predicate \(\sum_{t\models\phi}x_t\bowtie q\), where \(q\) is rational and \(\bowtie\) includes equality and inequalities. Given a GAI utility over the resulting Boolean property values, compute a mass vector \(x\) that maximizes that utility.
A GAI quota-selection problem over types \(t\), with supply mass \(\mu_t\), decision variable \(x_t\in[0,\mu_t]\), quota predicates on aggregate selected mass, and objective equal to the supplied GAI utility of those predicate values.
It targets Theorems 2 and 5’s restricted TCP-net and GAI hardness claims; it leaves Theorem 1’s other hardness reduction, Theorems 3 and 4’s tractable classes, and the empirical search results open.
The strongest mirror is high-multiplicity subset selection: choose a mass of available item types, then evaluate the selected group by the same kinds of set properties the paper studies. This continuizes the population of selectable objects, not the outcome space or the preference language.
A plausible regime is a large scholarship or training program selecting a cohort from a national applicant pool. A type is an applicant’s complete profile for this decision—say field, region, experience band, and qualification band. If the program uses only those attributes, applicants with the same profile are interchangeable, and there may be many applicants of each of a comparatively small number \(\tau\) of profiles. The selection rules can then be stated naturally as proportions of the cohort: for example, at least \(q\) of the selected mass comes from a region. The actual applicants are still accepted or rejected individually; a type-level mass records their aggregate selection rate.
Formally, let \(T\) be the supported profiles, with rational masses \(\mu_t>0\) summing to \(1\). Choose \(x_t\in[0,\mu_t]\), the selected mass of type \(t\). For an item formula \(\phi\), define
\[
M_\phi(x)=\sum_{t\models\phi}x_t.
\]
A set property becomes a rational quota comparison such as \(M_\phi(x)\ge q\), or \(M_\phi(x)\ge qM_{\mathrm{true}}(x)\) for a proportion of the selected cohort. Once property truth values are fixed, these are linear constraints. The input records the supported types, their masses, the property formulas and quotas, and either a TCP-net or a GAI value function. A solution is a rational mass vector \(x\) whose induced property values are optimal under that preference specification.
My lead anchor is Theorem 2, proved in this paper. It says that finding an optimal subset under TCP-based preferences is NP-hard even with one item attribute, binary-valued set properties, and at most two logical connectives per property (\(a=1,k=2\)). The proof reduces from 3-SAT: it creates an item for each literal, a property requiring exactly one of \(v\) and \(\neg v\) for each variable, and a property requiring at least one literal from each clause. Each property independently prefers true to false. A subset making all properties true corresponds to a satisfying assignment.
The corresponding problem is TCP-Quota-POS\(_\infty\): given a rational type distribution, quota properties with those one-attribute and two-connective restrictions, and independent TCP preferences that favor true, find an undominated selected mass vector. My prediction for this restricted mirror is Class A, tractable. A fixed assignment to the property values is a system of linear inequalities. Starting with no properties fixed, test whether each preferred value, true, remains feasible alongside the earlier choices; keep it if so, otherwise fix the property to false. This takes a polynomial number of linear-feasibility calls. The paper’s discrete reduction encodes a literal choice with indivisible items; in the mass model, the literal types can split their selected mass. That is a meaningful continuization of the same selection question, and the likely loss of hardness is precisely what makes the mirror worth studying.
A second anchor is Theorem 5, also proved here. It establishes NP-hardness for GAI-based POS with one item attribute, binary set properties, and at most one logical connective per property (\(a=1,k=1\)). Its proof reduces from MAX-2SAT: variable properties require exactly one of the two corresponding literals, clause properties reward satisfying a two-literal clause, and an additive utility gives a large penalty for a false variable-consistency property and a reward for each true clause property.
Its mirror, GAI-Quota-POS\(_\infty\), has the same mass input and property semantics, but asks for \(x\) maximizing the supplied GAI utility. My provisional prediction for the general GAI mirror is Class C, continuum-specifically hard: choosing among feasible truth patterns of threshold properties can remain combinatorial even when the mass variables are continuous. But Theorem 5’s MAX-2SAT reduction does not establish that prediction. Fractional literal mass may make clause properties simultaneously true, so a continuous hardness proof would need a new construction. Finding out whether this version is instead tractable is a useful further question.
These mirrors cover the paper’s worst-case hardness results for TCP and GAI subset selection. They do not claim to continuize the paper’s empirical search experiments or every subset-selection setting. The paper’s finite counts over individual subsets are not already a continuous-population model; the mirror replaces those counts with mass and asks a computational question about the resulting optimization.
The weakest point is that the paper’s motivating examples include small, fixed-size recommendation sets and committees, where fractional cohort choices may not be credible. The applicant-cohort regime avoids that problem: the selected group can be large, the relevant criteria are naturally percentages, and the paper’s own formalism deliberately treats items with identical relevant attributes as equivalent. If individual scores or costs matter, they must be included in the type; that can increase \(\tau\), so the case depends on a regime where the decision-relevant profiles remain relatively few compared with the applicant pool.
I cannot make a strong case that both anchors lack a worthwhile mirror. The paper does have named computational results: Theorems 2 and 5 establish NP-hardness for optimal subset selection. So the “no computational result to mirror” objection is unavailable.
The strongest concern is that the paper’s input is a menu of items and one decision maker’s preferences over subsets. It has no electorate or preference aggregation. In the proposed applicant scenario, the mass is a pool of people eligible for selection, while the preference still belongs to an outside organizer. That may put the problem outside ChoCo’s intended notion of a continuous society. But the paper explicitly includes committee formation from politicians, and composition by population shares is a plausible high-multiplicity version of that problem. This is a boundary question, not a decisive objection.
For Theorem 2, the proposed quota version is narrower than the paper’s full TCP-POS problem: it focuses on properties that independently favor truth. Still, that is the structure of the theorem’s reduction, so it is a real mirror. Fractional mass may make the SAT construction feasible when no integral selection exists; that changes the answer, but does not make the question unworthy. A more careful version could also include properties that distinguish zero mass from full type mass, making it possible to test whether a continuous model retains the reduction’s all-or-nothing choices.
For Theorem 5, the MAX-2SAT reduction may likewise stop working when literal mass can split: a fractional assignment can make every clause property true. But that does not defeat the mirror. GAI utilities can assign values to properties that test zero or full type mass, so a stronger formulation could reward endpoint selections and ask whether the hardness survives. Whether that can be encoded cleanly is open formulation work, not a reason to rule out the question.
The proponent’s predicted complexity classes are not established by these arguments; in particular, the stated mass semantics needs a precise quota model. But I cannot honestly claim that either anchor fails. The most defensible negative case is that these are population-based subset-selection problems, not clearly population-based social choice. Given the paper’s committee motivation, that case is weak, and the case against a worthwhile mirror overall is weaker still.
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.