Answer: \(\Theta_2^p\)-complete, hence \(\mathrm{NP}\)-hard; already \(\mathrm{DP}\)-complete when \(\tau=1\) and \(q=1\).
Theorem 6 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateLet G = (X1, X2) be a bargaining game, and D1 ⊆X1 and D2 ⊆X2. Deciding whether (D1, D2) is a deal of G is DP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
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 society is given by its support: a list of \(\tau\) buyer–supplier type pairs \((a,b)\) with positive binary-rational masses \(\mu_{ab}\) summing to \(1\); \(\tau\) is the support size, not the number of possible types.
Each supported pair has an explicitly given game \(G_{ab}=((X_1,\succeq_1),(X_2,\succeq_2))\), with finite, individually consistent sets of propositional formulas and total preorders satisfying: for \(r\ge1\) and \(\varphi_1,\ldots,\varphi_r,\psi\in X_i\), if \(\{\varphi_1,\ldots,\varphi_r\}\models\psi\), then \(\psi\succeq_i\varphi_j\) for some \(j\).
Represent each preorder by its ordered equivalence classes \(X_i^1,\ldots,X_i^{h_i}\), highest priority first; ties remain within a class. Formula identity and set intersection are syntactic.
For a game \(G\), let \(\Omega(G)\) contain exactly the pairs \(D=(D_1,D_2)\) such that, for each \(i\in\{1,2\}\), \(D_i\subseteq X_i\), \(X_1\cap X_2\subseteq D_i\), and for every \(1\le k\le h_i\), \(D_i\cap X_i^k\) is inclusion-maximal among \(S\subseteq X_i^k\) for which \(D_{3-i}\cup\bigcup_{j<k}(D_i\cap X_i^j)\cup S\) is consistent.
The input also supplies \(D^{ab}=(D_1^{ab},D_2^{ab})\), with \(D_i^{ab}\subseteq X_i^{ab}\), and a binary-rational threshold \(q\). Games satisfying the stated consistency and preorder conditions are promised inputs.
Is deciding whether \(\sum_{(a,b)}\mu_{ab}\mathbf{1}[D^{ab}\in\Omega(G_{ab})]\ge q\) in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? State running times in \(m\), \(\tau\), and \(L\), where \(m\) counts distinct propositional variables and \(L\) is the total input bit length.
Discrete deal recognition is stated to be \(\mathrm{DP}\)-complete by [Zhang and Zhang](https://arxiv.org/pdf/1405.5201). No result for this exact mass-threshold problem was located.
The mass-threshold problem is \(\Theta_2^p\)-complete under polynomial-time many-one reductions that preserve all the input promises. Here \(\Theta_2^p=\mathrm{P}_{\parallel}^{\mathrm{NP}}\) denotes polynomial-time computation with one nonadaptive batch of polynomially many SAT queries.
In particular, the problem is \(\mathrm{NP}\)-hard even when \(\tau=1\), each player has one priority class, and each demand set contains at most two formulas. Thus a polynomial-time algorithm for unrestricted inputs would imply \(\mathrm{P}=\mathrm{NP}\).
A deterministic algorithm runs in time
\(O\!\left(2^mL^2+(\tau+1)L^2\right)\)
and polynomial space. Consequently, the problem is fixed-parameter tractable in \(m\), and polynomial-time solvable when \(m=O(\log L)\).
Fix a game \(G\) and proposed deal \(D=(D_1,D_2)\). For each player \(i\) and class \(k\), define
\(P_{i,k}=D_{3-i}\cup\bigcup_{j\leq k}(D_i\cap X_i^j).\)
For every omitted formula \(\varphi\in X_i^k\setminus D_i\), define the extension set
\(E_{i,k,\varphi}=P_{i,k}\cup\{\varphi\}.\)
Lemma. The proposed deal belongs to \(\Omega(G)\) if and only if all three conditions hold:
Proof. Suppose first that \(D\in\Omega(G)\). The syntactic conditions are part of the definition.
An inclusion-maximal member of a family must itself belong to that family. Therefore every \(P_{i,k}\) is consistent. If either demand set is nonempty, its last class gives \(P_{i,h_i}=D_1\cup D_2\). If both demand sets are empty, their proposed subsets are empty, so their union is consistent as well.
If an extension \(E_{i,k,\varphi}\) were consistent, then \((D_i\cap X_i^k)\cup\{\varphi\}\) would be a feasible strict superset of the selected portion of class \(k\). This contradicts inclusion-maximality.
Conversely, suppose the three conditions hold. Each \(P_{i,k}\) is a subset of the consistent set \(D_1\cup D_2\), so the selected portion of every class is feasible.
If that portion were not inclusion-maximal, there would be a feasible strict superset \(S\subseteq X_i^k\). Choose \(\varphi\in S\setminus(D_i\cap X_i^k)\). Consistency is preserved under taking subsets, so \(E_{i,k,\varphi}\) would be consistent, contradicting condition 3. This proves maximality at every class. \(\square\)
The extension test uses only the player's selected formulas through class \(k\). Its selected formulas at lower priorities must not be included.
For a finite formula set \(Y\), let \(\operatorname{Conj}(Y)\) denote its conjunction, with the empty conjunction interpreted as true.
For each supported pair, construct the following SAT queries:
\(C=\operatorname{Conj}(D_1\cup D_2),\)
\(A=\bigvee_{i,k,\varphi\in X_i^k\setminus D_i}\operatorname{Conj}(E_{i,k,\varphi}).\)
An empty disjunction is interpreted as false. The lemma gives
\(D\in\Omega(G)\quad\Longleftrightarrow\quad\text{the syntactic conditions hold, }C\text{ is satisfiable, and }A\text{ is unsatisfiable}.\)
All queries are determined by the input before any oracle answer is received. There are at most \(2\tau\) queries.
Let \(\ell_{ab}\) be the encoding length of one game and its proposed deal. There are \(O(\ell_{ab})\) extension sets, each having conjunction length \(O(\ell_{ab})\). Thus the total query length is bounded by
\(O\!\left(\sum_{(a,b)}\ell_{ab}^2\right)=O(L^2).\)
After receiving the answers, compute the accepted mass exactly and compare it with \(q\). This proves membership in \(\mathrm{P}_{\parallel}^{\mathrm{NP}}\).
For completeness, this final arithmetic is polynomial in the bit length. Write \(\mu_{ab}=u_{ab}/v_{ab}\) and \(q=w/z\), with positive denominators. A common denominator is
\(\Delta=z\prod_{(a,b)}v_{ab}.\)
Its bit length is \(O(L)\). If \(b_{ab}\) is the computed deal indicator, compare the integers
\(\sum_{(a,b)}b_{ab}u_{ab}\frac{\Delta}{v_{ab}}\quad\text{and}\quad w\frac{\Delta}{z}.\)
Using elementary integer multiplication and division, these operations take \(O((\tau+1)L^2)\) bit operations.
Without an oracle, enumerate all \(2^m\) assignments and evaluate the query formulas. Their total length is \(O(L^2)\), giving the stated deterministic bound
\(O\!\left(2^mL^2+(\tau+1)L^2\right).\)
Only polynomial space is needed. This algorithm processes the explicitly listed \(\tau\) supported pairs.
[Zhang and Zhang, Theorem 6](https://arxiv.org/pdf/1405.5201), state that deal recognition is \(\mathrm{DP}\)-complete. The following independent construction explicitly preserves the promises in this question.
Let \(F,H\) be arbitrary propositional formulas. Rename their variables so that their variable sets are disjoint; this preserves their respective satisfiability statuses. Choose fresh variables \(p,r\).
Construct
\(X_1=\{p,\ r\vee H\},\qquad X_2=\{\neg p\vee F,\ \neg r\},\)
and put all formulas of each player in one equivalence class. Supply
\(D_1=\{p\},\qquad D_2=X_2.\)
Every constructed instance satisfies the promises:
The proposed union is
\(D_1\cup D_2=\{p,\ \neg p\vee F,\ \neg r\}.\)
It is consistent exactly when \(F\) is satisfiable.
There is exactly one omitted demand, namely \(r\vee H\). Adding it requires \(F\) and \(H\) simultaneously, because the selected formulas force \(p=\mathrm{true}\) and \(r=\mathrm{false}\). Since their variable sets are disjoint, this extension is consistent exactly when both formulas are satisfiable. Therefore
\(D\in\Omega(G)\quad\Longleftrightarrow\quad F\text{ is satisfiable and }H\text{ is unsatisfiable}.\)
Take a society with this single game, mass \(1\), and threshold \(q=1\). This is a reduction from SAT–UNSAT to the mass-threshold problem.
Here \(\mathrm{DP}\) consists of intersections of an \(\mathrm{NP}\) language and a \(\mathrm{coNP}\) language. SAT–UNSAT is complete for this class: reduce the first language to SAT and the complement of the second language to SAT. The local characterization also proves membership in \(\mathrm{DP}\). Hence the restriction \(\tau=1,\ q=1\) is \(\mathrm{DP}\)-complete.
In particular, fixing \(H\) to a contradiction gives a direct SAT reduction, proving \(\mathrm{NP}\)-hardness under all the stated restrictions.
We now show that allowing polynomially many supported pairs yields \(\Theta_2^p\)-hardness, even with uniform dyadic masses.
Let \(\mathcal{K}\) be any language in \(\mathrm{P}_{\parallel}^{\mathrm{NP}}\), and fix an input \(x\). Its deciding computation prepares a nonadaptive list of SAT queries
\(F_1,\ldots,F_t,\)
where \(t\) and the total query length are polynomially bounded in \(|x|\). Rename the variables of different queries to be disjoint.
After receiving their answer bits, the computation applies a polynomial-time Boolean function. With \(x\) fixed, represent that function by a polynomial-size Boolean circuit
\(f_x:\{0,1\}^t\longrightarrow\{0,1\}.\)
Such a circuit is constructible in polynomial time by unrolling the bounded deterministic computation after the oracle answers arrive.
Define the actual set of satisfiable query indices and its size by
\(S=\{j:F_j\text{ is satisfiable}\},\qquad c=|S|.\)
Thus \(x\in\mathcal{K}\) exactly when \(f_x(\mathbf{1}_S)=1\).
Introduce selector bits \(z_1,\ldots,z_t\). For each \(0\leq k\leq t\), construct formulas \(A_k,B_k\) having these satisfiability conditions:
These conditions have explicit polynomial-size circuit representations. Require exactly \(k\) selectors to be true, and impose
\(\bigwedge_{j=1}^t\bigl(\neg z_j\vee F_j\bigr).\)
For \(B_k\), additionally require the output of \(f_x(z)\) to be true.
The exact-cardinality condition has a polynomial-size circuit, for example by maintaining, for every prefix of the selectors, the possible exact counts. The disjoint variable sets of the \(F_j\) ensure that all selected queries can receive independent satisfying assignments.
Convert each resulting circuit to a propositional formula by introducing a fresh variable for every gate, conjoining a biconditional describing that gate, and asserting the output variable. For any assignment to the input variables, the gate constraints have exactly the extension prescribed by circuit evaluation. Thus the conversion preserves satisfiability and has polynomial size. Define \(A_{t+1}\) to be a contradiction.
It follows that
\(A_k\text{ is satisfiable}\quad\Longleftrightarrow\quad k\leq c\qquad(0\leq k\leq t+1).\)
Moreover, a selected set of size \(c\) consisting entirely of satisfiable queries must be exactly \(S\). Consequently,
\(B_c\text{ is satisfiable}\quad\Longleftrightarrow\quad f_x(\mathbf{1}_S)=1.\)
For each \(0\leq k\leq t\), consider the SAT–UNSAT condition
\(B_k\text{ is satisfiable and }A_{k+1}\text{ is unsatisfiable}.\)
There are three cases:
Therefore at most one of these conditions holds, and
\(x\in\mathcal{K}\quad\Longleftrightarrow\quad\text{at least one of these conditions holds}.\)
For each \(k\), apply the gadget from Section 3 with \(F=B_k\) and \(H=A_{k+1}\), again renaming the two formulas apart. The supplied deal is recognized exactly when the corresponding condition holds.
Let \(T\) be the smallest power of two satisfying \(T\geq t+1\). Pad the collection to \(T\) games using games whose supplied deals always fail. One such padding game is
\(X_1=\{u\},\qquad X_2=\{\neg u\},\qquad D=(X_1,X_2).\)
Both demand sets are individually consistent and have singleton priority classes, but the supplied union is inconsistent.
Assign distinct type-pair labels to all games, and give each supported pair mass \(1/T\). Set \(q=1/T\). These masses are positive dyadic rationals and sum to \(1\).
The society has \(\tau=T<2(t+1)\). Its accepted mass is \(1/T\) when \(x\in\mathcal{K}\), and \(0\) otherwise. Hence
\(\sum_{(a,b)}\mu_{ab}\mathbf{1}[D^{ab}\in\Omega(G_{ab})]\geq q\quad\Longleftrightarrow\quad x\in\mathcal{K}.\)
All circuits, formulas, games, labels, and rational encodings have polynomial total size and are constructible in polynomial time. Every output game satisfies the promises. This proves \(\Theta_2^p\)-hardness and, together with Section 2, completeness.
⟨structured verdict parsed — rendered above⟩
The prover’s output resolves the task. The recognition characterization, promise-preserving reductions, complexity classification, and running-time bound are correct. I found no major or minor mathematical issues.
The lemma correctly matches the definition of \(\Omega(G)\).
The extension sets correctly include all of the other player’s proposed deal and only the current player’s selected formulas through the current class. Lower-priority selections are correctly excluded.
The lemma also covers an empty demand set on one side. There are no class conditions for that side, and the nonempty side supplies the required consistency test.
Finding: Correct, including the relevant empty-set cases.
The formula \(C\) tests consistency of the proposed union. The formula \(A\) is satisfiable exactly when at least one prohibited extension is consistent. Thus the stated acceptance condition follows directly from the lemma.
The empty-disjunction convention correctly handles games with no omitted demands. Syntactic subset and intersection conditions are checked independently in polynomial time.
The queries are determined entirely from the input. Their answers therefore form one nonadaptive batch of at most \(2\tau\) SAT queries. Exact arithmetic afterward requires no further oracle queries.
For each game, there are \(O(\ell_{ab})\) extensions, each represented using \(O(\ell_{ab})\) bits. The total query-size bound
\(\displaystyle O\!\left(\sum_{(a,b)}\ell_{ab}^{2}\right)=O(L^{2})\)
is valid.
Finding: Membership in \(\mathrm{P}_{\parallel}^{\mathrm{NP}}\) is established.
The proposed common denominator is positive and divisible by every input denominator. Its bit length is \(O(L)\), since the bit lengths of those denominators are included in the total input length.
The integer comparison is exactly equivalent to the original rational comparison. It remains valid for negative thresholds and thresholds outside the interval \([0,1]\).
The bound \(O((\tau+1)L^{2})\) is sufficient for the stated elementary arithmetic operations. Enumerating all \(2^{m}\) assignments and evaluating formulas of total length \(O(L^{2})\) gives the claimed overall bound:
\(\displaystyle O\!\left(2^{m}L^{2}+(\tau+1)L^{2}\right).\)
The upper-bound construction introduces no new propositional variables. Therefore the assignment enumeration uses precisely the input parameter \(m\). Storing the queries, one assignment, and the arithmetic data requires only polynomial space.
Because the support is explicitly listed, \(\tau=O(L)\). The fixed-parameter tractability conclusion and the polynomial-time conclusion for \(m=O(\log L)\) both follow.
Finding: The running-time and space claims are justified.
All input promises are verified correctly:
The selected union forces \(p\) true and \(r\) false, so its consistency is equivalent to satisfiability of \(F\). There is exactly one omitted demand. Its extension is consistent exactly when \(F\) and \(H\) are simultaneously satisfiable. Renaming their variables apart justifies equivalence with their separate satisfiability.
The resulting recognition condition is therefore exactly “\(F\) satisfiable and \(H\) unsatisfiable.”
The single-game mass and threshold correctly translate recognition into the society decision. The stated \(\mathrm{DP}\)-membership and SAT–UNSAT reduction establish \(\mathrm{DP}\)-completeness for the restriction. Fixing \(H\) to a contradiction correctly gives the claimed SAT reduction.
The citation accurately identifies the deal-recognition statement in [Zhang and Zhang, Theorem 6](https://arxiv.org/pdf/1405.5201). The prover supplies an independent gadget, so it does not depend on transferring the paper’s construction to the present promises.
Finding: The restricted hardness claims are established.
The reduction correctly accommodates an arbitrary language decided using nonadaptive SAT queries and polynomial-time processing of their answers.
The circuit \(f_x\) is polynomial-size and constructible by unrolling the fixed polynomial-time computation. This is a uniform construction rather than an assumption of nonuniform circuit access.
The auxiliary formulas have the stated satisfiability meanings:
Consequently, \(A_k\) has the claimed threshold behavior. At size \(c\), the only selectable set is \(S\), so the claimed characterization of \(B_c\) is valid.
The three cases \(k<c\), \(k=c\), and \(k>c\) exhaust all indices and correctly show that at most one SAT–UNSAT condition holds. That condition holds precisely when the original computation accepts. Renaming each gadget’s two formulas apart preserves the satisfiability statuses used in this argument.
The construction also handles \(t=0\): the single index is \(k=0\), and \(A_1\) is the prescribed contradiction.
Finding: The full hardness argument is correct and polynomial-size.
The padding game satisfies individual consistency and the preorder promise, while its proposed union is inconsistent. Its deal therefore always fails.
Distinct type-pair labels produce the required support size. Uniform masses \(1/T\) are positive dyadic rationals summing to one, and \(q=1/T\) has polynomial encoding length. Since at most one genuine gadget succeeds, the accepted mass is exactly \(1/T\) or zero as asserted.
Thus the reduction preserves every promise and establishes \(\Theta_2^p\)-hardness. Together with the upper bound, it proves the claimed completeness classification and answers the task’s hardness question.
No repair or additional clarification is needed.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.