d4-conf-ecai-2012-0076

The strongest mirror is the paper’s cardinal-preference problem: choose a combinatorial outcome that minimizes the population’s weighted penalty. It preserves the paper’s central difficulty—the outcome is a complete assignment over many interdependent variables—while making the population a distribution over preference types.

A type \(t\) is a complete cardinal preference model: for example, a soft-constraint cost function \(f_t\) over outcomes. Let \(V=\{X_1,\ldots,X_m\}\) be finite-domain variables and \(X=\prod_i D_{X_i}\) the finite outcome space. An instance of Continuous Type-Weighted Cardinal Winner gives \(\tau\) types, positive binary-rational masses \(\mu_t\) summing to \(1\), and compactly represented costs. A concrete version uses factorized soft-constraint costs,
\[ f_t(x)=\sum_j \phi_{tj}(x|_{S_{tj}}). \]
The question is to return every outcome minimizing
\[ S_\mu(x)=\sum_t \mu_t f_t(x). \]
The solution is an ordinary discrete outcome; only the population is continuous.

A plausible regime is a large constituency choosing a bundle of interdependent policies, where millions of people use a moderate number of standardized preference models. The mass of a type is its share of the constituency. This is a credible high-multiplicity instance when people assigned to a type really do share the same costs and preferences. The type count is then the number of distinct models, not the number of people.

My anchor is Theorem 2, asserted as a result of this paper; its proof is omitted in the proceedings version, which points to a longer version with full proofs. It says: if the cardinal evaluation function \(F_{\text{Cardinal}}\) is admissible, SC* returns the set of winners under the chosen aggregation rule \(\circ\). The relevant premise is supplied by Theorem 1: when \(\circ\) is non-decreasing in each argument and commutative, \(F_{\text{Cardinal}}\) is admissible. These are exactness results, not claims that the problem is in P.

For the continuous problem, use
\[ F_\mu(a)=\sum_t\mu_t f_t(\operatorname{BPA}_t(a)), \]
where \(\operatorname{BPA}_t(a)\) is type \(t\)’s minimum-cost completion of partial assignment \(a\). Positive weights preserve the lower-bound property. And if the masses are rational, clearing denominators gives integer multiplicities \(q_t\); repeating each type \(q_t\) times multiplies \(S_\mu\) by a common positive constant and leaves its minimizers unchanged. So the weighted-type version is a direct high-multiplicity form of the problem Theorem 2 computes.

I expect this mirror to be Class B: hardness transfers, rather than a tractability result. The paper’s soft-constraint language can express a 3-CNF formula’s number of violated clauses as the cost of a single type. With \(\tau=1\), a minimum-cost outcome satisfies every clause exactly when the formula is satisfiable. That places the hard combinatorics in the number of outcome variables, not in population size. This hardness observation is a reduction from the model, not a hardness theorem proved by the paper. The continuous question still makes sense even if the answer is negative: it identifies a boundary where continuizing the population does not remove the outcome-space difficulty.

This case covers Theorem 2’s cardinal aggregation result for the weighted-sum rule. It does not extend the paper’s Copeland or Minimax sections, whose named results concern non-admissibility of their evaluation functions, or its max-aggregation experiments.

The weakest point is that the anchor establishes correctness, not an efficient running time in \(m,\tau,L\). The rational-mass dictionary also makes the mirror close to repeated finite profiles. Thus the paper supports the legitimacy and exact formulation of this continuous problem, but gives no bound showing that SC* or another algorithm avoids exponential search. Further questions include whether particular factor-graph structures yield algorithms parameterized by treewidth, and how the continuous runtime compares with high-multiplicity discrete input when \(\tau\) is small.