| paper | d4-journals-jair-2011-0054 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(m,\tau,k,L\), using two exact rational linear programs. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given worker types \(T\) with rational population shares \(\mu_t\), roles \(R\), eligibility and contribution data, rational linear coverage constraints \(Ax\ge b\), and unit costs \(c_{t,r}\) and qualities \(q_{t,r}\), find a feasible assignment mass vector \(x\) minimizing \(C(x)=\sum_{t,r}c_{t,r}x_{t,r}\), then maximizing \(Q(x)=\sum_{t,r}q_{t,r}x_{t,r}\) among minimum-cost assignments; report infeasibility if none exists. Each worker receives at most one integral role, while \(x_{t,r}\) records the share of type \(t\) assigned to role \(r\).
A distribution \(\mu\) over interchangeable worker types, assignment masses \(x_{t,r}\ge0\), type supply constraints \(\sum_r x_{t,r}\le\mu_t\), rational linear service requirements \(Ax\ge b\), and additive aggregate cost and quality; compute the lexicographic optimum minimizing \(C(x)\) and then maximizing \(Q(x)\).
The workforce model treats the population as supply for a planner and uses linear additive attributes, so it does not carry over the paper's general qualitative partial preferences or worst-frontier aggregation.
fatal: False
The mirror covers Theorem 4's guarantee in a cost-priority, additive staffing subcase; it leaves the paper's general qualitative and worst-frontier settings, other algorithmic guarantees, and dominance results aside.
There is one credible, narrow mirror: choosing a preferred feasible composition from a high-multiplicity population of interchangeable components.
My lead anchor is Theorem 4, “Soundness and Weak Completeness of Algorithm 2” (proved in this paper, with its proof in Appendix A). For a set \(C\) of feasible compositions, let \(\Psi_{\succ_d}(C)\) be the non-dominated compositions under the paper’s dominance relation. The theorem says Algorithm 2 returns a set \(\theta\) such that \(\theta\subseteq\Psi_{\succ_d}(C)\), and if \(\Psi_{\succ_d}(C)\neq\varnothing\), then \(\theta\neq\varnothing\). Thus it returns only non-dominated feasible compositions and returns at least one whenever any feasible composition exists. The paper has named algorithmic guarantees like this, but no named theorem classifying its problems as polynomial-time, NP-hard, or similar; this is a correctness anchor, not a complexity-class result.
A plausible regime is a national service network assembled from a large workforce: perhaps \(N=100{,}000\) available people but only \(\tau=40\) distinct types. A type records everything the composition problem uses: skills and role eligibility, service contribution, cost, quality, and any other relevant parameters. People of the same type are interchangeable for this task. Let \(\mu_t\) be type \(t\)’s share of the workforce, and let \(x_{t,r}\) be the mass of type \(t\) assigned to role \(r\). The variables satisfy \(\sum_r x_{t,r}\leq\mu_t\), while rational linear constraints \(Ax\geq b\) express the service and coverage requirements. Here \(x_{t,r}\) is a population share; individual workers still take integral roles.
Call the resulting problem High-Multiplicity Preferred Composition. Its instance consists of the rational type masses \(\mu\), the role contributions and eligibility data, the functional requirements \(A,b\), and unit cost and quality values. The aggregate attributes are \(C(x)=\sum_{t,r}c_{t,r}x_{t,r}\), with lower cost preferred, and \(Q(x)=\sum_{t,r}q_{t,r}x_{t,r}\), with higher quality preferred. Give cost higher relative importance than quality. The question is: report infeasibility if no \(x\) satisfies the constraints; otherwise return a feasible \(x\) for which no feasible \(y\) has lower cost, or equal cost and higher quality. A returned vector is a solution exactly when it is feasible and non-dominated by this preference rule.
I expect this version to be Class A. The feasible mass vectors form a bounded rational polytope. Minimize \(C(x)\), constrain cost to that optimum, then maximize \(Q(x)\). Exact linear programming produces a rational maximal composition in time polynomial in the support size, input bit length, and constraint description. Summation is one of the paper’s explicit aggregation choices, and the paper studies selecting feasible collections by preferences over aggregate component attributes. The continuous task preserves that question while replacing a large list of interchangeable components with their type masses. It also raises the natural discrete bridge: with \(\mu_t=n_t/N\), how much error is introduced by rounding a continuous composition back to integer assignments?
The obvious extensions are less settled: can the same guarantee be obtained for genuinely partial qualitative preferences or worst-frontier aggregation, and what happens when functional feasibility depends on component interactions rather than linear coverage constraints?
The weakest point is the regime and its social-choice interpretation. The paper’s course-selection example is small, and its composition problem has one user expressing preferences; it is not an election over alternatives. A large workforce is a plausible high-multiplicity population for composition, but the continuous version is most convincing only where aggregate service requirements and attributes really are linear. The authors should recognize the underlying task—finding preferred feasible collections—though they might regard this as a specialized large-scale application rather than a mirror of the paper’s general framework.
Theorem 4 is the proponent’s strongest anchor, but it proves a correctness guarantee over a finite set \(C\) of feasible compositions. Algorithm 2 obtains that set through a functional-composition algorithm and then filters it; the theorem gives no complexity classification, and the running time depends on that black box. So it is a real computational result, but it does not itself chart the kind of complexity landscape ChoCo is meant to study.
The staffing LP is a plausible continuous problem. Its tractability comes from requiring linear feasibility constraints, additive numerical attributes, and a cost-first preference rule. Those choices produce a lexicographic linear optimization problem. They also leave out the paper’s harder distinctive features: arbitrary qualitative partial preferences, worst-frontier aggregation, and composition feasibility supplied by a black box. The LP therefore mirrors the general task of choosing a preferred feasible composition, but it does not continuize Theorem 4’s algorithmic guarantee in a way that tests those features. This is a limitation of the anchor, not an objection that an easy answer would be uninteresting.
A stronger proposed mirror would use many interchangeable workers or components and optimize a team or system assembled from them. That is a sensible high-multiplicity regime when type really captures every relevant property. But it treats the population as an inventory of resources. The paper’s preference is supplied by one user choosing a composition; the components do not express preferences that are aggregated into a collective decision. If many users each choose a composition, identical users simply repeat the same choice. Shared capacities could couple their choices, but that adds an allocation problem beyond the paper’s model.
That leaves a real case against treating this anchor as evidence for a continuous *social-choice* mirror: the authors’ algorithms operate on finite collections and their stated preferences, while the proponent’s strongest construction turns those collections into divisible supply for a planner. Still, I cannot honestly make the universal negative airtight. High-multiplicity team formation is plausible, and the paper explicitly studies preferred feasible collections. An author could recognize that broader task as theirs. My case against is strongest as a challenge to the specific Theorem 4 anchor and its fit to ChoCo; the proposed workforce mirror remains a credible adjacent problem.
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.