d4-conf-atal-2017-0121

The strongest mirror is continuous type-based coalition structure generation. It keeps the paper’s decision problem—form coalitions to maximize total value—and makes repeated agents a population distribution.

Consider a team-building market with a very large workforce: perhaps millions of people but only a few dozen relevant profiles, defined by skill, credential, availability, and compatibility. People with the same profile are interchangeable for team formation. Let \(T\) be the supported profiles and let \(\mu_t\) be the fraction of workers of type \(t\), with \(\sum_{t\in T}\mu_t=1\). A type-level MC-net rule \(r=(P_r,N_r,v_r)\) awards \(v_r>0\) to a team containing every required type in \(P_r\) and no type in \(N_r\). This is a natural high-multiplicity version of the paper’s team-synergy setting: the rule describes what a team needs, rather than naming a particular worker.

Here is a precise problem for a prover. The input is \(T\), rational masses \(\mu_t>0\), and a list of rules with \(P_r\ne\varnothing\), \(P_r\cap N_r=\varnothing\), and positive rational weights. For each nonempty \(S\subseteq T\), define
\[ V(S)=\sum_{\substack{r:\ P_r\subseteq S\\N_r\cap S=\varnothing}}v_r. \]
Let \(x_S\ge 0\) be the number of teams of composition \(S\) per member of the population. The mass-balance constraints are
\[ \sum_{S\ni t}x_S=\mu_t \qquad (t\in T). \]
The problem, Continuous Type CSG, is to maximize \(\sum_{S\ne\varnothing}V(S)x_S\), or, in its threshold form, decide whether a feasible \(x\) achieves value at least a given rational \(q\). A rational vector \(x\) attaining the maximum is a solution. The variables represent actual frequencies of teams under mass conservation, not a lottery over outcomes.

Allowing at most one worker of each type in a team is without loss for this rule language: a duplicate does not change which rules apply, and can be split into another team without reducing the original team’s value. In a finite workforce of \(n\) people, \(x_S\) corresponds to the number of such teams divided by \(n\); the continuous problem allows these frequencies to be fractional. Thus this is an explicit high-multiplicity relaxation of the discrete problem. Its LP has \(2^\tau-1\) possible team compositions. The dual’s pricing question is to find \(S\) maximizing \(V(S)-\sum_{t\in S}\lambda_t\), which makes the paper’s rule-interaction structure visible in the continuous model. The relevant input parameters are \(\tau\), the number of rules \(r\), and their binary encoding length \(L\), rather than the workforce size \(n\). In particular, enumerating all compositions gives an \(2^\tau\operatorname{poly}(\tau,r,L)\)-time algorithm, so the problem is FPT in \(\tau\).

My lead anchor is Theorem 1, which the paper attributes to Ohta et al. [25, Theorem 2], rather than proving here. In the paper’s setting of basic MC-nets with positive weights and no rule whose positive precondition is empty, it says that finding an optimal coalition structure is strongly NP-hard; moreover, unless \(\mathrm{P}=\mathrm{NP}\), there is no polynomial-time \(O(|P|^{1-\epsilon})\)-approximation for any \(\epsilon>0\), where \(P\) is the set of rules with nonempty positive preconditions. The paper notes that the strong-hardness statement follows from the cited proof.

The corresponding question is the unrestricted Continuous Type CSG problem above: determine its exact complexity and approximation landscape as \(\tau,r,L\) vary. My working prediction is hardness when \(\tau\) is part of the input—plausibly hardness specific to the continuous problem, because the difficult choice may sit in pricing over exponentially many type coalitions. But Theorem 1 does not establish that conclusion. The continuous LP can use fractional team frequencies, so the discrete inapproximability result might disappear. A useful next question is whether column pricing is polynomial, or whether that apparent LP bottleneck is itself hard.

A second, narrower anchor is Proposition 1, proved in this paper: under the same positive-weight, nonempty-positive-precondition assumptions, CSG is NP-hard even when the CSG-graph has at most three red edges. In the type-level version, form the same graph on rules: green edges record shared positive preconditions, and red edges record a positive precondition of one rule conflicting with a negative precondition of another. The mirror question is Three-Red-Edge Continuous Type CSG: solve the same threshold or optimization problem, with the promise that this graph has at most three red edges. I expect this case also to be hard as \(\tau\) grows, though with lower confidence: the paper’s reduction identifies a compact source of rule conflict, but its discrete NP-hardness need not survive fractional coalition frequencies. A polynomial algorithm here would be especially informative about where continuization changes the frontier.

I consider Theorem 1 the stronger anchor because it supplies both exact hardness and an approximation barrier. These mirrors cover the paper’s CSG hardness results in Section 3, including the three-red-edge restriction; they do not claim to mirror the CS-core results or the bipolar-MC-net tractability result.

The authors’ recognition test seems passable: the paper already studies coalition formation and uses project teams with positive synergies as its motivating example. A large workforce with many interchangeable workers per profile is a plausible regime for that same team-formation problem. The rules remain about coalition value; what changes is that they refer to shared types rather than named people.

The weakest point is that this type-level rule language is a modeling extension of the paper’s identity-based MC-nets, and the fractional \(x_S\) may erase precisely the discrete hardness the anchors establish. Also, when \(\tau\) is very small the problem is straightforward by explicit enumeration. Those are real limits on the hardness claim, but they do not undermine the mirror question: they make the type parameter and the discrete-to-continuous gap the subject of the complexity analysis.