Implementation with Evidence

Abstract.

We generalize the canonical problem of Nash implementation by allowing agents to voluntarily provide discriminatory signals, i.e. evidence.  Evidence can either take the form of hard information or, more generally, have differential but non-prohibitive costs in different states.  In such environments, social choice functions that are not Maskin-monotonic can be implemented.  We formulate a more general property, evidence-monotonicity, and show that this is a necessary condition for implementation.  Evidence-monotonicity is also sufficient for implementation in economic environments.  In some settings, such as when agents have small preferences for honesty, any social choice function is evidence-monotonic.  Additional characterizations are obtained for hard evidence.  We discuss the relationship between the implementation problem where evidence provision is voluntary and a hypothetical problem where evidence can be chosen by the planner as part of an extended outcome space.

1. Introduction

A classic issue in mechanism design is that of (full) Nash implementation.  The goal is to design a mechanism such that in every state of the world, every Nash equilibrium outcome of the game induced by the mechanism is desirable.  A maintained assumption in almost all of the literature following Maskin (1999, circulated in 1977) is that agents can manipulate their information without restraint.  Specifically, the set of messages that is available to an agent in a given mechanism is assumed to be state independent; furthermore, all messages are assumed to be costless.  In this sense, all messages are “cheap talk”: they do not affect an agent’s payoff directly, and only matter indirectly insofar as they affect the outcome chosen by the mechanism.

Our goal is to focus attention on why this aspect of the implementation problem is restrictive, and to generalize the set of environments that the theory can be applied to.  To motivate our treatment, here are three examples:

1. A principal wishes to divide a fixed sum of money between agents as some function of their individual output.  If only asked to send cheap-talk messages about their output, agents could claim anything they want.  But agents may also be able to provide physical verification or some other kind of certification of their output.  An agent would be unable to certify that his output is greater than it in fact is, but she could certify less, for example by simply not furnishing all of it.  If it is costless to provide such certification, the setting is one of hard or verifiable information.  If instead agents bear costs as a function of how much output they carry to the principal’s court (so to speak), but not how much they have actually produced, then we have a costly signaling instrument that combines hard information with “burning money”.  If the cost of certification also depends on how much they actually produced, then a more complex signaling instrument is at hand.

2. A principal wants to hire the agent who has the highest ability and pay him a wage equal to his marginal product.  In addition to sending messages as requested by the mechanism, agents have the choice to voluntarily acquire any amount of education.  Education is intrinsically useless, but the marginal cost depends on an agent’s ability.  This is an implementation version of the classical education-signaling problem (Spence, 1973).

3. When asked to report a direct message about the state, some agents may have a (possibly small) degree of aversion to lying: they prefer to send a truthful message about the state if it results in an outcome that is not much worse for them than what could be obtained by lying.  The extent of this aversion may be heterogenous across agents.

Common to all these examples is that some messages or actions are either only feasible for an agent in some states of the world or have differential costs in different states.  As this naturally arises in numerous settings, it is important to study implementation in a framework that accommodates this feature.  While the issue has received some attention in the context of partial- or weak-implementation, it has received almost none in treatments of full-implementation, with exceptions that we discuss subsequently.

Accordingly, this paper adds evidence to an otherwise standard Nash-implementation environment.  (Hereafter, we use the term “implementation” without qualification to mean “full implementation in Nash equilibrium”.)  The defining feature of a piece of evidence is that it is a discriminatory signal about the state of the world, as opposed to a cheap-talk message.  A mechanism can not only rely on cheap-talk messages as usual, but also on the profile of evidence submitted by the players.  Given the ability to commit to a mechanism, a planner cannot do worse when evidence is available than when it is not; our interest is in understanding exactly when there is a strict benefit and precisely how much so.  In particular, which social objectives are implementable given some evidentiary structure, and what evidentiary structure is needed to make a particular social objective implementable?

In Section 2, we formulate a fairly general problem of complete-information implementation with evidence.  Each player $i$ chooses which evidence to provide from some feasible set, $E_i$.  While our formal treatment is broader, assume for this introduction that at each state $\theta$, player $i$ has preferences that are separable between the outcome chosen by the planner — his outcome-preference — and the evidence she submits.  We posit that submitting any evidence imposes a non-negative cost on a player, but the magnitude of the cost can depend on the evidence and the state of the world.  Crucially, a player’s choice of evidence is inalienable: a mechanism cannot force any player to submit any particular piece of evidence.  This renders a fundamental distinction between the profile of submitted evidence and the outcome chosen by the planner.

We investigate when a social choice function (SCF) is Nash-implementable in this setting, where the notion of implementation requires that no evidentiary costs be incurred on the equilibrium path.  Without evidence, a SCF is implementable only if it is Maskin-monotonic with respect to players’ outcome-preferences (Maskin, 1999).  A simple but significant observation is that this is no longer true once evidence is in the picture.  Rather, what matters is preferences over the joint space of outcomes and evidence.  In Section 3, we identify a necessary condition for implementablity that we call evidence-monotonicity. This condition is weaker than Maskin-monotonicity, and the two concepts coincide if and only if there is no evidence.  Our condition can be roughly described by considering a hypothetical problem where instead of choosing an outcome after players voluntarily submit evidence and cheap-talk messages, the planner instead chooses both an outcome and an evidence profile after players only submit cheap-talk messages.  Loosely speaking, evidence-monotonicity requires that one finds an augmented SCF on this joint outcome-plus-evidence space that only uses costless evidence and is Maskin-monotonic with respect to the players preferences on the joint space.

Viewed in this way, it is fairly intuitive why evidence-monotonicity is necessary for implementation.  We prove that it is also almost sufficient in the sense that any evidence-monotonic SCF can be implemented when there are three or more players and the environment is economic. An economic environment is one where in any state, given any outcome, there are at least two players for whom this outcome is not top-ranked. This sufficiency result is unexpected because the choice of what evidence to furnish is inalienable or voluntary, whereas the intuition described above behind the evidence-monotonicity condition assumes the planner has the power to choose the evidence profile.  Section 4 develops a “bridge” between the two problems.

The characterization of implementability in terms of evidence-monotonicity has a number of applications.  In some problems, such as the benchmark education-signaling described earlier, natural SCFs cannot be implemented because they are not evidence-monotonic.  On the other hand, under some evidentiary cost structures, every SCF becomes evidence-monotonic.  A striking case is when at least one player has a small preference for honesty.  Formally, this is captured by setting each player’s feasible set of evidence to be $E_i=\mathrm{\Theta }$, where $\mathrm{\Theta }$ is the set of all possible states of the world.  The assumption is that an honest player suffers an arbitrarily small cost of submitting non-truthful evidence.  Our results imply that in such a setting with three or more players, any SCF can be implemented in economic environments.  Dutta and Sen (2011) and Matsushima (2008a, b) find related results focussing specifically on preferences for honesty and with some differences in formalization.

Section 5 specializes our general model to settings of hard or non-manipulable evidence: it is prohibitively costly for an agent to produce evidence that she does not in fact possess.  Formally, in each state $\theta$, each agent $i$ has a set of evidence, $E_i^{\mathrm{\ell }}(\theta )\subseteq E_i$, such that she can costlessly submit any $e_i\in E_i^{\mathrm{\ell }}(\theta )$ but incurs such a large cost of submitting any $e_i\notin E_i^{\mathrm{\ell }}(\theta )$ that the latter is strictly dominated.  As we place no restriction on the evidence structure, $\left\{E_i^{\mathrm{\ell }}(\theta )\right\}$, the standard environment without evidence is a special case where for all $\theta$, $E_i^{\mathrm{\ell }}(\theta )=E_i$ for any player $i$.  We deduce the implications of evidence-monotonicity in this setting of hard evidence.  Of particular interest, we find that (i) when there are no outcome-preference reversals to exploit, evidence needs to distinguish in an appropriate sense not only particular pairs of states, but moreover certain states from other sets of states or events, and (ii) some ability to reward agents for providing evidence is necessary.  Further insights are developed for the sub-class of hard evidence problems that satisfy normality or full reports (Bull and Watson, 2007; Lipman and Seppi, 1995), which can be interpreted as a “no time constraints” assumption on the provision of evidence.

Before turning to a discussion of related literature, let us address one potential concern that some readers may have: why study Nash implementation in a setting with evidence when earlier work has already shown that quite permissive results can be obtained without evidence by either using refinements of Nash equilibrium (e.g. Moore and Repullo, 1988; Jackson, Palfrey, and Srivastava, 1994) or focussing on approximate or virtual implementation (Abreu and Sen, 1991; Matsushima, 1988)?  There are at least three reasons.  First, our motivation is not merely to broaden the scope of what is implementable, but rather to understand the role that evidence can play in implementation by studying such environments directly.  It is natural to begin with the Nash benchmark, and indeed our necessary conditions identify constraints on how evidence can be used.  Second, the aforementioned permissive results without evidence are not without limits; and third, these results have been questioned from various perspectives.

This paper contributes to the burgeoning literature on mechanism design with evidence.  Most of this literature concerns partial-implementation with hard evidence.  An early reference is Green and Laffont (1986), and a sample of more recent work is Bull and Watson (2004, 2007), Deneckere and Severinov (2008), Glazer and Rubinstein (2004, 2006), Sher (2010), and Singh and Wittman (2001).   Bull (2008) and Deneckere and Severinov (2007) study partial-implementation with costly evidence production.

In the full-implementation literature, there is a small set of papers that study feasible implementation, where the set of feasible allocations is unknown to the planner.  It is typically assumed that the planner can partially verify players’ claims in particular ways.  For example, in a Walrasian economy setting, Hurwicz, Maskin, and Postlewaite (1995) and Postlewaite and Wettstein (1989) assume that a player can claim to have any subset of his true endowment but not exaggerate; in a taxation problem with unknown incomes, Dagan, Volij, and Serrano (1999) make a similar assumption.  In our model, the set of allocations is constant and known to the planner; instead, it is the set of messages for players that either varies with or has varying costs with the state.

Closest to our work is a recent paper by Ben-Porath and Lipman (2011), who also tackle complete information full-implementation with evidence.  While our results were derived independently, we have benefitted from reading their treatment.  The motivations for their work and ours are similar—particularly with respect to advancing the prior literature—but the analytical focus is quite different.  The two most important differences are that (i) our paper provides a treatment of a general costly evidence provision setting, whereas they focus entirely on hard evidence; and (ii) we study Nash implementation throughout, whereas they focus on subgame-perfect implementation.  Moreover, their main results require that the planner can augment monetary transfers off the equilibrium path; as mentioned earlier, we show that some ability to reward players is in fact necessary to exploit hard evidence.

2. The Model

There is a non-empty set of agents or players, $I=\{1,\mathrm{\dots },n\}$, a set of allocations or outcomes, $A$, and a set of states of the world, $\mathrm{\Theta }$.  To avoid trivialities, $\left|A\right|>1$ and $\left|\mathrm{\Theta }\right|>1$.  The state is common knowledge to the agents, but unknown to the planner.  The planner’s objectives are given by a social choice function (SCF), which is a function $f:\mathrm{\Theta }\to A$.  In any state, agent $i$ can produce a piece of evidence, $e_i\in E_i$, where $E_i\ne \mathrm{\varnothing }$ is $i$’s feasible set of evidence.  Let $E:=E_1\times \mathrm{\cdots }\times E_n$.  Throughout, we use a subscript $-i$ to denote all players excluding $i$, so that, for example, $E_{-i}:={\times }_{j\ne i}{E}_j$.

Agents are expected utility maximizers, and an agent $i$’s preferences are represented by a von Neumann-Morgenstern utility function, $U_i:A\times E_i\times \mathrm{\Theta }\to ℝ$.  Here, $U_i(a,e_i,\theta )$ is agent $i$’s utility in state $\theta$ when the outcome is $a$ and she submits evidence $e_i$.  We assume that utilities are bounded in each state: for all $i$ and $\theta$, and ${inf}_{a,e_i}{U}_i(a,e_i,\theta )>-\mathrm{\infty }$.  We say that preferences are separable (between outcomes and evidence) if for all $i$ there is a decomposition $U_i(a,e_i,\theta )=u_i(a,\theta )-c_i(e_i,\theta )$.  Under separability, $u_i(a,\theta )$ represents agent $i$’s preferences over outcomes and $c_i(e_i,\theta )$ represents the cost to agent $i$ of evidence provision.

