| paper | d4-conf-aaai-2014-0330 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard, even with \(\tau=2\) and both masses equal to \(\tfrac12\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 12
statement extracted from the paper’s text layer
Given a binary-rational distribution \(\mu\) over compact preference-statement types on \(D=2^U\), with beneficiary type \(b\) having a two-level preference, does there exist a target type \(t\ne b\), a valid report \(q\), and a binary-rational mass \(x\) with \(0<x\le\mu_t\) such that \(\mu'=\mu-x\mathbf e_t+x\mathbf e_q\) and \(\operatorname{Opt}(\mu')\succ_{\rm ar,b}\operatorname{Opt}(\mu)\)? Here Pareto dominance is determined by all types of positive mass, and \(\succ_{\rm ar,b}\) is the beneficiary's strict average-rank comparison.
A continuous society is a distribution \(\mu\) over complete preference-statement types. A beneficiary with type \(b\) evaluates the Pareto-optimal outcome set using average rank; the decision is whether bribing a positive mass of some other type \(t\) to report \(q\) strictly improves that set.
The paper studies bribing one target, while the mirror needs a positive-mass bloc action; the delegate scenario makes that plausible but does not establish that the authors would recognize coalition bribery as their problem.
fatal: False
The mirror covers mass versions of average-rank bribery from Theorem 12 and lexmin bribery from Theorem 11. It leaves manipulation, compare-worst bribery, and the paper's structural characterizations aside.
The strongest defensible mirror is mass bribery: keep the paper’s combinatorial outcomes, Pareto aggregation, and way of comparing outcome sets, while making the population a distribution over preference types. The scenario is a large deliberative population choosing a combinatorial public plan. Residents with the same complete preference over plans belong to one type; their mass is their share of the population. Think millions of residents but comparatively few distinct preference types, each described by a compact preference statement. A recognized constituency can act through a delegate and coordinate a change to its reported preference.
Formally, let \(D=2^U\), and let the supported types \(p_1,\dots,p_\tau\) be preference statements over \(D\), with binary-rational masses \(\mu_j>0\) summing to one. Define \(X\succeq_\mu Y\) when every type of positive mass weakly prefers \(X\) to \(Y\); let \(\operatorname{Opt}(\mu)\) be the resulting Pareto-optimal set. For a designated beneficiary type \(b\), a mass-bribery action chooses a different target type \(t\), a report \(q\), and \(x\in(0,\mu_t]\), replacing that mass of type \(t\) by type \(q\):
\[
\mu'=\mu-x\mathbf e_t+x\mathbf e_q.
\]
The decision question is whether some such action makes the outcome set strictly better for \(b\). A solution gives \(t,q,x\) and the resulting comparison of \(\operatorname{Opt}(\mu')\) with \(\operatorname{Opt}(\mu)\). There is no monetary cost objective in the paper; the objective here is simply to obtain a strict improvement under the specified set comparison.
The lead anchor is Theorem 12, proved in this paper. It establishes that \(EM_{\rm ar}\) and \(EB_{\rm ar}\) are each \(\Sigma^P_2\)-complete when the agent seeking manipulation or bribery has a two-level preference. My mirror is the \(EB_{\rm ar}\) case: require the beneficiary type \(b\) to have two indifference strata, and measure improvement by lower average rank of the resulting Pareto-optimal set under \(p_b\). This preserves the paper’s underlying bribery question and its average-rank evaluation; only the target’s action is scaled from one agent to a positive mass of agents sharing a type.
A second anchor is Theorem 11, also proved here: both \(EM_{\rm lmin}\) and \(EB_{\rm lmin}\) are NP-complete. The corresponding continuous question uses the same mass-transfer instance and asks whether a target type can report \(q\) so that the beneficiary’s lexmin comparison improves—at the first preference stratum where the two sets differ, the new set has more outcomes in that stratum. This is a distinct mirror because it keeps the paper’s lexmin lifting rather than average rank.
I expect hardness to transfer for both unrestricted mass-bribery questions. A discrete profile with \(N\) agents maps directly to masses \(\mu_t=n_t/N\); bribing one agent of type \(t\) is the transfer \(x=1/N\). Thus the continuous formulation includes the paper’s instances and their hardness. The reductions may use \(\tau\) comparable to \(N\), however, so these anchors do not establish hardness when the number of types is small relative to the population. That is a separate high-multiplicity question. Useful next questions include whether the problems become tractable for fixed \(\tau\), and how the answers change when one limits the mass that can be bribed.
The mirror covers the paper’s computational results for strategic bribery and manipulation under Pareto aggregation with compact logical preferences. It does not continuize the outcome space or replace the paper’s lifting rules; the population is the continuous object.
The soft spot is that the paper studies a single agent bribing a single target, whereas a positive-mass transfer is naturally a coordinated bloc action. A nonatomic individual cannot change the support of the society and therefore cannot affect its Pareto frontier. The bloc version is plausible where constituencies act through delegates, but it is an extension of the authors’ unilateral problem. Also, Pareto optimality depends only on which types have positive mass: the numerical weights matter mainly for the size of the transfer and whether it removes a type altogether. So this is a credible continuous-population analogue, but it does not yet show that the paper’s problems gain the continuous-optimization advantages found in other continuization results.
The strongest problem for both proposed mirrors is the Pareto rule itself. For a society with support \(S=\{t:\mu_t>0\}\), Pareto dominance depends on which types are present, not on their masses: \(a\succeq_\mu b\) exactly when every \(t\in S\) weakly prefers \(a\) to \(b\). The same is true of \(\operatorname{Opt}(\mu)\). Cloning the population while keeping its type proportions fixed changes none of this.
That makes the two anchors behave alike. In Theorem 12, average rank evaluates the set of optimal *outcomes*; it does not average over the population. In Theorem 11, lexmin counts outcomes in preference strata; it also gives no role to population mass. In either mirror, the continuous coordinates matter only when they reach zero or become positive. A transfer of any amount \(x\in(0,\mu_t)\) leaves type \(t\) present, so its effect on the Pareto frontier is the same for every such \(x\). Transferring all of \(\mu_t\) can remove \(t\), which is a discrete support change. Both questions can be formulated, but their strategic geometry is about editing a finite support of preferences, not about how much population holds each preference.
There is also a singularity in carrying over the paper’s strategic act. The paper asks whether one agent can manipulate or bribe one target. In a society of \(N\) people, that target has mass \(1/N\). As the population grows, this mass tends to zero. If one agent has zero mass in the limiting model, changing their report leaves the society and its Pareto frontier unchanged. If any positive transfer is allowed so that a report can matter, the strategic act becomes a positive-mass coalition’s report. Since any positive mass of a new type imposes the same Pareto constraint, even an arbitrarily small coalition can have the full effect. That is a different strategic unit from the paper’s single target.
The constituency-and-delegate scenario is the best rescue: an organized bloc might coordinate a report, and a question about bribing such blocs could interest the authors. But it requires a coalition action that changes the preferences of a whole type at once. Adding a mass-based price does not smooth the Pareto effect: introducing a type has infimum cost zero, while removing one requires transferring its whole mass. Requiring a minimum share would add a new threshold to the model; making mass affect dominance would replace the paper’s Pareto principle. Either move could motivate a separate project, but neither follows from these anchors.
The case against is limited. A support-based coalition-bribery problem is well-defined, and the paper’s authors might recognize it as a useful extension. The argument here is that Theorems 11 and 12 do not, by themselves, yield a continuous-population mirror of unilateral manipulation or bribery: their population masses drop out, while preserving a single agent’s action makes that action vanish in the continuum.
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.