| paper | d4-journals-jair-2008-0047 |
| 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: \(\Theta_2^p\)-complete, hence \(\mathrm{NP}\)-hard; already \(\mathrm{DP}\)-complete when \(\tau=1\) and \(q=1\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 6
statement extracted from the paper’s text layer
Given a finite support of buyer–supplier type pairs \((a,b)\), binary-rational masses \(\mu_{ab}\) summing to \(1\), a bargaining game \(G_{ab}\) and proposed deal \(D^{ab}\) for each pair, and a rational threshold \(q\), decide whether \(\sum_{(a,b)}\mu_{ab}\mathbf{1}[D^{ab}\in\Omega(G_{ab})]\ge q\).
A distribution \(\mu\) over repeated buyer–supplier type pairs, where each type fully specifies a party’s demands and priorities. Each pair has its own bargaining game and proposed deal; the computational task is to determine whether the mass of pairs whose deals pass the paper’s verification test reaches \(q\).
The mass is over independent transactions rather than participants in one shared bargaining problem; the case acknowledges this but does not establish that the authors would treat the aggregate audit as their bargaining question.
fatal: False
The mirror covers Theorem 6’s deal verification. It leaves the paper’s core bargaining solution and its other complexity results, including solution checking, untouched.
The strongest mirror I see is a population-level audit of proposed deals in a high-volume bargaining platform. Buyers and suppliers repeatedly negotiate standardized contracts. A buyer type is its complete logical demand set and priority ordering; a supplier type is defined the same way. Matching induces a rational mass \(\mu_{ab}\) on each buyer–supplier type pair \((a,b)\), with total mass \(1\). In a large platform, the number \(N\) of negotiations can be enormous while the number \(\tau\) of distinct type pairs is small. Each type pair specifies a bargaining game \(G_{ab}\) and a proposed deal \((D^{ab}_1,D^{ab}_2)\).
My lead anchor is Theorem 6, proved in this paper. It says that, given a finite bargaining game \(G=(X_1,X_2)\) with demand sets partitioned into priority levels \(X_i^1,\ldots,X_i^{r_i}\), deciding whether a proposed pair \((D_1,D_2)\) is a deal is DP-complete. A deal must satisfy, for each player \(i\): \(D_i\subseteq X_i\); it must contain every common demand, \(X_1\cap X_2\subseteq D_i\); and, at every level \(k\), \(D_i\cap X_i^k\) must be an inclusion-maximal subset of \(X_i^k\) such that \(D_{-i}\cup\bigcup_{j=1}^k(D_i\cap X_i^j)\) is consistent. The theorem’s proof establishes membership and reduces a SAT-and-UNSAT conjunction to deal checking. The printed statement has a repeated \(D_1\) where the second component is evidently \(D_2\), as in the definition of a deal.
Call the mirror Continuous Deal-Mass Verification. Its instance gives the finite support of type pairs, their binary-rational masses \(\mu_{ab}\), each game \(G_{ab}\), a proposed deal for each supported pair, and a rational threshold \(q\). It asks whether
\[ \rho=\sum_{(a,b)}\mu_{ab}\,\mathbf{1}\!\left[(D^{ab}_1,D^{ab}_2)\in\Omega(G_{ab})\right]\ge q. \]
A solution can report the exact rational \(\rho\), which also answers the threshold question. Each negotiation still has an ordinary logical deal; the fractional quantity is the mass of negotiations whose proposed deal passes the paper’s deal test.
I expect the hardness to transfer (Class B). With one supported type pair of mass \(1\) and \(q=1\), this problem is exactly Theorem 6’s deal decision problem. Its combinatorics live in logical consistency and maximality, not in the number of negotiations, so making the transaction population continuous does not remove them. The mirror covers deal verification, not the paper’s full bargaining solution or its other complexity results. It also opens questions about the aggregate threshold problem’s complexity in \(\tau\) and formula length \(L\), and about when repeated type pairs make exact auditing or approximation practical.
The weak point is that this is a population of independent negotiations, rather than one negotiation with a shared agreement among heterogeneous populations. The authors would recognize the deal predicate and the high-volume setting as a direct computational extension of their model, but a referee could reasonably view it as a batch audit rather than the continuous form of the bilateral bargaining problem itself.
Theorem 6 is a real computational anchor: checking whether a proposed pair is a deal is DP-complete. The strongest case against is that the proposed continuous version changes what the population represents. In the paper, an instance is one interaction between two parties, each described by a complete set of logical demands and priorities. The theorem checks consistency and maximality between those two sets. Neither the people inside a bargaining game nor the demands within it are interchangeable units of mass.
The proposed \(\rho\) instead puts weights on whole bargaining instances, checks each instance separately, then reports the weighted fraction that passes. That can be a useful audit metric for a platform, but it is a population of computational tasks, not one bargaining society. Repeating one game at mass \(1\) simply recovers Theorem 6; using several games adds a weighted aggregation around independent local checks. The population does not change the deal relation or create a shared decision problem. The authors might recognize this as an application of their verifier, but it is harder to see them recognizing the aggregate threshold question as the bargaining problem their paper studies.
The stronger version would give buyers and suppliers separate type distributions and couple them through matching, limited supply, or a shared platform policy. Without such coupling, the model still decomposes into independent bilateral games. With it, the question becomes market clearing or multi-agent bargaining, and the paper supplies neither the shared constraint nor a solution concept for that problem. Its own discussion identifies mutual belief revision with more than two agents as an open modeling challenge.
So the best negative case is about fit: Theorem 6 concerns a single bilateral game, while the proposed continuum aggregates a portfolio of games. That is a substantive objection to this anchor, but it does not establish the universal claim. A high-volume platform could plausibly care about the mass of deals passing the verifier, and the paper’s authors might accept that as their problem. I cannot honestly rule out that scenario; the negative case is weakest precisely at the question of whether such an audit counts as a worthwhile continuous mirror.
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.