| paper | d4-conf-sagt-2020-0003 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Proposition 3
statement extracted from the paper’s text layer
Given candidates \(C\), positions \(P\), and a rational distribution \(\mu\) over approval sets \(A_t\subseteq C\times P\), where \(S(c,p)=\sum_{t:(c,p)\in A_t}\mu_t\), can one compute an injective line-up with no reasonably dissatisfied pair under \(S\)?
Use complete voter types \(A_t\subseteq C\times P\) with rational masses \(\mu_t\). Derive pair scores \(S(c,p)=\sum_{t:(c,p)\in A_t}\mu_t\), then repeatedly assign the highest-scoring remaining candidate-position pair. The resulting line-up is reasonably satisfying under the score matrix \(S\).
The type distribution aggregates to the score matrix, so the support size adds no computational axis; the proponent acknowledges this but does not show a distinct complexity question.
fatal: False
Covers Proposition 3’s constructively computable reasonably satisfying line-up for approval-derived scores; it does not continuize the OWA complexity questions, the other rule properties, or the experiments.
The strict anchor requirement blocks a formal positive case here: the paper has no numbered computational result. Theorems 1–13 and Propositions 1–3 concern axioms and rule properties. Section 4 does state algorithmic facts—such as the polynomial algorithms for utilitarian and egalitarian line-ups—and says the harmonic rules’ complexity is open, but those claims are not numbered results. The NP-hardness statement for arbitrary OWA assignment is attributed to Lesca et al., so it is external. I can’t honestly present any of these as an eligible anchor from this paper.
The strongest plausible mirror is a Continuous-Population OWA Line-Up Winner problem. Consider a large membership organization choosing \(q\) people from \(m\) candidates for distinct roles. Members assess candidate-role pairs, and members with the same complete approval set are one voter type. An instance gives the support of types \(T\subseteq 2^{C\times P}\), with rational masses \(\mu_t\geq 0\) summing to \(1\). The score of a pair is its approval mass,
\[
S(c,p)=\sum_{t:(c,p)\in t}\mu_t.
\]
Given an OWA vector \(\Lambda\), the task is to return an injective assignment \(\pi:P\to C\) maximizing \(\Lambda\big(S(\pi_{p_1},p_1),\ldots,S(\pi_{p_q},p_q)\big)\). The input size and running time should be measured in \(m,q,\tau,L\), and the encoding size of \(\Lambda\); a solution is the maximizing line-up.
The regime is plausible when a large association, union, or public body evaluates a relatively small slate for several offices. It could have many members but comparatively few distinct approval profiles, so \(N\gg\tau\). This keeps the paper’s core decision intact: choose a line-up with one distinct candidate per position, using the same OWA objective. The paper’s opening approval-voting example and its stated interest in future preference-based inputs make this a recognizable extension of its model.
For arbitrary OWA assignment, the expected direction is hardness transfers: discrete score-matrix instances can be represented by approval-type masses, with scores scaled uniformly, which preserves the maximizing line-ups. The paper’s cited NP-hardness result for that broader problem supports this expectation, but is not an eligible anchor. For fixed harmonic or inverse-harmonic vectors—the rules the paper computes experimentally—the complexity question remains open. This mirror covers OWA winner determination only; it does not continuize the paper’s axioms, sequential rules, or experiments.
The weak point is that the paper already takes the aggregated score matrix as input. Once the masses are summed into \(S\), voter count and type support no longer affect the winner computation. So this is a sensible high-multiplicity formulation, but its connection to the paper’s own computational results is limited—and, under the required anchor rule, there is no numbered result on which to base the case.
The strongest case against starts with the anchor requirement: the paper has no numbered computational result to mirror. Theorems 1–13 and Propositions 1–3 establish axiomatic properties and counterexamples. Section 4 gives algorithmic facts for the utilitarian and egalitarian rules and leaves the harmonic rules’ complexity open, but those are not numbered computational results proved by the paper. The NP-hardness statement for general OWA assignment is attributed to earlier work. Under the stipulated test, there is no eligible anchor.
The proposed continuous OWA winner problem is still worth assessing. Let each voter type be an approval set over candidate–position pairs, and let \(\mu_t\) be its mass. The score matrix is \(S(c,p)=\sum_{t:(c,p)\in t}\mu_t\). Every line-up’s OWA score depends only on \(S\); correlations among a voter’s approvals across pairs never matter. One can aggregate the input types into \(S\), then solve exactly the score-matrix problem the paper already defines. Conversely, every rational matrix in \([0,1]^{m\times q}\) can be represented by a distribution over approval types, with support at most \(mq+1\). So this population encoding adds no substantive restriction or new computational axis. The harmonic-rule question remains the same open score-matrix question, and its difficulty comes from the assignment objective, not the population representation.
A larger membership organization is a plausible setting for those approval masses. But the paper’s formal problem begins after voter input has already been reduced to a score matrix; it has no voter count or ballots whose high-multiplicity version could be studied. The mass description is a redundant lift of the input, rather than a relaxation of a discrete computational problem in the paper.
A stronger proposal might let the organization move mass between approval types to make a target line-up win. That could be a sensible new problem, but it adds campaigning, conversion costs, and a target-winner condition that the paper does not study. Any new complexity would depend on those additions, not on a continuous mirror of one of its results. Likewise, the paper’s future direction of deriving scores from voter preferences would first require specifying how those preferences produce candidate–position scores; once specified, the winner problem again factors through the resulting matrix.
This makes the negative case strong against the proposed anchor, but weaker as a universal claim. The harmonic winner problem is open, and a population-based extension may be worth studying on its own. What the paper does not offer is a numbered computational result whose high-multiplicity or continuous-population version would advance the continuization programme.
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.