# Implementation with Uncertain Evidence††thanks: We would like to thank
Jingfeng Lu, Satoru Takahashi and Junjie Zhou for helpful comments and
suggestions. Financial support from the Singapore Ministry of Education
Academic Research Fund Tier 1 is gratefully acknowledged.

Soumen Banerjee Department of Economics, National University of Singapore.
Email<EMAIL_ADDRESS>Yi-Chun Chen Department of Economics,
National University of Singapore. Email<EMAIL_ADDRESS>
###### Abstract

We study a full implementation problem with hard evidence where the state is
common knowledge but agents face uncertainty about the evidence endowments of
other agents. We identify a necessary and sufficient condition for
implementation in mixed-strategy Bayesian Nash equilibria called No Perfect
Deceptions. The implementing mechanism requires only two agents and a finite
message space, imposes transfers only off the equilibrium, and invoke no
device with ”…questionable features…” such as integer or modulo games.
Requiring only implementation in pure-strategy equilibria weakens the
necessary and sufficient condition to No Pure-Perfect Deceptions. In general
type spaces where the state is not common knowledge, a condition called
higher-order measurability is necessary and sufficient for rationalizable
implementation with arbitrarily small transfers alongside.

##  1 Introduction

Consider a government funding a research grant for a vaccine for a new
disease. Several firms have prior experience of developing vaccines for
closely related diseases and can apply for the grant. Being mature firms in
the same sector, firms are familiar (owing to prior experience) with the
quality of research processes of the other firms. However, candidate vaccines
for the new disease (which serve as evidence of the quality of a firm’s
research) are products of the firm’s internal research processes, and are,
therefore, private information. Firms want the grant to be awarded to them
irrespective of the true quality of their research processes while the
government wants to maximize the probability of obtaining a functional
vaccine.

Alternately, consider a personal injury trial where a judge faces the problem
of determining the level of compensation that a defendant should pay a
plaintiff. Suppose that the judge wants to set a level of compensation
commensurate to the damage that has been caused, but does not know what that
damage is. Each agent knows the extent of the damage, and irrespective of the
level of damage, the plaintiff wants more compensation and the defendant less.
In such a setting, evidence is likely to be the result of investigation and
therefore uncertain. However, both the defendant and the plaintiff may have
some notion of the possible evidence which may arise.

The common threads that underlie the two situations described above are the
following - there is a (decision relevant) state commonly known to the agents
but not to the designer, agents have state independent incentives which are
not aligned with those of the designer, and while there is evidence in the
setting, it is uncertain, so that agents do not know precisely what evidence
other agents may possess. This characterizes a wide variety of practical
situations and thus it is important to study how to obtain credible
information for decision making in these settings.

In this paper, we study a setup inspired by Ben-Porath and Lipman (2012), but
different in one important aspect - the evidence is uncertain. This means that
articles of evidence are drawn (independently) from a distribution, and the
actual realization of evidence is private information for the agents. The
setup is Bayesian in the evidence dimension, i.e. while agents do not know
what evidence other agents have, the distribution from which this evidence is
drawn is common knowledge. This is more realistic than complete information
along all dimensions, evidence often being the product of research, which is
fundamentally uncertain in nature. It is however, conceivable, that even
though the exact outcome of the search for evidence may be unknown, prior
experience may allow agents to roughly predict what evidence may arise in a
certain situation.

Evidence variation is used in two distinct ways in the mechanisms we construct
- first, in presenting evidence, an agent directly _refutes_ all the states
where she may not possess such evidence with positive probability; second, if
an agent cannot present the evidence for a state claim (perhaps because some
evidence is not available with enough probability), the distribution induced
on her evidence report varies from the expected distribution under truth-
telling - a difference which we will show can be used to flag incorrect
reporting using a system of _bets_. Our result relies on a novel
classification of lies (incorrect state claims) based on their refutability
with evidence, and for some lies which cannot be directly refuted with
evidence, the latter technique involving bets is used.

When constructing mechanisms, agents may attempt to deceive the designer by
either misreporting the state, or withholding some part of their evidence
endowment, since their incentives are not necessarily aligned with those of
the designer. Such strategies, which deviate from truth-telling, are called
_deceptions_. Sometimes, deceptions might exist which perfectly mimic another
state in both the state and evidence dimensions. In such cases, we will show
that the designer cannot separate these states by using a mechanism, and this
yields our implementing condition - No Perfect Deceptions (NPD). More
precisely, NPD can be summarized as follows: if states $s$ and $s^{\prime}$
are such that $s^{\prime}$ is a lie in state $s$ which cannot be directly
refuted by evidence, and at state $s$, it is possible for all agents to induce
the same distribution on their evidence as they would under truth-telling in
state $s^{\prime}$, then the social choice function must induce the same
outcome at $s$ and $s^{\prime}$.

To establish the sufficiency of NPD for mixed-strategy implementation, we
present a finite mechanism which fully implements any social choice function
(SCF) which satisfies NPD in mixed-strategy Bayesian Nash equilibria. The
mechanism works with two or more agents and uses off-equilibrium transfers. A
striking feature of this mechanism is that while most Bayesian implementation
results (see for example Jackson (1991) and Serrano and Vohra (2010)) require
three or more agents and involve ”…questionable features…” such as integer or
modulo games111See Jackson (1992) for a description of the issues which arise
from the use of these questionable features., we obtain exact implementation
with only two agents and without the use of such ”…questionable features…”. We
note however, that unlike in Jackson (1991), where each agent knows only her
own type, the domain of the social choice function is common knowledge in our
setup, and agents only contend with uncertainty along the evidence dimension.

A strictly weaker condition, which we call No Pure-Perfect Deceptions (NPPD)
is necessary and sufficient for pure-strategy implementation. It requires that
the strategies the agents use to mimic the true distribution at another state
be pure, and is therefore strictly weaker than NPD. This result spells out a
clear distinction in this setup between pure and mixed-strategy
implementation, with the set of mixed-strategy implementable SCFs being
strictly smaller than the set of pure-strategy implementable SCFs.222This is
consistent with Bayesian implementation with preference variation, where Mixed
Bayesian Monotonicity is strictly stronger than Bayesian Monotonicity. It is,
however, different from implementation with complete information, where Maskin
monotonicity characterizes implementation with preference variation, and
measurability characterizes implementation with evidence irrespective of pure
or mixed strategies. This condition is still stronger than a stochastic
version of the measurability condition in Ben-Porath and Lipman (2012) (which
we term _stochastic measurability_)__ however, elucidating an important point
- when uncertain evidence is considered, conditions in the flavour of
measurability (which only require that the evidence distribution vary between
states with different desired outcomes) no longer suffice, and stronger
conditions are required even when limiting attention to pure strategies.

At a methodological level, we introduce two significant innovations. First, in
line with our treatment of deterministic evidence in Banerjee, Chen, and Sun
(2021), we use a novel classification of lies (incorrect state claims) in
terms of their refutability with evidence and eliminate these lies
successively in a mechanism. This eschews the canonical approach of first
obtaining consistent reports using an integer game and then using the
implementing condition to argue that consistent reports may only obtain on the
truth. The versatility of this approach is evidenced by its utility in both
deterministic and uncertain evidence settings. To motivate the second
innovation, we first draw attention to the fact that our setting allows for
the existence of lies which cannot be eliminated with positive probability by
evidence possessed by any agent.333This is possible even though the evidence
distribution varies between two states. In particular, the support of the
evidence distribution could be the same, while the probabilities of particular
collections of evidence vary amongst the states. In these cases, the necessary
condition (NPD) yields that some agents presenting these lies will not be able
to present every article of evidence with the same probability as they would
be expected to under truthful reporting if the lie were indeed the truth. In
this case, it becomes possible for agents to profitably signal to the designer
that a lie is being presented by placing monetary bets on the evidence
realizations of other agents. This is a form of arbitrage over probability
distributions and is critical to the treatment of mixed strategies alongside
Bayesian uncertainty. The technique is somewhat close in spirit to the
approach in Crémer and McLean (1988), where it finds use in efficient partial
implementation from agents about correlated valuations. This paper marks, to
our knowledge, the first use of such an approach in the field of full
implementation of general SCFs.444Note that Crémer and McLean (1988) focuses
on efficient allocation with cheap talk messages while we focus on
implementation of SCFs.

We then turn to a more general setup where agents’ private information is
represented by a general type, and evidence is contained within this type.
Further, arbitrary correlations are allowed in these types, so that evidence
draws may now be correlated. In this context, we present a mechanism which
implements a given SCF in rationalizable strategies but with arbitrarily small
transfers alongside. This requires that at least one of the agents be able to
separate between states (type profiles) at which different outcomes are
prescribed in terms of their beliefs at some finite order, a condition we term
_higher-order measurability._ While this condition bears a resemblance to the
measurability condition in Abreu and Matsushima (1992), we spell out the
difference here. In an environment without preference variation, only constant
SCFs satisfy the measurability condition in Abreu and Matsushima (1992).
However, in such a scenario, with sufficient evidence variation, we can build
belief hierarchies which allow for implementing non-constant SCFs. In a
setting with independent evidence endowments, such as the one we study for
Bayesian Nash implementation, higher order measurability is identical to
stochastic measurability, and therefore weaker than both NPD and NPPD. We show
that higher-order measurability is necessary and sufficient for implementation
in rationalizable strategies with small transfers, alongside the usual
incentive compatibility condition. This significantly expands the scope of
obtaining implementation with evidence, albeit at the cost of small transfers
alongside the desired outcome and a significantly more complicated mechanism.

The rest of the paper is organized as follows - In Section 2, we describe a
illustrating example more formally to provide context for the analysis in
later sections. Section 3 defines the setup formally and introduces some
properties of the evidence structure. Section 4 deals with the Bayes-Nash
implementation result. Section 5 discusses pure-strategy Bayes-Nash
implementation. Section 6 details rationalizable implementation in the setup.
Finally, Section 7 reviews and compares our results with the literature.

##  2 Illustrating Example - Research Grant

For the aforementioned problem of research grants for a vaccine, suppose there
are two firms, $A$ and $B$, which apply for the grant. Firm $A$ is a startup
whose research process quality may either be low ($L$), medium ($M$) or high
($H$). A low quality research process is characterized either by having a low
quality candidate vaccine (e.g. with major side effects). A firm with a medium
quality research process has a probability $0.4$ of having a high quality
candidate (one with only minor side effects). A firm with a high quality
research process produces a high quality candidate with a probability $0.6$.
Firm $B$ is an incumbent with (commonly known) medium research quality ($M$).
The government is not aware of Firm $A$’s research process quality, so that
the states of the world are given by $L,M,$ or $H$.

In state $L$, the government wants to allot the grant to firm $B$, in state
$H$ to firm $A$, and in state $M$ to firm $B$. As in the introduction, we
argue that the research process quality of firm A is common knowledge amongst
the firms, but unknown to the government. With the social choice function so
defined, we turn our attention to the following formal representation of the
evidence structure.

State | Evidence (Firm A)
---|---
$H$ | $0.6\times\\{\\{M,H\\},\\{L,M,H\\}\\}+0.4\times\\{\\{L,M,H\\}\\}$
$M$ | $0.4\times\\{\\{M,H\\},\\{L,M,H\\}\\}+0.6\times\\{\\{L,M,H\\}\\}$
$L$ | $\\{\\{L,M,H\\}\\}$

Note that the articles of evidence in the above example have been associated
with subsets of the state space. In general, we could have abstract articles
of evidence, such as $e_{1}$ and $e_{2}~{}$instead of $\\{L,M,H\\}$, and
$\\{M,H\\}$ respectively. These ”names” are obtained by associating an article
of evidence with the states in which they appear with positive probability.
This form of nomenclature is used in Ben-Porath and Lipman (2012), albeit in a
deterministic setting. We use this nomenclature to simplify the exposition
(especially within examples) in several places in the paper. The articles of
evidence above are interpreted thus - $\\{L,M,H\\}$ is interpreted as
possessing a low quality candidate, and $\\{M,H\\}$ as possessing a high
quality candidate. Thus, firm A, in presenting the article $\\{M,H\\}$ proves
that its research quality is not $L$. The above table essentially captures the
intuition presented in the opening of this section - as we move upwards in
research quality, we see an increasing probability of having a high quality
candidate. Notice that firm A of type $H$ maybe unable to separate itself from
a firm A type $M$, since either the type $M$ may have the high quality
candidate or the type $H$ may not possess the high quality candidate. This
yields that an unraveling result of the flavour of Milgrom (1981) or Grossman
(1981) may have no bite in this setup. This is a property possessed by the
setup in Ben-Porath and Lipman (2012), and shared by the more general setup we
study here.

From the above intuition of evidence, it is clear that no agent can eliminate
state $M$ at state $H$. This provides a major challenge in achieving
implementation. To see this, suppose the mechanism were direct, requiring only
a state and an evidentiary claim. Further, consider the following strategies
for firm A in state $H$ possessed with $\\{\\{M,H\\},\\{LMH\\}\\}$: Report
$\\{\\{M,H\\},\\{LMH\\}\\}$ with probability $\frac{2}{3}$ and report
$\\{\\{LMH\\}\\}$ with probability $\frac{1}{3}$; In the state dimension,
always claim that the state is $M$. With this strategy, the agents would
induce the same distribution on their reports as if the true state were $M$,
and they were reporting truthfully. This form of strategy is later dubbed a
_perfect_ deception. If perfect deceptions exist, it is not possible to
separate states in any mechanism (direct or indirect) which relies on Bayesian
Nash Implementation. This result is formally proved in Section 4.1 and
followed by an intuitive description. Note that there is also a perfect
deception for type $M$ to type $L$, but $L$ is refutable at $M$ with positive
probability, so that types $M$ and $L$ are separable by a mechanism.

With the above evidence structure then, it is not possible for the government
to allot the grant to firm $A$ in state $H$ and firm $B$ in state $M$.
Consider though the following mild perturbation of the evidence structure: An
additional article of evidence $\\{\\{H\\}\\}$ is available to firm $A$ with a
small probability when its research quality is $H$. For instance, the
distribution in state $H$ may be
$0.1\times\\{\\{H\\}\\}+0.5\times\\{\\{M,H\\},\\{LMH\\}\\}+0.4\times\\{\\{L,M,H\\}\\}$.
In this case, the government can actually implement different outcomes in
states $M$ and $H\ $\- while in state $M$, $H$ is nonrefutable, the article
$\\{\\{H\\}\\}$ is not available, so that a perfect deception is impossible;
in state $H$, while it is possible to perfectly match the evidence
distribution for state $M$, $M$ is actually refutable with positive
probability.

