Answer: Polynomial-time solvable: accept exactly when \(\bigcup_{t=1}^{\tau} I_t=\binom{N}{2}\). For every accepted society, \(q_0=3\) suffices.
Theorem 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateSuppose that (1) there are at least three jurors, (2) every pair of contestants is an indi¤erent pair for one juror at least, and (3) the designer of the mechanism knows who the juror is that has among his indi¤erent pairs to each pair of contestants. Then the socially optimal rule is Nash imple- mentable.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite contestant set \(N\) and a finite support \(T\) of complete juror types with positive rational masses \(\mu_t\) summing to one, determine whether there is a threshold \(q_0\) and a constructible mechanism scheme such that, for every \(q\ge q_0\) with \(q\mu_t\in\mathbb{Z}\) for all \(t\), the mechanism Nash implements the true ranking in the jury containing \(q\mu_t\) jurors of each type, for every admissible state.
Let \(N\) contain \(m\ge 3\) contestants, and let \(\Pi\) be their strict rankings. A society is given by its support: the list of \(\tau\) types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types. Let \(L\) be the total input bit length.
Each type specifies a designer-known set \(I_t\subsetneq\binom{N}{2}\) of indifferent pairs, encoded explicitly. For every positive integer \(q\) satisfying \(q\mu_t\in\mathbb Z\), the replica jury has \(q\mu_t\) individually identified jurors of type \(t\).
An admissible state consists of a true ranking \(\rho\in\Pi\) and, for each juror \(j\), a preference function \(R_j\) assigning a complete, transitive weak order on \(\Pi\) to every true ranking. Whenever two outcomes differ only by swapping an adjacent pair in \(I_t\), a type-\(t\) juror strictly prefers the outcome ordering that pair as in the true ranking. There are no further preference restrictions; jurors of the same type may have different admissible preference functions.
The state is common knowledge among jurors; the designer knows their types but cannot observe the state. A mechanism is deterministic, has finite message spaces, and outputs a ranking. It Nash implements truth if, in every admissible state, pure Nash equilibria exist and their outcome set is exactly \(\{\rho\}\).
A constructible scheme is one algorithm that, given the society and an eligible \(q\), produces a finite description of such a mechanism, including a terminating outcome algorithm; it cannot depend on the state. Neither anonymity nor a polynomial bound on mechanism construction is imposed.
Is deciding whether there exist an integer \(q_0\ge 3\) and a constructible scheme implementing truth for every eligible \(q\ge q_0\) solvable in polynomial time in \(m,\tau,L\), or is this decision problem NP-hard?
For finite juries with at least three jurors, known indifferent-pair sets covering every contestant pair suffice for Nash implementation; pair coverage is also necessary on this admissible-state domain. [Verified finite-jury results](https://dialnet.unirioja.es/descarga/articulo/2133084.pdf).
No separate complexity classification for this support-encoded, eventual-replica decision problem was located.
The decision problem is solvable in deterministic polynomial time. Its exact criterion is
\( \displaystyle \bigcup_{t=1}^{\tau} I_t=\binom{N}{2}. \)
If this criterion holds, one may take \(q_0=3\). The proof below also establishes the required uniform constructibility.
Write each mass in reduced form as \(\mu_t=a_t/b_t\), and let \(D=\operatorname{lcm}(b_1,\ldots,b_\tau)\). Every positive multiple of \(D\) is eligible, so eligible replica sizes are unbounded.
Fix an eligible \(q\). Since \(\mu_t>0\), the integer \(q\mu_t\) is at least one. Thus every supported type appears in the replica. Moreover, its total number of jurors is
\( \displaystyle \sum_{t=1}^{\tau}q\mu_t=q. \)
Let \(J_q\) denote its individually identified jurors, and assign \(I_j=I_t\) to each juror of type \(t\). Consequently,
\( \displaystyle \bigcup_{j\in J_q}I_j=\bigcup_{t=1}^{\tau}I_t. \)
In particular, replication changes multiplicities but never changes pair coverage.
We prove necessity directly, including the existence of the preference functions used in the impossibility argument.
Suppose \(\{a,b\}\notin\bigcup_t I_t\). Choose a ranking \(\rho\) in which \(a,b\) are adjacent, and let \(\rho'\) result from swapping them. These rankings differ in the relative order of exactly the pair \(\{a,b\}\).
For each juror \(j\), each possible true ranking \(\sigma\), and each outcome \(x\in\Pi\), define
\( \displaystyle u_j^\sigma(x)=-\left|\left\{e\in I_j:\text{the relative order of }e\text{ in }x\text{ differs from its order in }\sigma\right\}\right|. \)
Define \(R_j(\sigma)\) by weakly preferring outcomes with higher utility. This is a complete, transitive weak order.
To check admissibility, consider outcomes differing only by an adjacent swap of a pair \(e\in I_j\). Such a swap changes the relative order of \(e\) and no other contestant pair. Therefore the outcome ordering \(e\) as in \(\sigma\) has utility exactly one greater than the other outcome. The required strict preference holds. Since this construction applies to every \(\sigma\), it defines an admissible preference function.
Because \(\rho,\rho'\) disagree only on the uncovered pair, they agree on every pair in \(I_j\). Hence, for every juror and every outcome,
\( \displaystyle u_j^\rho(x)=u_j^{\rho'}(x), \qquad R_j(\rho)=R_j(\rho'). \)
Now fix any eligible replica and any proposed mechanism. At the two admissible states consisting of these same preference functions and truths \(\rho,\rho'\), respectively, every juror has identical preferences over outcomes. The induced games therefore have identical pure Nash equilibrium sets.
Implementation at truth \(\rho\) requires an equilibrium whose outcome is \(\rho\). That same message profile is an equilibrium at truth \(\rho'\), where its outcome remains \(\rho\ne\rho'\). This contradicts implementation.
Thus an uncovered pair prevents implementation for every eligible replica. Since eligible sizes are unbounded, no threshold \(q_0\) can avoid this obstruction.
We use the finite-jury sufficiency theorem supplied in the question:
Finite-jury theorem. For at least three jurors with designer-known proper indifferent-pair sets, coverage of every contestant pair suffices for deterministic Nash implementation of truth on the stated admissible preference domain.
The cited paper’s Theorem 1 establishes sufficiency; its appendix uses a finite message space consisting of a ranking and a permutation for each juror. Thus the result provides finite-message implementation. [Amorós, *Eliciting Socially Optimal Rankings from Unfair Jurors*, Theorem 1 and appendix](https://dialnet.unirioja.es/descarga/articulo/2133084.pdf).
Suppose now that \(\bigcup_t I_t=\binom{N}{2}\), and fix any eligible \(q\ge3\). All hypotheses hold:
The theorem therefore gives a finite implementing mechanism for this replica. It remains to justify that these separate existence statements yield one constructible scheme.
For any fixed replica, whether a proposed finite mechanism implements truth is decidable by exhaustive finite verification.
Indeed, \(\Pi\) is finite. Every complete, transitive weak order on \(\Pi\) can be represented by an ordered partition of \(\Pi\) into indifference classes. Enumerating all ordered partitions therefore enumerates all such weak orders.
For each juror \(j\), enumerate every function assigning one of these weak orders to each \(\sigma\in\Pi\). Retain precisely the functions satisfying the required adjacent-swap comparisons for every \(\sigma\). This filtering is a finite computation: it checks finitely many truths, pairs, and outcomes.
Taking all combinations of retained functions across the individually identified jurors, together with all truths, enumerates every admissible state. In particular, the enumeration permits different preference functions for jurors of the same type.
For a candidate mechanism specified by finite message sets and an outcome table, enumerate its message profiles. At each admissible state, a profile \(z\) is a pure Nash equilibrium exactly when
\( \displaystyle g(z)\;R_j(\sigma)\;g(z'_j,z_{-j}) \)
for every juror \(j\) and every message \(z'_j\) available to that juror. All these comparisons are finite and decidable. Check that at least one equilibrium exists and that every equilibrium has outcome \(\sigma\).
Now define one construction algorithm as follows.
Each stage contains finitely many candidates and terminates. Every finite mechanism occurs eventually, up to relabeling its messages. Under coverage, Section 3 guarantees that an implementing finite mechanism exists, so the search terminates.
The returned outcome algorithm also terminates, since it performs a finite table lookup. The construction uses only the society and \(q\); enumerating all possible states does not require observing the actual state.
This is one uniform constructible scheme. Its running time need not be polynomial, which the question explicitly permits. If an output is required for eligible sizes below three, the algorithm can return any fixed finite mechanism there; the implementation guarantee concerns sizes at least \(q_0=3\).
Combining the preceding sections gives the equivalence
\( \displaystyle \text{eventual constructible implementation exists} \quad\Longleftrightarrow\quad \bigcup_{t=1}^{\tau}I_t=\binom{N}{2}. \)
To decide the right-hand side, initialize a Boolean table indexed by unordered contestant pairs, mark every explicitly listed pair in every \(I_t\), and accept exactly when all entries are marked.
Writing \(S=\sum_t|I_t|\), this requires \(O(m^2+S)\) elementary table operations. Pair indices use polynomially many bits, and reading the input takes polynomial time in \(L\). Hence the decision procedure runs in polynomial time in \(m,\tau,L\). It never expands a replica or searches for a mechanism.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned decision problem correctly. The coverage criterion, impossibility argument, uniform construction, and polynomial decision procedure are valid. No major or minor gaps were found.
The denominator argument is correct. Each reduced denominator \(b_t\) is a positive integer, so \(D=\operatorname{lcm}(b_1,\ldots,b_\tau)\) exists. Every positive multiple of \(D\) makes every \(q\mu_t\) integral. Eligible replica sizes are therefore unbounded, preventing the eventual-implementation requirement from becoming vacuous.
For any eligible \(q\), positivity of \(\mu_t\) and integrality of \(q\mu_t\) imply \(q\mu_t\ge1\). Every supported type is consequently represented. The normalization of the masses gives exactly \(q\) jurors.
Thus
\[
\bigcup_{j\in J_q}I_j=\bigcup_{t=1}^{\tau}I_t
\]
holds for every eligible replica. No assumption about identical preferences within a type is used.
The choice of adjacent contestants \(a,b\) is legitimate. Swapping adjacent contestants changes the relative order of that pair alone.
The proposed utilities define a preference function at every possible true ranking, as required by the state definition. Ordering outcomes by integer utility gives a complete, transitive weak order, including when \(I_j\) is empty.
The admissibility calculation is correct: swapping an adjacent pair \(e\in I_j\) changes exactly one counted disagreement. The outcome agreeing with the truth on \(e\) has utility exactly one greater.
Because the uncovered pair belongs to no \(I_j\), the two truths agree on every pair counted by every juror. Consequently, the utility functions—and hence the outcome preferences—are identical at those two truths.
For a fixed mechanism, identical outcome preferences induce identical pure Nash equilibrium sets. The contradiction correctly uses the required existence of an equilibrium at the first truth: its message profile remains an equilibrium at the second truth, with the same incorrect outcome there.
This proves impossibility for every eligible replica. Unbounded eligibility then rules out every proposed threshold.
The cited result supports the theorem as used. Theorem 1 assumes at least three jurors, coverage of every contestant pair, and designer knowledge of the relevant jurors. The paper’s admissible-state definition matches the preference-function framework, and its appendix specifies messages consisting of a ranking and a permutation of the finite contestant set. These message spaces are finite, and the outcome rule is deterministic. See [Amorós, definitions, Theorem 1, and appendix](https://dialnet.unirioja.es/descarga/articulo/2133084.pdf).
The prover verifies the applicable hypotheses:
The conclusion of finite implementation is therefore justified. No unverified anonymity or shared-preference assumption enters the application.
The exhaustive verification procedure is valid.
Since \(\Pi\) is finite, ordered partitions enumerate all complete, transitive weak orders on \(\Pi\). Functions from the finite set of truths to this finite collection can also be exhaustively enumerated.
Filtering those functions by every required adjacent-swap comparison is a finite, decidable operation. Combining the retained functions independently across jurors and enumerating truths covers precisely the admissible states.
The equilibrium test has the correct direction: the current outcome must be weakly preferred to every outcome obtainable through a unilateral deviation. Complete preferences make this equivalent to having no strictly profitable unilateral deviation.
Checking equilibrium existence and requiring every equilibrium outcome to equal the truth verifies exactly the implementation definition.
The search over message-space sizes and outcome tables is effective. For each fixed bound, there are finitely many candidates, and each candidate’s verification terminates.
Every mechanism with finite nonempty message spaces is represented by some enumerated table after relabeling its messages. Under coverage, the finite-jury theorem supplies such a mechanism, so the search eventually terminates.
The output is a finite mechanism description with a terminating table-lookup outcome algorithm. The construction depends only on the society and replica size. Exhaustively considering possible states does not make it depend on the actual state.
The potentially enormous construction time does not violate the task, which imposes no polynomial construction bound. Returning an arbitrary mechanism below three jurors is also consistent with the guarantee beginning at \(q_0=3\).
The established equivalence is exactly the assigned eventual-replica decision criterion.
The Boolean coverage test uses \(O(m^2+S)\) table operations, where \(S=\sum_t|I_t|\). Explicit pair encoding and polynomial-size indices make the bit-operation cost polynomial in \(m,\tau,L\). The decision algorithm does not expand replicas or execute the mechanism search.
Empty individual pair sets, repeated pair listings across types, arbitrarily small positive masses, and eligibility denominators do not invalidate the argument. The assumptions \(m\ge3\), positive masses, and normalized total mass are all used consistently.
Required repair feedback: None.
⟨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.