We wish to capture situations in which evidence submission is not intrinsically valued by the agents or the planner.  Let $E_i^{\mathrm{\ell }}(\theta ,a):={\arg \max }_{e_i}{U}_i(a,e_i,\theta )$ be the set of least-cost evidence for a player $i$ given the outcome $a$ and state $\theta$.  We assume that for each player $i$, outcome $a$, and state $\theta$, $E_i^{\mathrm{\ell }}(\theta ,a)\ne \mathrm{\varnothing }$.  Let $E^{\mathrm{\ell }}(\theta ,a):=E_1^{\mathrm{\ell }}(\theta ,a)\times \mathrm{\cdots }\times E_n^{\mathrm{\ell }}(\theta ,a)$, so that given outcome $a$ and state $\theta$, any profile of evidence in $E^{\mathrm{\ell }}(\theta ,a)$ consists of each player submitting some least-cost evidence.  For short, we call $e\in E^{\mathrm{\ell }}(\theta ,a)$ a costless evidence profile.  We say that $e_i$ is cheap-talk evidence if $e_i\in {\bigcap }_{\theta }{\bigcap }_a{E}_i^{\mathrm{\ell }}(\theta ,a)$, because such an $e_i$ is a least-cost evidence for $i$ no matter the state or outcome.  If preferences are separable, we write $E_i^{\mathrm{\ell }}(\theta )={\arg \min }_{e_i}{c}_i(e_i,\theta )$.

In standard Nash-implementation theory, a mechanism consists of a (cheap-talk) message space and an outcome function which specifies an outcome for every profile of messages.  In the current setting, a mechanism can also take advantage of the evidence that players submit.  Formally, a mechanism is a pair $(M,g),$ where $M=M_1\times \mathrm{\cdots }\times M_n$ is a message space, and $g:M\times E\to A$ is an outcome function that specifies an outcome for every profile of messages and evidence.

A mechanism $(M,g)$ induces a strategic-form game in each state of the world, $\theta$, where a pure strategy for player $i$ is $(m_i,e_i)\in M_i\times E_i$ and a pure-strategy profile $(m,e):={(m_i,e_i)}_{i=1}^n$ yields a payoff $U_i(g(m,e),e_i,\theta )$ to player $i$.  Let $NE(M,g,\theta )$ be the set of pure strategy Nash equilibria (NE, hereafter) of the mechanism $(M,g)$ in state $\theta$.  For expositional simplicity, we restrict attention to pure strategy equilibria; our results can be extended to mixed strategy equilibria as discussed in Remark 1 following Theorem 2.

Since the planner’s objective, represented by the SCF, only specifies an outcome for each state, a definition of implementation must take a stance on what profiles of evidence are acceptable to the planner.  We adopt the following notion.

Definition 1 (Implementation).

A mechanism $(M,g)$ implements the SCF $f$ if

1. $\forall \theta :f(\theta )=\{a:a=g(m,e)\text{ for some }(m,e)\in NE(M,g,\theta )\}$, and

2. $(m,e)\in NE(M,g,\theta )⟹e\in E^{\mathrm{\ell }}(\theta ,f(\theta ))$.

A SCF is implementable if there is a mechanism that implements it.

We now comment on a number of aspects of the model:

1. One can think of any $e_i$ as a document, physical object, verbal claim, or action that agent $i$ can submit, provide, or take.  What is crucial is that the decision of which evidence to submit is a player’s private decision as in Myerson (1982) and cannot be coerced by the planner at any point.  In this sense, following Bull and Watson’s (2007) terminology, we view evidence as inalienable.  This renders a fundamental distinction between the outcome space, $A$, which falls under the planner’s purview, and the evidence profile space, $E$, which does not.

2. The present framework nests the standard model without evidence as a special case: it arises when all evidence for every player is cheap-talk evidence, in which case preferences are separable and one can set $c_i(e_i,\theta )=0$ for all $i,e_i,\theta$.  Note that the second part of Definition 1 is trivially satisfied in this case, because for any $a$ and $\theta$, $E^{\mathrm{\ell }}(\theta ,a)=E$. Hence, without evidence, our notion of implementation reduces to the standard notion.

3. More generally, part two of Definition 1 requires that only costless evidence profiles must be sent in any equilibrium of an implementing mechanism.  Given our motivation that evidence is not intrinsically valued by the planner or the players, the interpretation is that an implementing mechanism should not lead to any (Pareto) inefficient evidence production.  This is a natural benchmark, although not the only reasonable one, as discussed in the conclusion.

4. We have assumed that a player’s preferences depend only on the evidence she provides but not on the evidence submitted by other players.  While this is obviously appropriate in many situations, there may be some applications where it is restrictive, i.e. where a player’s evidence submission may have a direct externality on other players. We leave such cases to future research.

5. Consider settings with separable preferences.  The framework allows for the possibility that two distinct states are identical in terms of all players’ preferences over outcomes.  In traditional implementation theory, it is common to equate states with profiles of preferences because, in the absence of evidence, it is impossible to implement different outcomes in two states that do not differ in players’ (outcome-)preferences.  We will see that this is no longer the case once evidence is available.  As emphasized by Ben-Porath and Lipman (2011), in many applications, such as contract and legal settings, a planner may wish to condition the outcome on the state even though players’ preferences over outcomes are entirely state-independent.

6. Each player’s feasible set of evidence, $E_i$, is assumed to be non-empty.  This is without loss of generality because we can always endow a player who has “no evidence” with some cheap-talk evidence, since the planner can require submission of a cheap-talk message.

7. It is also without loss of generality that each player must submit exactly one piece of evidence.  If one wants to allow a player to submit zero or no evidence, this just requires labeling a particular piece of evidence as “no evidence”.  If one wants to allow a player to submit multiple pieces of evidence, this just requires adding the appropriate conjunctions of underlying evidence.  On the other hand, in particular applications, it may be reasonable that submitting “no evidence” is either not allowed, or at least is not costless, and similarly that submitting multiple pieces of evidence imposes higher (possibly prohibitive) costs; we provide some examples later.

8. Our formulation of a mechanism is inherently static since we are considering the strategic-form game it induces in each state.  Given the focus on Nash equilibrium, our results would not change if we were to consider dynamic mechanisms. Furthermore, while our formulation only considers deterministic mechanisms, stochastic mechanisms can be encompassed by viewing $A$ as a lottery space.

9. Finally, we do not allow the planner to prohibit or forbid players from submitting some pieces of evidence.  This squares well with the view that a player’s choice of evidence is inalienable.  In any case, our results would not change even if a planner could forbid some evidence.

10. An important special case of our model is when any piece of evidence is either costless or prohibitively costly:

    Definition 2 (Hard Evidence).

    The setting is of hard evidence if preferences are separable and for all $i$, $\theta$, and $e_i$, either $c_i(e_i,\theta )=0$ or $c_i(e_i,\theta )>{sup}_a{u}_i(a,\theta )-{inf}_a{u}_i(a,\theta )$.

    In a setting with hard evidence, submitting any $e_i^{\prime }\in E_i^{\mathrm{\ell }}(\theta )$ strictly dominates submitting any $e_i\notin E_i^{\mathrm{\ell }}(\theta )$ for player $i$ at state $\theta$ because the latter’s cost strictly outweighs any possible utility gain from inducing a preferred outcome.  Thus, by submitting $e_i$ player $i$ effectively proves that the state is in the set $\{\theta :e_i\in E_i^{\mathrm{\ell }}(\theta )\}$.  This justifies why such a setting is one of hard evidence, also referred to sometimes as “certifiability”, “verifiability”, or “partial provability”. Note that the standard environment without evidence is in fact a special case of a hard-evidence setting, where for any $i$, $E_i^{\mathrm{\ell }}(\theta )=E_i$ for all $\theta$.

3. General Results

Maskin (1999) showed that in a setting without evidence—which can be represented in our framework as a setting where all evidence is cheap-talk evidence and preferences are separable—a SCF must satisfy a monotonicity condition with respect to players’ preferences over outcomes to be implementable.  We will refer to his condition as Maskin-monotonicity, which can be stated as follows whenever preferences in the current context are separable:

Definition 3 (Maskin-monotonicity).

Assume separable preferences.  A SCF is Maskin-monotonic provided that for all $\theta$ and ${\theta }^{\prime }$, if

$$\forall i,a:[u_i(f(\theta ),\theta )\ge u_i(a,\theta )⟹u_i(f(\theta ),{\theta }^{\prime })\ge u_i(a,{\theta }^{\prime })],$$ (1)

then $f(\theta )=f({\theta }^{\prime })$.

When evidence is available, Maskin-monotonicity is not necessary for implementation, as illustrated starkly in the following example.

Example 1.

Assume separable preferences and suppose $E_1=\mathrm{\Theta }$ with