##  3 Model and Preliminaries

###  3.1 Setup

There is a set of agents $\mathcal{I=}\left\\{1,...,I\right\\},$ $I\geq 2$, a
set of outcomes $A$ and a finite set of states $S.$ Agents have bounded
utility over the outcomes given by $\bar{u}_{i}:A\times
S\rightarrow\mathbb{R}$. Their preferences are quasilinear, so that
$u_{i}(a,\bar{\tau}_{i},s)=\bar{u}_{i}(a,s)+\bar{\tau}_{i}$, where
$\bar{\tau}_{i}$ is the transfer of money to agent $i$. The bound of
$\bar{u}_{i}$ can be normalized so that it is strictly less than $1$, that is,
an agent can be persuaded to accept any outcome if the the alternative were
any other outcome with a penalty of $1$ dollar.

Each agent $i$ is endowed with a collection (mathematically, a set) of
articles of evidence $E_{i}$ which can vary from state to state. A profile of
collections (one for each agent) is denoted by $E$. The set of all possible
collections of evidence for agent $i$ is denoted by $\mathbb{E}_{i}$ and we
denote by $\mathbb{E}$ ($=\Pi_{i\in\mathcal{I}}\mathbb{E}_{i}$), the set of
all possible profiles of evidence collections. As in the illustrating example,
each collection of evidence can be associated with a set of subsets of the
state space - namely those subsets in which the article occurs with positive
probability.

We also assume that it is possible for an agent to submit the entire
collection of evidence she is endowed with. This condition, which is commonly
called _normality_ , is present in Ben-Porath and Lipman (2012) as well, and
is, generally speaking, a common feature of single stage mechanisms in such
settings. In case of uncertain evidence though, there emerges a subtle
difference. In Ben-Porath and Lipman (2012), normality is formulated by
requiring that a single ”most informative” evidence message be available in
any state to any agent.555In context of the example for instance, the article
$\\{M,H\\}$ is more informative than the article $\\{L,M,H\\}$. In general,
the most informative article of evidence is given by the intersection of all
the available articles of evidence, when they are named with subsets of the
state space (as in the example). In this setting however, it is essential that
agents be allowed to submit an entire collection of evidence, rather than just
the most informative message. Intuitively, this is because several different
collections of evidence may yield the same “most informative” evidence
message. However, it may be possible to distinguish between these collections
when each member is observed by the designer. We discuss this point formally
in Appendix A.1.

Evidence at state $s$ is distributed according to the commonly known prior
$p:S\rightarrow\Pi_{i\in\mathcal{I}}\Delta(\mathbb{E}_{i})$. Denote the
marginals of $p(s)$ on $\mathbb{E}_{i}$ and $\Pi_{j\neq i}\mathbb{E}_{j}$ by
$p_{i}(s)$ and $p_{-i}(s)$, respectively. Deterministic evidence is a special
case of this (the above distribution is degenerate). Note that $p$ is defined
as a product distribution, eschewing the possibility of the evidence draws
being correlated. This assumption is maintained in most of the paper, but
relaxed in Section 6.

Let $P_{i}$ denote the set of all possible evidence distributions for agent
$i$, i.e. $P_{i}=\\{p_{i}(s):s\in S\\}$. We denote by $P$, the set
$\Pi_{i\in\mathcal{I}}P_{i}$.

###  3.2 Mechanisms and Implementation

Any mechanism $\mathcal{M}$ is represented by the tuple $(M,g,\tau)$ where $M$
is the message space, $g:M\rightarrow A$ is the outcome function, and
$\tau=\left(\tau_{i}\right)_{i\in\mathcal{I}}$ is the profile of transfer
rules with $\tau_{i}:M\rightarrow\mathbb{R}$. At state $s$, and with a prior
$p$, a mechanism $\mathcal{M}$ induces a Bayesian game
$G(\mathcal{M},u,s,p)=\left\langle\mathcal{I},s,p,\left\langle
M_{i},u_{i},S\times\mathbb{E}_{i}\right\rangle_{i\in\mathcal{I}}\right\rangle$
with the following properties:

  * •

The type space of a typical agent $i$ is : $S\times\mathbb{E}_{i}$.

  * •

Every type of every agent forms beliefs on $\mathbb{E}_{-i}$ according to
$p_{-i}$.

  * •

The action space of a type $(s,E_{i})$ is given by $M_{i}(E_{i})$ (as some
messages may be contingent on evidence availability). We only consider finite
mechanisms , so that $M_{i}(E_{i})$ is finite for any $E_{i}$.

  * •

A typical (mixed) strategy for an agent $i$ at the state $s$ is a function:
$\sigma_{i}:S\times\mathbb{E}_{i}\rightarrow\Delta(M_{i})$ such that
$\sigma_{i}(s,E_{i})\in M_{i}(E_{i})$.

The common prior type space is specified by $p$. Given a game
$G(\mathcal{M},u,s,p)$, say $\sigma_{i}(s,\cdot)$ is a best response to
$\sigma_{-i}(s,.)$ if

$\displaystyle\sigma_{i}(s,E_{i})\left(m_{i}\right)>0\Rightarrow$
$\displaystyle m_{i}\in\arg\max_{m_{i}^{\prime}\in
M_{i}}\sum_{E_{-i}\in\mathbb{E}_{-i}}p_{-i}(s)(E_{-i})\sum_{m_{-i}\in
M_{-i}}\sigma_{-i}(s,E_{-i})(m_{-i})[u_{i}(g(m_{i}^{\prime},m_{-i}),\tau_{i}(m_{i}^{\prime},m_{-i}),s)].$

Next, we define the notion of a Bayesian Nash equilibrium in this particular
setting.

###### Definition 1

A Bayesian Nash equilibrium (henceforth BNE) of the game
$G(\mathcal{M},u,s,p)$ is defined as a profile of strategies $\sigma$ such
that $\forall i,s$, $\sigma_{i}(s,\cdot)$ is a best response to
$\sigma_{-i}(s,.)$.

A pure-strategy BNE is a BNE $\sigma$ such that for any $i$ and $s$,
$\sigma_{i}\left(s,E_{i}\right)\left(m_{i}\right)=1$ for some $m_{i}$. We then
define the main notion of implementation we work with in this paper.

###### Definition 2

An SCF $f$ is implementable in mixed-strategy BNE by a finite mechanism if
there exists a finite mechanism $\mathcal{M}=(M,g,\tau)$ such that for any
profile of bounded utility functions $\bar{u}$, at any state $s$, we have
$g(m)=f(s)$ and $\tau(m)=0$ for every message $m\in M$ in the support of
$\sigma(s)$ of any BNE $\sigma$ of the Bayesian game $G(\mathcal{M},u,s,p)$.

That is, for any BNE of the Bayesian game induced by the mechanism, the
outcome is correct, and there are no transfers. We stress here that
implementation should obtain regardless of the realized profile of evidence
collections. Since we wish to implement by depending solely on evidence,
rather than depending on preference variation, the notion of implementation
above requires that implementation obtain regardless of the profile of bounded
utility functions.

###  3.3 Lies and their classification

At the heart of the Bayesian implementation result is a classification of lies
(states not identical to the truth), which we illustrate below.

###### Definition 3

A collection of evidence $E_{i}$ refutes a state $s$ (denoted $E_{i}\downarrow
s$) if agent $i$ does not have $E_{i}$ or a superset of $E_{i}$ with positive
probability at $s$. Otherwise, $E_{i}\not\downarrow s$.

That is, $E_{i}\downarrow s$ if $p_{i}(s)(E_{i}^{\prime})=0$ $\forall
E_{i}^{\prime}\supseteq E_{i}$. In a mechanism, agents will always have the
opportunity to withhold some articles from a collection. Therefore, even if a
collection does not occur at $s$ with positive probability, being presented
with this collection does not directly imply that $s$ is false. Indeed the
evidence presented may be part of a larger collection which can occur.
Therefore, only when a collection _or any superset_ does not occur at $s$, can
we claim that it refutes $s$.

In the context of the leading example, in state $M$ or $H$, the article
$\\{M,H\\}$ refutes the state $L$. A difference from the deterministic
evidence setting is that it is not available with probability 1. For instance,
if some firm claims that another firm’s research process is of low quality
(when it is of medium quality), the latter firm cannot necessarily prove this
claim to be false by presenting the article $\\{M,H\\}$ because it is not
available with probability 1. This is different from a setting of
deterministic evidence, where the necessary condition (measurability) entails
that the realization of the evidence vary between states, so that the article
$\\{M,H\\}$ would have to be available with probability 1.666In a setting of
complete information (e.g. Ben-Porath and Lipman (2012)) , an SCF $f$
satisfies measurability if whenever $f(s)\neq f(s^{\prime})$, there is an
agent $i$ whose evidence endowment varies between $s$ and $s^{\prime}$.

Also, if firm $A$, when possessed with the article $\\{H\\}$ claims a medium
quality process, then it is the only agent who can prove this claim to be
false.777Note that in context of this example, it would not be to the
advantage of this firm to make such a claim, but since we do not rely on
preference variation, in the general case, such issues may easily arise. This
scenario, referred to as a self-refutable lie, also exists under deterministic
evidence, but under deterministic evidence, the firm would be able to refute a
lie about itself with probability 1, rather than being able to do so only with
some probability (as in the above example).

The following conditions arise as a result of the definition of refutation
used in our setup:

  1. 1.

(se1) For any agent $i$,$\ p_{i}(s)(E_{i}\mathcal{)}=0$ if $E_{i}\downarrow
s$. That is, at any state, the probability that collections of evidence which
refute the truth are available is zero. In short, proof is true.

  2. 2.

(se2) If $E_{i}\not\downarrow s^{\prime}$ then
$p_{i}(s^{\prime})(E_{i}^{\prime})>0$ for some $E_{i}^{\prime}\supseteq
E_{i}$. That is, if a collection of evidence $E_{i}$ does not refute
$s^{\prime}$, then it (or a superset) is available in state $s^{\prime}$ as
well.

In Appendix A.1, we study the connections between this setup and the
deterministic evidence setup from Ben-Porath and Lipman (2012).

###### Definition 4

A lie $s^{\prime}\in S$ is said to be refutable by $i$ at $s$ if $\exists
E_{i}\in\mathbb{E}_{i}$ s.t. $p_{i}(s)(E_{i})>0$ and $E_{i}\downarrow
s^{\prime}$.

That is, at $s$, $s^{\prime}$ is refutable by $i$ if $i$ may have a collection
of evidence $E_{i}$ such that $E_{i}\downarrow s^{\prime}$. Clearly from
(se1), $E_{i}$ is not available at $s^{\prime}$ (if it were available, then
$E_{i}$ cannot refute $s^{\prime}$). Then, the support of the evidence
distribution for agent $i$ contains a collection under the truth which is
missing under a refutable lie.

###### Definition 5

A lie $s^{\prime}\in S$ is said to be refutable at $s$ if there is an agent
$i$ so that $s^{\prime}$ is refutable by $i$ at $s$. Otherwise, it is
nonrefutable.

Returning to the leading example, $H$ is nonrefutable at $M$. This brings up
another difference from the deterministic evidence setting, which is that it
is not possible for a firm to prove that it’s research process is of high
quality rather than being of medium quality. This is because there is no
additional article of evidence available at state $H$ which is not available
at state $M$. This scenario, called a nonrefutable lie (e.g. $H$ is
nonrefutable at $M$), also occurs under deterministic evidence, but under
deterministic evidence, it is necessary that some agent has additional
evidence under a non-refutable lie than under the truth with probability 1.
Indeed the treatment of non-refutable lies is one of the main differences
between the deterministic and uncertain evidence setups.

We note that if $s^{\prime}$ is a nonrefutable lie at $s$, then no agent may
possess (with positive probability) any articles of evidence in state $s$
which they may not possess at state $s^{\prime}$, since these articles would
refute $s^{\prime}$. Therefore, if $s^{\prime}$ is nonrefutable at $s$, there
are two possibilities with respect to the support of the evidence distribution
at $s^{\prime}$. Either it strictly includes the support under $s$, so that
$s$ is refutable (with positive probability) at $s^{\prime}$, or the supports
are identical, so that only the probabilities with which various collections
of evidence are available has changed. The latter scenario poses a major
challenge in the implementation result we pursue.

##  4 Mixed-Strategy Bayesian Nash Implementation

###  4.1 A Necessary Condition: No Perfect Deceptions

Given that under deterministic evidence, the implementing condition (called
measurability) entails only that at least some agent is endowed with a
different set of evidence, it would be natural to expect that a stochastic
version of this condition, which entails requiring $p(s)\neq p(s^{\prime})$
whenever $f(s)\neq f(s^{\prime})$ would suffice as the implementing condition
for Bayesian implementation. We term this condition _stochastic
measurability_. It turns out however, that not every non-refutable lie can be
eliminated by a mechanism, necessitating a stronger implementing condition. We
establish the condition and prove its necessity after some preliminaries
below.

First, we define a deception for an agent of type $(s,E_{i})$.

###### Definition 6

A deception for an agent $i$ is a function
$\alpha_{i}:S\times\mathbb{E}_{i}\rightarrow\Delta(S\times\mathbb{E}_{i}\mathbb{)}$
such that if
$(s^{\prime},E_{i}^{\prime})\in\operatorname{supp}\alpha_{i}(s,E_{i})$, then
$E_{i}^{\prime}\subseteq E_{i}$.

We interpret $\alpha_{i}$ as being a function from the agent’s true type to a
distribution over types she can mimic (which requires that true type has a
weakly larger collection of evidence than the mimiced type). A profile of
deceptions is denoted by $\alpha=(\alpha_{i})_{i\in\mathcal{I}}$. This notion
is similar to the one with the same name in Jackson (1991).

Note that a deception can also be interpreted as a strategy for an agent in a
direct mechanism (a mechanism where agents only report their types, i.e.
$M_{i}=S\times\mathbb{E}_{i}$ for each agent).

###### Definition 7

A deception $\alpha_{i}$ is perfect for state $s^{\prime}$ at state $s$ for
agent $i$ if,

$\forall
E_{i}^{\prime}\text{,}\sum_{E_{i}\in\mathbb{E}_{i}}p_{i}(s)(E_{i})\alpha_{i}(s,E_{i})(s^{\prime},E_{i}^{\prime})=p_{i}(s^{\prime})(E_{i}^{\prime})\text{.}$

