| paper | d4-conf-ijcai-2017-0763 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete, even for \(\tau=2\) with both masses equal to \(\frac12\) and integer offer payoffs. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 1
statement extracted from the paper’s text layer
Given a finite-support distribution \(\mu\) over responder types \(t=(w_t,P_t)\), where \(w_t\) is a resource capacity and \(P_t\) is that type’s finite menu of offers \((q_{tj},\pi_{tj})\), compute an aggregate response plan maximizing total payoff. For each type, feasible response sets are \(\mathcal F_t=\{S\subseteq P_t:\sum_{j\in S}q_{tj}\le w_t\}\). Choose \(\lambda_{t,S}\ge0\) with \(\sum_{S\in\mathcal F_t}\lambda_{t,S}=\mu_t\) to maximize \(\sum_t\sum_{S\in\mathcal F_t}\lambda_{t,S}\sum_{j\in S}\pi_{tj}\).
Types are complete responder profiles \((w_t,P_t)\); \(\mu_t\) is their population mass. Decision variables \(\lambda_{t,S}\) allocate each type’s mass among feasible accept-or-reject sets, maximizing aggregate payoff while preserving each individual resource cap.
The mirror covers Proposition 1’s response-choice hardness. It leaves the probability inequalities, coalition-selection methods, the full formation protocol, and the experimental comparisons unmirrored.
The strongest mirror is the paper’s Proposition 1, proved here: an agent’s optimal response to received proposals is NP-hard. Each proposal \(\tau\) has a required resource amount \(q_\tau\) and payoff \(\pi_\tau\); with resource capacity \(w\), the agent chooses a binary acceptance vector \(x\) maximizing
\[
\sum_\tau x_\tau \pi_\tau
\quad\text{subject to}\quad
\sum_\tau x_\tau q_\tau \le w.
\]
The paper says this follows by a reduction from KNAPSACK. This is a narrow result, but it gives a precise underlying problem to mirror.
Imagine a large platform or organization that issues standardized offers to many participants: for example, cohorts of volunteers choosing among shared projects, with a fixed contribution budget and the same task-specific contribution requests and rewards. A type \(t\) consists of a participant’s resource capacity \(w_t\) and complete menu of offers \((q_{tj},\pi_{tj})\). The society is a distribution \(\mu\) over these types. In a plausible high-multiplicity regime, there are many participants but few standardized capacity-and-menu profiles.
Here is the continuous problem. For each type \(t\), let \(P_t\) be its offers, and let \(\mathcal F_t\) contain the feasible response sets:
\[
\mathcal F_t
=
\left\{
S\subseteq P_t :
\sum_{j\in S} q_{tj}\le w_t
\right\}.
\]
Choose masses \(\lambda_{t,S}\ge 0\), where \(\lambda_{t,S}\) is the fraction of society of type \(t\) that accepts exactly the offers in \(S\). Require \(\sum_{S\in\mathcal F_t}\lambda_{t,S}=\mu_t\), and maximize total payoff:
\[
\max
\sum_t\sum_{S\in\mathcal F_t}
\lambda_{t,S}\sum_{j\in S}\pi_{tj}.
\]
Call this Continuous Coalition-Offer Response. Its solution is an aggregate response plan assigning mass to feasible acceptance sets. It preserves the paper’s individual resource cap and accept-or-reject choices; the fractional quantity is the share of each type taking each feasible response.
This is an exact population aggregation of the response problem, not a relaxation that makes an individual’s resource or offer divisible. With one type of mass \(1\), an optimal aggregate plan must place its mass on a best feasible response set. Thus an exact algorithm for the continuous problem would solve the KNAPSACK response instance. The expected classification is hardness transfers (Class B): the hard combinatorics are in the number of offers and their resource demands, not in the number of agents. Continuity does not dissolve this anchor.
This is a mirror of the response step in the authors’ protocol, not of their probability-bound methods or the entire overlapping-coalition-formation problem. The strongest objection is that Proposition 1 concerns one agent’s auxiliary decision, and identical incoming menus may be a restrictive regime in the paper’s network setting. Standardized offers to large cohorts make that regime plausible, but the mirror is less central than one of the paper’s probability-bound results would be if it had a named computational-complexity guarantee.
The formulation raises follow-up questions: how do the number of offers, resource capacity, and number of types affect exact and approximate algorithms? Does a pricing algorithm for the response sets yield useful methods when there are many types? And do shared constraints between responders—if introduced in a richer protocol—change the complexity of the aggregate problem?
Proposition 1 is the only result here that establishes computational hardness. The other numbered results are probability inequalities; the paper’s coalition-selection methods and protocol are evaluated experimentally, but no complexity classification is proved for them.
The proposed Continuous Coalition-Offer Response is a valid population model, but its aggregate optimization collapses. For each type \(t\), let \(v_t^*=\max_{S\in\mathcal F_t}\sum_{j\in S}\pi_{tj}\). Since there are no constraints linking one agent’s response to another’s, the proposed LP has value
\[
\sum_t \mu_t v_t^*.
\]
Every unit of mass of a type can take the same best response; splitting that mass among different responses helps only when they tie. This is the continuum degenerating in the relevant sense: the population creates no aggregate decision beyond scaling independent individual optima.
That remains true in the stronger version with many types and standardized menus. It asks for a collection of separate response optimizations, one per type. To make those optimizations interact, one could add shared task quotas, fairness constraints, or a central planner’s global objective. But none is part of Proposition 1’s response problem: agents choose independently under their own resource caps. Such constraints would define a new coordinated allocation problem, not a co-modification forced by making the population continuous.
So the mirror is legitimate, and hardness surviving in it is not my objection. The concern is that its computational content is still the individual knapsack choice that Proposition 1 already identifies. The continuum neither supplies a population-level optimization problem nor creates a role for the continuous-optimization machinery that motivates ChoCo. The paper’s probability-bound methods might inspire a different aggregate question, but without a complexity result for them that would be a new target, not a mirror of a named computational theorem.
This negative case is about value, not impossibility. A large organization with repeated offer menus is plausible, and the authors could recognize the aggregate formulation. But even there, the mass formulation only repeats independent decisions across types. I would reject this as a worthwhile ChoCo mirror, while conceding that the case is not airtight.
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.