Robust mechanism design

Robust mechanism design: base-information and prior-ambiguity certificates

Version 3. The full catalogue problem remains unresolved. Problem: D82-56. Status: Partial results; the complete catalogue target remains unresolved.

Problem and scope

The target is a mechanism maximizing its worst payoff over admissible information structures and all their Bayes--Nash equilibria. We retain the inner program and continuous-class approximation from earlier versions. Version 3 then closes two restrictions of that inner program: players may have pre-existing private information, and the common prior may be chosen adversarially from a declared polytope. The new joint program conditions obedience on the information players actually retain. The earlier continuity theorem still requires its explicit strict-obedience margin; the new exact inner program does not. The obedience reduction is the Bayes-correlated-equilibrium approach of Bergemann and Morris [BM]; its proof specifies exactly which ambiguity set makes the certificate valid.

A finite obedience program

Let $\Omega$ and $A_i$ be finite, $A=\prod_i A_i$, and let $\pi$ be a probability distribution on $\Omega$. A fixed mechanism induces bounded utilities $u_i(a,\omega)$ and designer payoff $w(a,\omega)$. Initially players have no information about $\omega$. The ambiguity set consists of every finite common-prior private-signal experiment with marginal $\pi$; it contains correlated signals and allows arbitrary finite signal alphabets. Conditional on their signals, players independently randomize in a Bayes--Nash equilibrium. Mechanism lotteries have already been integrated into $u_i$ and $w$.

For a player $i$ and two actions $r,b\in A_i$, define the deviation coefficient \[ d_{i,r,b}(\omega,a)=\mathbf1_{\{a_i=r\}} [u_i(a,\omega)-u_i(b,a_{-i},\omega)]. \] The finite obedience program is \begin{align} L=\min_{z\ge0}\quad &\sum_{\omega,a}w(a,\omega)z(\omega,a),\label{wsref-0-6c-70-3a-70-72-69-6d-61-6c}\\ \sum_a z(\omega,a)&=\pi(\omega)\quad(\omega\in\Omega),\nonumber\\ \sum_{\omega,a_{-i}}z(\omega,a_i,a_{-i}) [u_i(a_i,a_{-i},\omega)-u_i(b_i,a_{-i},\omega)]&\ge0 \quad(i,a_i,b_i).\nonumber \end{align}

Certificates and robust constraints

Index obedience inequalities by $j$ and write their coefficients as $d_j(\omega,a)$. A dual certificate consists of real $y_\omega$ and nonnegative $\lambda_j$ satisfying \[ y_\omega+\sum_j\lambda_j d_j(\omega,a)\le w(a,\omega) \quad\text{for every }(\omega,a). \]

Suppose robust feasibility is specified by finitely many expected inequalities $\mathbb E[h_\ell(a,\omega)]\ge0$ required at every equilibrium and experiment. Apply the same program with objective $h_\ell$. The mechanism is feasible precisely when every resulting minimum is nonnegative. For an ex-post violation set $B$, maximize $\sum_{(\omega,a)\in B}z(\omega,a)$; almost-sure feasibility at all admissible outcomes is equivalent to a zero maximum. These tests do not turn an interim participation condition into an ex-post one. A voluntarily available opt-out action, for example, gives conditional participation relative to that action through obedience.

Continuous mechanism classes and a uniform obedience margin

Let $(\mathcal M,d)$ be a nonempty compact metric parameter space of mechanisms, all with the same finite $\Omega$, $A_i$ and prior $\pi$ as above. Each mechanism has payoff arrays $u_i^m(a,\omega)$ and $w^m(a,\omega)$. The private-signal ambiguity set remains all finite experiments with marginal $\pi$. All additional mechanism feasibility requirements must hold for every $m\in\mathcal M$: for example, allocation lotteries, bounded transfers and ex-post budget restrictions can be built into the parameterization. If interim robust constraints are imposed, their satisfaction throughout $\mathcal M$ is a separate assumption or certification task. Compactness alone does not show that a nearby parameter remains feasible for such constraints.

