| paper | d4-conf-ecai-2010-0094 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper’s numbered results characterize deal rationality and reachability, but none asserts that an allocation or deal can be computed, or that computing one is hard. The paper explicitly leaves the complexity of allocation feasibility and sufficient deals to future work, so the plausible continuous allocation question has no computational result here to anchor it.
fails bit a — no named computational result to mirror
The proposed mirror concerns reaching a welfare-maximizing allocation from an initial allocation through individually rational deals; it leaves the paper’s linear-logic encoding, valuation-language results, and proof-search background aside.
The positive case has a limit: this paper contains no numbered result that classifies a computational problem as in P, NP-hard, or otherwise. It develops a formal model and proves structural results, but its conclusion explicitly leaves the complexity of allocation feasibility and sufficient deals to future work. So, under your anchor rule, there is no qualifying anchor.
The closest substantive result is Theorem 23, proved in the paper: for any allocation \(A\) with less utilitarian social welfare than a maximum-welfare allocation \(A^*\), there is an individually rational deal taking \(A\) to \(A^*\). The proof uses Proposition 16, which says any two allocations can be related by some deal formula, and Theorem 22. Theorem 22, also proved here, says that a deal from \(A\) to \(A'\) is individually rational exactly when \(A'\)'s utilitarian social welfare exceeds \(A\)'s by at least one unit. The paper notes that this adapts Endriss et al.’s Lemma 1 to integer-valued utilities. These are useful anchors for a mirror, but they are not complexity classifications.
The most convincing regime is a large public or platform resource-allocation system: many recipients, but relatively few recurring valuation profiles over bundles of resources. A type is a recipient’s complete valuation function, including any relevant constraints; mass \(\mu_t\) is the fraction of the population with type \(t\). It is plausible to have millions of recipients and tens of types. Bundles remain integral for each recipient; a type’s mass may be split across different bundles. Resource supplies scale with population, so their per-capita amounts are specified in the instance. This makes the society continuous while keeping the paper’s allocation question recognizable.
My lead candidate is Continuous Individually Rational Reachability to Welfare Optimum. An instance gives resource kinds \(G\), rational per-capita supplies \(q_g\), a finite support of \(\tau\) valuation types with rational masses \(\mu_t\), and a feasible initial allocation \(x^0_{t,B}\). Here \(x^0_{t,B}\) is the mass of type \(t\) receiving integral bundle \(B\), and each type’s mass sums to \(\mu_t\). Valuations \(v_t(B)\) may be given explicitly or by the paper’s valuation formulas.
The question is to find a feasible allocation \(x^*\) maximizing
\[
W(x)=\sum_{t,B}x_{t,B}v_t(B),
\]
together with a mass-flow deal \(z_{t,B,B'}\) taking recipients from their initial bundles to their final bundles, and per-recipient money transfers on those flows. The deal must respect resource supplies, balance payments across the population, and leave every participant weakly better off, with a positive mass strictly better off if the initial allocation was suboptimal. If the initial allocation is already optimal, the solution reports that and returns a no-op. The solution is the allocation, deal, and transfers—not a proof encoding.
This is a direct population analogue of Theorem 23: it asks whether the society can reach a socially optimal allocation through an individually rational deal. Theorem 22 supplies the expected transfer condition: with divisible population mass, strict aggregate welfare increase replaces the discrete theorem’s increase of at least one utility unit. That changes the threshold because welfare is now aggregated over rational masses; it does not change the underlying negotiation question.
For explicitly listed bundles and values, the allocation part is an LP over the variables \(x_{t,B}\); the deal and balanced transfers can also be represented with linear constraints. That is a Class A expectation in this representation. With compact valuation formulas, the interesting question is whether the LP’s pricing problem—optimizing a type’s value against resource prices over integral bundles—is efficient. That is where the continuous-optimization machinery mentioned in the programme could matter. The discrete bridge is natural: a finite election-style population with \(n_t\) agents of each type gives \(\mu_t=n_t/n\), while the continuous model allows type mass to split across bundles without requiring individual identities in the instance.
My weakest point is also the central one: this would be a worthwhile continuous-population problem, but it is not a mirror of a complexity result in this paper, because the paper proves no such result. With explicit bundle values, the LP may make the computational question straightforward; with compact formulas, its complexity depends on the pricing problem that the paper does not analyze. The authors could recognize the model as a sensible high-multiplicity version of their welfare-and-negotiation problem, but the required anchor-based case cannot honestly be made from this paper.
The strongest negative is that this paper offers no computational result about resource allocation or negotiation to continuize. Its conclusion explicitly leaves the complexity of allocation feasibility and sufficient deals to future work. The proof-search complexity statements in Section 3 are background results about fragments of linear logic, not complexity classifications of the paper’s allocation problems. So the proposed mirror has no qualifying computational anchor.
The proponent’s best anchors are Theorems 22 and 23, but their content makes the proposed reachability question collapse. Theorem 22 equates individual rationality, with unrestricted balanced side payments, to a strict increase in utilitarian welfare. Proposition 16 lets an arbitrary deal formula express any transition between allocations. Together, they make Theorem 23 an existence statement: any feasible welfare-improving transition can be called a deal, and any welfare optimum is reachable in one such deal. A continuous version with mass flows and transfers preserves that structure. Its central computation is simply finding a welfare-maximizing allocation; the negotiation language adds no constraint the optimizer must solve.
A stronger formulation could use many recipients with a small number of recurring valuation types, integral bundles for each recipient, and supplies that scale with population. That is a plausible high-multiplicity regime, and fractional mass assigned across bundles is a sensible aggregate description. But it does not rescue these anchors. If bundle values are explicitly listed, the allocation problem is an ordinary LP whose size depends on the list. If valuations are compactly represented, the interesting difficulty is pricing over bundles; this paper neither studies that problem nor shows that its continuous version is tractable. Either way, the pricing question would be a new computational project attached to the paper’s setting, not a mirror of its results.
I cannot honestly defend the universal claim that no worthwhile continuous-population problem can arise in any scenario: the repeated-recipient regime is plausible, and a pricing study could be worthwhile on its own. The defensible negative is narrower. This paper gives no computational result for the continuization programme to mirror, and its strongest structural results reduce to welfare improvement under unrestricted deals. The proposed model may motivate new work, but it does not establish a worthwhile continuous mirror of this paper.
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.