| paper | d4-conf-ijcai-2019-0902 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: every valid instance admits a pairwise stable allocation. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 6
Given finite types \(T\), item categories \(A\) with graph \(H\), rational type masses \(\mu_t>0\) summing to \(1\), rational per-capita supplies \(q_a>0\) summing to \(1\), valuations \(v_t(a)\), and directed influence coefficients \(\alpha_{s,t}\), does there exist \(x_{t,a}\ge 0\) with \(\sum_a x_{t,a}=\mu_t\) and \(\sum_t x_{t,a}=q_a\) such that no positive-mass assignments \(x_{t,a},x_{s,b}>0\) satisfy both \(U_t(b;x)>U_t(a;x)\) and \(U_s(a;x)>U_s(b;x)\), where \(U_t(a;x)=v_t(a)+\sum_s\alpha_{s,t}\frac{\sum_{c\in N_H(a)}x_{s,c}}{\mu_s}\)?
A continuum limit of a repeated-role block network: each person receives one whole item from an interchangeable category, while \(x_{t,a}\) records the mass of type \(t\) assigned to category \(a\). Type \(t\)'s utility for category \(a\) is \(U_t(a;x)=v_t(a)+\sum_s\alpha_{s,t}\frac{\sum_{c\in N_H(a)}x_{s,c}}{\mu_s}\); 2-stability rules out a mutually beneficial swap between any two positively represented assignments, evaluated at the unchanged aggregate \(x\).
The mirror covers Theorem 6's question of whether a 2-stable allocation exists. It leaves the PLS-complete computation result, the DAG core-stability result, and the envy-freeness result unmirrored.
The strongest honest mirror I see is existence of a pairwise-stable allocation in a nonatomic, typed graphical market. It keeps the paper’s central question—whether two agents can both gain by exchanging items—and makes the population large by repeating complete agent types.
Take a finite set of agent types \(T\), with rational masses \(\mu_t>0\) summing to \(1\), and item categories \(A\), with rational per-capita supplies \(q_a>0\) summing to \(1\). Each person receives one whole item; categories collect identical copies. The item categories form an undirected graph \(H\). Type \(t\) has an intrinsic valuation \(v_t(a)\) for category \(a\), and a directed influence profile \(\alpha_{s,t}\) describing how the assignment mix among type \(s\) affects type \(t\). A type includes the full valuation and influence profile, so people with different profiles count as different types.
The decision variable is \(x_{t,a}\), the mass of type \(t\) assigned category \(a\), subject to
\[
\sum_{a\in A}x_{t,a}=\mu_t,\qquad
\sum_{t\in T}x_{t,a}=q_a,\qquad x_{t,a}\ge 0.
\]
Each person still receives a whole item: \(x_{t,a}\) records what fraction of a type cohort receives category \(a\). Define the utility of a type-\(t\) person holding category \(a\) in mass allocation \(x\) by
\[
U_t(a;x)=v_t(a)+\sum_{s\in T}\alpha_{s,t}
\frac{\sum_{b\in N_H(a)}x_{s,b}}{\mu_s}.
\]
Call \(x\) 2-stable if there are no types \(t,s\) and categories \(a,b\) with \(x_{t,a}>0\), \(x_{s,b}>0\), \(U_t(b;x)>U_t(a;x)\), and \(U_s(a;x)>U_s(b;x)\). The question is: does a 2-stable mass allocation exist? A swap between two individual people has zero mass in this limit, so it leaves the type proportions \(x\) unchanged when evaluating their gains.
A plausible regime is a large organization assigning many employees to project families. Employees with the same project valuations and influence profiles form a type; their influence from another role is a normalized effect of that role’s assignment mix. With \(K\) interchangeable employees per role, the population has \(K|T|\) people and support size \(\tau=|T|\), where \(K\) can be much larger than \(\tau\). The type count may still grow with the input. That matters here: the paper’s NP-hardness reduction uses \(4m+2q\) player roles for a formula with \(m\) clauses and \(q\) variables. Its “six types” are broad sets, not necessarily six complete types once each role’s distinct influence profile is counted.
My anchor is Theorem 6, proved in this paper: deciding whether a graphical matching instance has a 2-stable allocation is NP-complete. Membership follows because a proposed allocation can be checked for blocking pairs in polynomial time; hardness is proved by reduction from 3-SAT. In that reduction, the constructed market has \(4m+2q\) players, with valuations, item categories, and directed influence weights arranged so a 2-stable allocation exists exactly when the formula is satisfiable. [Theorem 6 in *Graphical One-Sided Markets*](https://www.cse.iitk.ac.in/users/simon/papers/one-market.pdf).
I expect the typed mass-existence problem to remain hard, probably for continuum-specific reasons: the asymmetric influence structure remains, and choosing which type-category pairs have positive mass is itself combinatorial. But Theorem 6 does not establish that hardness. Its reduction may rely on assigning each role wholly to a category, while a mass allocation can split a type across categories. A reduction that rules out useful mixed assignments would support hardness transfer; without one, the finite result is an anchor for the question, not its answer.
I think the authors would recognize this as their problem’s continuous analogue: it retains one item per person, item-specific neighborhood effects, directed influence, and mutual-improvement swaps. The co-modifications are a supply of item categories that scales with population and a normalized, dense interaction profile, so that a type’s influence is determined by other types’ assignment proportions.
The weakest point is that this changes how neighborhoods are represented. The paper specifies edges between named people; the mirror aggregates influence between types. It fits a workforce with repeated roles and broad cohort-level exposure, but it does not cover every sparse, identity-specific network in the paper. This case covers Theorem 6’s 2-stable-existence question only; it does not claim a mirror for the paper’s PLS-complete computation result, DAG core stability, or envy-freeness.
The serious objection is to Theorem 6, the NP-completeness result for deciding whether a 2-stable allocation exists. There is no way to dismiss it as a missing computational anchor: the paper states the problem and gives a 3-SAT reduction.
The reduction, though, does not exhibit a high-multiplicity market. Its \(4m+2q\) players carry clause- and variable-specific influence edges and valuations. The six groups in the proof are broad role classes, not complete types: members need not have the same full influence profile. Grouping by that profile can leave nearly one type per player. So the hardness construction itself offers little evidence that the problem has a useful few-type population regime.
The stronger objection is about what the proposed mass model preserves. Its matrix \(x\) determines utilities only when people of a type have the same exposure to each other type, and items within a category are interchangeable. In a finite market, that amounts to a block-structured graph with normalized, often dense, interactions. If neighborhoods instead depend on particular coworkers or on local overlap patterns, \(x\) loses information needed to evaluate a swap; preserving that information can require splitting people into many types. The proposed model is therefore a new block-network market, not a general limit of the paper’s graphical matching problem.
That objection makes the mirror conditional, but it does not defeat the best version. Block networks are a special case of the paper’s weighted graphs, and repeated roles with shared project categories and cohort-level influence are plausible. In that setting, a mass allocation and a negligible pairwise swap are coherently defined. The fact that swaps do not change aggregate mass does not by itself make the stability question vacuous: the two participants can still compare their utilities at the unchanged aggregate.
So the strongest negative case is that the 3-SAT reduction does not justify the proposed population regime, and the proposed regime needs an independent case for its relevance to the authors’ problem. I would not call the mirror established by the paper’s hardness result. But I cannot honestly defend the universal claim that no worthwhile mirror exists: a typed block-network version is plausible, and Theorem 6 gives it a named computational question to study. The negative case is weak exactly where it must be strongest—against that better, restricted model.
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.