| paper | On Graphical Modeling of Preference and Importance |
| authors | R. Brafman, C. Domshlak, S. E. Shimony |
| venue | JAIR 2006 |
| filed under | voting · combinatorial |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | no |
The paper has clear named computational results, but the proposed \(B_N(\mu)\) puts mass on selector assignments inside one agent's outcome-space representation, not on a society of agent types. Under full support, the proposed decision problem merely rewrites the paper's existential cycle test; treating \(w\) as an external customer type changes the model and requires a new population-validation problem. The opponent therefore defeats all three anchors as continuous-population mirrors.
fails bit b-changes — the continuum limit changes the question
The risk statistic weights assignments internal to one TCP-net, so it does not create a population-level computational problem; making them external types changes the semantics.
fatal: True
The proposed construction addresses Theorems 2–4 only through the conditional-acyclicity certificate; it leaves the paper's optimization, dominance, and consistency-construction results untouched.
The strongest mirror I believe in is a population-level version of the paper’s conditional-acyclicity test. The population is not made continuous by fractionalising product configurations; each customer still receives an ordinary integral configuration. What becomes continuous is the mass of customers or configuration requests occupying different contexts under a shared TCP-net.
Consider a large product-configuring service. Millions of customers use the same standardized preference template \(N\), over binary product attributes \(V\), but their fixed context values differ: deployment environment, urgency, budget tier, intended use, and so on. Let \(S(N)\) be the TCP-net’s selector variables. A complete agent type is \(t_w=(N,w)\), where \(w\in\{0,1\}^{S(N)}\) is that customer’s context. The society is a distribution \(\mu\) over these types, with \(\mu_w\) the fraction of requests having context \(w\). In the high-multiplicity regime, many customers share every practically relevant context type.
For each \(w\), form exactly the \(w\)-directed dependency graph \(N_w^\star\) from Definitions 8 and 9 of the paper. Define the conditional-acyclicity risk
\[ B_N(\mu)=\sum_{w\in\{0,1\}^{S(N)}}\mu_w\, \mathbf 1[N_w^\star\text{ contains a directed cycle}]. \]
The continuous problem is TCP-Net Continuum Risk: given \(N\), \(\mu\), and a tolerance \(\varepsilon\), decide whether \(B_N(\mu)>\varepsilon\), or compute \(B_N(\mu)\). Operationally, a deployment team may quarantine or re-elicit a mass \(\rho_w\) of each context type, minimizing \(\sum_w\rho_w\), subject to the remaining population having conditional-acyclicity risk at most \(\varepsilon\). At zero tolerance, the minimum quarantined mass is exactly \(B_N(\mu)\).
This is a genuine population question: the output is the fraction of society for which the paper’s structural consistency certificate fails. It does not replace the paper’s TCP-net, its CITs, its selector semantics, or its directed-cycle condition by an easier preference model. It replaces the paper’s universal question “does some possible context create a cycle?” with the practically distinct question “what mass of actual users or requests lies in such contexts?”
My lead anchor is Theorem 2, proved in this paper. It states that, for a binary-valued TCP-net \(N\), deciding whether \(N^\star\) has a conditionally directed cycle is NP-complete, even when every ci-arc has a selector set of size exactly at most \(1\). The reduction is from 3-SAT: it creates Boolean variables for formula variables, clause variables, and literal variables; adds importance arcs from each clause variable to its literals; and adds conditional-importance arcs whose orientations depend on the corresponding truth variable. A clause gives a directed path to the next clause exactly when that clause is satisfied, so the network has a conditionally directed cycle exactly when the formula is satisfiable. Membership in NP follows from guessing a semi-directed cycle and a selector assignment that orients it into a directed cycle.
The corresponding continuous problem is Full-Support TCP-Net Risk, the above problem restricted to such binary TCP-nets and to a full-support population, for example the uniform distribution \(\mu_w=2^{-|S(N)|}\). The question is whether \(B_N(\mu)>0\). Because every \(w\) has positive mass,
\[ B_N(\mu)>0 \quad\Longleftrightarrow\quad \text{some }w\text{ makes }N_w^\star\text{ cyclic}. \]
Thus Theorem 2 gives NP-completeness of the zero-versus-positive-risk version, and the richer exact-risk problem is at least NP-hard. The expected classification is Class B: the hardness lives in the TCP-net’s variable and clause structure, not in the number of agents. Repeating each context among a huge population does not dissolve it. Exact computation of \(B_N(\mu)\) would naturally raise a further weighted-counting question, plausibly related to \(\#\)SAT, although that stronger claim is not proved by this paper.
A second worthwhile anchor is Theorem 3, also proved here. It states that the same conditional-directed-cycle decision problem remains NP-complete for binary-valued, \(1\)-cycle-bounded TCP-nets, even when every ci-arc has selector set of size at most \(3\). Here the constructed dependency graph has only one semi-directed cycle, \(C,C_1,\ldots,C_n,C\). The selector set of the arc from \(C_j\) to \(C_{j+1}\) consists only of the variables in clause \(C_j\), and the arc points forward exactly when that clause is satisfied. Consequently, the sole cycle can be oriented precisely when all clauses are satisfied.
Its mirror, Single-Cycle Continuum Risk, uses the same \(B_N(\mu)>0\) question but restricts \(N\) to this one-cycle, selector-arity-three class. Theorem 3 again gives NP-completeness under full-support \(\mu\). This is not merely a duplicate of Theorem 2: it shows that the positive case cannot dismiss the hardness as an artefact of exponentially many possible semi-directed cycles. The expected classification is again Class B.
The useful boundary anchor is Theorem 4, proved in this paper using Lemma 4 and a reduction to \(k\)-SAT, with the standard polynomial-time algorithm for \(2\)-SAT cited from elsewhere. It states that, for a binary-valued \(m\)-cycle-bounded TCP-net where \(m\) is polynomial in the input size and every ci-arc has selector set of size at most \(2\), deciding whether \(N^\star\) has a conditionally directed cycle is in P. The paper encodes the possible orientation of each semi-directed cycle as a \(k\)-CNF formula; when \(k=2\), this is a polynomial-time \(2\)-SAT test, and the polynomial number of cycles can be checked separately.
The corresponding problem, Two-Selector Continuum Risk, asks whether \(B_N(\mu)>0\) under the same structural restrictions. For full-support \(\mu\), this is exactly the paper’s existence question, so Theorem 4 gives a polynomial algorithm. This is a Class A region of the mirror. It does not imply that exact computation of \(B_N(\mu)\) is polynomial: exact risk may require weighted counting of satisfying selector assignments. The theorem supports the positive-risk detection problem, while leaving a natural continuum-specific counting problem open.
The authors should recognize this mirror as close to their own application domain. The paper explicitly motivates TCP-nets by personalized product configuration, resource-constrained choice, and preference elicitation “en masse.” A population of customers sharing standardized TCP-net templates is a credible high-multiplicity regime. The continuous object is the society of requests, not the product space: configurations remain discrete, and the mass \(\mu_w\) records how much society is exposed to each context. This is also not a novelty collision. The paper studies one TCP-net and requires every possible selector assignment to yield an acyclic directed graph; it does not study a distribution over agents or the mass of contexts failing that condition.
The weakest point is that the population extension is deliberately built around the paper’s conditional-acyclicity certificate rather than its constrained optimization algorithm. A hostile reader could call it a weighted quality-assurance wrapper around a single-agent problem, especially when the support distribution is given succinctly as a product distribution. I would not claim that Theorems 2–4 establish hardness or tractability for every possible population-level TCP-net optimization problem. But the mirror preserves the paper’s exact computational object, gives mass a real operational meaning, has a plausible high-multiplicity scenario, and exposes a clean hardness/tractability boundary. It therefore provides a defensible continuous mirror for the paper’s conditional-acyclicity results, with Theorem 2 as the strongest anchor.
The negative case is that the proposed “risk” is not a continuization of the paper’s computational problem. It turns an internal consistency certificate for one TCP-net into a weighted audit statistic over assignments to that network.
In the paper, \(w\in D(S(N))\) is an assignment to selector variables within the outcome space. It is not a voter type or a customer context. The conditional-acyclicity requirement quantifies over every such \(w\) because the TCP-net is supposed to define one preference relation over the whole outcome space. If one assignment produces a directed cycle, the network has no globally satisfying preference order. Giving that assignment zero population mass does not repair the network; it merely changes the domain on which consistency is demanded.
Thus the proposed quantity
\[ B_N(\mu)=\sum_w \mu_w\mathbf 1[N_w^\star\text{ is cyclic}] \]
measures the frequency of bad certificates in the assignment space of one representation. It does not measure a population property relevant to the paper’s decision problem. The “quarantine” problem is correspondingly separable: inspect each \(w\), remove the bad ones, and add their masses. There is no shared allocation, social outcome, preference aggregation, or population-level intervention. The continuum contributes weights, but no computational coupling.
This defeats Theorem 2 as an anchor. Under full support,
\[ B_N(\mu)>0 \]
is simply the paper’s existential question written with a positive weight on every assignment. The selector assignment witnessing satisfiability has been relabelled as a “context,” but it has not become a population type. If \(w\) is instead made an external customer context, then it is no longer a selector variable ranging over the TCP-net’s outcome space; one has introduced a restricted-domain or context-indexed model that the paper does not define. That may be a sensible new model, but Theorem 2 no longer directly anchors its central computational question.
Theorem 3 does not repair this defect. Removing all but one semi-directed cycle makes the underlying certificate simpler, but \(C,C_1,\ldots,C_n\) and the selector variables remain parts of one constructed TCP-net. The alleged population still consists only of assignments to a single-instance reduction gadget. “Single-cycle continuum risk” is therefore the same audit construction with a smaller graph, not a population version of the theorem.
Theorem 4 has the same problem in the positive direction. Its polynomial result concerns whether any assignment can orient a cycle. The proposed full-support problem merely asks whether the corresponding weighted bad-assignment mass is positive. The paper gives no result about computing the weighted mass itself, and the exact-risk extension becomes a new weighted-counting problem rather than a continuization of the theorem’s algorithm. The two-selector restriction is a boundary of the TCP-net certificate, not a boundary concerning population multiplicity.
The strongest rescue would assign each customer a complete TCP-net, perhaps with external context, and ask for the mass of customers whose models are inconsistent. That is well-defined, and the high-multiplicity story is plausible; I am not objecting to repeated TCP-net types, finite type spaces, or integral configurations. But this rescue is a model-validation problem, not social choice. If one adds a common configuration, shared resources, majority aggregation, or a winner-selection rule so that the population genuinely interacts, those additions supply the substantive problem. The paper contains no aggregation or population-allocation semantics to determine which one to use, and Theorems 2–4 cease to be results about that central task.
So the paper does contain genuine computational theorems, and the proponent is right that high multiplicity is not inherently implausible here. The failure is more basic: the proposed mirrors put mass on contexts that are semantically internal to a single preference representation. Keeping the paper’s semantics yields a weighted certificate audit; making the contexts genuinely population-level requires adding a new social-choice problem. On the programme’s standard, neither is a worthwhile continuous mirror of this paper.
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.