d4-conf-aaai-2017-0902

The strongest mirror I see is narrow: the weak least-core computation for the induced subgraph game in Theorem 7, proved in this paper. The theorem says that, given a weighted hypergraph \(G=(V,E,w)\), one can compute a value division in its strong and weak least cores in \(O(|V|^2 f(|V|, O(\sum_{e\in E}|e|))L)\) time, where \(f\) is the max-flow running time on the associated graph and \(L\) is polynomial in \(|V|\) and \(|E|\). The paper proves this using an ellipsoid method and hypergraph minimum-cut separation; the max-flow/min-cut subroutine is cited. The paper gives no comparable named hardness result, so this is the right kind of algorithmic anchor.

A plausible high-multiplicity setting is a large collaboration network: many firms participate in joint projects, and a project creates surplus only when all its required participants join the same alliance. Firms of the same type have the same role and the same interaction rates with every combination of roles. There might be millions of firms but only a few dozen such types. This is a mirror of block-structured induced-subgraph games, not of every arbitrary hypergraph in the theorem.

Here is the direct continuous problem I would hand to a prover: Block-Hypergraph Weak Least Core. Let \(\Omega\) be an atomless population of total mass \(1\), partitioned into \(\tau\) types with rational masses \(\mu_t>0\). Give a finite list of interaction schemas \(h=(t_1,\ldots,t_r)\), each with nonnegative rational weight \(w_h\): an interaction of that schema contributes its weight when all its participants belong to the coalition. For a coalition \(A\), let \(z_t=\mu(A\cap\Omega_t)\). Its normalized value is
\[ \nu(z)=\sum_{h} w_h\prod_{j=1}^{r(h)}z_{t_j}. \]
A division pays each member of type \(t\) at rate \(p_t\). Find the largest \(\epsilon\), and a division attaining it, subject to
\[ p_t\ge 0,\qquad \sum_t\mu_t p_t=\nu(\mu),\qquad \sum_t p_t z_t\ge \nu(z)+\epsilon\sum_t z_t \]
for every coalition with \(0<\sum_t z_t<1\). The continuous weak least-core value in the paper’s sign convention is \(-\epsilon\). Every vector \(z\) in the type-mass box is realizable by a coalition, since each type is atomless.

For this exact mirror, I expect tractability—but with a degenerate answer. Any budget-balanced division has slack tending to zero for coalitions whose mass tends to the whole population. Since the weak margin there tends to \(\epsilon\), no \(\epsilon>0\) can satisfy all the constraints. Thus the optimum is \(0\). A core division is available explicitly: split each interaction’s value equally among its participants, giving
\[ p_t=\sum_h \frac{w_h}{r(h)} \sum_{j:t_j=t}\ \prod_{k\ne j}\mu_{t_k}. \]
For each schema, this allocation to a coalition is at least that schema’s value for the coalition, so the constraints hold at \(\epsilon=0\). Computing these rates is polynomial in the number of schemas, their size, \(\tau\), and the input bit length.

That is a faithful population-continuous version of the paper’s weak least-core question, and the authors should recognize the model. It also shows why the mirror is modest: the nontrivial algorithmic content of Theorem 7 disappears in the atomless limit. A natural follow-up is a macroscopic weak least core, imposing the deviation constraint only when \(\rho\le\sum_t z_t\le1-\rho\) for a fixed rational \(\rho>0\). That avoids both vanishingly small coalitions and coalitions arbitrarily close to the grand coalition. Its separation problem resembles a mass-constrained hypergraph cut; I would expect hardness to transfer from a corresponding finite, balanced-deviation problem, though that is a conjecture, not a result of this paper.

My weakest point is that this useful macroscopic variant changes which coalitions count as deviations, while the exact continuous mirror has a zero margin. I would therefore claim a sound, recognizable mirror for the weak least-core part of Theorem 7—not that its original polynomial-time result survives unchanged, or that this one model covers the paper’s other results.