| paper | d4-conf-ijcai-2018-0216 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(\operatorname{poly}(\tau(Q_1+Q_2),L)\) time, including an exact minimum and an attaining rational division. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given rational type masses \(\mu_t\) with \(\sum_t\mu_t=1\), a total utility \(T\), and two coalition-value functions \(\nu_i(q)=\max_{j\in[Q_i]}(b_{ij}+\sum_t a_{ijt}q_t)\) on \(D(\mu)=\prod_t[0,\mu_t]\), compute the minimum \(\epsilon_1+\epsilon_2\) and a type-symmetric per-unit division \(x\) attaining it, subject to \(\sum_t\mu_t x_t=T\), \(\epsilon_i\ge 0\), and \(\sum_t q_t x_t\ge\nu_i(q)-\epsilon_i\) for every \(q\in D(\mu)\) and \(i\in\{1,2\}\).
A society is a distribution \(\mu\) over a finite catalog of complete employee role types. Each scenario has an explicitly represented, convex, lattice-supermodular, piecewise-linear value function over coalition mass vectors; a type receives a common per-unit allocation \(x_t\), and coalitions may contain any mass \(q_t\in[0,\mu_t]\). Minimize combined scenario slack while finding a stable division. For the stated affine-piece representation, the constraints reduce to a rational LP.
The mirror covers the preference-core value and division results in Theorems 3 and 4 for explicit role-type value functions. It does not cover Theorem 5 or the specialized airport, multicast-tree, and induced-subgraph results.
The strongest mirror is the paper’s general two-scenario preference-core problem. It keeps the central question intact: can one divide a committed pool of utility so that no coalition wants to leave in either scenario, up to specified slack? The population becomes continuous; the scenarios and the utility-division question remain.
The paper’s Theorem 4, proved here using Edmonds’s cited submodular-intersection theorem, is my lead anchor. It states that the preference \((\epsilon_1,\epsilon_2)\)-core is nonempty exactly when
\[
\epsilon_1+\epsilon_2\ge
\epsilon^*=
\max_{S\subseteq N}\bigl(\nu_1(S)+\nu_2(N\setminus S)\bigr)-T,
\]
and that \(\epsilon^*\) can be computed in polynomial time in \(|N|\). The paper calls \(\max\{\epsilon^*,0\}\) the preference core value.
A second useful anchor is Theorem 3, also proved here: for fixed \(\epsilon_1,\epsilon_2\), if the preference core is nonempty, a value division in it can be found in polynomial time in \(|N|\).
Here is a concrete population regime. Consider a large employer dividing a committed reward pool between employees before it is known which of two project plans will be used. Employees fall into a fixed catalog of role types: employees of one type have the same skills, task portfolio, and terms relevant to both plans. The number of employees \(n\) is large compared with the number \(\tau\) of types. This resembles the paper’s own research-and-development example, but makes the cohort structure explicit. A coalition can consist of any fraction of each role type. Its mass vector \(q\) lies in
\[
D(\mu)=\prod_{t=1}^{\tau}[0,\mu_t],
\qquad
\sum_t\mu_t=1.
\]
Here \(\mu_t\) is the population share of type \(t\). Each scenario has a coalition-value function \(\nu_i(q)\), and a type-symmetric division pays \(x_t\) per unit of type \(t\), with \(\sum_t\mu_t x_t=T\). The values can include synergies among roles, so this is not restricted to additive rewards.
The specific continuous input class I would hand to a prover is rational and explicit: each \(\nu_i\) is a convex, lattice-supermodular, piecewise-linear function given as the maximum of \(Q_i\) affine functions,
\[
\nu_i(q)=\max_{j\in[Q_i]}
\left(b_{ij}+\sum_t a_{ijt}q_t\right),
\]
with \(\nu_i(0)=0\) and \(\nu_i(\mu)\le T\). For denominator \(n\) with \(n\mu_t\) integral, this gives a high-multiplicity discrete game: there are \(n\mu_t\) employees of type \(t\), a coalition with mass vector \(q\) has value \(n\nu_i(q)\), and each employee of type \(t\) receives \(x_t\). Dividing the discrete blocking inequalities by \(n\) gives the continuous ones.
For Theorem 3, the mirror question is: given \(\mu,\nu_1,\nu_2,T,\epsilon_1,\epsilon_2\), decide whether there is an \(x\) with \(\sum_t\mu_t x_t=T\) such that
\[
\sum_t q_t x_t\ge \nu_i(q)-\epsilon_i
\quad\text{for every }q\in D(\mu),\ i\in\{1,2\},
\]
and return such an \(x\) when one exists. This is a direct continuous version of finding a value division in the preference core. I expect it to be tractable for the stated representation.
For Theorem 4, the mirror question is: compute the least combined slack and a division attaining it, namely
\[
\mathrm{pcv}_{\infty}=
\min_{\substack{x,\epsilon_1,\epsilon_2\ge0\\
\sum_t\mu_t x_t=T}}
(\epsilon_1+\epsilon_2)
\quad\text{subject to}\quad
\sum_t q_t x_t\ge\nu_i(q)-\epsilon_i
\quad\forall q\in D(\mu),\ i\in\{1,2\}.
\]
This asks for the continuous preference-core value and a corresponding utility division. For the explicit piecewise-linear input above, both mirror questions reduce to a rational linear program. For each affine piece \(j\), the requirement over all \(q\in D(\mu)\) is equivalent to
\[
\epsilon_i\ge b_{ij}+\sum_t\mu_t\max\{a_{ijt}-x_t,0\}.
\]
Introducing variables for those positive parts gives an LP of size polynomial in \(\tau\), \(Q_1+Q_2\), and the input bit length. So the expected direction is Class A for this specified type-value model.
This covers Theorems 3 and 4, the paper’s general preference-core results. It does not claim a mirror for the specialized airport, multicast-tree, or induced-subgraph results. A natural further question is whether Theorem 4’s exact characterization also extends, with the subset maximum replaced by
\[
\sup_{q\in D(\mu)}
\bigl(\nu_1(q)+\nu_2(\mu-q)\bigr)-T.
\]
Another is how far the algorithm extends beyond explicitly listed affine pieces to more succinct descriptions of coalition values.
The weak point is the representation and anonymity assumption. The paper permits arbitrary supermodular characteristic functions on named players; this mirror assumes a small catalog of complete types and explicit piecewise-linear type-level value functions. A referee might accept it as a continuous version of the same preference-core problem, but not as a result covering the paper’s full input model. That limitation is real; it does not erase the mirror’s core question, which still ranges over fractional coalitions and asks for a stable division under two scenarios.
The strongest objection is that the proposed model adds the main structure it then exploits. Theorem 3 is a result about divisions for arbitrary supermodular games, using submodular intersection over subsets of named players. The mirror instead assumes permutation symmetry within each type, a scaling rule \(v_n(S)=n\nu(q(S))\), and an explicit piecewise-linear production function \(\nu\). Those assumptions make the coalition constraints an LP, but the paper’s theorem does not supply them.
That gap matters for the paper’s examples. In an induced-subgraph game, a player’s effect depends on their edges; in a multicast game, it depends on their location and paths. Grouping players by job title or location can discard exactly that information, while refining types to include the relevant network structure can make the number of types grow with the population. Airport games pose a different problem: coalition value can depend on whether even one high-cost player is present, rather than on a smooth per-capita mass. A better, succinct representation might preserve these structures, but the paper’s submodular-intersection theorem alone gives no continuous separation procedure for it.
Theorem 4 has the same limitation. Its formula over \(S\) and \(N\setminus S\) follows from a discrete min–max theorem. Replacing subsets by mass vectors and writing \(\sup_q[\nu_1(q)+\nu_2(\mu-q)]-T\) is a plausible question, but the paper does not establish that identity for the proposed continuous class. The alternative in the case for—minimizing total slack over the piecewise-linear model—is well-defined and LP-solvable, but it is a result about that new aggregate technology, not a consequence of the paper’s characterization.
This makes the case against strongest as a challenge to fidelity and scope: both anchors survive only after a substantial choice of anonymous, scalable coalition values. But I cannot honestly turn that into “no worthwhile mirror in any scenario.” The employee-role cohort is plausible, and the resulting core question remains recognizable. The negative case is therefore weak against the universal claim: it shows that the proposed mirror may not carry the paper’s general model or its named network examples, but it does not eliminate the role-based mirror.
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.