Likewise, a profile of deceptions $\alpha=(\alpha_{i})_{i\in\mathcal{I}}$ is
perfect for state $s^{\prime}$ at state $s$ if $\alpha_{i}$ is perfect for
state $s^{\prime}$ at state $s$ for each agent $i$.

That is, a deception is perfect for state $s^{\prime}$ at state $s$ if every
agent induces the same distribution over her types as she would if the true
state were $s^{\prime}$ and if she were reporting truthfully.

We denote by $s\rightarrow_{i}s^{\prime}$ the notion that agent $i$ has a
perfect deception from $s$ to $s^{\prime}$. Therefore, if there is a perfect
deception from $s$ to $s^{\prime}$, then, $s\rightarrow_{i}s^{\prime}$
$\forall i\in\mathcal{I}$. Further, $s\not\rightarrow_{i}s^{\prime}$ denotes
the notion that $i$ does not have a perfect deception from $s$ to $s^{\prime}$
and $s\not\rightarrow s^{\prime}$ denotes that there is no perfect deception
from $s$ to $s^{\prime}$.

As mentioned earlier, it is not possible to eliminate non-refutable lies such
that there is a perfect deception for the non-refutable lie at the true state.
We now define the necessary condition for implementation.

###### Definition 8

(Condition NPD - No Perfect Deceptions) We say that a social choice function
$f$ satisfies NPD whenever for two states $s$ and $s^{\prime}$, if at $s$,
state $s^{\prime}$ is nonrefutable, and there exists a perfect deception for
$s^{\prime}$, then $f(s)=f(s^{\prime})$.

That is, to have different desirable outcomes between $s$ and $s^{\prime}$,
either more evidence must be available at $s$ than is available at
$s^{\prime}$, or it must be impossible to have a perfect deception for state
$s^{\prime}$ at state $s$. We note that one way for a perfect deception to be
impossible is if there are articles of evidence at $s^{\prime}$ which are not
available at $s$. We can therefore also interpret the above condition as
follows: we are able to eliminate all kinds of lies other than nonrefutable
lies so that agents can mimic the lie both in the state and the evidence
dimensions perfectly.

We also wish to stress the fact that the existence of a perfect deception from
$s$ to $s^{\prime}$ does not by itself preclude our ability to separate the
states by a mechanism. Indeed it must be the case that $s^{\prime}$ is
nonrefutable at $s$. To see this, consider a scenario where the evidence
structure is identical between $s$ and $s^{\prime}\emph{except}$ that each
collection at $s$ is appended with an additional article of evidence $e_{i}$
for each agent $i$. Clearly, a perfect deception involves each agent claiming
the state is $s^{\prime}$ and withholding the article $e_{i}$. However, it is
clear that these states can be separated by incentivizing refutation of a
state claim by presenting any $e_{i}$.

For an example of a social choice function and an evidence structure under
which the evidence distribution varies between two states, we refer the reader
to the leading example in Section 2. We reproduce the evidence structure
below:

State | Evidence (Firm A)
---|---
$H$ | $0.6\times\\{\\{M,H\\},\\{L,M,H\\}\\}+0.4\times\\{\\{L,M,H\\}\\}$
$M$ | $0.4\times\\{\\{M,H\\},\\{L,M,H\\}\\}+0.6\times\\{\\{L,M,H\\}\\}$
$L$ | $\\{\\{L,M,H\\}\\}$

It is clear that the distribution of evidence does change between every pair
of states, so that every SCF is stochastically measurable. However, it can be
seen that it is possible to mimic the distribution at $M$ when the true state
is $H$, as the article $\\{M,H\\}$ is available with extra probability at $H$.
For instance, the deception
$\alpha_{A}(H,\\{\\{M,H\\},\\{L,M,H\\}\\})\rightarrow\frac{1}{3}(M,\\{\\{L,M,H\\}\\})+\frac{2}{3}(M,\\{\\{M,H\\},\\{L,M,H\\}\\})$
suffices to do so. However, it is not possible to mimic the distribution at
$H$ when the state is $M$, as the article $\\{M,H\\}$ isn’t available often
enough. This establishes an important property of the NPD condition, that is,
it is not bidirectional. Therefore, the structure induced by the social choice
function on the state space is not partitional. We stress here that this is a
stark point of differentiation between deterministic and uncertain evidence,
since the necessary condition under deterministic evidence - measurability,
induces a partitional structure on the state space.

We present the main result of the paper below.

###### Theorem 1

A social choice function is implementable in BNE if and only if it satisfies
NPD.

We present the proof of necessity below, while the implementing mechanism
which constitutes the sufficiency proof is presented in Section 4.4.

Proof. (Necessity of NPD) Suppose a mechanism $\mathcal{M}=(M,g,\tau)$
implements $f$ and consider a pair of states $s$ and $s^{\prime}$ so that
$s^{\prime}$ is nonrefutable at $s$ and there is a perfect deception from $s$
to $s^{\prime}$.

First, we claim that

This follows from the nonrefutability of $s^{\prime}$ at $s$.

Now, consider any equilibrium $\sigma$ of the mechanism and the following
strategy for agent $i$ at state $s$ when endowed with the collection $E_{i}$.
First, the agent plays according to the deception $\alpha_{i}(s,E_{i})$. This
yields another type realization, which we denote by
$(s^{\prime},E_{i}^{\prime})$. Now, the agent plays
$\sigma_{i}(s^{\prime},E_{i}^{\prime})$. Since there is no additional
collection of evidence at $s$, this object is well defined. With some abuse of
notation, we denote the profile of such strategies by $\sigma\circ\alpha$.

We claim that $\sigma\circ\alpha$ forms an equilibrium at $s$ with outcome
$f(s^{\prime})$. To see this, consider an arbitrary agent $i$. First, given
the strategies of other agents $j\neq i$, the belief induced over the actions
of other agents $j$ is the same under $\sigma\circ\alpha$ at $s$ as that under
$\sigma$ at the state $s^{\prime}$. Given these beliefs, at state
$s^{\prime}$, $\sigma$ induces the outcome $f(s^{\prime})$ with no transfers.
Each type of agent $i$ can obtain this outcome in state $s$ by playing
according to $\sigma_{i}\circ\alpha_{i}$. If any type $E_{i}$ of agent $i$ at
$s$ has a profitable deviation, then there is another type of agent $i$ at
$s^{\prime}$ which has weakly more evidence than $E_{i}$ (from the claim
(LABEL:*) above) and can also deviate profitably. This contradicts the
optimality of $\sigma_{i}$ against $\sigma_{-i}$ at $s^{\prime}$. Therefore,
playing according to $\sigma_{i}\circ\alpha_{i}$ continues to be a best
response for the type. Thus, if there is a perfect deception $\alpha$ from $s$
to $s^{\prime}$, then any implementable social choice function must have
$f(s)=f(s^{\prime})$.

Informally, under $\alpha$, agents pretend to be other types and play the
equilibrium strategy under $\sigma$ of the mimiced type. The reason a type is
best responding even though she may be playing the equilibrium strategy of
another type is that the outcome is the same and the preferences of agents do
not change from state to state. That is, even though the concerned type may
have extra evidence, and therefore be able to play other messages, there was
another type at $s^{\prime}$ who also had that extra evidence and that type’s
best response still led to the outcome $f(s^{\prime})$ which this agent is
also getting from her strategy under $\sigma(\alpha(s))$, so that she
continues to best respond. Therefore, since an equilibrium outcome at $s$ is
$f(s^{\prime})$, then $f$ is implementable only if $f(s)=f(s^{\prime})$.

We note here that whereas the discussion above has centered around deceptions
where an agent pretends to mimic herself at another state, this applies to
mimicing a profile of distributions as well. More precisely, suppose that in
the true state $s^{\ast}$, which is characterized by the profile of
distributions $(p_{i}^{\ast})_{i\in\mathcal{I}}$, agents pretend to mimic
themselves at another state $s^{\prime}$, which is characterized by a profile
of distributions $(p_{i}^{\prime})_{i\in\mathcal{I}}$. If they can perfectly
mimic this other state (in terms of playing their equilibrium strategies for
state $s^{\prime}$), then by Theorem 1, $f$ is implementable only if
$f(s^{\ast})=f(s^{\prime})$.

This yields an interesting insight, which is that since it is always possible
to mimic any cheap talk messages in the message space, non-refutable lies
$s^{\prime}$ for which agents do not have perfect deceptions from the truth
must require presentation of evidence which is impossible in the true state.
Then, if an agent $i$ does not have a perfect deception at state $s$ for
$s^{\prime}$, then she cannot mimic the distribution $p_{i}^{{}^{\prime}}$, as
otherwise it would be possible for her to play the equilibrium strategies for
the state $s^{\prime}$. This highlights the role of evidence in this setup,
which is twofold. Either agents can refute distributional claims using
evidence, or agents are unable to mimic incorrect states perfectly owing to
their inability to mimic the distribution of evidence.

###  4.2 A Challenge Scheme

The above discussion established that when agents report certain nonrefutable
lies, they are unable to mimic the distribution of evidence for these lies.
This brings up the question of how we can exploit this fact in the
construction of mechanisms to facilitate the elimination of nonrefutable lies.
To elucidate the underlying idea, we first consider an analogous situation.

Consider a setting with two agents. The first agent has a deck of cards, from
which she draws a card and presents it. The second agent knows that the
firsts’ deck of cards is missing one black card. How does she convey this
information credibly to the designer if it is not possible to check the entire
deck? If she simply says there is a card missing, this claim may not be
credible. Rather, the second agent can place a bet of the following form \- if
you draw a black card, take a dollar from me. If you draw a red card, give me
99 cents. This bet clearly loses the second agent money if there is no card
missing. If she believes there is a black card missing though, then this wins
her money, as $\frac{26}{51}\times 0.99+\frac{25}{51}\times(-1)>0$. The fact
that the second agent is willing to take this bet credibly signals to the
designer that there is something wrong with the deck.

Note that the deck of cards is analogous to agent 1’s mixed-strategy.
Therefore, it is impossible to check the deck of cards and the second agent
must find this alternate solution to inform the designer that the first agent
is not playing the truth-telling strategy. Individual cards are analogous to
collections of evidence, and the inability to induce the correct distribution
of evidence is analogous to not having a black card. For the implementation
problem then, agents can blow the whistle on an incorrect (nonrefutable) state
report by identifying which agent does not have a perfect deception from the
truth to the nonrefutable lie, and then betting sums of money on that agent’s
plausible collections of evidence so that - (i) If the nonrefutable lie were
to be the truth, then the bet loses money, and (ii) Since this is not the
case, the bet actually wins money. As we will discuss later, this can be
thought of as analogous to a monotonicity like condition, yielding a
“reversal” between true and false states. Returning to the illustrating
example, if firm A tried to claim $H$ when the true state was $M$, it would,
at best be able to induce probability $0.4$ on the article $\\{M,H\\}$ as that
is the maximum probability with which it is available in state $M$. Then,
consider the following bet: $1$ dollar on $\\{\\{L,M,H\\}\\}$ and $1$ dollar
against $\\{\\{L,M,H\\},\\{M,H\\}\\}$. In state $H$ under truthful reporting,
it yields an expected loss of 20 cents, while in state $M$, it yields a
minimum expected profit of 20 cents. We will show below that this is possible
whenever there is no perfect deception. Before that, we will provide a simple
way for an agent to place such a bet.

Asking agents to place bets on (say) agent $i$’s evidence would mean that
agents would have to provide the designer a vector of numbers (one for each
collection in $\mathbb{E}_{i}$). This yields a complex message space. In fact,
the designer can make the appropriate bets for agents. All that she needs to
know is what state (say $s^{\prime}$) is being claimed, and what is the true
state. With this information, the designer can deduce which agent has no
perfect deception for the claimed state and place an appropriate bet against
the evidence of that agent on behalf of the agent who wishes to raise the
challenge. We will denote these bets by $b_{i}:S\times
S\rightarrow\mathbb{R}^{|\mathbb{E}_{i}|}$.

###### Remark 1

The above can also be viewed as the building block of a monotonicity like
condition. That is, for a pair of states $s$ and $s^{\prime}$ such that
$s\not\rightarrow_{i}s^{\prime}$, if all agents claim that the state is
$s^{\prime}$, then there is an agent $j$ for whom
$(f(s^{\prime})+b_{\hat{\imath}}(s^{\prime},s)(E_{\hat{\imath}}))$ is strictly
preferred to $f(s^{\prime})$ in state $s$ while $f(s^{\prime})$ is weakly
preferred to
$(f(s^{\prime})+b_{\hat{\imath}}(s^{\prime},s)(E_{\hat{\imath}}))$ in state
$s^{\prime}$. The allocation
$f(s^{\prime})+b_{\hat{\imath}}(s^{\prime},s)(E_{\hat{\imath}})$ therefore,
forms a test allocation which yields a reversal for an agent $j$ with
$f(s^{\prime})$ between the states $s$ and $s^{\prime}$.

We formalize this notion below. First, denote by $\mathcal{A}_{i}(s,E_{i})$
the set of all deceptions $\alpha_{i}(s,E_{i})$ for agent $i$ when endowed
with evidence $E_{i}$ at state $s$. Let $\alpha_{i}(s)$ be defined as
$\alpha_{i}(s)=(\alpha_{i}(s,E_{i}))_{E_{i}^{\prime}\in\mathbb{E}_{i}}$, and
analogously, let $\mathcal{A}_{i}(s)$ be the set of all possible profiles
$\alpha_{i}(s)$. Further, denote by $p_{\alpha_{i},s}(E_{i}^{\prime})$ the
probability induced over evidence collection $E_{i}^{\prime}$ induced by agent
$i$ under $\alpha_{i}(s)$. That is,

$p_{\alpha_{i},s}(E_{i}^{\prime})=\sum_{E_{i}\in\mathbb{E}_{i}}p_{i}(s)(E_{i})\alpha_{i}(s,E_{i})(s^{\prime},E_{i}^{\prime})\text{.}$

