| paper | d4-conf-ijcai-2018-0360 |
| 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→P discrete result → its continuous mirror
Answer: polynomial-time solvable · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 4
statement extracted from the paper’s text layer
Given a finite set of complete agent types \(\mathcal T\), rational masses \(\mu_\theta>0\) summing to one, and utilities \(u_\theta(\rho,s_\kappa)=v_\theta(\rho)+w_\theta(s_\kappa)\), choose nonnegative masses \(x_{\theta\kappa\rho}\) to maximize \(\min_{x_{\theta\kappa\rho}>0}u_\theta(\rho,s_\kappa)\), subject to \(\sum_{\kappa,\rho}x_{\theta\kappa\rho}=\mu_\theta\) for every \(\theta\) and \(\sum_\kappa x_{\theta\kappa\rho}=\sum_\lambda x_{\rho\theta\lambda}\) for every \(\theta,\rho\). Here \(x_{\theta\kappa\rho}\) is the mass of type-\(\theta\) agents who receive a service from type \(\kappa\) and supply their service to type \(\rho\); determine the optimum and its complexity in \(|\mathcal T|\) and the input bit length.
An atomless population with rational type masses and complete type-level utility profiles; each agent receives and supplies one indivisible service. Decision variables \(x_{\theta\kappa\rho}\) describe mass assigned to each incoming and outgoing type pair, reciprocal flows must balance, and the objective maximizes the least utility attained by any positive mass.
The mirror covers Proposition 4's Min objective for additively separable utilities. It does not claim mirrors for Proposition 3's Pareto-efficient and individually rational problem or the paper's Sum objectives.
The strongest mirror I see is Continuous Min-Service Exchange, anchored on the paper’s Proposition 4: “Computing a Min-optimal matching is NP-hard even for AS utility functions.” The authors prove this result here, by reduction from \((3,\mathrm{B2})\)-SAT. In their terminology, Min-optimal means maximizing the utility of the least-served agent, and AS means each agent’s utility separates into a term for who receives her service and a term for which service she receives. This is my sole anchor and lead.
The scenario I would offer is a large reciprocal service-capacity exchange: for example, participating units in a health or education network each contribute one indivisible service slot and receive one in return. A unit values both the kind of service it receives and the partner category that receives its own slot—for instance, specialty and accreditation or region. There could be tens of thousands of exchange units across dozens or hundreds of types. A type must specify the unit’s service and its complete utility profile, including how it values each recipient type. That preserves the paper’s partner externality; grouping agents merely by the service they offer would lose it.
Formally, let \(\mathcal T\) be the finite set of types, with rational masses \(\mu_\theta\) summing to one. A type-\(\theta\) agent supplies one whole service \(s_\theta\), and has utility \(u_\theta(\rho,s_\kappa)=v_\theta(\rho)+w_\theta(s_\kappa)\) when type \(\rho\) receives her service and she receives service \(s_\kappa\). Assume these values and masses are binary rationals. A solution is a nonnegative mass plan \(x_{\theta\kappa\rho}\): the mass of type-\(\theta\) agents who receive service from type \(\kappa\) and send their own service to type \(\rho\). It must satisfy
\(\sum_{\kappa,\rho\in\mathcal T}x_{\theta\kappa\rho}=\mu_\theta\quad\text{for every }\theta\),
and
\(\sum_{\kappa\in\mathcal T}x_{\theta\kappa\rho}=\sum_{\lambda\in\mathcal T}x_{\rho\theta\lambda}\quad\text{for every }\theta,\rho.\)
The second equality balances each type’s service sent to another type against the mass of that recipient type receiving it. In an atomless population these balanced masses can be paired into a measure-preserving exchange: each agent gets one whole service and sends one whole service. The question is to find such a plan maximizing \(\min\{u_\theta(\rho,s_\kappa):x_{\theta\kappa\rho}>0\}\), the least utility actually received by any positive mass of agents. This matches the paper’s Min objective without replacing it with average utility.
I expect this continuous problem to be tractable (Class A). For a proposed guarantee \(q\), forbid triples whose utility is below \(q\) and ask whether the remaining mass-balance system is feasible. That is an LP with at most \(\tau^3\) variables and \(\tau+\tau^2\) equalities, where \(\tau=|\mathcal T|\). There are at most \(\tau^3\) distinct utility values to check, so the exact optimum can be found in time polynomial in \(\tau\) and the input bit length \(L\). In fact, this LP argument works for arbitrary finite type-level utility tables; the AS restriction keeps the mirror aligned with Proposition 4.
The paper’s NP-hardness is still doing useful work here: it gives a sharp discrete anchor whose hardness may dissolve when a large population of identical types can divide across exchange patterns. A finite matching with \(n\) agents induces masses in multiples of \(1/n\); the continuous plan allows finer splits. This is the high-multiplicity relaxation at the heart of the mirror, and the change is visible in the feasible set. I would cover Proposition 4’s AS Min problem only, not claim a mirror for the paper’s Pareto-efficient and individually rational results or its other cardinal objectives.
The weakest point is that the regime depends on real repetition in the *complete* type profile. If partners are valued by personal identity—as in a house swap based on individual friendships—types may proliferate until \(\tau\) is close to the population size, and the scenario becomes unconvincing as a high-multiplicity one. The exchange-capacity example works only when partner categories genuinely capture the relevant differences. There is also a natural follow-up: quantify how well the continuous optimum can be rounded to a finite exchange with \(n\) agents, and identify when the discrete Min hardness reappears as the number of types grows.
The strongest objection is that the mirror’s useful compression may remove the paper’s defining externality. Each agent evaluates not just the service received but the *particular person* receiving her service. In settings like house swaps, where trust or familiarity is person-specific, a complete type must encode that person’s values for every possible recipient. As the population grows, those profiles may proliferate with the agents. Grouping people by broad partner categories would restore a small type space, but it could erase distinctions the original model was built to capture.
That objection does not defeat the proposed mirror. A network of exchange units could plausibly value partners by category, with each type recording its full utility profile over those categories. In that regime, the mass plan preserves the reciprocal exchange constraint, and maximizing the least utility has a direct threshold-LP formulation with polynomially many variables in the number of types. The paper’s Proposition 4 is a clear computational anchor, and the continuous question is well-posed even if its answer is straightforward.
So the negative case rests on uncertainty about whether a low-support, category-based regime is faithful to the authors’ intended service-exchange problem. The paper itself offers settings where such categories seem plausible. I cannot honestly turn that uncertainty into a claim that no worthwhile continuous mirror exists; this anchor survives the strongest objection available from the text.
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.