Answer: \(\mathrm{NP}\text{-complete}\)
THEOREM 6 — class: hardness
Given a finite support \(T_\mu\) of complete agent profiles with positive rational masses \(\mu_t\) summing to \(1\), finite signal and outcome sets \(S\) and \(O\), rational valuations \(v(t,o)\), arbitrary signaling costs \(c(t,s)\in\mathbb{Q}_{\ge 0}\cup\{\infty\}\), and an injective target rule \(F:T_\mu\to O\), does there exist a deterministic mechanism \(A:S\to O\) such that for every \(t\in T_\mu\), some utility-maximizing signal yields the required outcome: \(\exists s_t\in\arg\max_{s\in S}\bigl(v(t,A(s))-c(t,s)\bigr)\) with \(A(s_t)=F(t)\)?
A society is given by its support: a list \(T_\mu\) of \(\tau\) types with positive binary rational masses \(\mu_t\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
The input also contains nonempty finite signal and outcome sets \(S,O\), explicit tables \(v:T_\mu\times O\to\mathbb Q\) and \(c:T_\mu\times S\to\mathbb Q_{\ge0}\cup\{\infty\}\), and an injective target rule \(F:T_\mu\to O\). Valuations may have either sign; infinite cost means a signal is unavailable.
A deterministic mechanism is a total map \(A:S\to O\), with no transfers or prescribed utility levels. It implements \(F\) if every \(t\in T_\mu\) has an available signal \(s_t\) satisfying \(A(s_t)=F(t)\) and \(v(t,A(s_t))-c(t,s_t)\ge v(t,A(s))-c(t,s)\) for every available signal \(s\). Ties permit any maximizing signal yielding the target; a type with no available signal makes implementation impossible.
Let \(m=|O|\), \(q=|S|\), and \(L\) be the total binary input length; state running times in \(m,\tau,q,L\).
Is deciding whether such a mechanism exists in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?
For a finite type list, deterministic implementation without transfers, with unrestricted signaling costs and an injective target rule, is \(\mathrm{NP}\)-complete ([Kephart–Conitzer](https://www.cs.cmu.edu/~conitzer/signalingAAMAS15.pdf)). No separate result for the mass formulation was located.
The decision problem is \(\mathrm{NP}\)-complete. The positive rational masses do not change feasibility, so the cited finite-type hardness result transfers by a polynomial-time reduction.
Throughout, \(\tau\) denotes the explicitly listed support size.
A certificate specifies the total map \(A:S\to O\), requiring \(O(q\log(m+1))\) bits.
For each type \(t\), define its available signals by
\(S_t=\{s\in S:c(t,s)<\infty\}\). Reject if \(S_t\) is empty. Otherwise compute
\(U_t=\max_{s\in S_t}\bigl(v(t,A(s))-c(t,s)\bigr)\).
Accept precisely when, for every \(t\), some \(s\in S_t\) satisfies both
\(A(s)=F(t)\) and \(v(t,A(s))-c(t,s)=U_t\).
This is exactly the stated implementation condition: a target-producing signal must attain the maximum, and equality permits ties.
Each utility is the difference of two input rationals and has \(O(L)\)-bit numerator and denominator. Exact comparisons by cross multiplication take \(O(L^2)\) bit operations using elementary integer arithmetic. Thus, on well-formed inputs, certificate verification takes
\(O\bigl(L+q\log(m+1)+\tau qL^2\bigr)\) time. Consequently, the problem belongs to \(\mathrm{NP}\).
Fix \(T_\mu,S,O,v,c,F\). For any total map \(A\), every condition defining implementation involves only these objects. No condition involves a mass \(\mu_t\).
Therefore changing the positive masses while retaining the same support preserves the set of implementing mechanisms. In particular, attaching positive masses to a finite type list preserves its yes/no answer.
This observation concerns feasibility for every supported type; it does not require averaging utilities or expanding rational masses into repeated agents.
Theorem 6 of [Kephart–Conitzer, *Complexity of Mechanism Design with Signaling Costs*](https://www.cs.cmu.edu/~conitzer/signalingAAMAS15.pdf) establishes \(\mathrm{NP}\)-completeness for explicitly listed finite types, no transfers, unrestricted signaling costs, free utility levels, and an injective target rule. Their implementation definition allows a maximizing signal yielding the target, as here. Their hardness construction uses nonnegative integer finite costs and integer valuations, so it lies within the numerical restrictions of this task.
Take an instance of that finite-type problem with types
\(T=\{t_1,\ldots,t_\tau\}\). Copy \(T,S,O,v,c,F\) unchanged and attach positive rational masses.
For completeness, masses can even be chosen dyadic. Set \(k=\lceil\log_2\tau\rceil\), and define
\(\mu_{t_i}=2^{-k}\) for \(1\le i<\tau\), and
\(\mu_{t_\tau}=(2^k-\tau+1)2^{-k}\).
Since \(2^k\ge\tau\), every mass is positive. Their sum is
\(\bigl((\tau-1)+(2^k-\tau+1)\bigr)2^{-k}=1\).
This also covers \(\tau=1\), giving mass \(1\).
Each mass requires \(O(\log(\tau+1))\) bits. If the source input length is \(L_0\), the resulting input length is
\(L=L_0+O(\tau\log(\tau+1))\), and the transformation takes time linear in that output length.
By Section 2, a map \(A\) implements the copied instance exactly when it implements the original instance. Hence this is a polynomial-time many-one reduction, proving \(\mathrm{NP}\)-hardness. Together with Section 1, it proves \(\mathrm{NP}\)-completeness.
Enumerating all \(m^q\) total maps and applying the verifier gives a deterministic bound
\(O\bigl(L+m^q\tau qL^2\bigr)\).
There is also an algorithm taking
\(O\bigl(L+q^\tau m\tau qL^2\bigr)\), which is polynomial for fixed \(\tau\). To justify it, enumerate one candidate witness signal \(s_t\) for each type.
Reject a tuple if any witness is unavailable or if two types choose the same signal: injectivity of \(F\) makes such a collision impossible. Otherwise prescribe \(A(s_t)=F(t)\) and set
\(u_t=v(t,F(t))-c(t,s_t)\).
Check that every prescribed signal gives each type that can access it utility at most \(u_t\). For each remaining signal \(s\), choose any outcome \(o\) satisfying
\(v(t,o)-c(t,s)\le u_t\) for every type \(t\) with \(c(t,s)<\infty\). Reject the tuple if no such outcome exists.
These choices are independent across remaining signals. If all checks succeed, each witness attains \(u_t\), and every available signal gives utility at most \(u_t\), proving implementation. Conversely, the witnesses of any implementing mechanism appear in the enumeration, and that mechanism’s outcomes pass every check.
Thus the general problem is \(\mathrm{NP}\)-complete, while fixed support size admits the stated polynomial-time algorithm.
⟨structured verdict parsed — rendered above⟩
The output resolves the assigned task. The argument establishes \(\mathrm{NP}\)-completeness for the explicitly represented support formulation. The verification procedure, mass reduction, and fixed-support algorithm are correct. No major or minor issues were found.
The certificate correctly specifies an outcome for every signal, including signals unavailable to every type. Its stated length, \(O(q\log(m+1))\), is sufficient; the expression also handles \(m=1\).
The verifier checks precisely the required condition:
The arithmetic bounds are valid. Subtracting two input rationals produces a numerator and denominator of \(O(L)\) bits. Comparing the resulting rationals by cross multiplication costs \(O(L^2)\) bit operations with elementary arithmetic. At most a constant number of scans through the \(\tau q\) type–signal pairs suffices.
Thus the stated verification bound
\[
O\bigl(L+q\log(m+1)+\tau qL^2\bigr)
\]
is valid, and membership in \(\mathrm{NP}\) follows.
This observation is exact: implementation quantifies over every supported type and contains no expression involving \(\mu_t\).
Preserving the support while changing its positive masses therefore preserves feasibility for each mechanism individually, and hence preserves the existence of an implementing mechanism. The argument does not confuse support size with a population obtained by expanding rational masses.
The citation matches the required problem. Theorem 6 states \(\mathrm{NP}\)-completeness for free utilities, no transfers, unrestricted costs, and an injective social choice function. The paper’s model uses a total signal-to-outcome map and permits a maximizing signal yielding the target. Its construction uses integer valuations and finite cost entries that are nonnegative integers; unavailable signals have infinite cost. These are permitted by the task. [Kephart–Conitzer, model and Theorem 6](https://www.cs.cmu.edu/~conitzer/signalingAAMAS15.pdf)
Accordingly, the prover invokes the correct theorem and verifies the relevant hypotheses. A separate hardness result formulated using masses is unnecessary because the proposed reduction supplies those masses explicitly.
A well-formed support has \(\tau\ge1\): positive masses on an empty support could not sum to \(1\). Thus \(k=\lceil\log_2\tau\rceil\) is defined.
The proposed masses satisfy all requirements:
Each numerator and denominator has \(O(\log(\tau+1))\) bits. The additional encoding length and claimed construction time are therefore polynomial in the source length.
Copying the other data preserves both directions of the implementation equivalence by Section 2. This is a valid polynomial-time many-one reduction, establishing \(\mathrm{NP}\)-hardness. Together with membership, it establishes \(\mathrm{NP}\)-completeness.
There are exactly \(m^q\) total maps. Applying the verifier to each gives the stated bound
\[
O\bigl(L+m^q\tau qL^2\bigr).
\]
The omitted certificate-reading term is absorbed by the displayed bound: on well-formed inputs, \(\tau\ge1\) and the explicit input length bounds the bits needed to identify outcomes.
The witness enumeration is complete: every implementation supplies one available target-producing maximizing signal per type.
Rejecting shared witness signals is correct. A deterministic map assigns one outcome to a signal, while injectivity requires distinct target outcomes for distinct types.
For each surviving tuple:
Consequently, every accepted tuple yields an implementation. Conversely, an implementing mechanism supplies a tuple whose prescribed and remaining outcomes satisfy every check. Weak inequalities preserve the intended treatment of ties.
There are at most \(q^\tau\) tuples. The outcome search and utility comparisons fit within \(O(m\tau qL^2)\) per tuple, giving the stated total bound
\[
O\bigl(L+q^\tau m\tau qL^2\bigr).
\]
For fixed \(\tau\), this is polynomial in the explicit input parameters.
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.