For constants $L_u,L_w,W<\infty$, assume for all $m,m'$, players, actions and states that \begin{align*} |u_i^m(a,\omega)-u_i^{m'}(a,\omega)|&\leq L_u d(m,m'),\\ |w^m(a,\omega)-w^{m'}(a,\omega)|&\leq L_w d(m,m'),\qquad |w^m(a,\omega)|\leq W. \end{align*} Index the deviation rows by $j=(i,r,b)$ with $r\ne b$; the omitted $r=b$ rows are identically zero. Write $d_j^m$ for their coefficients. The following assumption deliberately excludes parameter values where some distinct-action obedience constraint can only hold with equality.

The margin is measured in the unnormalized obedience inequalities, including the probabilities of the recommendations. Thus it imposes both enough recommendation mass and strictly positive average gains from following them. It is stronger than mere nonemptiness of the Bayes-correlated-equilibrium set, which holds without it.

For a requested $\varepsilon>0$, write $C=L_w+4WL_u/\sigma$. If $C>0$, choose $h\leq\varepsilon/(2C)$ and $\varepsilon_0\leq\varepsilon/2$. The guarantee is then $\varepsilon$-optimal. If $C=0$, the continuity bound makes $L$ constant on the class, so any member suffices. With rational coefficients at rational net points, the primal and dual certificates can be checked by exact arithmetic as in Version 1. This does not assert a polynomial bound on net size or linear-program bit complexity in an arbitrary mechanism dimension.

The margin is nonvacuous and cannot be silently omitted

This counterexample does not show that every particular dense grid fails. It shows why continuity or a uniform approximation error cannot be obtained merely by assuming continuous primitives and compact parameters. The repair proof states an explicit condition under which the needed quantitative stability is valid. It is an application of standard finite linear-program stability reasoning, not a claim that uniform strict obedience holds in arbitrary mechanism classes.

Preserving base information and ambiguity about the common prior

The preceding sections start players with no information about a state and fix its prior. We now replace those assumptions. Let $\Omega$, $T_i$ and $A_i$ be finite nonempty sets; write $T=\prod_iT_i$ and $A=\prod_iA_i$. A primitive outcome is $(\omega,t)$, and player $i$ privately observes its base type $t_i$ before receiving any supplementary information. Payoffs $u_i(a,\omega,t)$ and $w(a,\omega,t)$ are fixed bounded arrays for the mechanism under assessment. The designer's uncertainty concerns both the state and the distribution of players' base information.

Let $\mathcal Q$ be a nonempty compact polytope of probability laws $\mu$ on $\Omega\times T$. Nature chooses $\mu\in\mathcal Q$. The realized $\mu$ is the common prior used by all players in this Bayesian game; the designer's guarantee is uniform over those games. This is distinct from a model where the players themselves are ambiguity averse or have incompatible priors. For each such $\mu$, nature may choose any finite supplementary private-signal experiment conditional on $(\omega,t)$, allowing correlations among signals. Player $i$ observes $(t_i,s_i)$ and plays a Bayes--Nash equilibrium. Its base type cannot be erased or replaced by the supplementary signal. The robust value takes the infimum over all these priors, experiments and equilibria.

For $r,b\in A_i$ and a base type $\tau\in T_i$, define the linear obedience expression \begin{align*} (Dz)_{i,\tau,r,b} =\sum_{\omega,t_{-i},a_{-i}} &z\bigl(\omega,(\tau,t_{-i}),(r,a_{-i})\bigr)\\[-2pt] &\cdot\left[u_i\bigl((r,a_{-i}),\omega,(\tau,t_{-i})\bigr) -u_i\bigl((b,a_{-i}),\omega,(\tau,t_{-i})\bigr)\right]. \end{align*} Rows with $r=b$ may be omitted. Let $C$ be the marginal map $(Cz)(\omega,t)=\sum_a z(\omega,t,a)$. The new program is \begin{align} L_{\mathcal Q}=\min_{z\geq0}\quad & w\cdot z,\label{wsref-0-6c-70-3a-62-61-73-65}\\ &Cz\in\mathcal Q,\qquad Dz\geq0.\nonumber \end{align} It is one finite linear program: membership in $\mathcal Q$ consists of its declared linear equalities and inequalities. There is no conditional-probability division by an unknown prior mass. Obedience is indexed by both base type and recommended action, which is essential.

Certificates for the joint program

For clarity, represent the prior polytope in the form \[ \mathcal Q=\{\mu\geq0:H\mu=h,\ G\mu\geq g\}, \] where the equalities or inequalities include normalization and all restrictions defining $\mathcal Q$. The nonnegative marginal follows already from $z\geq0$. The letters $H,G,h,g$ denote finite matrices and vectors and have no relation to the earlier mechanism metric. A dual certificate consists of a free vector $y$ and nonnegative vectors $\gamma,\lambda$ such that \[ C^{\mathsf T}H^{\mathsf T}y+ C^{\mathsf T}G^{\mathsf T}\gamma+D^{\mathsf T}\lambda \leq w \tag{6} \] coordinatewise.

The sign and conditioning of each obedience row are part of the certificate. Replacing a row conditioned on $t_i$ by one that averages over all $t_i$ can admit recommendations a player would refuse using information it already possesses.

These are unconditional expected requirements. An interim requirement can instead be encoded with the appropriate type indicator and its stated outside option, provided its unnormalized form is equivalent on positive-probability types. It must not be silently replaced by an aggregate participation inequality. Similarly, restricting supplementary signal alphabets below the recommendation construction or imposing additional restrictions on experiments can make the displayed program a relaxation rather than an exact characterization.

Remaining gap

Version 3 supplies an exact finite inner problem that preserves private base types and jointly optimizes over a polyhedral family of common priors, with explicit certificates and an implementable adverse experiment. The single-prior, no-base-information program is its special case with singleton type sets and a singleton prior polytope. This is an application of the information-expansion/Bayes-correlated-equilibrium logic of Bergemann and Morris [BM], not a new general revelation principle or a claim of novelty for that characterization.

The outer design problem still needs a declared mechanism class. Earlier sections give one continuous-class approximation with fixed finite message sets under a uniform strict-obedience condition; the new exact inner program does not establish that condition automatically. Arbitrary message alphabets, nonpolyhedral prior restrictions without an approximation certificate, bounded supplementary communication, unknown or incompatible player priors, and preservation of binding interim robust constraints under outer discretization remain unresolved.

Completion Estimate

55%

This is a heuristic estimate for the full catalogue target. The exact pessimistic-equilibrium calculation now retains private base information and handles polyhedral ambiguity about the joint common prior, including rational primal/dual certificates. General outer design, unrestricted messages and more restrictive information-expansion classes still require arguments beyond this finite characterization.

References

• [BM] D. Bergemann and S. Morris (2016), Bayes correlated equilibrium and the comparison of information structures in games, Theoretical Economics 11, 487--522. https://www.econtheory.org/ojs/index.php/te/article/viewArticle/20160487. Source of the obedience/outcome characterization; the finite-library certification formulation above is derived here.
• [robust] D. Bergemann and S. Morris (2005), Robust mechanism design, Econometrica 73, 1771--1813. https://doi.org/10.1111/j.1468-0262.2005.00638.x. Background on informational robustness, not a solution of arbitrary outer design problems.

Robust mechanism design: continuous-class approximation with obedience certificates

Version 2. The full catalogue problem remains unresolved. Problem: D82-56. Status: Partial results; the complete catalogue target remains unresolved.

Problem and scope

The target is a mechanism maximizing its worst payoff over admissible information structures and all their Bayes--Nash equilibria. We retain the exact inner problem and finite-library certificates from Version 1, then prove a quantitative outer approximation for a compact continuous mechanism class under uniformly strict obedience feasibility. A counterexample explains why that regularity assumption is substantive. The obedience reduction is the Bayes-correlated-equilibrium approach of Bergemann and Morris [BM]; its proof specifies exactly which ambiguity set makes the certificate valid.

A finite obedience program

Let $\Omega$ and $A_i$ be finite, $A=\prod_i A_i$, and let $\pi$ be a probability distribution on $\Omega$. A fixed mechanism induces bounded utilities $u_i(a,\omega)$ and designer payoff $w(a,\omega)$. Initially players have no information about $\omega$. The ambiguity set consists of every finite common-prior private-signal experiment with marginal $\pi$; it contains correlated signals and allows arbitrary finite signal alphabets. Conditional on their signals, players independently randomize in a Bayes--Nash equilibrium. Mechanism lotteries have already been integrated into $u_i$ and $w$.

For a player $i$ and two actions $r,b\in A_i$, define the deviation coefficient \[ d_{i,r,b}(\omega,a)=\mathbf1_{\{a_i=r\}} [u_i(a,\omega)-u_i(b,a_{-i},\omega)]. \] The finite obedience program is \begin{align} L=\min_{z\ge0}\quad &\sum_{\omega,a}w(a,\omega)z(\omega,a),\label{wsref-0-6c-70-3a-70-72-69-6d-61-6c}\\ \sum_a z(\omega,a)&=\pi(\omega)\quad(\omega\in\Omega),\nonumber\\ \sum_{\omega,a_{-i}}z(\omega,a_i,a_{-i}) [u_i(a_i,a_{-i},\omega)-u_i(b_i,a_{-i},\omega)]&\ge0 \quad(i,a_i,b_i).\nonumber \end{align}

Certificates and robust constraints

Index obedience inequalities by $j$ and write their coefficients as $d_j(\omega,a)$. A dual certificate consists of real $y_\omega$ and nonnegative $\lambda_j$ satisfying \[ y_\omega+\sum_j\lambda_j d_j(\omega,a)\le w(a,\omega) \quad\text{for every }(\omega,a). \]

Suppose robust feasibility is specified by finitely many expected inequalities $\mathbb E[h_\ell(a,\omega)]\ge0$ required at every equilibrium and experiment. Apply the same program with objective $h_\ell$. The mechanism is feasible precisely when every resulting minimum is nonnegative. For an ex-post violation set $B$, maximize $\sum_{(\omega,a)\in B}z(\omega,a)$; almost-sure feasibility at all admissible outcomes is equivalent to a zero maximum. These tests do not turn an interim participation condition into an ex-post one. A voluntarily available opt-out action, for example, gives conditional participation relative to that action through obedience.

Continuous mechanism classes and a uniform obedience margin

Let $(\mathcal M,d)$ be a nonempty compact metric parameter space of mechanisms, all with the same finite $\Omega$, $A_i$ and prior $\pi$ as above. Each mechanism has payoff arrays $u_i^m(a,\omega)$ and $w^m(a,\omega)$. The private-signal ambiguity set remains all finite experiments with marginal $\pi$. All additional mechanism feasibility requirements must hold for every $m\in\mathcal M$: for example, allocation lotteries, bounded transfers and ex-post budget restrictions can be built into the parameterization. If interim robust constraints are imposed, their satisfaction throughout $\mathcal M$ is a separate assumption or certification task. Compactness alone does not show that a nearby parameter remains feasible for such constraints.

For constants $L_u,L_w,W<\infty$, assume for all $m,m'$, players, actions and states that \begin{align*} |u_i^m(a,\omega)-u_i^{m'}(a,\omega)|&\leq L_u d(m,m'),\\ |w^m(a,\omega)-w^{m'}(a,\omega)|&\leq L_w d(m,m'),\qquad |w^m(a,\omega)|\leq W. \end{align*} Index the deviation rows by $j=(i,r,b)$ with $r\ne b$; the omitted $r=b$ rows are identically zero. Write $d_j^m$ for their coefficients. The following assumption deliberately excludes parameter values where some distinct-action obedience constraint can only hold with equality.

The margin is measured in the unnormalized obedience inequalities, including the probabilities of the recommendations. Thus it imposes both enough recommendation mass and strictly positive average gains from following them. It is stronger than mere nonemptiness of the Bayes-correlated-equilibrium set, which holds without it.

For a requested $\varepsilon>0$, write $C=L_w+4WL_u/\sigma$. If $C>0$, choose $h\leq\varepsilon/(2C)$ and $\varepsilon_0\leq\varepsilon/2$. The guarantee is then $\varepsilon$-optimal. If $C=0$, the continuity bound makes $L$ constant on the class, so any member suffices. With rational coefficients at rational net points, the primal and dual certificates can be checked by exact arithmetic as in Version 1. This does not assert a polynomial bound on net size or linear-program bit complexity in an arbitrary mechanism dimension.

The margin is nonvacuous and cannot be silently omitted

This counterexample does not show that every particular dense grid fails. It shows why continuity or a uniform approximation error cannot be obtained merely by assuming continuous primitives and compact parameters. The repair proof states an explicit condition under which the needed quantitative stability is valid. It is an application of standard finite linear-program stability reasoning, not a claim that uniform strict obedience holds in arbitrary mechanism classes.

Remaining gap

The reduction includes pessimistic equilibrium selection without presuming truthful reporting. If the catalogue ambiguity set restricts signal alphabets or preserves pre-existing private information, the unrestricted program can be only a conservative bound unless those restrictions are encoded. Version 2 supplies an outer approximation theorem for a compact class with fixed message sizes and a uniform strict-obedience certificate. It does not approximate arbitrary message alphabets, prove that every optimal mechanism has a strict certificate, or automatically preserve binding interim robust constraints under discretization. Enlarging any ambiguity set weakly lowers the value of each fixed mechanism; when robust feasibility is also tightened, taking the supremum over the smaller feasible class preserves that inequality.

Completion Estimate

45%

This is a heuristic estimate for the full catalogue target. The continuous-class theorem now combines exact pessimistic-equilibrium certificates with a quantitative finite-net approximation and an explicit failure example. Uniform strict obedience, fixed message sets, feasible net construction and the unrestricted common-prior signal ambiguity remain substantial restrictions on the full design target.

References

• [BM] D. Bergemann and S. Morris (2016), Bayes correlated equilibrium and the comparison of information structures in games, Theoretical Economics 11, 487--522. https://www.econtheory.org/ojs/index.php/te/article/viewArticle/20160487. Source of the obedience/outcome characterization; the finite-library certification formulation above is derived here.
• [robust] D. Bergemann and S. Morris (2005), Robust mechanism design, Econometrica 73, 1771--1813. https://doi.org/10.1111/j.1468-0262.2005.00638.x. Background on informational robustness, not a solution of arbitrary outer design problems.

Robust mechanism design: exact certificates for a finite mechanism library

Problem: D82-56. Status: Partial results; the complete catalogue target remains unresolved.

Problem and scope

The target is a mechanism maximizing its worst payoff over admissible information structures and all their Bayes--Nash equilibria. We solve the inner problem exactly for a finite-state benchmark with unrestricted additional private signals, and the outer problem for a finite library. The obedience reduction is the Bayes-correlated-equilibrium approach of Bergemann and Morris [BM]; its proof is included to specify exactly which ambiguity set makes the certificate valid.

A finite obedience program

Let $\Omega$ and $A_i$ be finite, $A=\prod_i A_i$, and let $\pi$ be a probability distribution on $\Omega$. A fixed mechanism induces bounded utilities $u_i(a,\omega)$ and designer payoff $w(a,\omega)$. Initially players have no information about $\omega$. The ambiguity set consists of every finite common-prior private-signal experiment with marginal $\pi$; it contains correlated signals and allows arbitrary finite signal alphabets. Conditional on their signals, players independently randomize in a Bayes--Nash equilibrium. Mechanism lotteries have already been integrated into $u_i$ and $w$.

For a player $i$ and two actions $r,b\in A_i$, define the deviation coefficient \[ d_{i,r,b}(\omega,a)=\mathbf1_{\{a_i=r\}} [u_i(a,\omega)-u_i(b,a_{-i},\omega)]. \] The finite obedience program is \begin{align} L=\min_{z\ge0}\quad &\sum_{\omega,a}w(a,\omega)z(\omega,a),\label{wsref-0-6c-70-3a-70-72-69-6d-61-6c}\\ \sum_a z(\omega,a)&=\pi(\omega)\quad(\omega\in\Omega),\nonumber\\ \sum_{\omega,a_{-i}}z(\omega,a_i,a_{-i}) [u_i(a_i,a_{-i},\omega)-u_i(b_i,a_{-i},\omega)]&\ge0 \quad(i,a_i,b_i).\nonumber \end{align}

Certificates and robust constraints

Index obedience inequalities by $j$ and write their coefficients as $d_j(\omega,a)$. A dual certificate consists of real $y_\omega$ and nonnegative $\lambda_j$ satisfying \[ y_\omega+\sum_j\lambda_j d_j(\omega,a)\le w(a,\omega) \quad\text{for every }(\omega,a). \]

Suppose robust feasibility is specified by finitely many expected inequalities $\mathbb E[h_\ell(a,\omega)]\ge0$ required at every equilibrium and experiment. Apply the same program with objective $h_\ell$. The mechanism is feasible precisely when every resulting minimum is nonnegative. For an ex-post violation set $B$, maximize $\sum_{(\omega,a)\in B}z(\omega,a)$; almost-sure feasibility at all admissible outcomes is equivalent to a zero maximum. These tests do not turn an interim participation condition into an ex-post one. A voluntarily available opt-out action, for example, gives conditional participation relative to that action through obedience.

Remaining gap

The reduction includes pessimistic equilibrium selection without presuming truthful reporting. If the catalogue ambiguity set restricts signal alphabets or preserves pre-existing private information, the unrestricted program can be only a conservative bound unless those restrictions are encoded. A finite mechanism library also needs an independent approximation theorem before its optimum approximates an infinite admissible class. No such outer discretization theorem is established here. Enlarging any ambiguity set weakly lowers the value of each fixed mechanism; when robust feasibility is also tightened, taking the supremum over the smaller feasible class preserves that inequality.

References

• [BM] D. Bergemann and S. Morris (2016), Bayes correlated equilibrium and the comparison of information structures in games, Theoretical Economics 11, 487--522. https://www.econtheory.org/ojs/index.php/te/article/viewArticle/20160487. Source of the obedience/outcome characterization; the finite-library certification formulation above is derived here.
• [robust] D. Bergemann and S. Morris (2005), Robust mechanism design, Econometrica 73, 1771--1813. https://doi.org/10.1111/j.1468-0262.2005.00638.x. Background on informational robustness, not a solution of arbitrary outer design problems.

Completion Estimate

30%