| paper | d4-conf-ijcai-2023-0506 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete for each fixed feature family: product, minimum, and maximum. · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Proposition 2
statement extracted from the paper’s text layer
Given \(n\), a fixed questionnaire \(Q\) of rational alternative pairs \((x_q,y_q)\in[0,1]^n\), a fixed feature map \(\phi\), and a finite support of complete respondent profiles \(\rho\in\{\succ,\prec,\sim\}^{Q}\) with positive binary-rational masses \(\mu_\rho\) summing to \(1\), together with rational \(\lambda,\delta>0\), find a normalized model \(m\) minimizing \(\sum_{\rho}\mu_\rho\sum_{q\in Q}\ell_{\rho,q}(m)+\lambda\sum_{|S|\ge2}|m_S|\), subject to \(m_{\emptyset}=0\) and \(\sum_{S\subseteq N}m_S=1\). Here \(\ell_{\rho,q}(m)=(\delta-\langle m,\phi(x_q)-\phi(y_q)\rangle)_+\) for \(x_q\succ y_q\), the same expression with \(x_q,y_q\) reversed for \(y_q\succ x_q\), and \(|\langle m,\phi(x_q)-\phi(y_q)\rangle|\) for indifference.
A large panel answers a fixed questionnaire, and a respondent type is their complete response profile \(\rho\). The society is a distribution \(\mu\) over those profiles. Learn one normalized multilinear or Choquet model \(m\) by minimizing the paper's preference and indifference slack loss, weighted by respondent mass, plus its sparsity penalty on interactions.
The paper learns a model for one decision maker, while pooled responses from heterogeneous panelists may not represent a coherent collective preference; the paper does not give that pooling a social interpretation.
fatal: False
The mirror covers sparse learning of multilinear and conjunctive or disjunctive Choquet models from preference and indifference judgments. It does not claim a complexity result for monotonicity enforcement or cover every experiment and extension.
The strongest honest mirror I see is Population Sparse Interaction Learning. It continuizes the people supplying preference judgments while leaving the paper’s criteria, utility vectors, and interaction model intact.
Imagine a large panel evaluating pairs from a fixed bank of alternatives. Each panelist is asked one standardized comparison. A type is \(t=(x,y,r)\), where \(x,y\in[0,1]^n\) are the alternatives’ utility vectors on the \(n\) criteria, and \(r\) records whether the panelist prefers \(x\) to \(y\) or is indifferent. The society is a distribution \(\mu\) over these types: \(\mu_t\) is the fraction of the panel giving that comparison and response. A plausible regime has many panelists but a much smaller support of repeated query-response types.
The decision variable is the paper’s model, \(m=(m_S)_{S\subseteq N}\), with \(F(x)=\langle m,\phi(x)\rangle\). Here \(\phi\) is fixed in advance as the multilinear, conjunctive Choquet, or disjunctive Choquet feature map. The continuous problem is:
Given \(n\), a finite support of types \(t=(x,y,r)\) with binary-rational masses \(\mu_t>0\) summing to \(1\), rational \(\lambda>0\) and \(\delta>0\), and a specified feature map \(\phi\), find an optimal normalized model \(m\) and nonnegative slack variables minimizing
\[ > \sum_{t\in P}\mu_t\epsilon_t > +\sum_{t\in I}\mu_t(\epsilon_t^-+\epsilon_t^+) > +\lambda\sum_{|S|\ge 2}|m_S| > \]
subject to \(m_\emptyset=0\), \(\sum_{S\subseteq N}m_S=1\), and
\[ > \langle m,\phi(x)-\phi(y)\rangle+\epsilon_t\ge\delta > \quad(t=(x,y,\text{pref})\in P), > \]
\[ > \langle m,\phi(x)-\phi(y)\rangle+\epsilon_t^+-\epsilon_t^-=0 > \quad(t=(x,y,\text{indiff})\in I). > \]
A solution is an optimal model and its feasible slacks.
This retains the paper’s central task: learn sparse interactions from preference and indifference examples, without imposing a maximum interaction size. Replacing example counts by rational masses is a direct high-multiplicity version of its loss; the criteria do not become continuous, and the interaction model is not simplified.
My lead anchor is Proposition 2, proved in this paper. For each IRLS subproblem \(P_k\), it gives an equivalent dual \(D_k\) with \(p+q+1\) variables and \(2(p+q)\) constraints, where \(p=|P|\) and \(q=|I|\). In the paper’s notation, the dual maximizes
\[
-\frac{1}{4\lambda}\Gamma^\top Q^\top D_k^{-1}Q\Gamma+\Gamma^\top L,
\]
for \(\Gamma=(\alpha,\beta,\mu)\), subject to \(0\le\alpha\le1\) and \(-1\le\beta\le1\). The matrices \(Q=(\delta_P,\delta_I,\mathbf 1)\) and \(L=(\delta,\mathbf 0,1)\) are data-dependent; \(D_k\) contains the current IRLS weights over the \(2^n\) model features. With masses on the support types, the same derivation gives mass-weighted bounds on the dual variables and a dual dimension of \(\tau+1\), where \(\tau=|P|+|I|\) is the support size.
This is an algorithmic formulation anchor, not a theorem that the problem is in P. The exponential feature dimension remains in the dual quadratic form. The paper’s kernel calculations and its numerical results—including experiments up to 22 criteria—make an efficient implementation credible, but they do not establish a worst-case polynomial running time in \(n,\tau,L\).
I would provisionally expect Class A in regimes with moderate \(\tau\) and exploitable feature kernels or sparse active interactions: the exact dual keeps the number of optimization variables tied to the number of observed types rather than to all interaction terms. That is a research expectation, not a result of this paper. The prover’s next questions are whether the implicit feature operations can be maintained efficiently across IRLS iterations, whether exact optimization has a polynomial bound, and how enforcing monotonicity changes that picture. The paper treats monotonicity as an additional constraint-generation problem, so the question should specify whether it is required.
The mirror covers the paper’s sparse learning of multilinear and conjunctive/disjunctive Choquet representations from pairwise preference and indifference examples. It does not claim a mirror for every experiment or extension in the paper.
The weakest point is the population interpretation. The paper learns a model for a decision maker from examples; this mirror learns a shared model from a panel’s judgments. That is plausible for large-scale group preference learning, but it is a shift in who supplies the data. The fit to the authors’ mathematical problem is strong—the same model and example-wise loss—but an author or referee could reject the panel interpretation if they require the learned relation to represent one individual decision maker.
Proposition 2 is the strongest anchor offered, but it is a dual-formulation result, not a complexity result for a population problem. It proves that each IRLS subproblem can be written with \(p+q+1\) dual variables. Replacing example counts by rational masses gives the same derivation: the dual bounds scale with the masses, while the feature space and the rest of the optimization remain as before. That makes a weighted version mathematically natural, but Proposition 2 itself does not establish a new algorithmic problem or a running-time bound in \(n,\tau,L\).
The deeper concern is what those “types” represent. In the paper, \((x,y,r)\) is one elicited judgment by a decision maker, not a complete description of a person. A decision maker can supply many such judgments, often on distinct utility vectors. Treating each judgment as a population type makes the support size count distinct training examples; it does not identify a regime with many interchangeable people per type. With continuously varying utility vectors, exact repeats are not a natural default.
The best repair is a panel answering a fixed questionnaire. Define each person’s type as their complete response profile, and let the society be a distribution over those profiles. That is a coherent group preference-learning problem, and it avoids treating individual survey answers as people. But the paper learns a model for a decision maker’s preference relation; it does not define how to combine different people’s relations into a social preference. If panel judgments are pooled through the same loss, the optimization uses the weighted frequencies of responses to each question. The distribution over whole response profiles contributes no distinct population structure to that objective. The mirror therefore requires a shift to collective preference learning, rather than simply continuizing the paper’s learning task.
This is a real objection to the proposed anchor, not proof that no useful version exists. The paper mentions multi-agent decision making, and its authors might recognize a panel model as a worthwhile extension. If they do, a continuous society of respondents is plausible. So the negative case is weakest at the universal claim: I can argue that Proposition 2 does not supply a convincing continuous-population complexity question, and that the best panel scenario changes the target, but I cannot honestly rule out the authors accepting that scenario as their 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.