d4-conf-atal-2014-0068

The lead I would defend is Quota-MC Most-Violated Coalition: a continuous, type-based version of the paper’s question of whether some coalition earns more than its proposed payment.

My anchor is Theorem 3, proved in this paper. Its Class 6 entry says that CORE-EMPTINESS, NOT-IN-CORE, and MOST-VIOLATED-COALITION are all NP-complete for MC-nets with no negative pattern values, with both \(\land\) and \(\lor\) allowed, and with no \(\neg\). I rely on the last result: given a payment vector \(x\) with \(x(A)=v(A)\) and a goal \(\gamma\), deciding whether a proper nonempty coalition \(S\) has \(v(S)-x(S)>\gamma\) is NP-complete. The continuous question below mirrors that blocking-coalition computation.

A type is a role that completely specifies an agent’s participation in the issue patterns and their transfer rate. There are \(N\) agents but only \(\tau\) such roles: for example, \(K\) interchangeable members in each of \(\tau\) organizational cohorts, with \(N=K\tau\) and \(K\) large. The society is a distribution \(\mu\) over the roles, with \(\sum_t\mu_t=1\). A coalition is a mass vector \(z\) with \(0\le z_t\le\mu_t\). Its members remain whole people; \(z_t\) records how much of type \(t\)’s interchangeable cohort joined.

Here is the problem as I would hand it to a prover. Each issue is a nonnegative-weight formula using \(\land\) and \(\lor\), with atomic conditions of the form \(z_t\ge q\), where \(q\) is a rational participation quota for that type and issue. Let \(V(z)\) be the total weight of satisfied issues. The input also gives nonnegative per-unit-mass payment rates \(p_t\) satisfying \(\sum_t\mu_t p_t=V(\mu)\), and a rational goal \(\gamma\). Decide whether there is a proper nonempty coalition mass vector \(z\) such that \(V(z)-\sum_t p_tz_t>\gamma\). A solution is such a \(z\), which certifies a blocking coalition. The quota predicates give the formulas a direct population meaning: an issue pays when a role contributes its required share. A whole-society issue can use quotas \(q=\mu_t\) for every type.

This is a plausible regime for cooperative games about pooled projects, unions, or institutions: many people share each role, issues depend on role participation, and transfers are uniform within a role. The core question is unchanged: can a coalition obtain more than it is paid? Uniform rates do not discard meaningful individual distinctions here, because role membership includes every core-relevant distinction.

The continuous problem retains the anchor’s hardness. Adapt the paper’s hitting-set construction. Given \(H_1,\ldots,H_m\subseteq[n]\) and \(k\le n\), use types \(0,\ldots,n\), each with mass \(\mu_t=1/(n+1)\). For each \(H_i\), add an issue of weight \(1\) that fires if \(z_j\ge1/[2(n+1)]\) for some \(j\in H_i\). Add a weight-\(m\) issue that fires only when \(z_t=\mu_t\) for every type. Set \(p_j=2\) for \(j\ge1\), \(p_0=2(n+1)(m-n/(n+1))\), and \(\gamma=m-(k+1/2)/(n+1)\). The full society has value and total payment \(2m\). For a proper coalition, the grand-society issue does not fire. Recruiting the quota from any element type costs exactly \(1/(n+1)\), matching that element’s payment in the paper’s construction. Thus a hitting set of size at most \(k\) gives an excess above \(\gamma\); conversely, exceeding \(\gamma\) requires firing every hitting-set issue and recruiting at most \(k\) element types. Since the quota and formula thresholds are rational, witnesses can be represented by their finite threshold choices. This gives NP-hardness, and the finite threshold certificate gives NP membership for the stated nonnegative-rate problem.

I expect hardness to persist, in a Class B-like way: the reduction’s combinatorics are in the number of distinct roles and issue patterns, not in the number of people within each role. The construction is an explicit hardness argument for this continuous problem; it is not a claim that every finite MC-net instance embeds unchanged into it.

The scope is deliberately narrow: this mirrors the MOST-VIOLATED-COALITION result for the Class 6 structure. It does not claim to mirror every row of Table 1 or the paper’s results for other representations. It raises the further question of whether continuous core emptiness is also NP-complete under the same quota semantics, and whether restrictions such as bounded \(\tau\) or bounded formula width yield tractable cases.

My weakest point is the quota co-modification. The paper’s patterns test membership of named agents; this mirror tests whether a type supplies a specified mass. That is a genuine change in the worth model. I think authors working on compact issue patterns and coalition stability could recognize it as a natural high-multiplicity extension, especially for cohort-based participation problems, but it is less direct than simply allowing fractional payments. The case survives because the coalition, issue-value, transfer, and blocking questions all remain intact, and the adapted hardness argument makes the proposed question concrete.