| paper | d4-journals-jair-2005-0038 |
| 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→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard, even for \(\tau=2\); decidable in \(2^{O(m)}\operatorname{poly}(\tau,L)\) time. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
Given \(m\) resource kinds, a finite set of utility types \(\mathcal T\) with binary-rational masses \(\mu_t\) summing to \(1\), rational utility functions \(u_t\), per-capita supplies \(q_r\), and feasible initial and target configurations \(x^0,x^1\), decide whether a finite sequence of IR mass O-contracts reaches \(x^1\) from \(x^0\). A configuration \(x_{t,S}\) gives the mass of type \(t\) holding integral bundle \(S\subseteq R\), with \(\sum_S x_{t,S}=\mu_t\) and \(\sum_{t,S:r\in S}x_{t,S}=q_r\). Each stage transfers some \(\delta>0\) mass from \((t,S)\) and \((t',S')\) to \((t,S\cup\{r\})\) and \((t',S'\setminus\{r\})\), where \(r\notin S\), \(r\in S'\), and both source cohorts have at least mass \(\delta\); the stage is IR when it strictly increases utilitarian welfare.
A society is a distribution \(\mu\) over complete utility types; each type's mass is distributed over integral bundles, and each resource has fixed per-capita supply \(q_r\). A mass O-contract moves \(\delta\) mass between two type-bundle cohorts by transferring one resource, preserving type masses and supplies, and requiring a strict increase in total utility.
A cohort can split across bundles and recombine, so the discrete two-agent reduction's reachability obstruction may disappear; the proponent flags this issue but gives no preservation argument.
fatal: False
The mirror covers IR O-contract reachability and minimum IR O-contract path length over type-mass configurations. It leaves \(M(k)\)-contracts, other rationality criteria, and the paper's additional allocation properties aside.
The strongest mirror I believe in is continuous IR O-reachability. Consider a large resource exchange with many interchangeable agents but only a few complete utility types: for example, many firms trading standardized task bundles, with members of each type sharing the same valuation of every bundle. Let \(R\) be the \(m\) resource kinds, \(\mathcal T\) the \(\tau\) utility types, and \(\mu_t\) the fraction of society of type \(t\). A configuration \(x\) records \(x_{t,S}\), the mass of type \(t\) holding the integral bundle \(S\subseteq R\). Each resource has a fixed per-capita supply \(q_r=\sum_{t,S\ni r}x_{t,S}\). Thus individuals still hold indivisible bundles; only the population-level quantities are fractional. Take utilities \(u_t(S)\) to be rational-valued circuits on the bundle’s incidence vector, with monotonicity promised, and give the initial and target configurations as binary-rational support lists.
A continuous O-contract chooses a recipient type and bundle \((t,S)\), a donor type and bundle \((t',S')\), a resource \(r\notin S\) with \(r\in S'\), and a rational mass \(\delta>0\) available in both source cohorts. It transfers \(r\) from \(\delta\) mass of type \(t'\) holding \(S'\) to \(\delta\) mass of type \(t\) holding \(S\). The bundles of those individuals remain integral, and the transfer preserves each type’s mass and every \(q_r\). It is IR precisely when the paper’s utilitarian welfare strictly increases: \(\delta[u_t(S\cup\{r\})-u_t(S)+u_{t'}(S'\setminus\{r\})-u_{t'}(S')]>0\). This keeps the paper’s deal and rationality semantics while making mass, rather than agent identity, the unit of population change.
My lead anchor is Theorem 2, which is *quoted here, not proved here*: the paper’s Related Work attributes it to Dunne, Wooldridge, and Laurence (2003, Theorem 11). It says that deciding whether an individually rational deal between two allocations can be realized by an IR O-contract path is NP-hard, even with \(n=2\) agents and monotone utility functions. The continuous problem is Continuous IR O-Reachability: given \(m,\mathcal T,\mu,u,q\), and feasible initial and target configurations \(x^0,x^1\), decide whether a finite sequence of the mass O-contracts just defined takes \(x^0\) to \(x^1\). A solution is such a finite sequence, including each transfer’s types, bundles, resource, and mass. I expect hardness to transfer (Class B): the discrete hardness already holds with just two agents, so it is not driven by population size; the combinatorics over resource subsets remains in the mirror. The proof obligation is to show that divisible cohorts do not create a route unavailable to the discrete instance.
A second, related anchor is Theorem 4, proved in this paper. For \(m\ge14\), it constructs two-agent settings with monotone utilities and an IR endpoint deal such that every IR O-contract path realizing the deal has length at least \((77/128)2^{m/2}-3\) when \(m\) is even, and at least \((77/128)2^{(m-1)/2}-3\) when \(m\) is odd. Its mirror, Continuous IR O-Distance, asks for the minimum number of mass O-contract stages from \(x^0\) to \(x^1\), with value \(\infty\) if no path exists. I expect the individual-deal lower bound to weaken: one cohort transfer can move a positive mass of interchangeable agents at once. A plausible Class A target is a bound polynomial in the number of type-bundle configurations, with a further question of whether that can be compressed to a bound polynomial in \(m,\tau,L\). I would not claim that result without a scheduling argument; succinct utility representations may also make the relevant bundle optimization hard.
These are recognizable continuizations of the paper’s own questions: the resource kinds, integral bundles, utilities, O-contract, welfare test, and target reallocation all remain. What changes is that repeated agents of the same complete type become mass cohorts. The scenario has \(N\gg\tau\): many traders with a small number of recurring valuation and cost profiles, and resource supplies scaled with the population. I cover only IR O-contract reachability and path length. The paper’s \(M(k)\)-contract result is outside this mirror: limiting a deal to at most \(k\) named participants does not define a positive-mass action without changing the question.
The weak point is real: fractional cohorts can split and recombine, so a path that must visit exponentially many discrete allocations may acquire shortcuts. The reachability anchor is also cited from earlier work, and the supplied text does not specify that result’s utility encoding; matching its encoding is necessary to make a hardness-transfer claim. Still, this mirror gives the authors a direct question in their model: does allowing interchangeable populations to trade in mass change reachability or the minimum number of rational exchange stages?
The strongest case against these mirrors is about the meaning of a “deal.” The paper counts sequential bilateral contracts between particular agents. A positive-mass O-contract instead batches many such contracts into one stage. That changes the object Theorem 4 measures: different portions of the population could advance along different allocation paths in the same stage, so the paper’s unique long path need not survive. If a stage must remain one literal bilateral contract, then in a continuum each individual has measure zero and the move changes no aggregate state. Preserving the original coupling would require tracking who is paired with whom or which path each agent has followed; those labels could grow with the population and defeat the small-type premise.
The same problem weakens the Theorem 2 mirror. Its two-agent reduction moves through allocations of one shared set of resources. Cloning those agents into two mass cohorts allows exchanges across all clones, and a type-level configuration can split each cohort across many bundles. That is a coherent bulk-trading model, but its reachability question depends on choices the paper does not make: whether clones may trade across replicas, what resources scale with population, and how surplus compensates members who lose utility. Restricting trade to preserve the original two-agent interactions would require labels that undermine the proposed compression. The mirror therefore has no canonical lift from the paper’s reachability problem.
This is a real objection to treating either proposed result as a direct continuization of the paper’s negotiation process: the mass model changes what counts as a stage, and potentially which trades are available. It is weaker as an argument that no worthwhile mirror exists. A population of traders with a few shared utility types is plausible, and continuous bulk exchange is a sensible question in its own right. From the supplied text alone, I cannot honestly rule out a worthwhile mirror; the negative case depends on the authors not recognizing that bulk-trading question as theirs.
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.