$$c_1(\theta ,{\theta }^{\prime })=\{\begin{array}{c}0\text{ if }\theta ={\theta }^{\prime }\\ k\text{ if }\theta \ne {\theta }^{\prime },\end{array}$$

where $k>{sup}_{a,\theta }{u}_1(a,\theta )-{inf}_{a,\theta }{u}_1(a,\theta )$.  This can be interpreted as player one never being willing to misrepresent the state of the world.  Trivially then, no matter the agents’ preferences over outcomes, any SCF $f$ can be implemented by a mechanism with an arbitrary message space, $M$, and the outcome function $g(m,(e_1,\mathrm{\dots },e_n))=f(e_1)$.

The key to our analysis is identifying the appropriate notion of monotonicity in the present setting, which we call evidence-monotonicity.

Definition 4 (Evidence-monotonicity).

A SCF $f$ is evidence-monotonic if there exists $e^{\ast }:\mathrm{\Theta }\to E$ such that:

1. for all $\theta$, $e^{\ast }(\theta )\in E^{\mathrm{\ell }}(\theta ,f(\theta ))$; and

2. for all $\theta$ and ${\theta }^{\prime }$, if

   $$\forall i,a,e_i^{\prime }:\left[U_i(f(\theta ),e_i^{\ast }(\theta ),\theta )\ge U_i(a,e_i^{\prime },\theta )\Rightarrow U_i(f(\theta ),e_i^{\ast }(\theta ),{\theta }^{\prime })\ge U_i(a,e_i^{\prime },{\theta }^{\prime })\right],$$ (2)

   then $f(\theta )=f({\theta }^{\prime })$.

In words, a SCF is evidence-monotonic if there is a function $e^{\ast }$ that assigns a costless profile of evidence to each state such that if no player has a “preference reversal” with respect to the outcome and his component of $e^{\ast }$ when the state changes from $\theta$ to ${\theta }^{\prime }$, then $f(\theta )=f({\theta }^{\prime })$.  Intuitively, one should think of $e^{\ast }(\cdot )$ as the evidence profile that will be submitted to an implementing mechanism.  The existential quantifier on $e^{\ast }(\cdot )$ is unavoidable: it stems from the fact that the planner does not intrinsically care about which evidence profile is submitted.  We will show later that in a special but important class of problems, verifying the definition can be simplified.  Notice that the second part of Definition 4 bears a resemblance to how one would view Maskin-monotonicity on an extended outcome space, $A\times E$, if the planner could somehow choose evidence profiles in addition to choosing outcomes.  We will clarify the connection in Section 4.

In settings with separable preferences, evidence-monotonicity is a weaker requirement than Maskin-monotonicity, with the two concepts being equivalent when all evidence is cheap talk. Formally:

Proposition 1.

Assume separable preferences.  (1) Any Maskin-monotonic SCF is evidence-monotonic; (2) If all evidence is cheap-talk evidence, then any evidence-monotonic SCF is Maskin-monotonic.

Proof.

For the first statement, assume $f$ is Maskin-monotonic.  Let $e^{\ast }$ be any function such that for all $\theta$, $e^{\ast }(\theta )\in E^{\mathrm{\ell }}(\theta ,f(\theta ))$.  Fix any $\theta$ and ${\theta }^{\prime }$, and assume (2).  We must show that $f(\theta )=f({\theta }^{\prime })$.  Separability and (2) imply that for all $i,a,e_i^{\prime }$:

$$u_i(f(\theta ),\theta )\ge u_i(a,\theta )-(c_i(e_i^{\prime },\theta )-c_i(e_i^{\ast }(\theta ),\theta ))\Rightarrow u_i(f(\theta ),{\theta }^{\prime })\ge u_i(a,{\theta }^{\prime })-\left(c_i(e_i^{\prime },{\theta }^{\prime })-c_i(e_i^{\ast }(\theta ),{\theta }^{\prime })\right).$$

By taking $e_i^{\prime }=e_i^{\ast }(\theta )$ for all $i$ above and applying Maskin-monotonicity, it follows that $f(\theta )=f({\theta }^{\prime })$.  Thus, $f$ is evidence-monotonic.

For the second statement, notice that when all evidence is cheap-talk evidence and preferences are separable, Equation (2) reduces to (1). ∎

A striking observation is that even small evidentiary costs can create a substantial wedge between evidence-monotonicity and Maskin-monotonicity.  In particular, this arises when players have small preferences for honesty, as mentioned in the third motivating example of the introduction.  The following generalization of Example 1 demonstrates the point.

Example 2.

Consider a setting where players have a small preference for honesty when asked to report a direct message about the state.  Formally, assume separable preferences, and suppose that for each $i$, $E_i=\mathrm{\Theta }$ and the cost function is given by:

$$c_i(\theta ,{\theta }^{\prime })=\{\begin{array}{c}0\text{ if }\theta ={\theta }^{\prime }\\ \epsilon \text{ if }\theta \ne {\theta }^{\prime },\end{array}$$

where $\epsilon >0$ can be arbitrarily small.

This structure implies that for any $i$, $\theta$, and $a$, $E_i^{\mathrm{\ell }}(\theta ,a)=\{\theta \}$.  Hence, for any $a$ and $\theta$, $E^{\mathrm{\ell }}(\theta ,a)=\{(\theta ,\mathrm{\dots },\theta )\}$.  Let $e^{\ast }(\theta )=(\theta ,\mathrm{\dots },\theta )$ for all $\theta$.  Observe that for any $\theta$ and ${\theta }^{\prime }\ne \theta$, (2) is false: consider $a=f(\theta )$ and $e_i^{\prime }={\theta }^{\prime }$.  Thus, any SCF is evidence-monotonic.

In fact, it is not needed that all players have such a preference for honesty, only that in each state, there be some player who does (the identity of the player could vary with the state).

Our first main result is that only evidence-monotonic SCFs are implementable.

Theorem 1.

If $f$ is implementable then $f$ is evidence-monotonic.

Proof.

Assume $f$ is implementable and pick any mechanism $(M,g)$ that implements $f$.  For each $\theta$, there exists $(m(\theta ),e(\theta ))\in M\times E^{\mathrm{\ell }}(\theta ,f(\theta ))$ that is a Nash equilibrium at $\theta$ such that $g(m(\theta ),e(\theta ))=f(\theta )$.  For each $\theta$, set $e^{\ast }(\theta ):=e(\theta )$.  We will show that this choice verifies Definition 4.  Part (i) of the definition is obviously satisfied, so consider part (ii).  Pick any $\theta$ and ${\theta }^{\prime }$, and assume that (2) is satisfied.  Let $m$ be such that $(m,e^{\ast }(\theta ))\in NE(M,g,\theta )$, and fix any $i$.  By the optimality of $i$’s strategy,

$$U_i(f(\theta ),e_i^{\ast }(\theta ),\theta )\ge U_i(g(m_i^{\prime },e_i^{\prime },m_{-i},e_{-i}^{\ast }(\theta )),e_i^{\prime },\theta )$$

for any $(m_i^{\prime },e_i^{\prime })\in M_i\times E_i$.  By (2),

$$U_i(f(\theta ),e_i^{\ast }(\theta ),{\theta }^{\prime })\ge U_i(g(m_i^{\prime },e_i^{\prime },m_{-i},e_{-i}^{\ast }(\theta )),e_i^{\prime },{\theta }^{\prime })$$

for any $(m_i^{\prime },e_i^{\prime })\in M_i\times E_i$.

Consequently, $(m,e^{\ast }(\theta ))\in NE(M,g,{\theta }^{\prime })$.  Hence, $f(\theta )=g(m,e^{\ast }(\theta ))=f({\theta }^{\prime })$, as required. ∎

To illustrate how Theorem 1 has bite, we return to the second motivating example in the introduction about education signaling.

Example 3.

There are $n$ workers, each with an ability level measuring her marginal productivity.  The state of the world is a vector of abilities.  There is one job that must be allocated to a single worker along with a wage, so that $A=\{1,\mathrm{\dots },n\}\times {ℝ}_{+}$.  The SCF is $f(\theta )=(i^{\ast }(\theta ),{\theta }_{i^{\ast }(\theta )})$ where $i^{\ast }(\theta )=\max ({\arg \max }_i{\theta }_i)$, i.e. the goal is to allocate the job to the most-able worker and pay him his marginal product (ties in ability are broken in favor of workers with higher indices, which is convenient but inessential).  Suppose that workers can signal their ability through a choice $e_i$ of education, so that the evidence for $i$ is $e_i\in {ℝ}_{+}$.  Workers’ preferences are separable, and any worker $i$’s utility from an outcome $a=(a_1,a_2)$ is state-independent while his cost of education only depends on his own ability; hence, we can write $U_i(a,e_i,\theta )=u_i(a)-c_i(e_i,{\theta }_i)$.  Assume the cost of education satisfies two reasonable properties: for all $i$ and ${\theta }_i$, $c_i(e_i,{\theta }_i)=0$ if $e_i=0$; for all $i$, $c_i(e_i,{\theta }_i)$ is strictly increasing in $e_i$ and strictly decreasing in ${\theta }_i$.

Then for any $i$ and $\theta$, $E_i^{\mathrm{\ell }}(\theta )=\{0\}$, and it follows that the only candidate to verify evidence-monotonicity according to Definition 4 is $e^{\ast }(\theta )=(0,\mathrm{\dots },0)$.  It is easily checked that (2) is satisfied for any ${\theta }^{\prime }\le \theta$, in the sense of usual vector order. Since ${\theta }^{\prime }\le \theta$ does not imply $f({\theta }^{\prime })=f(\theta )$, $f$ is not evidence-monotonic, and by Theorem 1, not implementable.

While evidence-monotonicity is necessary for implementation, it is not sufficient.  Rather than pursuing an exhaustive characterization, we first tackle sufficiency in economic environments.

Definition 5 (Economic Environment).

The environment is economic if there is no state $\theta$, outcome $a$, and evidence profile $e$ such that $\left|\{i:(a,e_i)\in {\arg \max }_{b,e_i^{\prime }}{U}_i(b,e_i^{\prime },\theta )\}\right|\ge n-1.$

In other words, an environment is economic if in any state, given any outcome and evidence-profile pair $(a,e)$, there are at least two players for each of whom $(a,e_i)$ is not top-ranked. Various versions of such a domain restriction are used in the implementation literature. Definition 5 is identical to a condition in Bergemann and Morris (2008) that has the same name, so long as one views their condition on an extended outcome space $A\times E$; under separable preferences, it is equivalent to Bergemann and Morris’s (2008) condition viewed on the outcome space $A$ alone, because in this case our condition simplifies to requiring that for any $\theta$ and $a$,

To understand the scope of economic environments, focus on settings with three or more agents. An environment is economic if there is a divisible private good which is positively valued by all agents. In particular, the environment is economic if the planner can augment an underlying outcome space with arbitrarily small transfers, even with a requirement of budget balance (cf. Benoît and Ok, 2008; Ben-Porath and Lipman, 2011; Sanver, 2006).  Even without private goods or transfers, an environment will be economic so long as there is enough disagreement amongst agents about their most-preferred outcome in any state.

Theorem 2.

Assume $n\ge 3$ and an economic environment. If $f$ is evidence-monotonic, then $f$ is implementable.

The proof of Theorem 2 is by construction of a canonical mechanism that is familiar from existing mechanisms in the literature, but modified appropriately to deal with evidence.

Proof.

Since $f$ is evidence-monotonic, let $e^{\ast }$ be the function that verifies Definition 4.  For all $i$, set $M_i=\mathrm{\Theta }\times A\times \mathbb{N}$.  Define $g(m,e)$ according to the following rules:

1. If $m_1=\mathrm{\cdots }=m_n=(\theta ,f(\theta ),k)$ and $e=e^{\ast }(\theta )$, then $g(m,e)=f(\theta )$.

2. If $\exists i$ s.t. (i) for all $j\ne i$, $m_j=(\theta ,f(\theta ),k)$ and $e_j=e_j^{\ast }(\theta )$, and (ii) either $m_i=(\tilde{\theta },a,l)\ne (\theta ,f(\theta ),k)$ or $e_i\ne e_i^{\ast }(\theta )$, then

   (a) if $U_i(f(\theta ),e_i^{\ast }(\theta ),\theta )\ge U_i(a,e_i,\theta )$, then $g(m,e)=a;$

   (b) if , then $g(m,e)=f(\theta )$.

3. For any other $(m,e)$, letting $m_i=({\theta }_i,a_i,k_i)$ and $i^{\ast }=\min {\arg \max }_{i\in I}{k}_i$, $g(m,e)=a_{i^{\ast }}$.

Step 1.  It is routine to verify that for any $\theta$, there is a “truthful” NE where for some $k\in \mathbb{N}$, each agent $i$ plays $m_i=(\theta ,f(\theta ),k)$ and $e_i=e_i^{\ast }(\theta )$.  This NE results in outcome $f(\theta )$ and, moreover, $e$clearly belongs to $E^{\mathrm{\ell }}(\theta ,f(\theta ))$.

For the remainder of the proof, assume the true state is ${\theta }^{\prime }$ and $(m,e)$ is a NE.

Step 2.  We show that $(m,e)$ cannot fall into Rule (2).  Suppose, to contradiction, that $(m,e)$ is such an equilibrium.  Then it must be that for all $j\ne i$ (where $i$ is defined in Rule (2)), $(g(m,e),e_j)\in {\arg \max }_{b,e_j^{\prime }}{U}_j(b,e_j^{\prime },{\theta }^{\prime })$: otherwise one of these $n-1$ players, say $j^{\ast }$, can profitably deviate into Rule (3) submitting some $e_{j^{\ast }}^{\prime }$ and requesting and receiving some $b$ s.t. $U_{j^{\ast }}(b,e_{j^{\ast }}^{\prime },{\theta }^{\prime })>U_{j^{\ast }}(g(m,e),e_{j^{\ast }},{\theta }^{\prime })$.  But this contradicts the environment being economic.  A similar argument applies to show that no equilibrium $(m,e)$ can fall into Rule (3).

Step 3.  It remains to consider the case where $(m,e)$ falls into Rule (1), so that $e=e^{\ast }(\theta )$ for some $\theta$.  Here, $g(m,e)=f(\theta )$.  Condition (2) must hold since a player $i$ can always deviate into rule (2a) by producing evidence $e_i^{\prime }$ and get any outcome $a$ such that $U_i(f(\theta ),e_i^{\ast }(\theta ),\theta )\ge U_i(a,e_i^{\prime },\theta )$.  Thus, evidence-monotonicity implies that $f(\theta )=f({\theta }^{\prime })$. Finally, since any player can deviate to Rule (2a) and get the same outcome $f({\theta }^{\prime })$ while submitting some evidence in $E_i^{\mathrm{\ell }}({\theta }^{\prime },f({\theta }^{\prime }))$, the hypothesis that $(m,e)$ is a Nash equilibrium implies that $e\in E^{\mathrm{\ell }}({\theta }^{\prime },f({\theta }^{\prime }))$. ∎

Remark 1.

The mechanism used in the proof of Theorem 2 does not work when mixed Nash equilibria are considered.  Arguments analogous to those that deal with mixed strategies in standard settings without evidence (e.g. Kartik and Tercieux, 2009; Maskin and Sjöström, 2002, Section 4.3) can be adapted to extend Theorem 2 to mixed Nash equilibria.

Remark 2.

Theorem 2 concerns three or more agents. When there are only two agents, the economic environment condition is rather stringent. For $n=2$, evidence-monotonicity can be shown to be sufficient for implementation under a less demanding version of economic environments in conjunction with Moore and Repullo’s (1990) bad outcome condition.

To illustrate how Theorem 2 is useful, we apply it to a setting where players have (possibly-small) preferences for honesty:

Corollary 1.

Assume $n\ge 3$ and that the environment is economic. If in each state, at least one player has a preference for honesty as formalized in Example 2, then any SCF is implementable.

Proof.

As shown in Example 2, any SCF is evidence-monotonic when at least one player has a preference for honesty.  Thus, the Corollary is a direct implication of Theorem 2. ∎

There is a growing literature on implementation when players have preferences for honesty.  Matsushima (2008a, b) was the first to investigate such a question and obtain permissive results in related but not identical settings.  More similar to Corollary 1 is a contemporaneous finding of Dutta and Sen (2011).  Because their paper is entirely about implementation with preferences for honesty, their main result is slightly stronger than Corollary 1 and their proof uses a remarkably simple implementing mechanism.   Our approach has the benefit of identifying that the fundamental reason why a preference for honesty produces permissive results is that it renders any SCF evidence-monotonic.

We now discuss the role of the economic environment assumption in Theorem 2. In an economic environment, any SCF trivially satisfies the following version of Maskin’s (1999) no veto power condition:

Definition 6 (No Veto Power).

A SCF $f$ satisfies no veto power provided that for all $\theta$,

$$\text{if }(a,e)\text{ is such that }\left|\{i:(a,e_i)\in \underset{a^{\prime },e_i^{\prime }}{\arg \max }{U}_i(a^{\prime },e_i^{\prime },\theta )\}\right|\ge n-1\text{, then }a=f(\theta ).$$ (3)

In other words, if at any state, there is some outcome and evidence-profile pair that is top-ranked by at least $n-1$ players, then the outcome must be chosen by the SCF at that state.  Plainly, when preferences are separable — a fortiori, when all evidence is cheap-talk evidence — the above definition reduces to the standard no veto power condition. In a setting without evidence, Maskin (1999) showed that no veto power is sufficient to ensure that Maskin-monotonic SCFs are implementable, given $n\ge 3$. This might suggest that Theorem 2 could be strengthened by only assuming no veto power rather than an economic environment. The following counter-example proves otherwise.

Example 4.

Suppose $n=3$, $\mathrm{\Theta }=\{X,Y\}$, and $A=\{b,c,d_1,d_2,d_3\}$.   Only player 1 has non-cheap-talk evidence, so we ignore player 2’s and 3’s evidence.  Let $E_1=E=\{x,y\}$.  All players have separable preferences.  Using the standard notation of $\succ$ for strict preference, player 3’s preferences over outcomes are given by:

$X$ : $b\prec c\prec d_1\prec d_2\prec d_3$

$Y$ : $c\succ b\succ d_1\succ d_2\succ d_3$

Player 2’s preferences over outcomes are given by:

$X$ : $b\prec c\prec d_1\prec d_3\prec d_2$

$Y$ : $c\succ b\succ d_1\succ d_3\succ d_2$

Player 1’s preferences over outcome-evidence pairs are given by:

$X$ : $b,y\prec c,y\prec b,x\prec c,x\prec d_3,y\prec d_3,x\prec d_2,y\prec d_2,x\prec d_1,y\prec d_1,x$

$Y$ : $c,x\succ c,y\succ b,x\succ b,y\succ d_3,x\succ d_3,y\succ d_2,x\succ d_2,y\succ d_1,x\succ d_1,y$

It can be checked that player 1’s preferences are separable with $E_1^{\mathrm{\ell }}(X)=E_1^{\mathrm{\ell }}(Y)=\{x\}$. The important point to note is that in state $X$, the cost for player 1 of producing evidence $y$ outweighs her preference for outcome $c$ over $b$, whereas in state $Y$, the outcome-preference for $c$ over $b$ outweighs the cost of producing evidence $y$.

Consider the SCF $f$ where $f(X)=b$ and $f(Y)=c$. The following observations hold:

1. No veto power is satisfied because in state $X$ there is no outcome that is most-preferred by any two players, whereas in state $Y$, all players unanimously prefer outcome $c$ over any other and $f(Y)=c$. The latter point shows that the environment is not economic.

2. $f$ is evidence-monotonic; this can be verified by using $e_1^{\ast }(X)=e_1^{\ast }(Y)=x$ in Definition 4.

3. $f$ is not implementable. Suppose, to contradiction, that it is by a mechanism $(M,g)$. Then there is a message profile $m$ such that $g(m,x)=b$ and $(m,x)$ is a Nash equilibrium at $X$. Since $b$ is bottom-ranked by players 2 and 3 at state $X$, any unilateral deviation by either player 2 or 3 must not change the outcome. Moreover, if player 1 deviates by sending some cheap-talk message together with evidence $x$, this cannot induce outcome $c$; otherwise, this would constitute a profitable deviation for him at state $X$. Since $f(Y)=c$, $(m,x)$ cannot be a Nash equilibrium at $Y$, hence player 1 must have a unilateral deviation from $(m,x)$ by submitting evidence $y$ with some cheap-talk message to induce outcome $c$; let the resulting message profile and evidence be $(m^{\prime },y)$. But then $(m^{\prime },y)$ is a Nash equilibrium at state $Y$, because outcome $c$ is top-ranked by players 2 and 3, and no unilateral deviation of player 1 can induce $(c,x)$. Since $y\notin E_1^{\mathrm{\ell }}(Y)$, we contradict the assumption that $f$ is implemented by $(M,g)$.

Therefore, in a general evidentiary setting, evidence-monotonicity, no veto power, and $n\ge 3$ do not guarantee that a SCF is implementable (even if one assumes separable preferences). However, these conditions are sufficient in settings of hard evidence:

Theorem 3.

Assume $n\ge 3$ and a setting of hard evidence.  If $f$ is evidence-monotonic and satisfies no veto power, then $f$ is implementable.

Proof.

Consider the proof of Theorem 2 and the mechanism constructed therein. The economic environment condition was only used in Step 2 of the argument; so it suffices here to deal with equilibria that fall into Rule (2) or Rule (3) of the mechanism. Suppose the true state is ${\theta }^{\prime }$ and there is an equilibrium $(m,e)$ that falls into Rule (2) of the mechanism. It must be that for all $j\ne i$ (where $i$ is defined in Rule (2)), $(g(m,e),e_j)\in {\arg \max }_{b,e_j^{\prime }}{U}_j(b,e_j^{\prime },{\theta }^{\prime })$: otherwise one of these $n-1$ players, say $j^{\ast }$, can profitably deviate into Rule (3) submitting some $e_{j^{\ast }}^{\prime }$ and requesting and receiving some $b$ s.t. $U_{j^{\ast }}(b,e_{j^{\ast }}^{\prime },{\theta }^{\prime })>U_{j^{\ast }}(g(m,e),e_{j^{\ast }},{\theta }^{\prime })$.  No veto power now implies $g(m,e)=f({\theta }^{\prime })$. Moreover, for every player $k$, we must have $e_k\in E_k^{\mathrm{\ell }}({\theta }^{\prime })$, since in a hard evidence setting it is strictly dominated for $k$ to submit any $e_k\notin E_k^{\mathrm{\ell }}({\theta }^{\prime })$. Therefore $g(m,e)=f({\theta }^{\prime })$ and $e\in E^{\mathrm{\ell }}({\theta }^{\prime })$, as required. A similar argument applies if $(m,e)$ falls into Rule (3). ∎

Beyond its intrinsic interest, Theorem 3 also serves as a strict generalization of Maskin’s (1999) classic sufficiency result, because the traditional environment without evidence is a special case of a hard-evidence setting where for any $i$, $E_i^{\mathrm{\ell }}(\theta )=E_i$ for all $\theta$.

4. Inalienable and Alienable Evidence

As already noted, an important feature of the current implementation exercise is that evidence is inalienable, i.e. a player’s evidentiary choice is his private domain.  It is of interest to understand how constrained the planner is by evidence inalienability.  To this end, consider a hypothetical problem where the planner can in fact choose the profile of evidence along with the outcome, i.e. evidence becomes alienable.  Formally, define an extended outcome space, $\widehat{A}:=A\times E$, and say that a correspondence $\widehat{f}:\mathrm{\Theta }\rightrightarrows \widehat{A}$ is an extension of a SCF $f:\mathrm{\Theta }\to A$ if there exists a correspondence $\widehat{e}:\mathrm{\Theta }\rightrightarrows E$ such that $\widehat{f}=(f,\widehat{e})$, by which we mean that for all $\theta$, $\widehat{f}(\theta )=\{(a,e):a=f(\theta ),e\in \widehat{e}(\theta )\}$.  The reason to consider extensions of $f$ that are correspondences even though $f$ is a function will be clarified shortly.  Say that $\widehat{f}$ is a costless extension of $f$ if $\widehat{f}=(f,\widehat{e})$ for some correspondence $\widehat{e}$ such that for all $\theta$, $\widehat{e}(\theta )\subseteq E^{\mathrm{\ell }}(\theta ,f(\theta ))$.

If evidence were alienable, then the planner would face a standard implementation problem on the extended outcome space, hence Maskin-monotonicity of an extended social choice rule would be a necessary and almost-sufficient condition for its implementation. Theorems 1 and 2 have established that with inalienable evidence, evidence-monotonicity is necessary and, under some other conditions, also sufficient for implementation. We now derive a close relationship between evidence-monotonicity in the underlying problem and Maskin-monotonicity on the extended outcome space.

Theorem 4.

A SCF is evidence-monotonic if and only if it has a costless extension that is Maskin-monotonic on the extended outcome space.

Proof.

See Appendix. ∎

The equivalence in Theorem 4 requires allowing costless extensions to be correspondences; specifically, the “only if” direction would fail if one restricts attention to costless extensions that are single valued. Theorem 4 provides the foundation for a “bridge” between our implementation problem with inalienable evidence and a hypothetical implementation problem with alienable evidence. In particular:

Corollary 2.

Assume $n\ge 3$ and an economic environment. Then any SCF $f$ is implementable (with inalienable evidence) if and only if a costless extension of $f$ is implementable with alienable evidence on the extended outcome space.

Proof.

Assume $n\ge 3$ and an economic environment. By Theorems 1 and 2, a SCF $f$ is implementable if and only if it is evidence-monotonic. On the other hand, any extension of $f$ trivially satisfies standard no veto power on the extended outcome space, hence is implementable with alienable evidence if and only if it is Maskin-monotonic on the extended outcome space. The conclusion now follows from Theorem 4. ∎

For economic environments with at least three agents, we therefore have an equivalence between implementation with inalienable evidence and implementation with alienable evidence. The “only if” direction of Corollary 2 is intuitive, as inalienability can only make implementation harder than if evidence were alienable. Indeed, this direction of the equivalence does not depend on having $n\ge 3$ or an economic environment, because of the following logic: suppose $(M,g)$ is a mechanism that implements $f$. Define $\widehat{M}$ by ${\widehat{M}}_i=M_i\times E_i$ for all $i$ and $\widehat{g}:\widehat{M}\to \widehat{A}$ by $\widehat{g}(m,e)=(g(m,e),e)$ for all $(m,e)$. Then, on the extended outcome space, $(\widehat{M},\widehat{g})$ achieves standard implementation of the costless extension of $f$ given by $\widehat{f}=(f,\widehat{e})$, where for all $\theta$, $\widehat{e}(\theta ):=\{e\in E:\exists m\text{ s.t. }(m,e)\in NE(M,g,\theta )\}$.

On the other hand, the “if” direction of Corollary 2 is quite surprising because it implies that given $n\ge 3$ and an economic environment, making evidence alienable would be of no benefit to the planner. To understand why, assume $f$ has a costless extension $\widehat{f}=(f,\widehat{e})$ where $\widehat{e}(\cdot )$ is single valued. Consider the canonical mechanism presented in Maskin (1999) that would be used to implement $\widehat{f}$ on the extended outcome space, assuming $n\ge 3$ and that $\widehat{f}$ satisfies standard no veto power on the extended outcome space (which is ensured by an economic environment). This mechanism gives each agent $i$ a cheap-talk message space ${\widehat{M}}_i:=\mathrm{\Theta }\times A\times E\times \mathbb{N}$ and has an outcome function $\widehat{g}:{\widehat{M}}_1\times \mathrm{\cdots }\times {\widehat{M}}_n\to A\times E$. The key observation is that because agents’ preferences do not depend on other agents’ evidence, it is possible to reduce the message space for each agent $i$ to ${\widehat{M}}_i^{\prime }:=\mathrm{\Theta }\times A\times E_i\times \mathbb{N}$ and use an outcome function ${\widehat{g}}^{\prime }:{\widehat{M}}_1^{\prime }\times \mathrm{\cdots }\times {\widehat{M}}_n^{\prime }\to A\times E$ which is consistent with $\widehat{g}$ except that in Rules 2 and 3, when “rewarding” a deviator $i$, ${\widehat{g}}^{\prime }$ chooses for any $j\ne i$ the evidence that he has announced, and similarly when not rewarding a deviator in Rule 2, ${\widehat{g}}^{\prime }$ can choose for him the evidence he has announced. This modified mechanism always chooses an evidence for each agent that he has announced, hence even if evidence were inalienable, every equilibrium at any state $\theta$ would result in an outcome $f(\theta )$ and some costless evidence profile, i.e. we have achieved implementation with inalienable evidence. Indeed, given that $\widehat{e}(\cdot )$ is single valued by hypothesis here, this is precisely the mechanism used in proving Theorem 2.

Corollary 2 provides additional insight as to why the economic environment condition in Theorem 2 cannot be weakened to the SCF satisfying no veto power. By Corollary 2, what is sufficient to implement a SCF $f$ that is evidence-monotonic (given $n\ge 3$) is the existence of a costless extension that satisfies standard no veto power on the extended outcome space. This is a more demanding requirement than $f$ satisfying no veto power. It is this gap that drives Example 4: the SCF $f$ defined there has a unique costless extension, $\widehat{f}$ given by $\widehat{f}(X)=(b,x)$ and $\widehat{f}(Y)=(c,x)$.  While $f$ satisfies no veto power, $\widehat{f}$ does not satisfy standard no veto power on the extended outcome space because in state $Y$, $(c,y)$ is top-ranked by players 2 and 3 but involves costly evidence for player 1. Such a gap is not special; rather, it is to be expected in non-economic environments, even when preferences are separable.

The following example shows that the equivalence identified in Corollary 2 fails without the assumption of an economic environment.

Example 5.

$\mathrm{\Theta }=\{{\theta }_1,{\theta }_2\}$ and $n=3$, but only player 1 has non-cheap-talk evidence, so we ignore the evidence of players 2 and 3. Evidence is hard evidence with $E_1=\{x,y_1,y_2\}$, $E_1^{\mathrm{\ell }}({\theta }_1)=\{x,y_1\}$ and $E_1^{\mathrm{\ell }}({\theta }_2)=\{x,y_2\}$. $A=\{a_1,a_2\}$ and all players have identical preferences over outcomes such that they both strictly prefer $a_1$ to $a_2$ in state ${\theta }_1$ while they both strictly prefer $a_2$ to $a_1$ in state ${\theta }_2$. The SCF $f$ is given by $f({\theta }_1)=a_2$ and $f({\theta }_2)=a_1$.

It is straightforward that $f$ cannot be implemented: given any mechanism $(M,g)$, pick any message profile $m$. We must have $g(m,x)\in \{a_1,a_2\}$. If $g(m,x)=a_1$, then $(m,x)$ would be an undesirable Nash equilibrium at state ${\theta }_1$; if $g(m,x)=a_2$, then $(m,x)$ would be an undesirable Nash equilibrium at state ${\theta }_2$.

On the other hand, consider the costless extension of $f$, $\widehat{f}$ defined by $\widehat{f}({\theta }_1)=(a_2,y_1)$ and $\widehat{f}({\theta }_2)=(a_1,y_2)$. On the extended outcome space, $\widehat{f}$ can be implemented by just asking player 1 to send a cheap-talk direct message about the state and choosing $(a_2,y_1)$ if he reports ${\theta }_1$ while choosing $(a_1,y_2)$ if he reports ${\theta }_2$. Notice that $\widehat{f}$ does not satisfy standard no veto power on the extended outcome space; indeed, there is no costless extension of $f$ that does.

5. Hard Evidence

In a variety of contexts, many models assume that players can partially prove the state of the world by providing evidence. We now study how our general results yield particular insights for implementation in such environments.  We assume throughout this section that the setting is one of hard evidence as formalized in Definition 2: each player $i$’s preferences are separable and represented by $u_i(a,\theta )-c_i(e_i,\theta )$, and in any state of the world, $\theta$, any piece of evidence, $e_i$, has a zero cost for player $i$ (i.e., $c_i(e_i,\theta )=0$) or a sufficiently large cost (i.e. $c_i(e_i,\theta )>{sup}_a{u}_i(a,\theta )-{inf}_a{u}_i(a,\theta )$).  Plainly, player $i$ will never submit evidence that is not costless at the true state, and thus evidence $e_i$ is proof of the event $\{\theta :e_i\in E_i^{\mathrm{\ell }}(\theta )\}$. Without loss, we will say that the set of evidence a player $i$ has at state $\theta$ is $E_i^{\mathrm{\ell }}(\theta )$ — just his costless evidence — and the entire evidence structure is given by ${\left\{E_i^{\mathrm{\ell }}(\theta )\right\}}_{i,\theta }$. In addition, when referring to a player’s preferences in this section, we shall always mean outcome-preferences, since together with the evidence structure this contains all relevant information about preferences over the joint space of outcomes and evidence.

5.1. A Characterization of Evidence-Monotonicity

We begin by providing an alternative characterization of evidence-monotonicity for hard evidence. This characterization is useful because it (partially) disentangles the role of hard evidence from that of preferences over outcomes in satisfying evidence-monotonicity.

Proposition 2.

In a hard-evidence setting, a SCF is evidence-monotonic if and only if there exists $e^{\ast }:\mathrm{\Theta }\to E$ such that:

1. for all $\theta$, $e^{\ast }(\theta )\in E^{\mathrm{\ell }}(\theta )$; and

2. for all $\theta$ and ${\theta }^{\prime }$, if

   $$\forall i,a:[u_i(f(\theta ),\theta )\ge u_i(a,\theta )⟹u_i(f(\theta ),{\theta }^{\prime })\ge u_i(a,{\theta }^{\prime })]$$ (*)

   and

   $$(e^{\ast }(\theta )\in E^{\mathrm{\ell }}({\theta }^{\prime }))\text{ and }(\forall i:E_i^{\mathrm{\ell }}({\theta }^{\prime })\subseteq E_i^{\mathrm{\ell }}(\theta )\text{ or }f(\theta )\in \underset{a}{\arg \max }{u}_i(a,{\theta }^{\prime })),$$ (**)

   then $f\left(\theta \right)=f\left({\theta }^{\prime }\right)$.

Proof.

See Appendix. ∎

Compared to the definition of evidence-monotonicity, the difference in the characterization above is that (2) has been substituted by the conjunction of (*) and (**). Notice that (*) is the usual condition in Maskin-monotonicity which refers only to preferences over outcomes. This makes transparent that evidence-monotonicity in a hard-evidence setting is a generalization of Maskin-monotonicity: without (**), it would reduce to Maskin-monotonicity, whereas the presence of (**) makes it a weaker requirement.

Proposition 2 says that for a SCF $f$ to be evidence-monotonic, one must find a function $e^{\ast }(\cdot )$ such that condition (**) is falsified for every ordered pair of states $(\theta ,{\theta }^{\prime })$ over which $f$ violates Maskin-monotonicity (i.e. for which $f(\theta )\ne f({\theta }^{\prime })$ but (*) is satisfied).  Plainly, this is not possible unless some player’s evidence set varies across such a pair of states.  Fix some $e^{\ast }(\cdot )$ and a pair of states $\theta$ and ${\theta }^{\prime }$ such that $f(\theta )\ne f({\theta }^{\prime })$.  If $f(\theta )$ does not go down in any agent’s preference ordering when the state changes from $\theta$ to ${\theta }^{\prime }$ (i.e., condition (*) is satisfied), then we know from Maskin (1999) that to implement $f$, a mechanism has to exploit evidence.  Condition (**) says that for this to be possible, either: (i) the evidence profile being submitted at $\theta$, $e^{\ast }(\theta )$, is not available at ${\theta }^{\prime }$ (negating the first part of (**)), or (ii) some player must have evidence at ${\theta }^{\prime }$ that is not available at $\theta$, and outcome $f(\theta )$ should not be this player’s most-preferred outcome at ${\theta }^{\prime }$ (together, negating the second part of (**)).  The latter preference requirement is essential because otherwise a player cannot be given incentives to disprove $\theta$ when the true state is ${\theta }^{\prime }$ and she has the ability to submit evidence supporting $\theta$; this is why the requirement only enters in the second part of (**) and not the first part.

The existential quantifier over $e^{\ast }(\cdot )$ in Proposition 2 raises the possibility that it may be tedious to verify whether a given SCF is evidence-monotonic.  Subsequently, we show how the task can be simplified in particular domains.  For now, let us note that, loosely speaking, one should choose $e^{\ast }(\theta )$ to be an evidence profile that is “most informative” about state $\theta$ with respect to the other states that cause a problem for Maskin-monotonicity.  In particular, if there is an evidence profile in state $\theta$ that proves more about the state than any other evidence profile available at $\theta$, then one can take $e^{\ast }(\theta )$ to be this evidence profile.  The idea can be illustrated by returning to the first motivating example of the introduction, as follows.

Example 6.

A principal is concerned with dividing a fixed sum of money, say $M>0$, to agents as some function of their individual production.  The outcome space is $A=\{(a_1,\mathrm{\dots },a_n)\in {ℝ}_{+}^n:{\sum }_i{a}_i\le M\}$.  A state $\theta$ is a vector of units of output, i.e. $\theta =({\theta }_1,\mathrm{\dots },{\theta }_n)\in \mathrm{\Theta }={ℝ}_{+}^n$.  Each agent can show his true output or some subset of it, hence an agent is unable to claim that his output is larger than it in fact is, but she can claim that it is less.  Formally, $E_i=\mathrm{\Theta }$ and $E_i^{\mathrm{\ell }}(\theta )=[0,{\theta }_i]$ for all $i,\theta$.  Assume that $u_i((a_1,\mathrm{\dots },a_n),\theta )$ is strictly increasing in $a_i$.

For any SCF $f$, write $f(\theta )=:(f_1(\theta ),\mathrm{\dots },f_n(\theta ))$.  It follows that any SCF $f$ that satisfies is evidence-monotonic.  To see this, fix any such $f$.  For any $\theta$, let $e^{\ast }(\theta )=\theta$.  It suffices to argue that for any ${\theta }^{\prime }\ne \theta$, condition (**) is violated.  If ${\theta }^{\prime }\ne \theta$, there exists an agent $i$ such that ${\theta }_i^{\prime }\ne {\theta }_i$.  First, if then $e_i^{\ast }(\theta )={\theta }_i\notin [0,{\theta }_i^{\prime }]=E_i^{\mathrm{\ell }}({\theta }^{\prime })$ and so the first part of (**) is violated.  Second, if ${\theta }_i^{\prime }>{\theta }_i$ then ${\theta }_i^{\prime }\in E_i^{\mathrm{\ell }}({\theta }^{\prime })$ but ${\theta }_i^{\prime }\notin [0,{\theta }_i]=E_i^{\mathrm{\ell }}(\theta )$, hence $E_i^{\mathrm{\ell }}({\theta }^{\prime })⊈E_i^{\mathrm{\ell }}(\theta )$.  Moreover, $f(\theta )\notin {\arg \max }_a{u}_i(a,{\theta }^{\prime })$ because .  Therefore, the second part of (**) is violated.

The next example illustrates how the characterization in Proposition 2 can be applied and also provides more insight into the different elements of condition (**).

Example 7.

Let $n=4$, $\mathrm{\Theta }=\{{\theta }_1,{\theta }_2,{\theta }_3,{\theta }_4\}$, and $A=\{w,x,y,z\}$. Player 1’s evidence structure is given by: $E_1^{\mathrm{\ell }}({\theta }_1)=\{\alpha ,\beta \},E_1^{\mathrm{\ell }}({\theta }_2)=\{\alpha ,\beta \},E_1^{\mathrm{\ell }}({\theta }_3)=\left\{\alpha \right\},$ and $E_1^{\mathrm{\ell }}({\theta }_4)=\left\{\alpha \right\}$. All other players have no evidence (i.e. for $i>1$, $E_i^{\mathrm{\ell }}(\theta )$ is constant across $\theta$), so with some abuse of notation we ignore their evidence below.  The (ordinal) preferences of players 1 and 2 are given in the left table below, while those of players 3 and 4 are given in the right table:

${\theta }_1$ ${\theta }_2$ ${\theta }_3$ ${\theta }_4$

w w w w

x y x x

y x y y

z z z z

                                

${\theta }_1$ ${\theta }_2$ ${\theta }_3$ ${\theta }_4$

z z z z

x y x x

y x y y

w w w w

So, for example, $u_1(w,{\theta }_1)>u_1(x,{\theta }_1)>u_1(y,{\theta }_1)>u_1(z,{\theta }_1)$.

1. Consider the SCF $f$ where $f\left({\theta }_1\right)=f\left({\theta }_4\right)=x$ and $f\left({\theta }_2\right)=f\left({\theta }_3\right)=y$.  Since $E^{\mathrm{\ell }}({\theta }_3)=E^{\mathrm{\ell }}({\theta }_4)=\{\alpha \}$, any $e^{\ast }(\cdot )$ verifying evidence-monotonicity satisfies $e^{\ast }({\theta }_3)=e^{\ast }({\theta }_4)=\alpha$.  Since no player’s preferences change between states ${\theta }_3$ and ${\theta }_4$, both (*) and (**) are satisfied for $\theta ={\theta }_3$ and ${\theta }^{\prime }={\theta }_4$.  Hence $f$ is not evidence-monotonic, and by Theorem 1, not implementable.

2. Next consider the SCF $f^{\ast }$ where $f^{\ast }\left({\theta }_1\right)=x$ and $f^{\ast }\left({\theta }_2\right)=f^{\ast }\left({\theta }_3\right)=f^{\ast }\left({\theta }_4\right)=y$.  Even though $f^{\ast }$ is not Maskin-monotonic (because $f^{\ast }\left({\theta }_1\right)\ne f^{\ast }\left({\theta }_3\right)$ while preferences don’t change between states ${\theta }_1$ and ${\theta }_3$), one can check that $f^{\ast }$ is evidence-monotonic by using $e^{\ast }({\theta }_1)=e^{\ast }({\theta }_2)=\beta$ and $e^{\ast }({\theta }_3)=e^{\ast }({\theta }_4)=\alpha$ in Proposition 2 .    Note that $f^{\ast }({\theta }_1)=x$ is not top-ranked for any agent in state ${\theta }_3$ and $f({\theta }_3)=y$ is not top-ranked for any agent in state ${\theta }_1$; this is essential to the violation of (**) for $\theta ={\theta }_3$ and ${\theta }^{\prime }={\theta }_1$.  Furthermore, $f^{\ast }$ satisfies no veto power because no alternative is top-ranked in any state by more than two players.  Since $f^{\ast }$ is evidence-monotonic, it is implementable by Theorem 3.

3. Finally, consider the SCF $\tilde{f}$ where $\tilde{f}({\theta }_1)=x$ and $\tilde{f}({\theta }_2)=\tilde{f}({\theta }_3)=\tilde{f}({\theta }_4)=w$.  Consider $\theta ={\theta }_3$ and ${\theta }^{\prime }={\theta }_1$.  Since no player’s preferences change between ${\theta }_1$ and ${\theta }_3$, (*) is satisfied.  Since we must have $e^{\ast }({\theta }_3)=\alpha$, hence $e^{\ast }({\theta }_3)\in E^{\mathrm{\ell }}({\theta }_1)$, the first part of (**) is also satisfied.  The second part of (**) is trivially satisfied for all $i>1$ (they have no evidence); it is also satisfied for player 1 because $w$ is top-ranked for him in all states.  Thus, (**) is satisfied and $\tilde{f}$ is not evidence-monotonic, hence not implementable.  The problem here is that even though $E_1^{\mathrm{\ell }}({\theta }_3)⊊E_1^{\mathrm{\ell }}({\theta }_1)$, it is not possible to reward player $1$ in state ${\theta }_1$ for disproving ${\theta }_3$, because $\tilde{f}({\theta }_3)=w$ is 1’s most preferred outcome in state ${\theta }_1$.

5.2. Evidence-monotonicity and Distinguishability

Proposition 2 makes no assumption on preferences, the SCF, or the evidence structure (beyond a hard evidence setting).  We now discuss how the characterization can be considerably simplified.  The key is to completely disentangle properties of the evidence structure from properties of outcome-preferences in verifying evidence-monotonicity.  In general, condition (**) shows that these are inextricably linked, so some domain restriction is needed for this approach.  The following condition of non-satiation will prove useful.

Definition 7 (Non-satiation).

A SCF $f$ satisfies non-satiation if for all $i$, $\theta$, and $a\in \bigcup _{{\theta }^{\prime }}f({\theta }^{\prime })$, there exists $\tilde{a}$ such that $u_i(\tilde{a},\theta )>u_i(a,\theta )$.

Intuitively, if a SCF satisfies non-satiation, it is always possible to reward players.  For example, non-satiation is satisfied if there is a divisible private good that is positively valued by players and the SCF never allocates all of the private good to any player.  The important implication is that if $f$ satisfies non-satiation, the preference requirement in condition (**) can be ignored because the requirement is satisfied independent of the evidence structure.  Hence, under non-satiation, Proposition 2 holds if we replace (**) with the following weaker condition that depends only on the evidence structure:

$$e^{\ast }(\theta )\in E^{\mathrm{\ell }}({\theta }^{\prime })\text{ and }{E}^{\mathrm{\ell }}({\theta }^{\prime })\subseteq E^{\mathrm{\ell }}(\theta ),$$ (***)

Plainly, non-satiation is essential for this reduction. This can be seen by returning to the SCF $\tilde{f}$ in Example 7.  Condition (***) is falsified for ${\theta }^{\prime }={\theta }_1$ and $\theta ={\theta }_3$ because $E^{\mathrm{\ell }}({\theta }_1)⊈E^{\mathrm{\ell }}({\theta }_3)$.  But, as argued in the example, $\tilde{f}$ is not evidence-monotonic and thus not implementable: $\tilde{f}$ does not satisfy non-satiation.

Since non-satiation allows us to completely separate the roles of preferences and evidence structure in evidence-monotonicity (respectively captured by (*) and (***)), the remainder of this section derives a number of simplifications and implications of evidence-monotonicity within the domain of SCFs satisfying non-satiation.

A central question is what hard-evidence structures permit non-Maskin-monotonic SCFs to be implemented.  We will provide a sharp answer by introducing a notion of distinguishability. Recall that an ordered pair of states $(\theta ,{\theta }^{\prime })$ violates Maskin-monotonicity if $f(\theta )\ne f({\theta }^{\prime })$ but (*) is satisfied. For any $\theta$, define

$$T^f\left(\theta \right):=\{{\theta }^{\prime }\in \mathrm{\Theta }:(\theta ,{\theta }^{\prime })\text{ violates Maskin-monotonicity}\}\text{.}$$

In other words, given that the planner wishes to implement the outcome $f(\theta )$ in state $\theta$, $T^f\left(\theta \right)$ is the set of states that causes a problem for implementation of $f$ in the absence of evidence.  In particular, $f$ is implementable without evidence only if ${\bigcup }_{\theta \in \mathrm{\Theta }}{T}^f\left(\theta \right)=\mathrm{\varnothing }$.  Naturally, to implement $f$ in a setting with evidence, $\theta$ and $T^f\left(\theta \right)$ should be appropriately “distinguishable” using evidence. This notion is made precise by the following definition.

Definition 8 (Distinguishability).

For any $\theta$ and $\mathrm{\Omega }\subseteq \mathrm{\Theta }$, $\theta$ and $\mathrm{\Omega }$ are distinguishable if for any ${\mathrm{\Omega }}^{\prime }\subseteq \mathrm{\Omega }$, $E^{\mathrm{\ell }}(\theta )\ne {\displaystyle \bigcup _{{\theta }^{\prime }\in {\mathrm{\Omega }}^{\prime }}}{E}^{\mathrm{\ell }}({\theta }^{\prime })$.

Thus, a state $\theta$ is distinguishable from an event or set of states $\mathrm{\Omega }$ if for every subset ${\mathrm{\Omega }}^{\prime }$ of $\mathrm{\Omega }$, either some player can disprove ${\mathrm{\Omega }}^{\prime }$ when $\theta$ is the true state (which requires $E_i^{\mathrm{\ell }}(\theta )⊈{\displaystyle \bigcup _{{\theta }^{\prime }\in {\mathrm{\Omega }}^{\prime }}}{E}_i^{\mathrm{\ell }}({\theta }^{\prime })$) or some player can disprove $\theta$ when the true state state is in ${\mathrm{\Omega }}^{\prime }$ (which requires $E_i^{\mathrm{\ell }}(\theta )⊉{\displaystyle \bigcup _{{\theta }^{\prime }\in {\mathrm{\Omega }}^{\prime }}}{E}_i^{\mathrm{\ell }}({\theta }^{\prime })$).  Notice that if $\theta$ is distinguishable from $\mathrm{\Omega }$ then $\theta$ is distinguishable from any subset of $\mathrm{\Omega }$.  Consequently, if $\theta$ and $\mathrm{\Omega }$ are distinguishable, then $\theta$ must be “pairwise distinguishable” from every ${\theta }^{\prime }\in \mathrm{\Omega }$ (in particular, $\theta \notin \mathrm{\Omega }$).  However, such pairwise distinguishability need not be enough for distinguishability.  The following example illustrates this point and also shows how distinguishability is connected to evidence-monotonicity and implementability.

Example 8.

There are two propositions: $a$ and $b$.  Each member of a group of three or more experts knows which of the two propositions are true, if any.  Due to time or space limitations, however, each one can provide a proof of at most one proposition.  This problem can be represented by $\mathrm{\Theta }=\{\phi ,a,b,ab\}$, and for all $i$, $E_i^{\mathrm{\ell }}(\phi )=\{\phi \}$, $E_i^{\mathrm{\ell }}(a)=\{\phi ,a\}$, $E_i^{\mathrm{\ell }}(b)=\{\phi ,b\}$, and $E_i^{\mathrm{\ell }}(ab)=\{\phi ,a,b\}$, where $\phi$ represents “neither proposition is true” or “no proof provided.”

Suppose now that the experts’ preferences over outcomes are state-independent, so that (*) is always satisfied.  Then, for any choice of ${\{e_i^{\ast }(ab)\}}_{i=1}^n$, there exists ${\theta }^{\prime }\in \{a,b\}$ such that (**) is satisfied with $\theta =ab$.  It follows from Proposition 2 that not every SCF is evidence-monotonic, and hence that not every SCF is implementable.  In particular, implementability requires $f(ab)\in \{f(a),f(b)\}$.  On the other hand, by choosing $e_i^{\ast }(\phi )=\phi ,e_i^{\ast }(a)=a$, and $e_i^{\ast }(b)=b$, we see that $f(ab)\in \{f(a),f(b)\}$ is also sufficient for the SCF $f$ to falsify (***) and thus for $f$ to be implementable under no veto power and non-satiation.

Hence, although this evidence structure satisfies “pairwise distinguishability” (i.e. $\theta \ne {\theta }^{\prime }⟹E(\theta )\ne E^{\mathrm{\ell }}({\theta }^{\prime })$), evidence-monotonicity is not guaranteed even under non-satiation. The reason is that although state $ab$ is distinguishable from any other state $\theta \in \{\phi ,a,b\}$, state $ab$ is not distinguishable from the event $\{\phi ,a,b\}$ because of the assumption that an expert can provide a proof of at most one proposition.

The following result characterizes evidence-monotonicity in terms of distinguishability.

Proposition 3.

Assume $f$ satisfies non-satiation. $f$ is evidence-monotonic if and only if for all $\theta$, $\theta$ and $T^f(\theta )$ are distinguishable.

Proof.

See Appendix. ∎

An immediate implication of Proposition 3 is that a simple condition on the evidence structure guarantees that any SCF satisfying non-satiation is evidence-monotonic, no matter what the agents’ preferences are:

$$\forall \theta :\theta \text{ is distinguishable from }\mathrm{\Theta }\mathrm{╲}\left\{\theta \right\}.$$ (UD)

Condition (UD), short for Universal Distinguishability, requires that each state must be distinguishable from any event that does not contain it.  As seen in Example 8, this is generally a stronger requirement than every state being distinguishable from every other state.

Corollary 3.

Assume $n\ge 3$. Any SCF that satisfies both no veto power and non-satiation can be implemented if (UD) holds.

Proof.

Let $f$ be an arbitrary SCF satisfying non-satiation and no veto power.  Pick any $\theta$.  Since $\theta \notin T^f(\theta )$, (UD) implies that $\theta$ is distinguishable from $T^f(\theta )$.  By Proposition 3, $f$ is evidence-monotonic.  Theorem 3 yields the desired conclusion. ∎

The Corollary is tight in the sense that if (UD) is violated, there exists a profile of utility functions (for $n\ge 3$) and a SCF satisfying no veto power and non-satiation such that the SCF is not implementable.  We illustrate the Corollary with the following example.

Example 9.

$\mathrm{\Theta }=\{{\theta }_1,{\theta }_2,{\theta }_3\}$; $n=3$; $E_1^{\mathrm{\ell }}({\theta }_1)=\{x,y\}$, $E_1^{\mathrm{\ell }}({\theta }_2)=\left\{x\right\}$, $E_1^{\mathrm{\ell }}({\theta }_3)=\left\{y\right\}$, $E_2^{\mathrm{\ell }}({\theta }_1)=\{x,y\}$, $E_2^{\mathrm{\ell }}({\theta }_2)=\left\{y\right\}$, $E_2^{\mathrm{\ell }}({\theta }_3)=\left\{x\right\}$, and $E_3^{\mathrm{\ell }}(\theta )=\{z\}$ for all $\theta$.  (UD) holds because $E^{\mathrm{\ell }}({\theta }_1)=\{(x,x,z),(x,y,z),(y,x,z),(y,y,z)\},E^{\mathrm{\ell }}({\theta }_2)=\{(x,y,z)\}$, and $E^{\mathrm{\ell }}({\theta }_3)=\{(y,x,z)\}$.  Hence, by Corollary 3, any SCF satisfying no veto power and non-satiation is implementable.

Many models with hard evidence, both in mechanism design and beyond, assume that the structure of hard evidence satisfies a property known as normality, which captures the idea that agents face no constraints on time, effort, space, etc., in providing evidence. Formally:

Definition 9 (Normality).

The evidence structure is normal or satisfies normality if for all $i$ and $\theta$, there is some ${\overline{e}}_i(\theta )\in E_i^{\mathrm{\ell }}(\theta )$ such that $\left[{\overline{e}}_i(\theta )\in E_i^{\mathrm{\ell }}({\theta }^{\prime })⟹E_i^{\mathrm{\ell }}(\theta )\subseteq E_i^{\mathrm{\ell }}({\theta }^{\prime })\right]$.

The formulation above follows Bull and Watson (2007).  It says that for any player $i$ and state $\theta$, there is some evidence ${\overline{e}}_i(\theta )$ that can be interpreted as a maximal or summary evidence because it proves by itself what agent $i$ could prove by jointly sending all his available evidence.  The condition is equivalent to the full reports condition of Lipman and Seppi (1995) or the minimal closure condition of Forges and Koessler (2005), and is somewhat weaker than Green and Laffont’s (1986) nested range condition in their “direct mechanism” setting.

To illustrate the property, consider Example 6 again, where $\mathrm{\Theta }={ℝ}_{+}^n$, $E_i=\mathrm{\Theta }$ and $E_i^{\mathrm{\ell }}(\theta )=[0,{\theta }_i]$ for all $i,\theta$.  This evidence structure is seen to be normal by setting ${\overline{e}}_i(\theta )={\theta }_i$ for all $i,\theta$: if ${\overline{e}}_i(\theta )={\theta }_i\in E_i^{\mathrm{\ell }}({\theta }^{\prime })=[0,{\theta }_i^{\prime }]$ then it must be that ${\theta }_i\le {\theta }_i^{\prime }$ and so $E_i^{\mathrm{\ell }}(\theta )=[0,{\theta }_i]\subseteq [0,{\theta }_i^{\prime }]=E_i^{\mathrm{\ell }}({\theta }^{\prime })$, as required.  It is straightforward to also check that Example 7 satisfies normality, whereas Example 8 does not.

For SCFs satisfying non-satiation, normality implies that the characterization in Proposition 2 can be significantly simplified: a SCF satisfying non-satiation is evidence-monotonic if and only if for all $\theta$ and ${\theta }^{\prime }$, if (*) and

$$E^{\mathrm{\ell }}(\theta )=E^{\mathrm{\ell }}({\theta }^{\prime })\text{.}$$ (5)

hold, then $f(\theta )=f({\theta }^{\prime })$.

The reason is that under normality, no matter what $e^{\ast }(\cdot )$ is, (***) is equivalent to (5). Thus the existential qualifier in Proposition 2 can be dropped altogether.

A related observation is that when the evidence structure is normal, distinguishability of any state $\theta$ and event $\mathrm{\Omega }$ is equivalent to the distinguishability of $\theta$ from each ${\theta }^{\prime }\in \mathrm{\Omega }$. Combining this with Proposition 3 yields:

Corollary 4.

Assume the evidence structure is normal. A SCF that satisfies non-satiation is evidence-monotonic if and only if for any $\theta$ and ${\theta }^{\prime }\in T^f\left(\theta \right)$, $E^{\mathrm{\ell }}(\theta )\ne E^{\mathrm{\ell }}({\theta }^{\prime })$.

Corollary 4 identifies exactly which normal evidence structures permit implementation of non-Maskin-monotonic SCFs (under $n\ge 3$, non-satiation, and no veto power).  It can be combined with our earlier results to derive additional corollaries, such as:

Corollary 5.

Assume $n\ge 3$ and that the evidence structure is normal.  A SCF $f$ that satisfies both no veto power and non-satiation is implementable if

$$\forall \theta ,{\theta }^{\prime }:\left[E^{\mathrm{\ell }}(\theta )=E^{\mathrm{\ell }}({\theta }^{\prime })⟹f(\theta )=f({\theta }^{\prime })\right].$$ (6)

Remark 3.

Ben-Porath and Lipman (2011) study implementation with hard evidence.  They refer to condition (6) as “measurability” and show in their Proposition 1 that in this setting, a SCF is implementable when preferences are state-independent only if it satisfies (6).  Our Proposition 2 in fact implies a stronger necessary condition for implementation with state-independent preferences when the hard evidence structure is normal:

$$\forall \theta ,{\theta }^{\prime }:\left[\begin{array}{c}f\left(\theta \right)=f\left({\theta }^{\prime }\right)\\ \text{if}\\ \forall i:\text{either }{E}_i^{\mathrm{\ell }}(\theta )=E_i^{\mathrm{\ell }}({\theta }^{\prime })\text{ or }\left(f(\theta )\in {\arg \max }_a{u}_i(a,{\theta }^{\prime })\text{ and }{E}_i^{\mathrm{\ell }}(\theta )\subseteq E_i^{\mathrm{\ell }}({\theta }^{\prime })\right)\end{array}\right].$$ (7)

To verify this, observe first that under state-independent preferences, (*) is satisfied for all $\theta$ and ${\theta }^{\prime }$; second, if the conditional in (7) holds for some $\theta$ and ${\theta }^{\prime }$, then normality implies that (**) will be satisfied no matter the choice of $e^{\ast }(\cdot )$ (in particular, when $e^{\ast }(\theta )=\overline{e}(\theta )$ for all $\theta$).

Condition (7) is obviously stronger than (6) and emphasizes the necessity of being able to reward players for evidence submission.  Under non-satiation, the two conditions are equivalent.   Ben-Porath and Lipman (2011) have also independently proved a result similar to Corollary 5.   Note that even under normality, non-satiation and no veto power, (6) is not necessary for implementation when preferences are not state-independent, for instance the SCF $f^{\ast }$ in Example 7.  The reason is that when hard evidence is the same across two states, a mechanism can still exploit preference reversals to implement different outcomes, just as in the standard environment without evidence.

6. Conclusion

This paper has generalized the implementation problem to incorporate agents’ ability to provide discriminatory signals or evidence about the state.  The central theme of our results is that the planner can use either agents’ preferences over outcomes or their evidentiary technology to discriminate between states of the world, even though evidence submission is inalienable.  We have studied both hard evidence, where players can prove that the state lies in some subset of all possible states, and the costly production of evidence, where evidentiary costs are non-prohibitive but vary across states.  The results we have obtained may be useful in terms of both necessary conditions — in particular, the finding that the ability to reward players is sometimes needed — and sufficient conditions demonstrating how a wide class of social choice functions are implementable as a function of the evidence structure.  In particular, we have identified an appropriate generalization and weakening of Maskin-monotonicity, evidence-monotonicity, and shown that this is the key to implementation with evidence.

There are a number of directions in which this research can be developed.  Our analysis here substantially exploits the complete information setting, and it is obviously important to understand how the arguments can be extended when agents have private information.  We conjecture that a weakening of Jackson’s (1991) Bayesian monotonicity condition in a similar way to how evidence-monotonicity weakens Maskin-monotonicity will be central to Bayesian implementation, in conjunction with standard conditions like incentive compatability.

Within the complete information framework, it would also be useful to understand how evidence changes the implementation problem when one restricts attention to “nice” mechanisms, for example, “bounded mechanisms” (Jackson, 1992).  In a related vein, the presence of evidence will generally allow greater scope for implementation with weaker solutions concepts, such as in dominant strategies.  These are likely to be fruitful avenues for further study.

Finally, we note that our notion of implementation in this paper has been that no evidentiary costs should be incurred in equilibrium. This is without loss of generality in a hard-evidence setting, but is not when there are non-prohibitive evidentiary costs. For example, the literature on screening shows that it may be possible to design a mechanism that induces information revelation from an agent (in a unique equilibrium) at the cost of incurring inefficient signaling distortions; this would apply in versions of our Example 3. It would be interesting to extend our analysis to full implementation in a general framework that allows for costly evidence provision in equilibrium.

Appendix: Omitted Proofs

The following Lemma is used in the proof of Theorem 4.

Lemma 1.

A SCF $f$ is evidence-monotonic if and only if there exists a nonempty-valued correspondence $e^{\ast \ast }:\mathrm{\Theta }\rightrightarrows E$ such that

1. for all $\theta$, $e^{\ast \ast }(\theta )\subseteq E^{\mathrm{\ell }}(\theta ,f(\theta ))$; and

2. for all $\theta$, ${\theta }^{\prime }$, and $e\in e^{\ast \ast }(\theta )$, if

   $$\forall i,b,e_i^{\prime }:\left[U_i(f(\theta ),e_i,\theta )\ge U_i(b,e_i^{\prime },\theta )\Rightarrow U_i(f(\theta ),e_i,{\theta }^{\prime })\ge U_i(b,e_i^{\prime },{\theta }^{\prime })\right],$$ (8)

   then $f(\theta )=f({\theta }^{\prime })$ and $e\in e^{\ast \ast }({\theta }^{\prime })$.

Notice two differences between the definition of evidence-monotonicity and the condition given in Lemma 1: first, the mapping $e^{\ast \ast }$ above is a correspondence whereas the $e^{\ast }$ in Definition 4 is a function; and second, part (2) in above places a requirement on the relationship between $e^{\ast \ast }(\theta )$ and $e^{\ast \ast }({\theta }^{\prime })$ that is not required by Definition 4.

Proof of Lemma 1.

The “if” direction is straightforward because any single-valued selection from the correspondence $e^{\ast \ast }(\cdot )$ in the Lemma’s statement verifies Definition 4.

So consider the “only if” direction. Assume that $f$ is evidence-monotonic.  Fix any $e^{\ast }$ verifying Definition 4.  Define a binary relation $R$ on $\mathrm{\Theta }\times \mathrm{\Theta }$ as follows: $\theta R{\theta }^{\prime }$whenever condition (2) in Definition 4 holds, which we reproduce here as:

$$\forall i,a,e_i^{\prime }:\left[U_i(f(\theta ),e_i^{\ast }(\theta ),\theta )\ge U_i(a,e_i^{\prime },\theta )\Rightarrow U_i(f(\theta ),e_i^{\ast }(\theta ),{\theta }^{\prime })\ge U_i(a,e_i^{\prime },{\theta }^{\prime })\right]\text{.}$$ (9)

Define the correspondence $e^{\ast \ast }:\mathrm{\Theta }\rightrightarrows E$ as follows: for any ${\theta }^{\prime }$, $e^{\ast \ast }({\theta }^{\prime })=\bigcup _{\theta :\theta R{\theta }^{\prime }}{e}^{\ast }(\theta ).$ Note that because $R$ is reflexive, $e^{\ast }({\theta }^{\prime })\in e^{\ast \ast }({\theta }^{\prime })$ for any ${\theta }^{\prime }$.

We will show that this correspondence $e^{\ast \ast }(\cdot )$ satisfies the Lemma’s requirements.  To check the first requirement, pick any $e\in e^{\ast \ast }({\theta }^{\prime })$. By construction, this means that $e=e^{\ast }(\theta )$ for some $\theta$such that $\theta R{\theta }^{\prime }$. Thus, condition (9) holds, and hence evidence-monotonicity implies that $f({\theta }^{\prime })=f(\theta )$.  Moreover, by using $e_i^{\prime }=e_i^{\ast }({\theta }^{\prime })$ and $a=f(\theta )$ in condition (9), and the fact that $e^{\ast }({\theta }^{\prime })\in E^{\mathrm{\ell }}({\theta }^{\prime },f({\theta }^{\prime }))=E^{\mathrm{\ell }}({\theta }^{\prime },f(\theta ))$ (by part (i) of Definition 4), it follows that $e=e^{\ast }(\theta )\in E^{\mathrm{\ell }}({\theta }^{\prime },f(\theta ))=E^{\mathrm{\ell }}({\theta }^{\prime },f({\theta }^{\prime }))$. Since $e$ was an arbitrary choice from $e^{\ast \ast }({\theta }^{\prime })$, it follows that for all ${\theta }^{\prime }$, $e^{\ast \ast }({\theta }^{\prime })\subseteq E^{\mathrm{\ell }}({\theta }^{\prime },f({\theta }^{\prime }))$, which is the first requirement of the Lemma.

We now show that $e^{\ast \ast }(\cdot )$ also satisfies part (2) of the Lemma’s requirements . Pick any $\theta ,{\theta }^{\prime }$ and $e\in e^{\ast \ast }(\theta )$ satisfying (8). We must prove that $f(\theta )=f({\theta }^{\prime })$ and $e\in e^{\ast \ast }({\theta }^{\prime })$. Note that since $e\in e^{\ast \ast }(\theta )$, there must exist ${\theta }^{\prime \prime }$ such that $e=e^{\ast }({\theta }^{\prime \prime })$ and ${\theta }^{\prime \prime }R\theta$. By definition of $R$,

$$\forall i,a,e_i^{\prime }:\left[U_i(f({\theta }^{\prime \prime }),e_i^{\ast }({\theta }^{\prime \prime }),{\theta }^{\prime \prime })\ge U_i(a,e_i^{\prime },{\theta }^{\prime \prime })⟹U_i(f({\theta }^{\prime \prime }),e_i^{\ast }({\theta }^{\prime \prime }),\theta )\ge U_i(a,e_i^{\prime },\theta )\right].$$

That $f$ is evidence-monotonic implies $f({\theta }^{\prime \prime })=f(\theta )$. Hence, the above line is equivalent to

$$\forall i,a,e_i^{\prime }:\left[U_i(f(\theta ),e_i^{\ast }({\theta }^{\prime \prime }),{\theta }^{\prime \prime })\ge U_i(a,e_i^{\prime },{\theta }^{\prime \prime })⟹U_i(f(\theta ),e_i^{\ast }({\theta }^{\prime \prime }),\theta )\ge U_i(a,e_i^{\prime },\theta )\right].$$ (10)

On the other hand, from condition (8) and $e=e^{\ast \ast }({\theta }^{\prime \prime })$, we have

$$\forall i,a,e_i^{\prime }:\left[U_i(f(\theta ),e_i^{\ast }({\theta }^{\prime \prime }),\theta )\ge U_i(a,e_i^{\prime },\theta )⟹U_i(f(\theta ),e_i^{\ast }({\theta }^{\prime \prime }),{\theta }^{\prime })\ge U_i(a,e_i^{\prime },{\theta }^{\prime })\right].$$ (11)

Combining (10) and (11) yields

$$\forall i,a,e_i^{\prime }:\left[U_i(f(\theta ),e_i^{\ast }({\theta }^{\prime \prime }),{\theta }^{\prime \prime })\ge U_i(a,e_i^{\prime },{\theta }^{\prime \prime })⟹U_i(f(\theta ),e_i^{\ast }({\theta }^{\prime \prime }),{\theta }^{\prime })\ge U_i(a,e_i^{\prime },{\theta }^{\prime })\right].$$

Since $f({\theta }^{\prime \prime })=f(\theta )$, the above line is equivalent to ${\theta }^{\prime \prime }R{\theta }^{\prime }$. That $f$ is evidence-monotonic now implies that $f({\theta }^{\prime \prime })=f({\theta }^{\prime })$ and so $f(\theta )=f({\theta }^{\prime })$. Finally, observe that since ${\theta }^{\prime \prime }R{\theta }^{\prime }$, the construction of $e^{\ast \ast }(\cdot )$ implies that $e=e^{\ast }({\theta }^{\prime \prime })\in e^{\ast \ast }({\theta }^{\prime })$. ∎

Proof of Theorem 4.

For the “only if” direction, assume $f$ is evidence-monotonic. Pick any correspondence $e^{\ast \ast }(\cdot )$ that satisfies the conditions in Lemma 1, and let $\widehat{f}=(f,e^{\ast \ast })$. We will show that $\widehat{f}$ is Maskin-monotonic on the extended outcome space. To prove this, fix any $\theta$, $(a,e)\in \widehat{f}(\theta )$, and ${\theta }^{\prime }$. We must show the following: if

$$\forall i,b,e^{\prime }:[U_i(a,e_i,\theta )\ge U_i(b,e_i^{\prime },\theta )⟹U_i(a,e_i,{\theta }^{\prime })\ge U_i(b,e_i^{\prime },{\theta }^{\prime })],$$ (12)

then $(a,e)\in \widehat{f}({\theta }^{\prime })$. So assume (12). Then (8) is satisfied (since $a=f(\theta )$), hence Lemma 1 implies that $f({\theta }^{\prime })=f(\theta )$ and $e\in e^{\ast \ast }({\theta }^{\prime })$, which together imply that $(a,e)\in \widehat{f}({\theta }^{\prime })$, as required.

For the “if” direction, suppose $\widehat{f}=(f,e^{\ast \ast })$ is a costless extension of $f$ that is Maskin-monotonic on the extended outcome space.  To show that $f$ is evidence-monotonic, it suffices to show that $e^{\ast \ast }(\cdot )$ satisfies the requirements of Lemma 1.  The first requirement of Lemma 1 is obviously satisfied by the definition of a costless extension; to prove the second, fix $\theta$, ${\theta }^{\prime }$, $e\in e^{\ast \ast }(\theta )$, and assume (8).  We must show that $f({\theta }^{\prime })=f(\theta )$ and $e\in e^{\ast \ast }({\theta }^{\prime })$.  Condition (8) implies that (12) holds when $a=f(\theta )$.  Thus, Maskin-monotonicity of $(f,e^{\ast \ast })$ implies that $(f(\theta ),e)\in \widehat{f}({\theta }^{\prime })$, which implies that $f(\theta )=f({\theta }^{\prime })$ and $e\in e^{\ast \ast }({\theta }^{\prime })$, as required. ∎

Proof of Proposition 2.

Consider the hard evidence setting i.e. separable preferences and for all $i$, $\theta$, $e_i$, either $c_i(e_i,\theta )=0$ or $c_i(e_i,\theta )>{sup}_a{u}_i(a,\theta )-{inf}_a{u}_i(a,\theta )$.

First we prove sufficiency.  For this, it suffices to show that (2) $⟹$ (*) and (**).  So assume (2).  By considering $e_i^{\prime }=e_i^{\ast }(\theta )$ in (2), it is straightforward that (*) follows.  For the first part of (**), consider (2) with $a=f(\theta )$ and $e_i^{\prime }\in E_i^{\mathrm{\ell }}({\theta }^{\prime })$.  Since the antecedent within (2) is then satisfied, the consequent must be true, which yields $c_i(e_i^{\ast }(\theta ),{\theta }^{\prime })\le 0$, which implies $e_i^{\ast }(\theta )\in E_i^{\mathrm{\ell }}({\theta }^{\prime })$.  As this is true for all $i$, the first part of (**) has been shown.  Now observe that the second part of (**) is equivalent to: for all $i$,

$E_i^{\mathrm{\ell }}({\theta }^{\prime })⊈E_i^{\mathrm{\ell }}(\theta )⟹[\forall a:u_i(f(\theta ),{\theta }^{\prime })\ge u_i(a,{\theta }^{\prime })].$ (13)

Fix any $i$.  It suffices to show that (13) is satisfied.  For any $e_i^{\prime }\in E_i^{\mathrm{\ell }}({\theta }^{\prime })\setminus E_i^{\mathrm{\ell }}(\theta )$, it is straightforward to check that the antecedent within (2) is always satisfied for any $a$ (because $c_i(e_i^{\prime },\theta )>{sup}_a{u}_i(a,\theta )-{inf}_a{u}_i(a,\theta )$). Hence, for any $a$, the consequent of (2) must be true, and given that $e_i^{\ast }(\theta )\in E_i^{\mathrm{\ell }}({\theta }^{\prime })$ and $e_i^{\prime }\in E_i^{\mathrm{\ell }}({\theta }^{\prime })\setminus E_i^{\mathrm{\ell }}(\theta )$, it follows that the consequent of (13) holds.

Next we show necessity.  For this it suffices to show that (*) and (**) $⟹$ (2).  Accordingly, assume (*) and (**), which in particular implies (13) for all $i$.  If $e_i^{\prime }\notin E_i^{\mathrm{\ell }}({\theta }^{\prime })$, then $c_i(e_i^{\prime },{\theta }^{\prime })>{sup}_a{u}_i(a,{\theta }^{\prime })-{inf}_a{u}_i(a,{\theta }^{\prime })$, which combines with the first part of (**) to imply that (2) is satisfied (because the consequent therein holds, regardless of the antecedent). Next, if $e_i^{\prime }\in E_i^{\mathrm{\ell }}(\theta )$, then by (*) and the first part of (**), it follows that (2) must hold. Finally, for all $e_i^{\prime }\in E_i^{\mathrm{\ell }}({\theta }^{\prime })\setminus E_i^{\mathrm{\ell }}(\theta )$, (13) combined with the first part of (**) implies that the consequent in (2) is satisfied. ∎

Proof of Proposition 3.

Assume non-satiation.  Recall that we can then replace (**) by (***) in Proposition 2.  It follows from this version of Proposition 2 that $f$ is evidence-monotonic if and only if

$$\forall \theta ,\exists e^{\ast }(\theta )\in E^{\mathrm{\ell }}(\theta )\text{s.t. }\forall {\theta }^{\prime }\in T^f(\theta ),\exists i\text{ s.t. }\left(e_i^{\ast }(\theta )\notin E_i^{\mathrm{\ell }}({\theta }^{\prime })\right)\text{ or }\left(E_i^{\mathrm{\ell }}({\theta }^{\prime })⊈E_i^{\mathrm{\ell }}(\theta )\right).$$ (14)

We will work with this equivalent formulation.

For the “if” direction of the result, assume that

$\forall \theta \text{ and }\mathrm{\Omega }\subseteq T^f(\theta ):E^{\mathrm{\ell }}(\theta )\ne {\displaystyle \bigcup _{{\theta }^{\prime }\in \mathrm{\Omega }}}{E}^{\mathrm{\ell }}({\theta }^{\prime }),$ (15)

and, toward contradiction, that (14) is false.  This implies that there exists $\theta$ such that for all $e\in E^{\mathrm{\ell }}(\theta )$, there exists ${\theta }^{\prime }(e)\in T^f(\theta )$ for which

$$\forall i:\left(e_i\in E_i^{\mathrm{\ell }}({\theta }^{\prime }(e))\right)\text{ and }\left(E_i^{\mathrm{\ell }}({\theta }^{\prime }(e))\subseteq E_i^{\mathrm{\ell }}(\theta )\right).$$

Set $\mathrm{\Omega }:={\displaystyle \bigcup _{e\in E^{\mathrm{\ell }}(\theta )}}{\theta }^{\prime }(e)$, and note that $\mathrm{\Omega }\subseteq T^f(\theta )$.  Since $e\in E^{\mathrm{\ell }}({\theta }^{\prime }(e))$ for each $e\in E^{\mathrm{\ell }}(\theta )$, it follows that $E^{\mathrm{\ell }}(\theta )\subseteq {\displaystyle \bigcup _{{\theta }^{\prime }\in \mathrm{\Omega }}}{E}^{\mathrm{\ell }}({\theta }^{\prime })$.  Finally, for each $e\in E^{\mathrm{\ell }}(\theta )$, we have $E^{\mathrm{\ell }}({\theta }^{\prime }(e))\subseteq E^{\mathrm{\ell }}(\theta ),$ hence ${\displaystyle \bigcup _{{\theta }^{\prime }\in \mathrm{\Omega }}}{E}^{\mathrm{\ell }}({\theta }^{\prime })\subseteq E^{\mathrm{\ell }}(\theta )$, and so $E^{\mathrm{\ell }}(\theta )={\displaystyle \bigcup _{{\theta }^{\prime }\in \mathrm{\Omega }}}{E}^{\mathrm{\ell }}({\theta }^{\prime })$, a contradiction with (15).

For the “only if” direction, assume that $f$ satisfies (14). We proceed again by contradiction, assuming that for some $\theta$ and $\mathrm{\Omega }\subseteq T^f(\theta )$, $E^{\mathrm{\ell }}(\theta )={\displaystyle \bigcup _{{\theta }^{\prime }\in \mathrm{\Omega }}}{E}^{\mathrm{\ell }}({\theta }^{\prime })$.  This implies that for some $\theta$: (i) for all $e\in E^{\mathrm{\ell }}(\theta ),$ there exists ${\theta }^{\prime }(e)\in \mathrm{\Omega }\subseteq T^f(\theta )$ s.t. $e\in E^{\mathrm{\ell }}({\theta }^{\prime }(e))$, and (ii) $E^{\mathrm{\ell }}({\theta }^{\prime }(e))\subseteq E^{\mathrm{\ell }}(\theta )$.  But this contradicts the assumption that $f$ satisfies (14). ∎