Defining probability distributions over evidence, i.e.
$(p_{\alpha_{i},s}(E_{i}^{\prime}))_{E_{i}^{\prime}\in\mathbb{E}_{i}}$by
$p_{\alpha_{i},s}$, we then denote by $P_{i}(s)$ the set
$\\{p_{\alpha_{i},s}:\alpha_{i}\in\mathcal{A}_{i}\\}$, which is the set of all
possible such probability distributions which agent $i$ can induce by playing
any deception in state $s$. Among these distributions is also
$p_{\alpha_{i}^{\ast},s}$, the distribution over agent $i$’s evidence at $s$,
which corresponds to the “no deception” scenario. At state $s^{\prime}$ let
$p_{\alpha_{i}^{\ast},s^{\prime}}$ denote the induced distribution over
evidence by the “no deception” scenario.

With these preliminaries established, we now present the challenge scheme in
the following lemma.

###### Lemma 1

For every agent $i$, there is a finite set
$B_{i}=\\{b_{i}(s,s^{\prime}):s\not\rightarrow_{i}s^{\prime}\\}$ such that for
any pair of states $s$ and $s^{\prime}$ for which
$s\not\rightarrow_{i}s^{\prime}$, we have $b_{i}(s,s^{\prime})\cdot
p_{\alpha_{i}^{\ast},s^{\prime}}<0$ and $b_{i}(s,s^{\prime})\cdot p>0$
$\forall p\in P_{i}(s)$.

Proof. Since $s\not\rightarrow_{i}s^{\prime}$,
$p_{\alpha_{i}^{\ast},s^{\prime}}\notin P_{i}(s)$. Further, $P_{i}(s)$ is
closed and convex. Then, from the separating hyperplane theorem, there is a
hyperplane $b_{i}$ such that $b_{i}\cdot p_{\alpha_{i}^{\ast},s^{\prime}}<0$
and $b_{i}\cdot p>0$ $\forall p\in P_{i}(s)$.

For a pair of states $s$ and $s^{\prime}$ one such $b_{i}$ is sufficient.
Iterating over all possible pairs of states which satisfy the premise of no
perfect deception yields the set $B_{i}$. Therefore, each $B_{i}$ is finite.

###### Remark 2

The above lemma is interpreted as follows: there is a vector of real numbers
(one for each possible collection of evidence for $i$) so that under truthful
revelation in state $s^{\prime}$, the expectation of this vector is negative
whereas for any possible strategy of agent $i$ in state $s$, the expectation
is positive. Accordingly, if an agent $j$ were to receive/give sums of money
based on $b_{i}$ according to agent $i$’s evidence presentation in the direct
mechanism, then in state $s^{\prime}$ under truthful revelation by agent $i$,
agent $j$ loses money while under any strategy for agent $i$ in state $s$,
agent $j$ gains money. This yields a monotonicity like interpretation - if
$s^{\prime}$ is a lie, the agent $j$ can ”blow the whistle” and indeed chooses
to do so since it is profitable.

We remark here that the set $B_{i}$ is a set of possible bets, one for each
pair of states such that there is no prefect deception for one to another. For
the set to be usable in a mechanism, we need a way for an agent to utilize
members of this set to challenge unanimous but incorrect state claims. This
operationalization is achieved as follows. First, define a function
$\hat{\imath}:S\times S\rightarrow\mathcal{I}$ such that if $s\not\rightarrow
s^{\prime}$, $s\not\rightarrow_{\hat{\imath}(s,s^{\prime})}s^{\prime}$. That
is, $\hat{\imath}$ identifies the agent who does not have a perfect deception
from state $s$ to $s^{\prime}$. Then, $b_{\hat{\imath}}:S\times S\rightarrow
B_{\hat{\imath}}$ is defined such that $b_{\hat{\imath}}(s,s^{\prime})\cdot
p_{\sigma_{\hat{\imath}}^{\ast},s^{\prime}}<0$ and
$b_{\hat{\imath}}(s,s^{\prime})\cdot p>0$ $\forall p\in P_{\hat{\imath}}(s)$.
The existence of such functions follows immediately from Lemma 1.

That is, when an agent $j$ wants to bet against a report of $s^{\prime}$ in
state $s$, then merely telling the designer that the true state is $s$
suffices. This is because the designer can use the function $\hat{\imath}$ as
defined above to infer which agent has no perfect deception from $s$ to
$s^{\prime}$ and can appropriately place a bet against $\hat{\imath}$’s
evidence on behalf of $j$ using the function $b_{\hat{\imath}}$ so that the
bet loses money for $j$ if $s^{\prime}$ were indeed true and $\hat{\imath}$
were reporting truthfully, and wins money for $j$ if $s$ were true
irrespective of what strategy $\hat{\imath}$ employs.

###  4.3 A Sketch of the Proof

In Section 4.1, we have established that NPD is necessary for implementation.
In what follows, we will construct an implementing mechanism to establish that
it is also sufficient. To fix ideas, we begin with a sketch of the proof
first.

The mechanism asks each agent for the following reports: A distribution report
about herself, a distribution report for the agent to her right, an evidence
report, and a state report (used for placing bets). The proof utilizes the
following steps. The first step is an intermediate result that is used
frequently, and thus forms one of the main building blocks of the proof. In
essence, the result states that if each type of a particular agent (say $i$)
submits all the evidence it is endowed with, then every agent ($i$ herself,
and all others) present truthful reports about $i$’s evidence distribution.
This result is obtained as follows. First, we use a proper scoring rule
($\tau^{2}$ in the proof) to incentivize other agents to predict the evidence
report by agent $i$. Since agent $i$ presents maximal evidence in all her
types, the optimal predictor for other agents is the true distribution for
agent $i$. This truthful report is used (by means of a crosschecking penalty)
to discipline agent $i$’s report about herself. This is denoted by $\tau^{3}$
in the proof. To reiterate, agent $i$’s maximal evidence presentation
incentivizes other agents to make truthful predictions about her, whereupon a
crosscheck incentivizes agent $i$ to make truthful reports about her own
distribution. A direct corollary of this result is that if all agents present
maximal evidence, then the entire profile of reports is truthful.

A key novelty of this argument is in the solution to the central tension when
using scoring rules - on the one hand, the scoring rule must be active on all
realizations of evidence to elicit the true distribution (otherwise it elicits
the distribution conditional on being active, which may not yield truthful
elicitation), but on the other hand, we require zero transfers on equilibrium.
This is solved by breaking the scoring rule transfer into two parts - a direct
part, which incentivizes predictions, and an offset part, which is used to
cancel the direct part in equilibrium. When an agent makes a prediction, she
only controls the direct part, so that from her point of view, the scoring
rule is always active. This incentivizes her to make truthful predictions
about others. However, her truthful report is used to discipline other agent’s
reports about themselves, and this disciplined report is used to offset the
scoring rule, so that it does not result in a transfer on equilibrium.

Armed with this intermediate result, the second step argues that the report
profile must be pure (recall that agents are allowed to mix) and must be
consistent with some state $s$. This step depends on an incentive for evidence
presentation which is triggered if agents disagree with each other. This is
denoted by $\tau^{1}$ in the proof. Broadly, if agents mix, then agents expect
disagreement in the distribution reports, and if the message profile is
inconsistent (due to such disagreements), then each agent is incentivized to
present their maximal evidence. Then, from the above intermediate result, we
can argue that the message profile cannot be inconsistent, since agents must
make truthful reports if all evidence presentation is maximal and truthful
reports must, by definition, be consistent with the true state.

The third step establishes that there cannot be a consensus on a refutable
lie. We institute a penalty ($\tau^{4}$ in the proof) which penalizes agents
if this commonly agreed upon state $s$ is refuted by another agent. There is
also a small reward for refuting this consensus (this is implicit within
$\tau^{1}$, which is also activated upon refutation). This penalty
($\tau^{4}$) is chosen to be large enough to deter agents from agreeing on a
refutable lie.

The fourth and final step establishes that there cannot be a consensus on a
nonrefutable lie which has a different outcome than the truth. If this were to
be the case, then from Condition NPD, there is an agent (say $i$) who does not
have a perfect deception from the true state to $s$. Then, the mechanism
provides a way for agents to make a bet, as discussed in Section 4.2. Further
$\tau^{1}$ is activated when there is an active bet as well. This leads to the
submission of maximal evidence by all agents, which by the first step means
that the profile of reports must have been true, so that there could not have
been a consensus on a nonrefutable lie in the first place.

Thus, we are left only the possibility of a joint pure report of the true
state (or a state which is outcome equivalent to the truth), so that
implementation obtains. In Section 4.5.5, we also show that there are no
transfers in equilibrium.

###  4.4 Mechanism

####  4.4.1 Message Space

Suppose the agents are seated around a circular table, so that for each agent
$i$, there is an agent to her right (this is agent $i+1$). For agent $I$, the
agent considered as “being to the right of” her is agent $1$. With this, the
message space is defined as follows,

$M_{i}=P_{i}\times P_{i+1}\times\mathbb{E}_{i}\times S\text{,}$

and a typical message ($m_{i}$) is given by
$m_{i}=(p_{i,i},p_{i,i+1},E_{i},s_{i})$.

That is, each agent makes a claim about her own evidence distribution
($p_{i,i}$) , a claim about the evidence distribution of the agent to her
right ($p_{i,i+1}$), submits a collection of evidence and makes a state claim
for (possibly) betting against other’s evidence reports.

####  4.4.2 Outcome

A message profile $m$ is said to be _consistent_ with state $s$ if each
distributional claim matches the true distribution in state $s$. That is,
$m=(p_{i,i},p_{i,i+1},E_{i},s_{i})_{i\in\mathcal{I}}$ is consistent with $s$
if $\forall i,j$, $p_{i,j}=p_{j}(s)=p_{j,j}$. Otherwise, it is _inconsistent_.

The outcome is given by $f(s)$ if $m$ is consistent with a state $s$, and an
arbitrary outcome $a\in A$ otherwise.

####  4.4.3 Transfers

The mechanism uses five transfers. There are scaling parameters with most of
the transfers, and we will define the appropriate scaling in Section 4.4.4.

The first transfer provides an agent the incentive to submit evidence when
there is inconsistency, or an active bet, or if a consistent profile has been
refuted by an agent. That is,

