| paper | d4-conf-aaai-2013-0162 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: \(\mathrm{P}\) for all six rule–cost combinations, with running time \(\bigl((m+\tau)L\bigr)^{O(1)}\) bit operations. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given \(q\) binary issues, a supported type set \(T\subseteq\{0,1\}^q\) with binary-rational masses \(\mu_t\), a target bundle \(A\in\{0,1\}^q\), a rule \(V\in\{\mathrm{SP},\mathrm{SA},\mathrm{SB}\}\), a cost scheme \(C\in\{C_{\mathrm{equal}},C_{\mathrm{do}}\}\), and budget \(\beta\), is there a choice of converted masses \(b_t\in[0,\mu_t]\) for \(t\ne A\) that makes \(A\) win at cost at most \(\beta\)? Each type \(t\) has independent unary preferences with value \(1\) for \(t_i\) and \(0\) for the other value on issue \(i\); converting mass changes those preferences to favor \(A\). The cost is \(\kappa_C\sum_{t\ne A}b_t\), where \(\kappa_{C_{\mathrm{equal}}}=1\) and \(\kappa_{C_{\mathrm{do}}}=2\). For each issue \(i\), require the target value’s resulting mass to be at least one half when the fixed tie-break favors it, and strictly greater than one half otherwise.
A configurator population is given by fractions of users with each supported binary preference vector \(t\). The briber chooses mass \(b_t\) to convert from each type \(t\) to the target-preference type \(A\), paying the paper’s uniform per-unit cost for this family. Minimize \(\kappa_C\sum_{t\ne A}b_t\) subject to the target winning each issue under the paper’s sequential rules and tie-breaking; budget feasibility is linear feasibility with the corresponding weak or strict majority constraints.
Covers Theorem 5 on its independent binary, two-level fuzzy-preference family for \(\mathrm{SP}\), \(\mathrm{SA}\), and \(\mathrm{SB}\), with \(C_{\mathrm{equal}}\) or \(C_{\mathrm{do}}\); it does not cover general tree-shaped CSPs, the other cost schemes, or the paper’s one-step results.
The strongest anchor is Theorem 5, proved in this paper. It says that for tree-shaped fuzzy or weighted CSP profiles, \((V,C)\)-Bribery is NP-complete and W[2]-complete when parameterized by the budget, for each \(V\in\{\mathrm{SP},\mathrm{SA},\mathrm{SB}\}\) and \(C\in\{C_{\mathrm{equal}},C_{\mathrm{do}}\}\). The proof reduces from Optimal Lobbying; the paper cites Christian et al. (2007) for that problem’s W[2]-completeness. In the reduction, each lobbying row becomes a voter with independent binary issues and a unique best assignment; the target is the lobbying vector. A non-target voter costs \(1\) under \(C_{\mathrm{equal}}\), or \(2\) under \(C_{\mathrm{do}}\) for the two-level fuzzy preferences used there. Thus a budget of \(k\) or \(2k\), respectively, corresponds to changing at most \(k\) rows.
I would mirror the reduction’s own setting, rather than claim to have captured every feature of the paper. Consider a product configurator with \(q\) binary features. A user’s type \(t\in\{0,1\}^q\) is their complete preference model: an independent unary soft constraint for each feature, assigning preference \(1\) to \(t_i\) and \(0\) to the other value. Equivalently, \(t\) is their uniquely preferred bundle. A plausible high-multiplicity regime is a large customer survey in which millions of users choose among bundles built from a standard feature set, and many share one of a relatively small number \(\tau\) of recurring like/dislike profiles. A vendor seeking to make bundle \(A\) win offers incentives for customers to report preferences that favor \(A\).
Call the continuous problem Fractional Binary Sequential Bribery. An instance gives \(q\), a rule \(V\in\{\mathrm{SP},\mathrm{SA},\mathrm{SB}\}\), a cost scheme \(C\in\{C_{\mathrm{equal}},C_{\mathrm{do}}\}\), a support \(T\subseteq\{0,1\}^q\) with binary-rational masses \(\mu_t\) summing to \(1\), a target bundle \(A\), and a normalized budget \(\beta\). The briber chooses, for each type \(t\ne A\), a mass \(b_t\in[0,\mu_t]\) to convert to type \(A\): those users change their unary preferences so \(A\) becomes their unique optimum; the remaining mass keeps its original preferences. For the two-level fuzzy CSPs above, each converted unit costs \(1\) under \(C_{\mathrm{equal}}\) and \(2\) under \(C_{\mathrm{do}}\), exactly the paper’s charge for making a non-optimal target optimal. The question is whether the briber can make \(A\) win for total normalized cost at most \(\beta\); the optimization version minimizes that cost. The solution is the vector of converted masses and the resulting society. With binary domains, all three sequential rules reduce here to issue-by-issue majority, with the paper’s tie-breaking rule.
This problem has a direct LP formulation. At issue \(i\), the target’s vote margin after bribery is its original margin plus \(2\sum_{t:t_i\ne A_i}b_t\). Requiring that margin to meet the paper’s tie-breaking condition for every issue gives one linear comparison per issue; the cost bound is \(\kappa_C\sum_{t\ne A}b_t\le\beta\), where \(\kappa_C=1\) or \(2\). There are \(\tau\) mass variables and \(q\) winner constraints, so this mirror should be Class A: tractable by linear programming, including its exact budget-feasibility version. Its runtime is polynomial in \(q,\tau\), and the encoding length \(L\). A discrete election with \(N\) voters embeds when \(\mu_t=n_t/N\); discrete bribery choices correspond to masses \(b_t\) on the \(1/N\) grid. The continuous question relaxes that grid, which is precisely where the row-selection hardness may disappear.
The mirror covers Theorem 5’s sequential-rule and \(C_{\mathrm{equal}}/C_{\mathrm{do}}\) cases on the independent binary fuzzy-CSP family used in its reduction. It does not claim to cover the paper’s full tree-shaped CSP setting or its other cost schemes and one-step results. A natural next question is whether the same LP description extends to general tree-shaped types, where conditional reports across sequential rounds may interact, and how much the continuous optimum can differ from the finite \(1/N\)-grid optimum.
The weak point is that the proposed scenario uses users with exactly repeated, independent binary preferences. That is a restricted regime. Its defense is that this restriction is not an arbitrary simplification added to make bribery easy: it is the family the authors themselves use to establish Theorem 5. The case is therefore strongest as a mirror of that hardness result’s core. The broader claim—that all sequential soft-CSP bribery admits a similarly clean mass LP—would need separate proof.
The strongest case against this mirror is that it captures only the unusually spare family used in Theorem 5’s reduction. With independent binary issues and two-level preferences, SP, SA, and SB all collapse to issue-by-issue majority. The mirror therefore says little about how soft constraints or the three sequential rules behave beyond that family. Its bribery operation also assumes a per-capita price: a fraction of each type can be converted at the same unit cost as an individual. That is a modeling choice, not a consequence of the paper’s discrete budget.
But those points do not defeat the anchor. Theorem 5 proves hardness on exactly this family, and the choice of family is not an objection under the programme’s standard: a continuous mirror may cover one result’s meaningful instance regime. A population of configurator users with recurring preferences over a standard set of binary features is plausible, and the preference vector is a complete type for this problem.
The proposed LP also has the right shape. Let \(b_t\) be the mass converted from type \(t\) to the target type \(A\), with \(0\le b_t\le\mu_t\). At each issue, the target’s margin changes linearly with the mass whose vote changes toward \(A\). There are \(\tau\) conversion variables and \(q\) winner constraints; the per-unit costs for the reduction’s \(C_{\mathrm{equal}}\) and \(C_{\mathrm{do}}\) cases are uniform. Thus the continuous question is a genuine computational mirror with a direct Class A formulation. That its answer differs from the discrete hardness result cannot count against it.
A broader mirror could allow transfers among reporting types, with costs on the transfer arcs. Questions about whether that cost model is natural, or whether the fractional version is a familiar lobbying relaxation, make the proposed contribution narrower. They do not show that no scenario yields a worthwhile mirror. The honest negative case is weak here: Theorem 5’s anchor survives.
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.