| paper | Sharing Rewards in Cooperative Connectivity Games |
| authors | Yoram Bachrach, E. Porat, J. Rosenschein |
| venue | JAIR 2013 |
| filed under | coalition · wvg |
| judged by | gpt-5.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 under polynomial-time Turing reductions; the decision part is \(\mathrm{coNP}\)-complete. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given a finite graph \(G=(V,E)\) with primary vertices \(V_p\), backbone vertices \(V_b\), and standard server-role types \(T=V_s\), rational masses \(\mu_t\ge0\) with \(\sum_t\mu_t=1\), thresholds \(0<\theta_t\le\mu_t\), nonnegative reward densities \(q_t\) with \(\sum_t\mu_tq_t=1\), and rational \(\epsilon\), let \(x_t\in[0,\mu_t]\) be participating mass and declare role \(t\) active iff \(x_t\ge\theta_t\). Decide whether every \(x\) for which \(V_p\) is connected in \(G[V_p\cup V_b\cup\{t\in T:x_t\ge\theta_t\}]\) satisfies \(\sum_tq_tx_t\ge1-\epsilon\); equivalently, decide whether \(\min\{\sum_tq_tx_t:x\in[0,\mu],\ v_\theta(x)=1\}\ge1-\epsilon\), and return a violating \(x\) when not.
A quorum-activated typed population on a finite connectivity graph: each type \(t\) is a cohort of interchangeable operators for one server role, with mass \(\mu_t\), activation threshold \(\theta_t\), and reward density \(q_t\); the decision variable is participating mass \(x\), and the objective is the minimum reward \(q\cdot x\) of a winning mass coalition.
The quorum threshold changes the paper's characteristic function, and the reduction's continuous coordinates collapse to a finite selection of structurally distinct topology-bearing roles, so direct inheritance from Theorem 4 is not established.
fatal: False
The mirror covers Theorem 4's general-graph \(\epsilon\)-core membership hardness; it leaves the power-index results, tree algorithms, polynomial core computation, and nucleolus questions unmirrored.
My strongest mirror is a continuous-population version of the paper’s \( \epsilon \)-core membership problem, anchored in Theorem 4.
The regime is a large network-operations society. There are many interchangeable maintenance agents or server replicas, but only \( \tau \) distinct server-role types. A type \(t\) is defined by its incident network links, operational threshold, reward rate, and all other parameters relevant to connectivity. Its mass \( \mu_t \) is the fraction of the maintenance population assigned to that role, with \( \sum_t\mu_t=1 \) and typically \( \tau\ll N \).
The graph of primary, backbone, and standard server roles remains finite. What becomes continuous is the participating population. A coalition chooses a mass vector \(x\), where \(0\le x_t\le\mu_t\). Role \(t\) is operational when \(x_t\ge\theta_t\), where \(\theta_t\) is a quorum threshold, naturally \(\theta_t=\rho_t\mu_t\). The coalition wins when the primary vertices are connected in the graph induced by the operational standard roles together with the backbone and primary vertices. The quorum is the necessary co-modification: without it, any positive mass of a type would activate a server role, and individual agents in a nonatomic population would have zero pivotal power.
An imputation is now a nonnegative reward density \(q_t\) per unit mass, normalized by \( \sum_t\mu_tq_t=1 \). A winning coalition \(x\) receives \(q\cdot x=\sum_tq_tx_t\). The continuous question is therefore:
\[ \textsc{Mass-}\epsilon\textsc{-CG-Membership} \]
Given \(G\), its primary and backbone vertices, type masses \(\mu\), thresholds \(\theta\), reward densities \(q\), and rational \(\epsilon\), decide whether
\[ q\cdot x\ge 1-\epsilon \]
for every winning mass vector \(x\). Equivalently, determine whether the cheapest winning mass coalition has cost at least \(1-\epsilon\), and if not return a winning \(x\) violating the inequality.
This is a direct continuous analogue of the paper’s ECM problem: the reward remains a unit-valued connectivity reward, coalitions still deviate to establish their own network, and the core condition still quantifies over all winning coalitions. Only the population and coalition participation become fractional. With equal reward density \(q_t=1\), the imputation is the continuous counterpart of the equal imputation in the paper.
The anchor is Theorem 4, proved in this paper: “ECM is coNP-complete in general CGs, even if the imputation to be tested is the equal imputation \(p=(1/n,\ldots,1/n)\) and if there is a single backbone vertex.” The paper proves this by reducing VERTEX-COVER. Its construction creates one standard vertex for every original graph vertex, one primary vertex for every original edge, and one backbone vertex. A coalition wins exactly when the corresponding standard vertices form a vertex cover. Under the equal imputation, a winning coalition of size \(s\) has excess \(1-s/n\), so testing whether the maximal excess is at most \(1-t/n\) is equivalent to asking whether the original graph has a vertex cover of size at most \(t\).
The same reduction survives in the continuous problem. Set \(\mu_t=1/n\), \(q_t=1\), and \(\theta_t=\mu_t\). Then a role is operational only when its entire role mass participates, and every minimal winning mass vector corresponds exactly to a vertex cover. The continuous question is therefore coNP-hard on a literal subfamily of the model. More importantly, the replicated version with \(\theta_t=\rho\mu_t\), for fixed \(0<\rho<1\), remains meaningful: a fraction \(\rho\) of a large cohort of interchangeable server operators must be available. The cost of a cover of size \(s\) becomes \(\rho s/n\), so choosing \(\epsilon=1-\rho t/n\) gives the same reduction. I would expect hardness to transfer: the difficult combinatorics live in the network’s role structure, not in the number of individually named agents.
This is a credible high-multiplicity scenario. For example, a cloud or smart-grid operator may have thousands of interchangeable maintenance agents assigned to each of a small number of network roles, with a quorum of each role required for reliable service. The authors should recognize the question as theirs: it is still about stable reward sharing for coalitions that maintain network connectivity, not about fractional outcomes or an unrelated cooperative-game relaxation.
A second, somewhat weaker but still good mirror uses the paper’s Theorem 1, also proved here: “CG-BANZHAF is \(\#P\)-hard, even if there are no backbone vertices.” The paper establishes membership in \(\#P\) in Lemma 1, so together these results yield \(\#P\)-completeness. Theorem 1 reduces \(\#\)SET-COVER: a target vertex is critical precisely for coalitions corresponding to set covers.
The corresponding continuous problem is:
\[ \textsc{Mass-CG-Banzhaf} \]
Use the same typed population and connectivity rule, set \(\theta_t=\mu_t/2\), and independently draw a participation mass \(X_t\) uniformly from \([0,\mu_t]\) for every non-target type. Define the aggregate Banzhaf influence of target type \(\hat t\) as
\[ \beta_{\hat t}^{\infty} = \Pr\!\left[v(X_{-\hat t},\mu_{\hat t})=1\right] - \Pr\!\left[v(X_{-\hat t},0)=1\right]. \]
The task is to compute this rational number exactly. It measures the probability that the entire target cohort changes network connectivity when other cohorts have continuously varying participation masses.
This is not the ordinary Banzhaf index of one infinitesimal agent; that quantity collapses to zero in a nonatomic population. It is the natural aggregate index of a high-multiplicity type. With \(\theta_t=\mu_t/2\), each type is operational with probability \(1/2\), independently. Thus the continuous expression exactly reproduces the discrete Banzhaf calculation on the role types. Theorem 1’s \(\#\)SET-COVER reduction therefore embeds directly, so I expect \(\#P\)-hardness to transfer. The associated continuous Shapley question is also natural, but I would not use Corollary 1 as a separate anchor: it would add little beyond the Banzhaf case.
The further questions are worthwhile: whether approximate aggregate power is easier than exact power; whether bounded treewidth or tree networks give polynomial algorithms; whether the continuous Shapley and Banzhaf notions diverge under nonuniform thresholds; and whether the continuous least core or nucleolus can be computed through a separation oracle.
The weakest point is the quorum threshold and, for the power-index mirror, the shift from an individual agent to a whole type cohort. A referee could argue that a raw nonatomic version of the paper’s game is degenerate: an individual has zero mass and cannot change connectivity. I concede that objection. The positive case depends on the operationally natural replicated-server interpretation, where a role becomes usable only after a positive quorum of its interchangeable population is active. If that co-modification is rejected, the Banzhaf mirror is weak. The \( \epsilon \)-core mirror is more robust: it remains a direct mass version of the paper’s deviation and reward-sharing problem, and Theorem 4’s hardness survives even on the equal-density, single-backbone subfamily.
I would therefore grade the paper as supporting a serious continuous mirror, with Mass-\(\epsilon\)-CG-Membership as the lead question, expected to lie in Class B because its hardness is carried by the network structure rather than population multiplicity.
The negative case is strongest at the modelling level: in this paper, agents are not a population occupying interchangeable social types. Each agent is the owner of one structurally specific vertex. The agent set and the graph topology are the same object.
That defeats the proposed reading of Theorem 4. Setting \(\mu_t=1/n\) for one type per graph vertex does not create a high-multiplicity society; it merely relabels each named agent as a type and assigns it mass \(1/n\). The VERTEX-COVER reduction still uses \(n\) structurally distinct roles. In the programme’s sense, those roles are not interchangeable: their incident edges determine exactly which primary vertices they can connect.
Replicating each role does not repair this without changing the game. If copies are parallel replicas, the original connectivity condition activates a role as soon as any positive mass participates. In a nonatomic limit, the cost of activating a role collapses toward zero, and the continuous deviation problem degenerates. The proposed threshold \(\theta_t=\rho\mu_t\) prevents that collapse, but it is not forced by continuization. It introduces quorum-operated network roles and changes the characteristic function from the paper’s vertex-connectivity game to a new threshold connectivity game. That may be an interesting model, but Theorem 4 no longer establishes a continuous mirror of the paper’s problem; it establishes hardness for a newly designed role-quorum game.
The same issue is visible in the claimed preservation of the reduction. With \(q_t=1\), a winning mass vector is minimized by activating exactly the threshold of each selected role. Thus the supposedly continuous problem immediately rounds to a finite selection of roles. The mass coordinate is only a scaling device; the meaningful coalition is still a subset of graph positions. This is not a high-multiplicity relaxation of individual deviations, but a discrete role-selection problem decorated with divisible participation.
The Banzhaf proposal is weaker still. Banzhaf power is the marginal contribution of one named agent under uniformly random subsets. In a nonatomic population, one individual has measure zero and cannot change a positive connectivity threshold, so individual Banzhaf power is zero. The proposed \(\beta_{\hat t}^{\infty}\) instead assigns power to an entire type cohort. That is a different player set and a different index.
Nor does the proposed uniform random mass arise as the high-multiplicity limit of the paper’s Banzhaf experiment. If type \(t\) has \(N_t\) interchangeable agents, a uniformly random coalition produces
\[ X_t=\frac{K_t}{N_t}, \qquad K_t\sim\operatorname{Binomial}(N_t,1/2), \]
so \(X_t\) concentrates at \(1/2\) as \(N_t\to\infty\); it does not become uniform on \([0,\mu_t]\). Under this genuine limit, type-level connectivity becomes almost deterministic, while the power of an individual member tends to zero. Making the whole cohort the player yields the ordinary finite Banzhaf index on role types, not a continuous-population index. The proposed uniform law is therefore an added participation model, not a continuization of Theorem 1.
One could choose another law for random participation, or define a smooth reliability payoff depending on mass. But then the result is about a newly specified stochastic or threshold network-reliability model. The paper provides no canonical way to choose that law, and the resulting quantity is no longer the Banzhaf or Shapley value studied there. The continuous variable is either irrelevant between thresholds, or it is doing work only because extra semantics have been supplied.
This is not an objection that the continuous answer might remain hard. Hardness would be a perfectly worthwhile outcome if the population model were genuine. The objection is that the proposed anchors never reach that point: Theorem 4 is transferred by replacing named vertices with thresholded roles, while Theorem 1 is transferred by replacing individual power with an ad hoc cohort statistic. Both constructions move the combinatorial content into a finite role game and add continuity only as multiplicity or random participation.
The negative case is not airtight. A genuinely replicated-server setting with explicit quorum requirements could be a sensible new cooperative network model, and it might deserve separate study. But that is the strongest escape hatch, not a continuous mirror already latent in this paper. On the paper’s own terms, its computational agents are topology-bearing identities, not a high-multiplicity population; the proposed continuous mirrors require changing precisely that fact.
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.