$\tau_{i}^{1}\left(m\right)=\left\\{\begin{tabular}[]{ll}$\varepsilon\times|E_{i}|$,&if
$m$ involves inconsistency, or an active bet,\\\ &or if $m$ is consistent with
$s$ and $E_{i}\downarrow s$;\\\ $0$&otherwise.\end{tabular}\right.$

where $\varepsilon>0$ is a small positive number.

The second transfer is a modified proper scoring rule as defined below.

First, define $Q_{j}(p_{i,j},E_{j})=[2p_{i,j}(E_{j})-p_{i,j}\cdot p_{i,j}]$.
That is, $Q_{j}(p_{i,j},E_{j})$ gives the value of the scoring rule if $j$
presents the collection $E_{j}$ and agent $i$’s report about $j$ is $p_{i,j}$.
With this, define

$\tau_{i,i+1}^{2}(m)=\left\\{\underline{\tau}\times[Q_{i+1}(p_{i,i+1},E_{i+1})-Q_{i+1}(p_{i+1,i+1},E_{i+1})]\text{,}\right.$

Where $\underline{\tau}>0$. This transfer provides agent $i$ the incentive to
truthfully report agent $i+1$’s distribution (due to the first term) when
agent $i+1$ presents all her evidence. In equilibrium, the reports are
consistent and therefore the transfer is off.

$\tau_{i}^{3}(m)=\left\\{\begin{tabular}[]{ll}$-\underline{\tau}$,&if
$p_{i,i}\neq p_{i-1,i}$\\\ $0$&otherwise.\end{tabular}\right.$

Every agent’s report about herself is cross-checked with the report about her
by the agent to her left. If the reports are not in agreement, then the agent
is fined $\underline{\tau}$.

The fourth transfer is related to lies which other agents can refute.

$\tau_{i}^{4}\left(m\right)=\left\\{\begin{tabular}[]{ll}$-\bar{\tau}$,&if
$p_{i,i+1}=p_{i+1}(s)$ $\forall i$, and $E_{j}\downarrow s$ for some $j\neq
i$\\\ $0$&otherwise.\end{tabular}\right.$

That is, an agent $i$ is fined $\overline{\tau}$ if another agent has refuted
state $s$ obtained from the vector of reports by agents about the agents to
their right. Note that this transfer does not apply to an agent’s report about
herself. Further, this transfer is inactive when the profile
$(p_{i,i+1})_{i\in\mathcal{I}}$ is not consistent.

$\tau^{5}$ is as defined below.

$\tau_{i}^{5}\left(m\right)=\left\\{\begin{tabular}[]{ll}$\varepsilon\times
b_{j}(s^{\prime},s_{i})(E_{j})$, where $j=\hat{\imath}(s^{\prime},s_{i})$&if
$m$ is consistent with $s^{\prime}$\\\ $0$&otherwise.\end{tabular}\right.$

where $\varepsilon>0$ is a small positive number as defined earlier. Note that
$\tau^{1}$ and $\tau^{5}$ are scaled using the same number $\varepsilon$.

That is, if agent $i$ bets against a unanimous report consistent with state
$s^{\prime}$ with a bet claiming state $s_{i}$, the designer evaluates the
challenge in accordance with the set $B_{j}$, where
$j=\hat{\imath}(s^{\prime},s_{i})$ and the function $b_{j}$ defined in Section
4.2 and pays out the revenue from the bet to agent $i$.

####  4.4.4 Scaling

In this section, we will define some parameters used for appropriately scaling
the transfers, and then establish that there are values for $\overline{\tau}$,
$\varepsilon$, and $\underline{\tau}$ so that the appropriate scaling is
possible.

First, we provide an intuitive overview of the scaling based on the proof
sketch in Section 4.3. Recall that we are working in a normalized setup in
which the utility of the outcome has been normalized to a number less than 1.
Since an arbitrarily small $\varepsilon$ provides sufficient incentive for
agents to submit evidence and make bets, we can choose $\varepsilon$ small
enough so that a penalty of 1 dollar is enough to dominate not only any change
in outcome, but also any gains or losses from $\tau^{1}$ or $\tau^{5}$. The
scoring rule $\tau^{2}$ is at the medium scale ($\underline{\tau}$) and
dominates any effect from a change of outcome.888This is, strictly speaking,
larger than it needs to be, since $\tau^{2}$ needs only to dominate the
transfers at $\varepsilon$ scale (as in setting her report about the agent to
her right, an agent may cause (or break) consistency). However, we scale it at
the level of $\underline{\tau}$ for notational parsimony. The crosscheck
$\tau^{3}$ is also at this scale since similar considerations apply to the
agent’s report about herself. Since we wish to prioritize the elimination of
lies which others can refute above other incentive considerations, $\tau^{4}$
dominates all other transfers, so that it belongs to the highest transfer
scale ($\overline{\tau}$). We define the transfer scales formally below.

Since $\tau^{2}$ is a proper scoring rule, if an agent $i+1$ presents all her
evidence, agent $i$ maximizes her revenues from $\tau^{2}$ by truthfully
reporting agent $i+1$’s evidence distribution. We require that the minimum
expected loss for an agent $i$ from lying about agent $i+1$’s distribution
dominates any effect from a change in the outcome. That is,

$\min_{s\in S}\min_{p_{i,j}\neq
p_{j}(s)}\sum_{E_{j}\in\mathbb{E}_{j}}p_{j}(s)(E_{j})\underline{\tau}[Q_{j}(p_{j}(s),E_{j})-Q_{j}(p_{i,j},E_{j})]>1$
(2)

Turning to the crosscheck, it must dominate any incentive from the outcome.
Since the minimum loss from lying about agent $i+1$’s distribution scales
linearly in $\underline{\tau}$, we can choose $\underline{\tau}>1$ such that
inequality 2 is satisfied.

Further, define as $\bar{\tau}^{2}$ the maximum possible change in utility
from $\tau^{2}$. That is, i.e.

$\bar{\tau}^{2}=\max_{i\in\mathcal{I}}\max_{E_{i+1}\in\mathbb{E}_{i+1}}\max_{p_{i,i+1},p_{i,i+1}^{\prime}\in
P_{i+1}}\underline{\tau}[Q_{i+1}(p_{i,i+1},E_{i+1})-Q_{i+1}(p_{i,i+1}^{\prime},E_{i+1})]$

Now we define the fourth scaling inequality as follows:

$\overline{\tau}\geq\frac{1+\bar{\tau}^{2}}{\min_{s^{\prime}\in
RL_{i}(s)}\\{p_{i}(s)(E_{i}):E_{i}\downarrow s^{\prime}\\}},\forall s\in
S,\forall i\in\mathcal{I}\text{.}$ (3)

That is, $\tau^{4}$ provides sufficient incentive to avoid being caught lying
even for the smallest probability with which refutable lies may be refuted by
the evidence of other agents.

It is then clear that the parameters $\varepsilon$, $\underline{\tau}$ and
$\overline{\tau}$ can be chosen to satisfy the above inequalities
simultaneously.

###  4.5 Proof of Implementation

In what follows, we assume that the true state is $s^{\ast}$ and that it
induces the profile of evidence distributions
$(p_{i}^{\ast})_{i\in\mathcal{I}}$.

####  4.5.1 Preliminary Results

###### Lemma 2

If agent $i$ presents all her evidence in $E_{i}$, then each agent
$j\in\mathcal{I}$ presents the truth in each message $p_{j,i}$.

Proof. If agent $i$ presents all her evidence in $E_{i}$, then for agent
$i-1$, setting $p_{i-1,i}=p_{i}^{\ast}$ maximizes her payoff from $\tau^{2}$
(since truthful reporting is optimal under a scoring rule). However, this
could also cause losses from $\tau^{1}$ (by creating consistency) and
$\tau^{5}$ (by activating a bet via creating consistency). However, since
$\underline{\tau}>1$ (by choice), $p_{i-1,i}=p_{i}^{\ast}$ is the best
response for agent $i-1$ in equilibrium. Then, since $\underline{\tau}>1$,
$p_{i,i}=p_{i}^{\ast}$ is the best response for agent $i$.

####  4.5.2 Consistency

###### Claim 1

In any equilibrium, there is a state $s$ such that the message profile is
consistent with $s$.

Proof. If all agents present all their evidence, then Lemma 2 yields that all
agents present true distributional claims in their reports and thus the
profile of reports must be consistent with the truth, so that $s=s^{\ast}$.

Now, suppose that there is inconsistency but not all agents present all their
evidence. We claim that this is only possible if precisely one agent $i$
randomizes in her reports $p_{i,i}$ or $p_{i,i+1}$. To see this, notice that
if two or more agents randomize in their distribution reports, then each type
of each agent expects inconsistency with positive probability and presents all
their evidence. So suppose that only agent $i$ mixes. Then in each message,
each agent $j\neq i$ expects inconsistency with positive probability and
presents all her evidence ($\varepsilon>0$). Then, from Lemma 2, $p_{k,j}$ is
the truth for all $k\in\mathcal{I}$ and $j\neq i$. Therefore, $i$ can only mix
in $p_{i,i}$. However, by hypothesis, each agent $j\neq i$ presents a pure
report in $p_{j,i}$. Therefore, in any message $m_{i}$ where $p_{i,i}\neq
p_{j,i}$, she incurs a loss from $\tau^{3}$. Note that there are no losses
from $\tau^{4}$ since agent $i$ is only changing $p_{i,i}$ and $\tau^{4}$ does
not apply to an agent’s report about herself. Consider a deviation to match
$p_{j,i}$. This avoids the loss from $\tau^{4}$, but may cause losses from
$\tau^{2}$ (by creating consistency) and $\tau^{5}$ (by activating a bet via
creating consistency). Since $\underline{\tau}>1$, this is a profitable
deviation. Therefore, we have a contradiction.

####  4.5.3 Eliminating Refutable Lies

###### Claim 2

There is no equilibrium where the distribution reports are consistent with a
refutable lie.

Proof. Suppose instead that $m$ is consistent with a refutable lie $s$. If it
is refutable by two or more agents, then $\tau^{1}$ provides the incentive to
refute the lie, and so all agents expect the lie to be refuted with positive
probability so that they present maximal evidence. In turn, Lemma 2 implies
the profile must be consistent with the truth, a contradiction.

So suppose $s$ can only be refuted by some agent $i$. Then, all agents other
than $i$ expect agent $i$ to refute $s$ with positive probability and
therefore present maximal evidence. Thus, from Lemma 2, $p_{.,j}=p_{j}^{\ast}$
$\forall j\neq i$. Then, $p_{i-1,i}\neq p_{i}^{\ast}$ (otherwise the profile
would be consistent with the truth). Therefore, in presenting $p_{i-1,i}$,
agent $i-1$ knows that this claim will be refuted with probability at least
$\min_{E_{i}\in\mathbb{E}_{i}}\\{p_{i}(s^{\ast})(E_{i}):E_{i}\downarrow s\\}$.
However, if she deviates to $p_{i-1,i}=p_{i}^{\ast}$, the profile has
$p_{i,i+1}=p_{i+1}(s^{\ast})$ $\forall i$ and therefore cannot be refuted. So,
the agent gains $\overline{\tau}$ from $\tau^{4}$. Also, the agent is
deviating away from consistency, so that $\tau^{1}$ yields no losses. Since
$\overline{\tau}$ dominates all the other incentives (Inequality (3)),
deviating to $p_{i}^{\ast}$ instead of presenting $p_{i-1,i}$ is a profitable
deviation for agent $i$.

####  4.5.4 No Bets in Equilibrium

###### Claim 3

In any equilibrium, the distribution reports are not consistent with a non-
refutable lie.

Proof. From Claim 1, the agents must all present pure distribution reports
which are consistent with a state $s$. From Claim 2, $s$ is not refutable by
any agent, since this would mean that an agent is presenting a lie which
another agent can refute. If $f$ prescribes a different outcome at $s$ than at
the truth, then there must be an agent $i$ such that
$s^{\ast}\not\rightarrow_{i}s$, that is, agent $i$ does not have a perfect
deception from the truth to $s$. Then, any agent $j\neq i$ has the incentive
to bet with probability 1, since $\varepsilon>0$, whereupon all evidence
presentation is maximal (due to $\tau^{1}$) and Lemma 2 presents a
contradiction.

####  4.5.5 Implementation

###### Claim 4

In any equilibrium, the outcome is $f(s^{\ast})$ and there are no transfers.

Proof. From Claims 1-3, the report profile is consistent with the true state.
Therefore, the outcome is $f(s^{\ast})$. Clearly, such a consensus is not
refutable, since any collection available under the truth cannot (by
definition) refute it.

Now, we claim that there are no bets in equilibrium. To see this, notice that
if an agent $i$ bets in equilibrium, then it must be that agents have not
presented all their evidence in $E$, since from Lemma 1, a bet yields a loss
if placed against a truthful reporting strategy. If some agent $i$ finds it
profitable to place a bet in any of her messages, then she must find it
profitable to bet in all of her messages. Then, each agent finds it optimal to
present all their evidence in $E$, a contradiction. Since the message profile
is consistent, and features no bets in equilibrium, $\tau^{1}$, $\tau^{3}$ and
$\tau^{5}$ are inactive as well.

Finally, notice that the absence of any inconsistency yields that each agent’s
claims about herself must be the same as those of the agent to her left. That
is, $p_{i,i+1}=p_{i+1,i+1}$ $\forall i$. Then, $\tau^{2}$ is inactive as well.
Thus, there are no transfers.

##  5 Pure-Strategy Bayesian Nash Implementation

In this section, we take a brief digression to discuss pure-strategy
implementation. While NPD was shown to be necessary for mixed-strategy
implementation, a weaker version, called No Pure-Perfect Deceptions (NPPD)
suffices for pure-strategy implementation. It is essentially identical to NPD
except for the additional requirement that any deception $\alpha$ be
degenerate, since playing a non-degenerate deception requires mixing by the
agents. A pure-perfect deception is defined below.

###### Definition 9

A deception $\alpha=(\alpha_{i})_{i\in\mathcal{I}}$ is pure-perfect for state
$s^{\prime}$ at state $s$ if it is a perfect deception for $s$ at $s^{\prime}$
and $\alpha$ is degenerate.

We now define the No Pure-perfect deceptions condition.

###### Definition 10

(Condition NPPD - No Pure-Perfect Deceptions) We say that a social choice
function $f$ satisfies NPPD whenever for two states $s$ and $s^{\prime}$, if
at $s$, state $s^{\prime}$ is nonrefutable, and there exists a pure-perfect
deception for $s^{\prime}$, then $f(s)=f(s^{\prime})$.

We now state the pure-strategy implementation result.

###### Theorem 2

A social choice function is implementable in pure-strategy BNE if and only if
it satisfies NPPD.

The proof of this result is derived as a simplification of our mixed-strategy
implementation result, and is relegated to Appendix A.3.

No Pure-perfect deceptions is shown to be strictly weaker than NPD and
strictly stronger than Stochastic Measurability in Appendix A.2. Therefore, in
our setup, mixed-strategy implementation is a strictly harder problem than
pure-strategy implementation. We note that this distinguishes this setup from
the complete-information setup in Ben-Porath and Lipman (2012) where mixed-
strategy Nash Implementation does not require a stronger condition on the
social choice function. However, it is consistent with the rest of the
Bayesian implementation literature though, in that mixed-strategy Nash
implementation in Serrano and Vohra (2010) requires Mixed Bayesian
Monotonicity, which is stronger than Bayesian Monotonicity which is required
for pure-strategy implementation (Jackson (1991)).

##  6 Implementation with a General Type Space

In this section, we study a more general model than the one considered above.
We allow agents to have a type $t_{i}\in T_{i}$ (where $T_{i}$ is finite) and
allow agents’ types to be correlated. A type profile $t$ determines agents’
preferences over the outcomes in a set $A$, so that $\bar{u}_{i}(a,t)\,$ is
agent $i$’s bounded utility when the outcome is $a$ and the type profile is
given by $t$. Further, $u_{i}(a,\bar{\tau}_{i},t)=$
$\bar{u}_{i}(a,t)\,+\bar{\tau}_{i}$ is the quasilinear extension of
$\bar{u}_{i}$. The type profile $t$ also determines agents’ evidence, which is
represented by $\hat{E}_{i}(t_{i})\in\mathbb{E}_{i}$. States of the world are
represented by type profiles $t=(t_{i})_{i\in\mathcal{I}}$. Each agent has a
belief $q_{i}:T_{i}\rightarrow\Delta(T_{-i})$ where $T_{-i}=\Pi_{j\neq
i}T_{j}$. Such a model is represented by
$\mathcal{T=}(T_{i},\hat{E}_{i},q_{i})_{{}_{i\in\mathcal{I}}}$. A social
choice function maps a state to the desirable outcome in that state, so that
$f:T\rightarrow A$, where $T=\Pi_{i}T_{i}$. Once again, we are interested in
implementing $f$ without relying on preference variation, so that we consider
constant preferences as a possibility.

In this section, we will adapt the solution concept of Interim Correlated
Rationalizability from Dekel, Fudenberg, and Morris (2007) to our setting.
Consider a mechanism $\mathcal{M}=(M,g,\tau)$, which induces a static Bayesian
game denoted by $G\left(\mathcal{M},\mathcal{T},u\right)$. Define the set of
messages feasible for an agent $i$ of type $t_{i}$ by $M_{i,t_{i}}$. Denote by
$R_{i}^{G}\left(t_{i}\right)$ use the set of rationalizable messages for agent
$i$ of type $t_{i}$. Then, we have
$R_{i,0}^{G}\left(t_{i}\right)=M_{i,t_{i}}$;

$R_{i,k+1}^{G}\left(t_{i}\right)=\left\\{\begin{array}[]{l|l}m_{i}\in
M_{i,t_{i}}&\begin{array}[]{l}\text{ there exists
}\pi_{i}\in\Delta\left(T_{-i}\times M_{-i}\right)\text{ such that }\\\
(1)\pi_{i}\left(t_{-i},m_{-i}\right)>0\Rightarrow m_{-i}\in\Pi_{j\neq
i}R_{j,k}^{G}\left(t_{j}\right)\\\ (2)m_{i}\in\underset{m_{i}^{\prime}\in
M_{i,t_{i}}}{\arg\max}\sum_{E_{-i},m_{-i}}u_{i}(g\left(m_{i}^{\prime},m_{-i}\right),\tau_{i}\left(m_{i}^{\prime},m_{-i}\right),t)\\\
(3)\sum_{m_{-i}}\pi_{i}\left(t_{-i},m_{-i}\right)=q_{i}(t_{i})(t_{-i})\end{array}\end{array}\right\\}\text{;}$

and
$R_{i}^{G}\left(t_{i}\right)=\cap_{k=1}^{\infty}R_{i,k}^{G}\left(t_{i}\right)$.
Then, denote by $R^{G}\left(t\right)=\Pi_{i\in I}R_{i}^{G}\left(t_{i}\right)$
as the profile of all rationalizable messages.

With this solution concept, we formalize the implementation notion below.

###### Definition 11

A social choice function $f$ is rationalizably implementable with arbitrarily
small transfers if for any $\varepsilon>0$, there is a mechanism
$\mathcal{M}=(M,g,\tau)$ such that for any profile of bounded utility
functions $\bar{u}=\left(\bar{u}_{i}\right)_{i\in\mathcal{I}}$, any type
profile $t$, and any profile of rationalizable messages $m\in
R^{G}\left(t\right)$ of the game $G\left(\mathcal{M},\mathcal{T},u\right)$, we
have $g(m)=f(t)$. Further, $|\tau_{i}(m)|\leq\varepsilon$ for every message
profile $m$.

That is, given an arbitrarily small (strictly) positive number $\varepsilon$,
it should be possible to obtain the socially optimal outcome at any profile of
rationalizable messages, and limit the transfers for any message profile
(rationalizable or otherwise) to being no higher than $\varepsilon$. This
represents a relaxation of the prior requirement that the transfers should be
zero in equilibrium, but yields a relaxation of the solution concept to
rationalizability, allows correlation among types, and (we will show) yields a
weaker implementing condition than either NPD or NPPD.

We now describe the agent’s higher order beliefs. Since we wish to implement
without relying on preference variation, so that constant preferences are a
possibility, we restrict agents to form beliefs only on evidence to obtain a
necessary condition which is strong enough to allow implementation when
preferences are constant. Note that the implementing mechanism we will present
later will allow for preference variation, but will not rely on it for
implementation. To this end, define $Z_{i}^{0}=\mathbb{E}_{-i}$, and for
$k\geq 1$, define $Z_{i}^{k}=Z_{i}^{k-1}\times\Delta(Z_{-i}^{k-1})$. For each
$i$, let $T_{i}^{\ast}$ denote the set of $i$’s collectively coherent
hierarchies (Mertens and Zamir (1985)). For each $t_{i}\in T_{i}$, let
$\hat{\pi}_{i}^{0}(t_{i})=\hat{E}_{i}(t_{i})$; construct mappings
$\hat{\pi}_{i}^{k}:T_{i}\rightarrow\Delta(Z_{i}^{k-1})$ recursively for all
$i\in\mathcal{I}$ and $k\geq 1$, such that $\hat{\pi}_{i}^{1}$ is the push-
forward of $q_{i}(t_{i})$ given by the map from $T_{-i}$ to $Z_{-i}^{0}$, such
that

$t_{-i}\longmapsto\hat{\pi}_{-i}^{0}(t_{-i})\text{,}$

and $\hat{\pi}_{i}^{k}(t_{i})$ is the push-forward of $q_{i}(t_{i})$ given by
the map from $T_{-i}$ to $Z_{-i}^{k-1}$ such that

$t_{-i}\longmapsto(\hat{\pi}_{-i}^{0}(t_{-i}),\hat{\pi}_{-i}^{1}(t_{-i}),...,\hat{\pi}_{-i}^{k-1}(t_{-i}))\text{,}$

where for any $k=0,1,2,..$, $\hat{\pi}_{-i}^{k}(t_{-i})=\Pi_{j\neq
i}\hat{\pi}_{j}^{k}(t_{j})$.

The mappings thus constructed, i.e.
$\hat{\pi}_{i}^{\ast}(t_{i})=(\hat{\pi}_{i}^{0}(t_{i}),\hat{\pi}_{i}^{1}(t_{i}),...)$
assign to each type a hierarchy of beliefs. We now propose a new implementing
condition which we term higher-order measurability.

###### Definition 12

A social choice function $f$ satisfies higher-order measurability if for any
pair of states $t$ and $t^{\prime}$ such that $f(t)\neq f(t^{\prime})$, there
is $k\in\mathbb{N}$ such that there is an agent $i$ whose $k^{th}$ order
belief $\hat{\pi}_{i}^{k}(t_{i})\neq\hat{\pi}_{i}^{k}(t_{i}^{\prime})$.

The necessity of higher-order measurability is demonstrated in Appendix A.4.
Intuitively, higher-order measurability requires that the social choice
function $f$ be measurable on a partition of $T$ where each cell of the
partition is such that if $t$ and $t^{\prime}$ belong to the same cell, then
each agent has the same belief hierarchy in both $t$ and $t^{\prime}$.

We now consider the setup we work with for Bayesian Nash implementation.
Suppose an SCF $f$ satisfies stochastic measurability, so that if $f(s)\neq
f(s^{\prime})$, then there is an agent $i$ such that $p_{i}(s)\neq
p_{i}(s^{\prime})$. Then, the first order belief of any agent $j\neq i$ is
different between $s$ and $s^{\prime}$, so that $f$ must satisfy higher-order
measurability. Conversely, if there are two states $s$ and $s^{\prime}$ so
that for each agent $i$, $p_{i}(s)=p_{i}(s^{\prime})$, and evidence
distributions are independent, then $f(s)$ must be identical to
$f(s^{\prime})$ if $f$ is to satisfy higher-order measurability. Therefore, in
such a setup, higher-order measurability is identical to stochastic
measurability, and therefore weaker than either NPD or NPPD.

Towards establishing that higher-order measurability is also sufficient for
implementation with the above implementation notion, we will define the
relevant version of incentive compatibility in this setting. To do so,
consider the direct mechanism with respect to
$\mathcal{T=}(T_{i},\hat{E}_{i},q_{i})_{{}_{i\in\mathcal{I}}}$, where each
agent $i$ makes a report $t_{i}\in T_{i}$ and the outcome chosen is
$f((t_{i})_{i\in\mathcal{I}}$. No transfers are induced.

###### Definition 13

A social choice function $f$ satisfies evidence incentive compatibility if for
each agent $i$, and each type $t_{i}\in T_{i}$,

$t_{i}\in\arg\max_{t_{i}^{\prime}\in\hat{T}_{i}(t_{i})}\sum_{t_{-i}\in
T_{-i}}q_{i}(t_{i})(t_{-i})\bar{u}_{i}(f(t_{i}^{\prime},t_{-i}),(t_{i},t_{-i}))$

where
$\hat{T}_{i}(t_{i})=\\{t_{i}^{\prime}:\hat{E}_{i}(t_{i}^{\prime})\subseteq\hat{E}_{i}(t_{i})\\}$.

That is, if agent $i$ is endowed with type $t_{i}$, and anticipates every
other agent to report their type truthfully, then it is among her best
responses to also report truthfully. This is consistent with Deneckere and
Severinov (2008), who show that if agents can send every combination of their
available messages, then the above condition is necessary and sufficient for
truthtelling to be a Bayesian Nash equilibrium. Theorems 1 and 2, however, do
not require this condition since the use of large transfers causes it to be
automatically satisfied. Now, we present the main result of this section.

###### Theorem 3

A social choice function is rationalizably implementable with arbitrarily
small transfers iff it satisfies higher-order measurability and evidence
incentive compatibility.

The sufficiency of higher-order measurability is demonstrated through the
construction of an implementing mechanism which is presented in Appendix A.4.
Here, we describe the intuition behind the construction, which follows ideas
from Abreu and Matsushima (1992). The first step is to use a small incentive
to extract the evidence from each agent. Irrespective of the other reports
they make, it will be a strictly dominant strategy to present all their
evidence. In the second step, we ask each agent to predict the evidence
presentation of the other agents and score their predictions using a quadratic
scoring rule. The input to the scoring rule is the agent’s own type, since
common knowledge of the type allows the designer to compute the posterior
distribution $q_{i}(t_{i})$ and score the prediction appropriately. Since each
agent expects every other agent will have presented all their evidence, she
presents her true belief about the evidence presentations of the other agent
in order to maximize the returns from this scoring rule. This elicits the
other agent’s true first order belief. In the third step, we extract the
agents true second order belief by asking them to predict the first order
beliefs extracted in the previous step and scoring their predictions using a
quadratic scoring rule. Higher-order measurability assures us that if we
repeat this process enough times, we will have extracted the true types of the
agents. This mechanism performs the role of the _dictatorial choice function_
in Abreu and Matsushima (1992). Each transfer here can be made small enough so
that the overall transfer can be bounded below any preselected $\varepsilon$.
In what follows, we refer to this extracted profile of types as $t^{0}$ and to
agent $i$’s component of $t^{0}$ as $t_{i}^{0}$.

After achieving extraction, we proceed towards the goal of implementing the
social choice function. The steps taken are essentially identical to those in
Abreu and Matsushima (1992). Agents are asked for $J$ additional reports of
their type, denoted $(t_{i}^{j})_{j=1,2,..,J}$ in what follows. Each profile
of reports determines the outcome with a probability of $\frac{1}{J}$, but the
following penalties are applied. To the first agent $i$ who deviates in their
report $t_{i}^{j}$ from $t_{i}^{0}$, a penalty is applied which is large
enough to dominate the incentive from affecting the outcome with a probability
of $\frac{1}{J}$ but not so large as to incentivize lying in $t^{0}$. That
such a balance can be achieved can be deduced from the fact that the designer
can choose $J$ to be as large as required to reduce the incentive to affect
the outcome. Then, no agent wants to be the first to deviate from the truthful
report in $t^{0}$ and implementation obtains while the penalties remain
switched off.

This mechanism however inherits some of the well known critiques of the Abreu-
Matsushima type of mechanisms, most notably that it requires a high depth of
reasoning, involves a fairly complex message space, and is more vulnerable to
renegotiation (than say the mechanism proposed in the proof of Theorem 1)
owing to the use of small transfers.

##  7 Related Literature

In this section, we discuss our paper’s results alongside some other related
papers, to provide further insight into our contributions.

An early reference in the field of mechanism design with evidence is Green and
Laffont (1986) who study the principal-agent problem when the agent cannot
manipulate the truth arbitrarily. This corresponds to a notion of evidence -
an agent, by presenting messages which are only available to her in a certain
set of states, can prove that the true state is within that set. Early
contributions in the field of game theory and evidence include Milgrom (1981),
Grossman (1981) and Dye (1985). More recent papers involving mechanism design
include Glazer and Rubinstein (2004), Glazer and Rubinstein (2006), Bull and
Watson (2007), Deneckere and Severinov (2008), Hart, Kremer, and Perry (2017),
and Ben-Porath, Dekel, and Lipman (2019). Ben-Porath, Dekel, and Lipman (2021)
study a setup involving stochastic evidence. While we assume that agents are
endowed with evidence to begin with, Ben-Porath, Dekel, and Lipman (2021)
study the process of evidence acquisition and the value of commitment. In
addition, they focus on partial implementation whereas our focus is on full
implementation.

Ben-Porath and Lipman (2012), Kartik and Tercieux (2012), and Banerjee, Chen,
and Sun (2021) study full implementation with hard evidence as well. While
Ben-Porath and Lipman (2012) and Banerjee, Chen, and Sun (2021) explictly
study hard evidence, Kartik and Tercieux (2012) model hard evidence within
their more general costly evidence framework when articles of evidence are
constrained to be either costless or infinitely costly. Specifically, in
Banerjee, Chen, and Sun (2021) we provide a direct mechanism to fully
implement SCFs in mixed strategies with two or more agents. The chief addition
to this line of inquiry in Ben-Porath and Lipman (2012) and Banerjee, Chen,
and Sun (2021) that the present paper contributes is uncertainty in the
dimension of evidence. We are able to provide a finite mechanism that fully
implements in mixed-strategy equilibria, but need an indirect mechanism to
achieve this goal.999In a classical setting with preference variation and no
evidence, Chen, Kunimoto, Sun, and Xiong (2022) also provides a finite
(indirect) mechanism for mixed-strategy implementation. It focuses on a
complete-information setting however. Restricting attention to direct
mechanisms, Peralta (2019) establishes necessary and sufficient conditions for
full Bayesian implementation with uncertain evidence; however, he also points
out that the restriction to direct mechanisms entails loss of
implementability.

Turning away from evidence, Jackson (1991) is a seminal paper in the theory of
Bayesian implementation, focusing on exploiting preference variation under
incomplete information to implement SCFs. While focusing on pure strategies,
it suggests that looking into mixed strategies is important. Serrano and Vohra
(2010) indeed extend the analysis in Jackson (1991) to mixed strategies. The
mechanisms in Jackson (1991) use modulo games and those in Serrano and Vohra
(2010) use integer games. In our setup, preference variation does not
necessarily exist and yet our implementation notion is robust to preference
variation. We present in this paper, to our knowledge, the first mechanism in
the literature that achieves implementation in a finite mechanism in a
Bayesian setting which explicitly accounts for mixed-strategy equilibrium.

##  Appendix A Appendix

###  A.1 Connection to Ben-Porath and Lipman (2012)

Ben-Porath and Lipman (2012) use a notion of nomenclature to associate
articles of evidence with subsets of the state space. In essence, an article
of evidence is associated with the set of states in which it occurs. A natural
generalization to the setting we study here would be to associate an article
of evidence with the set of states in which it occurs _with positive
probability_. When probability distributions are degenerate (so that we have a
deterministic evidence setting), it is clear that only one collection may
occur with positive (and indeed unit) probability. We denote this collection
by $E_{i}(s)$. With this notion of nomenclature, we state the analogous
conditions from Ben-Porath and Lipman (2012) below.

  1. 1.

(e1)$\ \forall e_{i}\in E_{i}(s)$, $s\in e_{i}$

  2. 2.

(e2) $e_{i}\in E_{i}(s)\implies e_{i}\in E_{i}(s^{\prime})$ for every
$s^{\prime}\in e_{i}$.

The following proposition proves that (se1) and (se2) are indeed
generalizations of (e1) and (e2).

###### Proposition 1

If $p$ is degenerate, then (se1) and (se2) are identical to (e1) and (e2)
respectively.

Proof. First, consider some $e_{i}$ such that $s\notin e_{i}$. Then, any
collection $E_{i}$ containing $e_{i}$ refutes $s$. From se1 therefore,
$p_{i}(s)(E_{i})=0$ for any $E_{i}\ni e_{i}$. Then, $E_{i}\neq E_{i}(s)$,
whereupon we have obtained that if $s\notin e_{i}$, then $e_{i}\notin
E_{i}(s)$, which is (e1). Thus, (se1) implies (e1).

Next, suppose $E_{i}\downarrow s$. Then, $\exists e_{i}\in E_{i}$ such that
$s\notin e_{i}$. From (e1), $e_{i}\notin E_{i}(s)$, so that
$p_{i}(s)(E_{i})=0$, which establishes (se1). Therefore, (e1) implies (se1) as
well.

Now, we turn to (se2). Consider a pair of states $s$ and a collection $E_{i}$
such that $E_{i}\not\downarrow s^{\prime}$. Notice that under degenerate
probabilities, $p_{i}(s^{\prime})(E_{i}^{\prime})>0\implies
E_{i}^{\prime}=E_{i}(s^{\prime})$ and $p_{i}(s)(E_{i})>0\implies
E_{i}=E_{i}(s)$, so that (se2) translates to the following: If $\forall
e_{i}\in E_{i}(s)$, if $s^{\prime}\in e_{i}$, then $E_{i}(s^{\prime})\supseteq
E_{i}(s)$. Now, consider any $e_{i}\in E_{i}(s)$ such that $s^{\prime}\in
e_{i}$. Then, $E_{i}(s^{\prime})\supseteq E_{i}(s)\implies e_{i}\in
E_{i}(s^{\prime})$, which establishes (e2).

Finally, suppose $E_{i}\not\downarrow s^{\prime}$ and $p_{i}(s)(E_{i})>0$.
Under degenerate probabilities, this yields $E_{i}(s)\not\downarrow
s^{\prime}$, so that $\forall e_{i}\in E_{i}(s)$, $s^{\prime}\in e_{i}$. From
(e2), $e_{i}\in E_{i}(s^{\prime})$. Since this is true for all $e_{i}$, we
have $E_{i}(s^{\prime})\supseteq E_{i}(s)$, which is identical to (se2) under
degenerate probabilities. We have, therefore established that (se1) and (se2)
correspond to (e1) and (e2) under degenerate probabilities.

Next, we consider the following question: Since articles can be named
according to the subset of states in which they occur with positive
probability, does it suffice to allow an agent to reveal a “most informative”
article of evidence rather than presenting an entire collection? More
precisely, consider the following example evidence structure:

State/Agent | A | B
---|---|---
$U$ | $\\{\\{L,M,H,U\\}\\}$ | $\\{\\{L,M,H,U\\}\\}$
$H$ | $0.3\times\\{\\{L,M,H,U\\},\\{M,H\\}\\}+0.7\times\\{\\{L,M,H\\},\\{M,H\\}\\}$ | $\\{\\{L,M,H,U\\}\\}$
$M$ | $0.5\times\\{\\{L,M,H,U\\},\\{M,H\\}\\}+0.5\times\\{\\{L,M,H\\},\\{M,H\\}\\}$ | $\\{\\{L,M,H,U\\}\\}$
$L$ | $\\{\\{L,M,H\\},\\{L,M,H,U\\}\\}$ | $\\{\\{L,M,H,U\\}\\}$

In both states $M$ and $H$, agent A, the only agent with evidence variation
always has the article $\\{M,H\\}$ and this is the most informative article
which is available to her. If we were to only allow her to present one article
of evidence, then there would be a perfect deception in both directions
between the states M and H so that we would not be able to distinguish them
using any mechanism. However, if we were to allow the submission of entire
collections of evidence, then there is no perfect deception from state M to H
(the article $\\{L,M,H\\}$ is not available often enough) and no perfect
deception from state H to M (the article $\\{L,M,H,U\\}$ is not available
often enough). Therefore, we can distinguish between these states. Thus, there
is a loss of generality when restricting attention to the most informative
article of evidence. In a deterministic evidence setting though, this
restriction is without loss of generality, as can be seen in both Ben-Porath
and Lipman (2012) and Banerjee, Chen, and Sun (2021).

###  A.2 NPPD vs NPD and Stochastic Measurability

In this section, we demonstrate that NPPD is strictly stronger than Stochastic
Measurability and strictly weaker than NPD. To see that NPPD is strictly
stronger than Stochastic Measurability, consider the example below.

State/Agent | A | B
---|---|---
$U$ | $0.1\times\\{\\{L,M,H,U\\}\\}$ | $\\{\\{L,M,H,U\\}\\}$
| $+0.9\times\\{\\{L,M,H,U\\},\\{M,H,U\\},\\{H,U\\}\\}$ |
$H$ | $0.1\times\\{\\{L,M,H,U\\},\\{M,H,U\\}\\}$ | $\\{\\{L,M,H,U\\}\\}$
| $+0.9\times\\{\\{L,M,H,U\\},\\{M,H,U\\},\\{H,U\\}\\}$ |
$M$ | $0.5\times\\{\\{L,M,H,U\\},\\{M,H,U\\}\\}+0.5\times\\{\\{L,M,H,U\\}\\}$ | $\\{\\{L,M,H,U\\}\\}$
$L$ | $\\{\\{L,M,H,U\\}\\}$ | $\\{\\{L,M,H,U\\}\\}$

Clearly, $U$ is nonrefutable at $H$. Consider the deception at state $H$ given
by

$\alpha_{A}(H,\\{\\{L,M,H,U\\},\\{M,H,U\\}\\})=(U,\\{\\{L,M,H,U\\}\\})\text{;}$
$\alpha_{A}(H,\\{\\{L,M,H,U\\},\\{M,H,U\\},\\{H,U\\}\\})=(U,\\{\\{L,M,H,U\\},\\{M,H,U\\},\\{H,U\\}\\}).$

While the SCF satisfies stochastic measurability, this is a pure-perfect
deception.

To see that NPPD is strictly weaker than NPD, we refer back to the example in
Section 2. We reproduce the evidence structure below:

State | Evidence (Firm A)
---|---
$H$ | $0.6\times\\{\\{M,H\\},\\{L,M,H\\}\\}+0.4\times\\{\\{L,M,H\\}\\}$
$M$ | $0.4\times\\{\\{M,H\\},\\{L,M,H\\}\\}+0.6\times\\{\\{L,M,H\\}\\}$
$L$ | $\\{\\{L,M,H\\}\\}$

It is easy to see that there is no pure-perfect deception in the above example
- at $H$, the type $\\{\\{M,H\\},\\{L,M,H\\}\\}$ must present all their
evidence, as type $\\{\\{L,M,H\\}\\}$ does not have enough evidence to mimic
$\\{\\{M,H\\},\\{L,M,H\\}\\}$ at $M$, but then we induce too much probability
(0.6 instead of 0.4) on $\\{\\{M,H\\},\\{L,M,H\\}\\}$. This demonstrates that
NPPD is strictly weaker than NPD.

###  A.3 Proof of Theorem 2

The necessity of NPPD stems from arguments similar to those for the proof of
necessity of NPD for mixed implementation. Sufficiency is established by
referring to the mechanism used in the proof of Theorem 1. With the exception
of the bets, the rest of the mechanism remains identical. Note that Claims 1
and 2 make no use of either the condition NPD or nontrivial randomization by
agents. Further, Claims 1 and 2 imply that there is no equilibrium where
agents present refutable lies. This leaves us with profiles consistent with
nonrefutable lies.

So suppose agents present a profile consistent with a nonrefutable lie
$s^{\prime}$. In contrast to the arguments in Section 4.2, where it was
sufficient for an agent to inform the designer of the true state, in this
paradigm, depending on the strategy profile, it is possible for different
evidence collections to be low or high in probability relative to the expected
probabilities in state $s^{\prime}$. Therefore, it is impossible for the
designer to place an appropriate bet if she is informed only of the true
state. Since $S$ and $\mathbb{E}$ are finite, the number of pure deceptions is
finite, since any pure deception profile is a map
$\alpha:S\times\mathbb{E}\rightarrow$ $S\times\mathbb{E}$. Therefore, they can
be identified with numbers from $1$ through $Z$ where $Z$ is the total number
of possible pure deceptions.

We augment the message space of the base mechanism by adding the strategy
identifier $z\in(1,2,..,Z)$. Once informed of the deception identifier, the
designer can identify an agent $i$ and a pair of collections $E_{i}^{\prime}$
and $E_{i}^{\prime\prime}$ such that
$p_{\alpha_{i}(s)}(E_{i}^{\prime})<p_{i}(s^{\prime})(E_{i}^{\prime})$ and
$p_{\alpha_{i}(s)}(E_{i}^{\prime\prime})>p_{i}(s^{\prime})(E_{i}^{\prime\prime})$
where $\alpha_{i}$ is the pure deception being played by agent $i$. Then,
there are numbers $\gamma<0$ and $\delta>0$ such that (i) $\gamma\times
p_{\alpha_{i}(s)}(E_{i}^{\prime})+\delta\times
p_{\alpha_{i}(s)}(E_{i}^{\prime\prime})>0$ and (ii) $\gamma\times
p(s^{\prime})(E_{i}^{\prime})+\delta\times
p(s^{\prime})(E_{i}^{\prime\prime})>0$. These numbers $\gamma$ and $\delta$
form the bets in this setting. It is profitable to place a bet because of
inequality (i). The rest of the analysis remains the same as earlier, in that
the bet induces evidence submission and triggers a realignment through Lemma
2. Therefore, agents must present truthful reports and we obtain
implementation. Note that there are no bets in equilibrium as betting against
the truth yields losses (from inequality (ii)).

###  A.4 Proof of Theorem 3

The reader will recall that higher-order measurability requires that the
social choice function $f$ be measurable on a partition of $T$ where each cell
of the partition is such that if $t$ and $t^{\prime}$ belong to the same cell,
then each agent has the same belief hierarchy in both $t$ and $t^{\prime}$. We
will show that higher-order measurability is necessary for rationalizable
implementation with arbitrarily small transfers regardless of the mechanism in
use. Accordingly, fix a mechanism $\mathcal{M}=(M,g,\tau)$.

A general type space model (see for instance Penta (2012)) is defined as
$\mathcal{T}=(T_{i},\hat{\theta}_{i},q_{i})_{i\in\mathcal{I}}$. The function
$\hat{\theta}_{i}$ maps each type to a payoff type. A payoff type consists of
any constituent component of an agent’s type which affects how she evaluates
an allocation. In general, such models assume that all the actions are
available to the agent in each state. In our case though, evidence is
involved, which may vary in its availability with the state. Recalling that we
work with utilities which are bounded by $1$ dollar, we associate the
following cost structure with evidence in order to model evidence
availability. Suppose the mechanism $\mathcal{M}$ induces a maximum transfer
of $\bar{U}$. If an agent $i$ of type $t_{i}$ presents only such articles as
are available to her in order to obtain an allocation $a$ and transfer
$\tau_{i}$, then her utility is given by $u_{i}(a,\tau_{i},t)$. If an agent
“presents” an unavailable article of evidence to do the same, her utility is
given by $u_{i}(a,\tau_{i},t)-2\bar{U}-1$. Since it is never worthwhile to
obtain an outcome if it involves a $2\bar{U}-1$ dollar cost in order to do so,
an agent never does so, so that we have effectively modelled evidence
availability. Further, we avoid depending on preference variation for
implementation, so that $u_{i}(a,\tau_{i},t)=u_{i}(a,\tau_{i},t^{\prime})$
$\forall t,t^{\prime}\in T$, i.e. preferences are constant. With these two
restrictions then, only evidence is payoff relevant, so that in our case,
$\hat{\theta}_{i}:T_{i}\rightarrow\mathbb{E}_{i}$, so that
$\hat{\theta}_{i}(t_{i})=\hat{E}_{i}(t_{i})$. Then, a general type space model
yields our model
$\mathcal{T=(}T_{i},\hat{E}_{i},q_{i})_{{}_{i\in\mathcal{I}}}$.

That higher-order measurability is necessary for implementation in
rationalizable strategies in then immediate from Proposition 2 in Penta (2012)
\- if the set of rationalizable strategies is identical for each type of each
agent, then different outcomes cannot be achieved in different states.
Alternately, any profile of strategies that is rationalizable at $t$ is also
rationalizable at $t^{\prime}$ if
$\hat{\pi}_{i}^{k}(t_{i})=\hat{\pi}_{i}^{k}(t_{i}^{\prime})$ for all $k$.

Now, we establish that the setup we worked with earlier can be obtained as a
(further) special case of the model in Section 6. First, we set
$T_{i}=S\times\mathbb{E}_{i}$ so that the type of each agent is defined.
$\hat{E}_{i}(s,E_{i})$ is therefore simply given by $E_{i}$. Note that $p$ was
defined as a prior in the previous setting, whereas here $q_{i}$ represents a
posterior belief once an agent is informed of her type. Since evidence is
uncorrelated, we have

$q_{i}(s_{i},E_{i})((s_{j},E_{j}))_{j\neq
i}=\left\\{\begin{tabular}[]{ll}$\Pi_{j\neq i}p_{j}(s)(E_{j})$,&if
$s=s_{i}=s_{j}\forall j\neq i$\\\ $0$&otherwise.\end{tabular}\right.$

The map $\hat{\theta}_{i}$ now maps $S\times\mathbb{E}_{i}$ to
$\mathbb{E}_{i}$ as we continue to assert constant preferences and with the
aforementioned cost structure, only evidence is payoff relevant. The social
choice function is defined as follows.

$f((s_{i},E_{i})_{i\in\mathcal{I}})=\left\\{\begin{tabular}[]{ll}$f(s)$,&if
$s=s_{i}$ $\forall i\in\mathcal{I}$\\\
$f(s_{1})$&otherwise.\end{tabular}\right.$

This definition does not lead to difficulties since only such profiles occur
with positive probability where $s_{i}=s$ for all $i$. Therefore, we have
derived the previous setup as a simplification of this one.

Now we will prove that evidence incentive compatibility is necessary for
rationalizable implementation with arbitrarily small transfers. If $f$ is
rationalizably implementable with arbitrarily small transfers, there is a
mechanism $\mathcal{M}=(M,g,\tau)$ which implements $f$ such that for any
profile of rationalizable messages $m\in R^{G}\left(t\right)$ of the game
$G\left(\mathcal{M},\mathcal{T},u\right)$, we have $g(m)=f(t)$. Further,
$\mathcal{M}$ can be chosen so that $|\tau_{i}(m)|\leq\frac{\varepsilon}{2}$
for every message profile $m$. The game
$G\left(\mathcal{M},\mathcal{T},u\right)$ must also have a Bayesian Nash
equilibrium. Such an equilibrium also must have outcome $f(t)$ (transfers
notwithstanding), since every Nash Equilibrium survives the iterated
elimination of strictly dominated strategies and thus constitutes a
rationalizable message profile. Suppose this equilibrium is given by $\sigma$.
Consider an alternate mechanism $\mathcal{M}^{\prime}$ where agents merely
report their type $t_{i}$ including the evidence and the designer plays their
strategy from $\sigma$ on their behalf. The outcome and transfers are chosen
to be identical to those induced by $\mathcal{M}$. Such a mechanism must have
a truth-telling equilibrium, say $\sigma^{\prime}$. That is, for each agent
$i$, and each type $t_{i}$, this type must have the incentive to truthfully
report her type $t_{i}$ if she knows others are reporting their type
accurately. That is,

$\sum_{t_{-i}\in
T_{-i}}q_{i}(t_{i})(t_{-i})u_{i}(f(t_{i},t_{-i}),\tau_{i}(t_{i},t_{-i}),(t_{i},t_{-i}))\geq\sum_{t_{-i}\in
T_{-i}}q_{i}(t_{i})(t_{-i})u_{i}(f(t_{i}^{\prime},t_{-i}),\tau_{i}(t_{i}^{\prime},t_{-i}),(t_{i},t_{-i}))\text{.}$

The above must be satisfied with for all $\varepsilon>0$. Then, taking limits
with $\varepsilon\rightarrow 0$, we obtain

$\sum_{t_{-i}\in
T_{-i}}q_{i}(t_{i})(t_{-i})\bar{u}_{i}(f(t_{i},t_{-i}),(t_{i},t_{-i}))\geq\sum_{t_{-i}\in
T_{-i}}q_{i}(t_{i})(t_{-i})\bar{u}_{i}(f(t_{i}^{\prime},t_{-i}),(t_{i}^{\prime},t_{-i}))\text{,}$

which shows that $f$ satisfies evidence incentive compatibility.

The sufficiency proof is by construction of an implementing mechanism.
Consider the following mechanism:

Message Space: $M_{i}=\mathbb{E}_{i}\times T_{i}\times T_{i}\times...\times
T_{i}$ ($\bar{k}+J+1$) times, where $\bar{k}$ is the minimum order of belief
at which any pair of states with different $f$-optimal outcomes can be
separated by some agent. A typical message for agent $i$ is denoted by
$m_{i}=(E_{i},(t_{i}^{0,k})_{k=1}^{\bar{k}+1},(t_{i}^{j})_{j=1}^{J})$.
Accordingly, $m=(m_{i})_{i\in\mathcal{I}}$ is a profile of messages.

Outcome: The outcome is given by $\frac{1}{J}\sum_{j=1}^{J}f(t^{j})$.

Transfers:

The mechanism uses the following transfers, which we document below. Let
$\beta$ is a small positive number. Define

$\tau_{i}^{1}\left(m\right)=\beta\times|E_{i}|\text{.}$

This transfer incentivizes agents to submit all their evidence. Further,
define

$\tau_{i}^{2,1}\left(m\right)=\beta\times[2\hat{\pi}_{i}^{1}(t_{i})(E_{-i})-\hat{\pi}_{i}^{1}(t_{i})\cdot\hat{\pi}_{i}^{1}(t_{i})]\text{;}$
$\tau_{i}^{2,k}\left(m\right)=\beta\times[2\hat{\pi}_{i}^{k}(t_{i}^{k})(\hat{\pi}_{-i}^{k-1}(t_{-i}^{k-1}),\hat{\pi}_{-i}^{k-2}(t_{-i}^{k-1}),...,\hat{\pi}_{-i}^{0}(t_{-i}^{k-1}))-\hat{\pi}_{i}^{k}(t_{i}^{k})\cdot\hat{\pi}_{i}^{k}(t_{i}^{k})],\forall
k=2,...,\bar{k}+1.$

This transfer is a set of proper scoring rules which incentivizes agents to
predict other agent’s lower order beliefs and their types using the report
$t_{i}^{k}$. Given the above transfer definitions, $\beta$ can be chosen to be
as small as required to meet any prescribed transfer bound $\varepsilon$. This
is critical, since these transfers are active for any profile of
rationalizable strategies.

From the above transfers, it is easy to see that the strategy that maximizes
agent $i$’s utility from $\tau^{1}$ and $\tau^{2}$ is to present all her
evidence and report truthfully in each $t_{i}^{0,k}$.

Given $\beta$, define as $\bar{\beta}_{i}$ the minimum loss in utility over
any type profile that agent $i$ endowed with any evidence can induce owing to
$\tau^{1}$ and $\tau^{2}$ by changing either her evidence report or her first
$\bar{k}+1$ type reports to be different from the truth.

Now, we define the transfers used to discipline the last $J$ reports, which
are used to set the outcome. The following transfer penalizes an agent for
being among the first deviants from $t^{0,\bar{k}+1}$.

$\tau_{i}^{3}\left(m\right)=\left\\{\begin{tabular}[]{ll}$-\bar{\tau}^{3}$,&if
$\exists j\in\\{1,..,J\\}$ s.t. $t_{i}^{j}\neq t_{i}^{\bar{k}+1}$ and
$t^{h}=t^{0,\bar{k}+1}$ $\forall h<j;$\\\ 0&otherwise.\end{tabular}\right.$

Finally, we define the following check between an agent’s report
$t_{i}^{0,\bar{k}+1}$ and $t_{i}^{j}$.

$\tau_{i,j}^{4}\left(m\right)=\left\\{\begin{tabular}[]{ll}$-\bar{\tau}^{4}$,&if
$t_{i}^{0,\bar{k}+1}\neq t_{i}^{j};$\\\ 0&otherwise.\end{tabular}\right.$

where $\bar{\tau}^{4}>0$. This transfer is repeated for every round.

We scale the transfers as follows. First, notice that for any given
$\varepsilon$, $\beta>0$ can be chosen so that the overall value of the
transfers $\tau^{1}$ and $\tau^{2}$ does not exceed $\varepsilon$. This fixes
each $\bar{\beta}_{i}$, and thereby $\min_{i}\bar{\beta}_{i}$. We now choose a
large enough number of rounds ($J$) such that
$\min_{i}\bar{\beta}_{i}>\frac{1}{J}$. This allows us to choose
$\bar{\tau}^{3}$ such that
$\min_{i}\bar{\beta}_{i}>\bar{\tau}^{3}>\frac{1}{J}$. Now, since
$\bar{\tau}^{4}$ is only required to be positive, a sufficiently small value
can be chosen so that
$\min_{i}\bar{\beta}_{i}>\bar{\tau}^{3}+J\bar{\tau}^{4}>\frac{1}{J}$.

Now, we will prove that this mechanism implements $f$ in rationalizable
strategies with arbitrarily small transfers. In the following proof, we denote
the true state by $t^{\ast}=(t_{i}^{\ast})_{i\in\mathcal{I}}$.

###### Claim 5

Each agent presents all her evidence, i.e. $\hat{E}_{i}(t_{i}^{\ast})$.

Proof. If not, the agent can improve her payoff by providing additional
articles of evidence due to the reward from $\tau^{1}$. There are no other
incentives which are affected by the provision of additional evidence.

###### Claim 6

Each agent $i$ only presents such reports in $(t_{i}^{0,k})_{k=1}^{\bar{k}+1}$
which induce the same $k^{th}$ order beliefs as $t_{i}$ for any
$k\leq\bar{k}+1$. Further, $f(t^{0,\bar{k}+1})=f(t)$.

Proof. From Claim 5, each agent presents all her evidence. Any report
$t_{i}^{0,k}$ for $k<\bar{k}+1$, only controls the agent’s payoff from
$\tau^{2}$ and therefore the only rationalizable report for any agent is to
present a report $t_{i}^{0,k}$ which induces the same belief as the agent’s
true type $t_{i}$. Any other report leads to a strictly lower payoff because
$\tau^{2}$ is a quadratic scoring rule and yields a unique maximum.

Consider the agent’s report $t_{i}^{0,\bar{k}+1}$. It controls the agent’s
payoff from $\tau^{2}$, $\tau^{3}$, and $\tau^{4}$ Changing
$t_{i}^{0,\bar{k}+1}$ leads to a loss of at least $\min_{i}\bar{\beta}_{i}$,
which by construction dominates gains from $\tau^{3}$ and $\tau^{4}$ (recall
that $\min_{i}\bar{\beta}_{i}>J\bar{\tau}^{4}+\bar{\tau}^{3}$), so that it is
not profitable to lie in $t_{i}^{0,\bar{k}+1}$. Higher-order measurability
then yields that the reports in $t^{0,\bar{k}+1}$ yield the correct cell of
the partition of $T$ to which $t$ belongs.

###### Claim 7

For any $j$, $t_{i}^{j}$ is the truth. Further, the mechanism implements and
for any profile of rationalizable messages $m$, $\tau_{i}^{3}\left(m\right)=0$
and $\tau_{i}^{4}\left(m\right)=0$ for all $i$.

Proof. The proof is by induction. Consider any report $t_{i}^{j}$, $j\geq 1$
and suppose agents report truthfully all the way up to the ($j-1$)th message.
If all agents $k\neq i$ report truthfully in $t^{j}$, then evidence incentive
compatibility ensures that truth-telling is among the best responses for agent
$i$. The small penalty from $\tau^{4}$ makes it the unique best response since
from Claim 6, $t^{0,\bar{k}+1}$ is true. If other agents $k\neq i$ also lie in
$t^{j}$, then the truth yields the agent a profit of $\bar{\tau}^{3}$ from
$\tau^{3}$, which dominates any gains from affecting the outcome with a
probability $\frac{1}{J}$, since $\bar{\tau}^{3}>\frac{1}{J}$. Therefore, such
a message is not rationalizable. Therefore, it is rationalizable to present
the truth in $t^{j}$. Then, the transfers $\tau^{3}$ and $\tau^{4}$ are
clearly inactive. Further, if every $t^{j}$ is true, then the outcome is
chosen correctly.

## References

  * (1)
  * Abreu and Matsushima (1992) Abreu, D., and H. Matsushima (1992): “Virtual Implementation in Iteratively Undominated Strategies: Incomplete Information,” _mimeo_.
  * Banerjee, Chen, and Sun (2021) Banerjee, S., Y.-C. Chen, and Y. Sun (2021): “Direct Implementation with Evidence,” _Working Paper, https://arxiv.org/abs/2105.12298_.
  * Ben-Porath, Dekel, and Lipman (2019) Ben-Porath, E., E. Dekel, and B. L. Lipman (2019): “Mechanisms with evidence: Commitment and robustness,” _Econometrica_ , 87(2), 529–566.
  * Ben-Porath, Dekel, and Lipman (2021) (2021): “Mechanism Design for Acquisition of/Stochastic Evidence,” _Working Paper_.
  * Ben-Porath and Lipman (2012) Ben-Porath, E., and B. L. Lipman (2012): “Implementation with partial provability,” _Journal of Economic Theory_ , 147(5), 1689–1724.
  * Bull and Watson (2007) Bull, J., and J. Watson (2007): “Hard evidence and mechanism design,” _Games and Economic Behavior_ , 58(1), 75–93.
  * Chen, Kunimoto, Sun, and Xiong (2022) Chen, Y.-C., T. Kunimoto, Y. Sun, and S. Xiong (2022): “Maskin meets abreu and matsushima,” _Theoretical Economics, forthcoming_.
  * Crémer and McLean (1988) Crémer, J., and R. P. McLean (1988): “Full extraction of the surplus in Bayesian and dominant strategy auctions,” _Econometrica: Journal of the Econometric Society_ , pp. 1247–1257.
  * Dekel, Fudenberg, and Morris (2007) Dekel, E., D. Fudenberg, and S. Morris (2007): “Interim correlated rationalizability,” _Theoretical Economics_.
  * Deneckere and Severinov (2008) Deneckere, R., and S. Severinov (2008): “Mechanism design with partial state verifiability,” _Games and Economic Behavior_ , 64(2), 487–513.
  * Dye (1985) Dye, R. A. (1985): “Disclosure of nonproprietary information,” _Journal of accounting research_ , pp. 123–145.
  * Glazer and Rubinstein (2004) Glazer, J., and A. Rubinstein (2004): “On optimal rules of persuasion,” _Econometrica_ , 72(6), 1715–1736.
  * Glazer and Rubinstein (2006) (2006): “A game theoretic approach to the pragmatics of debate: An expository note,” in _Game Theory and Pragmatics_ , pp. 248–262. Springer.
  * Green and Laffont (1986) Green, J. R., and J.-J. Laffont (1986): “Partially verifiable information and mechanism design,” _The Review of Economic Studies_ , 53(3), 447–456.
  * Grossman (1981) Grossman, S. J. (1981): “The informational role of warranties and private disclosure about product quality,” _The Journal of Law and Economics_ , 24(3), 461–483.
  * Hart, Kremer, and Perry (2017) Hart, S., I. Kremer, and M. Perry (2017): “Evidence games: Truth and commitment,” _American Economic Review_ , 107(3), 690–713.
  * Jackson (1991) Jackson, M. O. (1991): “Bayesian implementation,” _Econometrica: Journal of the Econometric Society_ , pp. 461–477.
  * Jackson (1992) Jackson, M. O. (1992): “Implementation in undominated strategies: A look at bounded mechanisms,” _The Review of Economic Studies_ , 59(4), 757–775.
  * Kartik and Tercieux (2012) Kartik, N., and O. Tercieux (2012): “Implementation with evidence,” _Theoretical Economics_ , 7(2), 323–355.
  * Mertens and Zamir (1985) Mertens, J.-F., and S. Zamir (1985): “Formulation of Bayesian analysis for games with incomplete information,” _International journal of game theory_ , 14(1), 1–29.
  * Milgrom (1981) Milgrom, P. R. (1981): “Good news and bad news: Representation theorems and applications,” _The Bell Journal of Economics_ , pp. 380–391.
  * Penta (2012) Penta, A. (2012): “Higher order uncertainty and information: Static and dynamic games,” _Econometrica_ , 80(2), 631–660.
  * Peralta (2019) Peralta, E. (2019): “Bayesian implementation with verifiable information,” _Games and Economic Behavior_ , 116, 65–72.
  * Serrano and Vohra (2010) Serrano, R., and R. Vohra (2010): “Multiplicity of mixed equilibria in mechanisms: A unified approach to exact and approximate implementation,” _Journal of Mathematical Economics_ , 46(5), 775–785.