| paper | d4-conf-ecai-2012-0021 |
| 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: The implication problem is in \(\mathrm{P}\), and a positive binary-rational violating distribution is computable in polynomial time whenever the implication fails. · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 1
Given a finite support \(T\) of complete rankings over options and rational comparative constraints \(V\) on type shares, decide whether every positive distribution \(\mu\) satisfying \(V\) has \(\mu(I)>\mu(J)\), where \(I\) contains types ranking \(a\) above \(b\) and \(J\) contains types ranking \(b\) above \(a\). Return a violating distribution when the implication fails.
A society consists of ranking types \(t\in T\) with positive shares \(\mu_t\) summing to \(1\); the input gives \(T\) and incomplete rational constraints \(V\) on sums of shares. The decision asks whether every admissible society gives \(a\) greater pairwise support than \(b\).
The population query has the same simplex and coalition calculations as the paper’s criterion-weight inference, so the proposed mirror adds a population interpretation rather than a new mathematical formulation.
fatal: False
The mirror covers necessary pairwise preference inference over ranking-type shares and the guaranteed-\(\rho\)-majority analogue; it leaves Smith-set construction and the search for minimal complete process-based explanations aside.
The strongest mirror is the paper’s inference about coalition weights, read as inference about population shares. The paper itself supplies the bridge: it says the approach also applies to social choice, where one may know which coalitions are winning without knowing exact weights.
Take a large public consultation on \(m\) options. Each respondent has a complete ranking of the options, and respondents with the same ranking form a type \(t\). A society is a distribution \(\mu\) over a listed set \(T\) of \(\tau\) ranking types: \(\mu_t\) is the fraction of respondents of type \(t\). A plausible regime has hundreds of thousands of respondents but only tens or hundreds of observed types. The input gives incomplete aggregate information as rational comparative constraints \(V\), such as \(\mu(E)>\mu(F)\) for disjoint sets of types \(E,F\). This is a natural social-choice instance of the paper’s incomplete information: rankings may be known while the shares are not. The admissible societies are the distributions satisfying those constraints and \(\sum_{t\in T}\mu_t=1\).
My lead is Continuous Necessary-Coalition Inference, mirroring Proposition 1 (proved in the paper). Given \(V\) and disjoint type sets \(I,J\), decide whether every admissible society satisfies \(\mu(I)>\mu(J)\). For a pair of options \(a,b\), take \(I\) to be the types ranking \(a\) above \(b\), and \(J\) the types ranking \(b\) above \(a\). A solution is yes or no; a no answer includes an admissible distribution witnessing the failure, and a yes answer can include a proof certificate.
Proposition 1 says that a comparative statement \([I\succ J]\) belongs to \(cl(V)\) exactly when the following integer system is feasible, with the displayed objective selecting the smallest coefficient sum. In the population mirror, replace each criterion index by a type index; \(\alpha_{E,F}\) multiplies a given share constraint, and \(\beta_t\) accounts for nonnegative mass:
\(\displaystyle \begin{aligned} \min\quad &\sum_{[E\succ F]\in V}\alpha_{E,F}+\sum_{t\in T}\beta_t+\gamma\\ \text{s.t.}\quad &\sum_{[E\succ F]\in V}\alpha_{E,F}\ge 1,\\ &\beta_t+ \sum_{\substack{[E\succ F]\in V\\t\in E}}\alpha_{E,F} -\sum_{\substack{[E\succ F]\in V\\t\in F}}\alpha_{E,F} = \begin{cases} \gamma & t\in I,\\ -\gamma & t\in J,\\ 0 & t\notin I\cup J, \end{cases} \qquad(t\in T),\\ &\alpha_{E,F},\beta_t,\gamma\in\mathbb Z_{\ge 0}. \end{aligned} \)
The paper proves this characterization using Motzkin’s theorem and computes with it in its closure procedure. It does not claim here that the problem is in P or NP-hard; this is a formulation-and-certificate result.
A second, narrower question is Guaranteed-\(\rho\)-Majority Share, anchored in Proposition 2 (proved in the paper, with proof sketched there). Given \(V\), a set of types \(I\), and rational \(\rho\in(1/2,1)\), decide whether every admissible society has \(\mu(I)>\rho\). The solution is again a yes/no answer, with a violating society if the answer is no and a certificate if yes. Proposition 2 characterizes this guarantee by feasibility of the following integer program, including its objective:
\(\displaystyle \begin{aligned} \min\quad &\sum_{[E\succ F]\in V}\alpha_{E,F}+\sum_{t\in T}\beta_t+\delta+\gamma\\ \text{s.t.}\quad &\sum_{[E\succ F]\in V}\alpha_{E,F}\ge 1,\\ &\beta_t+\delta+ \sum_{\substack{[E\succ F]\in V\\t\in E}}\alpha_{E,F} -\sum_{\substack{[E\succ F]\in V\\t\in F}}\alpha_{E,F} = \begin{cases} \gamma & t\in I,\\ 0 & t\notin I, \end{cases} \qquad(t\in T),\\ &\delta\ge\gamma\rho,\\ &\alpha_{E,F},\beta_t,\delta\in\mathbb Z_{\ge 0},\qquad \gamma\in\mathbb Z_{>0}. \end{aligned} \)
I expect both decision versions to be Class A in this explicit-support mirror. A counterexample is a distribution satisfying the comparative constraints and a weak violation of the queried inequality. Its existence can be tested by linear programming: introduce a slack \(\epsilon\), require each strict input inequality—and each listed type’s positive mass—to have margin at least \(\epsilon\), impose the weak violation, and maximize \(\epsilon\). A positive optimum gives a counterexample; otherwise the implication holds. This is polynomial in \(m,\tau,|V|\), and the rational bit length \(L\). That is an expected result for the mirror, not a complexity theorem claimed by the paper.
The scope is deliberately limited to the relative-weight inference behind these propositions, including the large-majority test. It does not claim to mirror the paper’s full process-based explanation procedure, its minimization over explanations, or the construction of a Smith set. Further questions include the complexity of generating minimal complete explanations across many pairwise contests, how the finite-\(N\) electorate relates to this continuous problem near strict-inequality boundaries, and whether minimizing certificate complexity creates a harder problem.
The weakest point is semantic: in the paper, weights belong to criteria, not to people. The population interpretation depends on the paper’s stated social-choice bridge and on a concrete consultation regime where type mass really is respondent share. I think that is plausible and keeps the underlying question intact, but it is the point a referee could reject. The case is strongest for these two inference problems; the paper supplies no hardness anchor from which to claim that discrete hardness dissolves.
The case against these two anchors is that the proposed mirror is already the paper’s model under a change of labels. Proposition 1 reasons over a simplex of weights, subject to comparative constraints, and asks whether those constraints imply a coalition inequality. Call each coordinate a voter type, each weight its population share, and each coalition a set of types: that is exactly Continuous Necessary-Coalition Inference. The proponent’s integer system is Proposition 1 with \(H\) renamed \(T\). Proposition 2 likewise already asks whether every feasible weight vector gives a coalition more than \(\rho\); renaming weights as type shares produces the proposed Guaranteed-\(\rho\)-Majority Share problem. The fact that the paper does not classify their complexity does not change the identity of the questions: the paper gives the characterizations the proposed mirrors ask for.
The social-choice interpretation is plausible, which makes the collision stronger, not weaker. The paper explicitly connects criteria coalitions to winning coalitions. A more convincing population scenario—many respondents with complete rankings, grouped by ranking type—still makes the mass of each type the coordinate in that same simplex. A fuller mirror could ask for Smith-set explanations or minimal explanations across pairwise contests. But with types as criteria and rankings as their preference orders, the paper’s necessary-preference definitions and explanation procedure already describe those calculations. The population story supplies an interpretation, not a new computational object.
A finite-electorate version would restrict the same simplex to points whose coordinates are multiples of \(1/n\). Studying how explanations behave near strict-inequality boundaries could be a separate question, but it would be a finite-to-continuous comparison, not a new continuous mirror of Propositions 1 and 2. And if a proposed mirror instead gives agents extra distinctions that affect the task, those distinctions must be included in the type; whether a useful high-multiplicity regime remains would then need its own justification.
This is not a universal proof that no worthwhile mirror exists. The paper’s social-choice connection makes a population interpretation natural, and a different computational task might survive. The negative case is narrower: the proponent’s two anchors, and the strongest direct extensions of them, restate computations the paper already formulates over continuous weights. That is the substantive obstacle to a new ChoCo mirror here—not that the population regime is implausible or that its answer might be easy.
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.