Answer: Polynomial-time solvable: every valid instance admits an implementing regime.
Theorem 2 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateWhen n > 2, f is repeatedly implementable if and only if f is dynamically monotonic with respect to some collection C = (Ci(θ))i,θ.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite alternatives \(A\) and states \(\Theta\), rational masses \(\mu_t\) over constituency types \(t\), per-capita utilities \(u_t(a,\theta)\), state probabilities \(p\), discount factor \(\delta\), and a fixed tie-breaking rule, let \(f_\mu(\theta)\) maximize \(\sum_t \mu_t u_t(a,\theta)\). With one coordinating organization per type observing each state, decide whether there is a regime of repeated, possibly stochastic mechanisms with a nonempty Nash equilibrium set such that every equilibrium selects \(f_\mu(\theta)\) in every period and state.
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. Assume \(\tau\geq3\).
Let \(A\) and \(\Theta\) be finite, with \(m=|A|\geq2\) and \(k=|\Theta|\geq1\). Input utilities \(u_t(a,\theta)\in\mathbb{Q}\) may have either sign and satisfy \(u_t(a,\theta)\neq u_t(b,\theta)\) whenever \(a\neq b\). Input probabilities satisfy \(p(\theta)>0\) and \(\sum_\theta p(\theta)=1\); the rational discount factor satisfies \(0<\delta<1\).
A fixed total order on \(A\) breaks ties in \(f_\mu(\theta)\in\arg\max_{a\in A}\sum_t\mu_tu_t(a,\theta)\).
There is one strategic organization per support type. Organization \(t\) maximizes \((1-\delta)\mathbb{E}[\sum_{j=0}^{\infty}\delta^j\mu_tu_t(a^j,\theta^j)]\). States are drawn independently with distribution \(p\) each period and observed by every organization, but never by the designer.
A stage mechanism has arbitrary message spaces \(M_t\) and an allocation rule \(g:\prod_tM_t\to\Delta(A)\). Organizations send simultaneous public messages; the selected alternative is public, and utilities over lotteries are expected utilities. No transfers or additional public randomization device are available.
A regime is a committed, commonly known rule selecting a stage mechanism, possibly randomly, from the history of mechanisms, messages and realized alternatives. Its realized mechanism is announced before messages; strategies may depend additionally on the entire state history and current state. Neither message spaces nor mechanisms are required to be finite or rationally encoded.
Call a regime implementing if its pure-strategy Nash equilibrium set is nonempty and, in every such equilibrium, every period and current state, at every history reached with positive probability, the allocation assigns probability one to \(f_\mu(\theta)\).
Is deciding whether an implementing regime exists solvable in polynomial time in \(m,\tau,k,L\), where \(L\) is the total input bit length, or is it \(\mathrm{NP}\)-hard?
For at least three finite agents with strict preferences, repeated pure-strategy Nash implementation using stochastic regimes is equivalent to dynamic monotonicity. [Āzacis and Vida](https://doi.org/10.1016/j.jet.2019.01.002)
No exact complexity classification for the organization-based decision problem above was located in the literature search.
The problem is polynomial-time solvable. In fact, every valid instance admits an implementing regime.
The fixed total order used to break welfare ties is essential to the proof. No uniqueness assumption on the welfare maximizers is needed.
Write \(I=\{1,\ldots,\tau\}\), define \(w_i(a,\theta)=\mu_i u_i(a,\theta)\), and abbreviate \(f=f_\mu\). These are the organizations’ stage utilities. Since \(\mu_i>0\), their preferences over distinct alternatives remain strict.
For a lottery \(q\in\Delta(A)\), write \(w_i(q,\theta)=\sum_{a\in A}q(a)w_i(a,\theta)\). Define the prescribed payoff vector by
\(v_i^f=\sum_{\theta\in\Theta}p(\theta)w_i(f(\theta),\theta)\).
Let the set of feasible expected payoff vectors be
\(V=\left\{\sum_{\theta\in\Theta}p(\theta)\sum_{a\in A}q_\theta(a)w(a,\theta):q_\theta\in\Delta(A)\text{ for every }\theta\right\}\).
This is a compact convex set. It also contains every feasible normalized discounted continuation payoff, including those generated by history-dependent allocations. Indeed, conditional on any history before the next state draw, let \(q_{j,\theta}\) be the allocation lottery conditional on state \(\theta\) in future period \(j\). Independence of future states gives the continuation payoff
\(\sum_{\theta\in\Theta}p(\theta)\sum_{a\in A}\left((1-\delta)\sum_{j=0}^{\infty}\delta^j q_{j,\theta}(a)\right)w(a,\theta)\).
The expression in parentheses defines a lottery for each \(\theta\), so this vector belongs to \(V\).
The projection of \(V\) onto coordinate \(i\) is exactly the interval \([\ell_i,h_i]\), where
\(\ell_i=\sum_\theta p(\theta)\min_{a\in A}w_i(a,\theta)\), and
\(h_i=\sum_\theta p(\theta)\max_{a\in A}w_i(a,\theta)\).
The endpoints are achieved by selecting an alternative minimizing or maximizing organization \(i\)’s utility in each state. Convexity gives every intermediate coordinate value.
Two consequences will be used:
Both statements allow welfare ties and utilities of either sign.
Lemma. If \(f(s)\neq f(r)\), there exist an organization \(i\), a lottery \(q\), and a vector \(v\in V\) such that
\((1-\delta)w_i(q,s)+\delta v_i\leq(1-\delta)w_i(f(s),s)+\delta v_i^f\),
but
\((1-\delta)w_i(q,r)+\delta v_i>(1-\delta)w_i(f(s),r)+\delta v_i^f\).
Proof. Put \(a=f(s)\), \(b=f(r)\), and define
\(d_i(s)=w_i(b,s)-w_i(a,s)\), and
\(d_i(r)=w_i(b,r)-w_i(a,r)\).
Optimality of the prescribed alternatives gives
\(\sum_i d_i(s)\leq0\), and \(\sum_i d_i(r)\geq0\).
These inequalities cannot both be equalities. If they were, both \(a\) and \(b\) would maximize welfare in both states. Selecting \(a\) in state \(s\) would require \(a\) to precede \(b\) in the fixed order, whereas selecting \(b\) in state \(r\) would require the reverse.
Consequently,
\(\sum_i\bigl(d_i(r)-d_i(s)\bigr)>0\).
Choose an organization \(i\) for which \(d_i(r)>d_i(s)\).
We first show that \(v_i^f>\ell_i\). If \(v_i^f=\ell_i\), then
\(\sum_\theta p(\theta)\left(w_i(f(\theta),\theta)-\min_c w_i(c,\theta)\right)=0\).
Every summand is nonnegative and every state has positive probability. Thus \(f(\theta)\) minimizes organization \(i\)’s utility in every state. Strict preferences and \(a\neq b\) would then give \(d_i(s)>0\) and \(d_i(r)<0\), contradicting our choice of \(i\).
There are now two cases.
Case 1: \(v_i^f=h_i\). The corresponding argument using maxima shows that \(f(\theta)\) maximizes organization \(i\)’s utility in every state. Hence strict preferences give \(d_i(s)<0<d_i(r)\). Taking \(q\) to assign probability one to \(b\), and taking \(v=v^f\), proves both inequalities.
Case 2: \(\ell_i<v_i^f<h_i\). Let
\(\eta=\min\{v_i^f-\ell_i,h_i-v_i^f\}>0\).
Because \(a\neq b\), strict preferences imply \(d_i(s)\neq0\). Choose
\(\varepsilon=\min\left\{\frac12,\frac{\delta\eta}{2(1-\delta)|d_i(s)|}\right\}>0\),
and let \(q\) assign probability \(1-\varepsilon\) to \(a\) and probability \(\varepsilon\) to \(b\). Set
\(x=v_i^f-\frac{1-\delta}{\delta}\varepsilon d_i(s)\).
The displacement from \(v_i^f\) is at most \(\eta/2\), so \(x\in[\ell_i,h_i]\). The projection property of \(V\) supplies a vector \(v\in V\) with \(v_i=x\).
In state \(s\), the payoff difference from the prescribed pair is exactly
\((1-\delta)\varepsilon d_i(s)+\delta(x-v_i^f)=0\).
In state \(r\), that difference is
\((1-\delta)\varepsilon d_i(r)+\delta(x-v_i^f) =(1-\delta)\varepsilon\bigl(d_i(r)-d_i(s)\bigr)>0\).
This proves the lemma. \(\square\)
The vector \(v\) here is a feasible payoff vector used in a monotonicity test. The lemma does not assume that a designer can directly enforce this continuation.
We use the implementation–dynamic-monotonicity equivalence supplied in the question. Its lower-contour formulation is described in [Āzacis and Vida, Section 3](https://epub.ub.uni-muenchen.de/25292/1/518.pdf).
Define
\(C_i(s)=\left\{(q,v)\in\Delta(A)\times V:(1-\delta)w_i(q,s)+\delta v_i\leq(1-\delta)w_i(f(s),s)+\delta v_i^f\right\}\).
A dynamic deception specifies a reported state \(s=\pi_h(r)\) after each finite state history \(h\) and current true state \(r\). Let \(W(h,r)\) denote the normalized continuation payoff vector from the next period onward when the deception continues.
Dynamic monotonicity requires that the following inclusions, holding at every node and for every organization, imply \(f(\pi_h(r))=f(r)\):
\(C_i(\pi_h(r))\subseteq\left\{(q,v)\in\Delta(A)\times V:(1-\delta)w_i(q,r)+\delta v_i\leq(1-\delta)w_i(f(\pi_h(r)),r)+\delta W_i(h,r)\right\}\).
Consider any deception satisfying these inclusions. Fix \(h,r\), and put \(s=\pi_h(r)\).
The pair consisting of the deterministic alternative \(f(s)\) and continuation \(v^f\) belongs to \(C_i(s)\) for every organization. Substituting this pair into the inclusion cancels the current utility terms and gives
\(W_i(h,r)\geq v_i^f\) for every \(i\).
The continuation vector \(W(h,r)\) is feasible, hence belongs to \(V\). By the second consequence in Section 1, it follows that
\(W(h,r)=v^f\).
If \(f(s)\neq f(r)\), the separation lemma supplies an organization and a pair belonging to \(C_i(s)\) whose payoff in state \(r\) strictly exceeds the threshold with continuation \(v^f\). Since \(W(h,r)=v^f\), this contradicts the required inclusion.
Therefore \(f(\pi_h(r))=f(r)\) at every node. This proves dynamic monotonicity.
The supplied implementation theorem applies: there are \(\tau\geq3\) finite organizations, finite alternatives and states, strict preferences, independent state draws with full support, and a common discount factor satisfying \(0<\delta<1\). The permitted stochastic regimes and lottery allocations are precisely the instruments covered by that characterization; no transfers or additional public randomization device are introduced.
Dynamic monotonicity therefore guarantees an implementing regime, including a nonempty pure-strategy Nash equilibrium set and the required allocation in every equilibrium.
Thus the decision algorithm returns YES on every valid input. Under the input promise this takes constant time; if validity must also be checked, rational arithmetic and the stated preference comparisons take polynomial time in \(m,\tau,k,L\).
⟨structured verdict parsed — rendered above⟩
The prover’s conclusion is correct: every valid instance admits an implementing regime, so the promised decision problem is polynomial-time solvable. I found no major or minor mathematical gaps.
The replacement \(w_i(a,\theta)=\mu_i u_i(a,\theta)\) correctly represents each organization’s objective. Since every support mass satisfies \(\mu_i>0\), this scaling preserves strict preferences between distinct alternatives.
The definition of \(v^f\) is consistent with normalized discounted utility: implementing the same state-dependent rule every period gives the stated expected stage payoff.
The set \(V\) is compact and convex because it is the linear image of a finite product of lottery simplices. The argument that history-dependent continuation payoffs belong to \(V\) is valid:
The coordinate projection is exactly \([\ell_i,h_i]\). The stated endpoint allocations attain both extremes, and convexity supplies all intermediate coordinate values. This asserts coordinate feasibility, not independent feasibility of arbitrary coordinates; the subsequent proof uses only the former.
Both welfare consequences are correct. Statewise welfare maximization bounds the sum of coordinates of every vector in \(V\). Consequently, a feasible vector weakly exceeding \(v^f\) coordinatewise must equal \(v^f\), since any strict coordinate improvement would strictly increase its sum. Negative utilities and welfare ties do not affect either argument.
Every step of the lemma checks out.
Welfare inequalities and tie-breaking. With \(a=f(s)\) and \(b=f(r)\), optimality yields \(\sum_i d_i(s)\leq0\) and \(\sum_i d_i(r)\geq0\). If both sums were zero, both alternatives would be welfare maximizers in both states. The same fixed total order could not select \(a\) over \(b\) in one state and \(b\) over \(a\) in the other. Thus \(\sum_i(d_i(r)-d_i(s))>0\), which guarantees an organization satisfying \(d_i(r)>d_i(s)\).
The presence of additional welfare-maximizing alternatives does not invalidate this reasoning: selecting \(a\) still requires it to precede every other maximizer, including \(b\).
Excluding the lower endpoint. If \(v_i^f=\ell_i\), full support and nonnegative statewise differences force \(f\) to minimize this organization’s utility in every state. Strict preferences then imply \(d_i(s)>0\) and \(d_i(r)<0\), contradicting the selected inequality. Therefore \(v_i^f>\ell_i\).
Upper-endpoint case. If \(v_i^f=h_i\), the corresponding statewise maximum argument gives \(d_i(s)<0<d_i(r)\). Choosing the deterministic lottery on \(b\) and continuation \(v^f\) satisfies the lemma’s weak inequality at \(s\) and strict inequality at \(r\).
Interior case. Here \(\eta>0\), and strict preferences ensure \(d_i(s)\neq0\), so the definition of \(\varepsilon\) is well-defined. It gives \(0<\varepsilon\leq1/2\), hence a valid lottery. The displacement satisfies \(|x-v_i^f|\leq\eta/2\), ensuring coordinate feasibility.
The two payoff calculations are exact. At \(s\), the current payoff change cancels the continuation change. At \(r\), the remaining difference is \((1-\delta)\varepsilon(d_i(r)-d_i(s))>0\).
The proof correctly avoids claiming that the witness continuation vector is itself enforceable.
The stated inclusions agree with Definition 3 of the cited manuscript, using the full lower-contour sets over lotteries and feasible continuation vectors. Its deceptions depend on finite true-state histories, matching the prover’s notation. [Āzacis and Vida, Section 3](https://epub.ub.uni-muenchen.de/25292/1/518.pdf)
The quantifiers are handled correctly: the argument starts with a deception satisfying every required inclusion and then fixes an arbitrary history and current state.
The pair \((f(s),v^f)\) belongs to every relevant \(C_i(s)\), with equality. Substitution yields \(W_i(h,r)\geq v_i^f\) for every organization. The continuation generated by the deception is feasible, so Section 1 implies \(W(h,r)=v^f\).
If the reported and true states prescribe different alternatives, the separation lemma then supplies a pair in the reported-state contour set that violates the true-state inclusion. This contradiction establishes the required allocation equality at every node.
There is no circular assumption that the deception already implements \(f\) truthfully: feasibility of its continuation suffices.
The theorem application is valid. Corollary 1 of the cited manuscript gives the equivalence for at least three agents with stochastic stage mechanisms and stochastic regime transitions. Its model uses pure-strategy Nash equilibria, requires nonempty equilibrium sets, and imposes deterministic target allocations at positive-probability equilibrium histories. These match the task’s requirements; an additional public randomization device is unnecessary. [Āzacis and Vida, Sections 2 and 4](https://epub.ub.uni-muenchen.de/25292/1/518.pdf)
All remaining hypotheses are satisfied as written: finitely many organizations, alternatives, and states; strict preferences; independent full-support state draws; and a common discount factor strictly between zero and one.
The algorithmic conclusion follows. Under the validity promise, returning YES decides every instance. Checking validity also takes polynomial time using exact rational arithmetic and finitely many utility comparisons. The task asks for an existence decision, so no finite encoding or efficient construction of the implementing regime is required.
The case \(k=1\), and more generally a constant prescribed alternative, causes no gap: no pair of states has different prescribed alternatives, and the dynamic-monotonicity conclusion remains valid.
No repair is necessary. Naming “Definition 3 and Corollary 1” explicitly would make the citation easier to locate, but this is an optional editorial improvement.
⟨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.