Frédéric Koessler
email: frederic.koessler@psemail.eu

Eduardo Perez-Richet
email: eduardo.perez@sciencespo.fr

Elhanan Ben Porath

Jeanne Hagenbach

Johannes Hörner

Matt Jack- Son

Emir Kamenica

Navin Kartik

David Levine

Ludovic Renou

Phil Reny

Olivier Tercieux

Evidence Reading Mechanisms *

Keywords: Implementation, Mechanism Design, Evidence, Hard Information, Commitment. JEL classification: C72; D82

In an environment with privately informed agents who can produce evidence, we study implementation of a social choice function by reading mechanisms: mechanisms that simply apply the social choice function to a consistent interpretation of the evidence. We provide sufficient conditions on the social choice function and the evidence structure for ex post implementability by such mechanisms. If the first-best policy of a mechanism designer satisfies this condition, then its implementation by a reading mechanism does not require commitment. We show that with rich evidence structures, (i) a function that is implementable with transfers is also implementable with evidence but no transfer, (ii) under private value, the efficient allocation is implementable with budget balanced and individually rational transfers, and (iii) in single-object auction and bilateral trade environments with interdependent values, the efficient allocation is implementable with budget balanced and individually rational transfers.

Introduction

The usual mechanism design approach assumes cheap talk communication: messages are equally accessible to all types of agents, regardless of what they know. Under this assumption, a designer who wants to implement a contingent plan of action must be able to deter all possible lies. In this paper, following a thin but grounded tradition in the mechanism design literature, we assume that privately informed agents have access to costless evidence, i.e., to type-dependent sets of messages (e.g., physical documents certifying endowments, costs, product characteristics, incomes, or health conditions). 1 We provide sufficient conditions for implementability by simple mechanisms and show that they apply to familiar environments like auctions and bilateral trade. These conditions also allow us to characterize evidence structures such that a social choice function that can be implemented with transfers can also be implemented with evidence but no transfer.

We focus on reading mechanisms. Such mechanisms simply apply the contingent plan of action of the designer (the social choice function) to a reading of the evidence, that is, a consistent interpretation of each message profile. To justify this approach think of the social choice function as the first-best plan of action of the designer, which she would implement if she knew the agents' types. The use of a reading mechanism ensures that, for all preferences of the designer that are compatible with her first-best, the actions mandated by the mechanism are optimal given beliefs that are consistent with the evidence provided by the agents. In particular, if her first-best is implementable by a reading mechanism with accurate readings on the equilibrium path, then, regardless of her particular preferences, it can be implemented as a perfect Bayesian equilibrium of the disclosure game in which the designer would choose her action as mandated by the mechanism after having observed the agents' reports. Hence, reading mechanisms are immune against a lack of commitment by the designer. In addition, they are, by construction, simple and deterministic.

To illustrate the restrictions imposed by reading mechanisms, consider the following simple example with a single agent with two possible types, t 1 and t 2 , and four alternatives, a 0 , a ′ 0 , a 1 and a 2 . The set of messages available to the agent is {m 0 , m 1 } when her type is t 1 and {m 0 , m 2 } when her type is t 2 , so her type is fully certifiable. Still, the agent can decide not to certify any information by sending the message m 0 , which provides no evidence. The utilities of the designer (first coordinate) and the agent (second coordinate) as a function of the alternative chosen by the designer and the type of the agent are given by the following table:

a 0 a ′ 0 a 1 a 2 t 1 0, -2 0, 1 2, 0 1, 2 t 2 0, 1 0, -2 1, 2 2, 0
The first-best of the designer (f (t 1 ) = a 1 , f (t 2 ) = a 2 ) can be implemented with the following mechanism: choose alternative a 1 after message m 1 , choose alternative a 2 after message m 2 , and randomize [START_REF] Sher | Price Discrimination Through Communication[END_REF], [START_REF] Hart | Evidence Games: Truth and Commitment[END_REF], [START_REF] Strausz | Mechanism Design with Partially Verifiable Information[END_REF]. [START_REF] Kartik | Implementation with Evidence[END_REF] consider Nash implementation, whereas Ben-Porath and [START_REF] Ben-Porath | Implementation with Partial Provability[END_REF] consider sub-game perfect implementation. [START_REF] Ben-Porath | Optimal allocation with costly verification[END_REF] consider costly information verification.

uniformly between alternatives a 0 and a ′ 0 after message m 0 . This is not a reading mechanism, because a reading mechanism should "read" the message m 0 as coming from either t 1 or t 2 , and then apply the first-best alternative (i.e., a 1 or a 2 ) to this reading. Hence, contrary to the above mechanism, a reading mechanism is necessarily deterministic and credible for the designer whatever her preference compatible with her first-best. In this example, the first-best cannot be implemented by a reading mechanism.

Implementation by an accurate reading mechanism requires two intuitive conditions. First, as it is the case for any mechanism with evidence, the evidence structure must be sufficiently rich to provide each informational type of each agent with a message that conveys her information. This message must be such that no other informational type of the same agent would be both willing to and capable of using the same message. We call this the evidence base condition. Second, the designer must be able to deter participants from using other messages than those in the evidence base. Her only lever to do so is her reading of evidence. Thus, implementation is possible whenever the designer can have a skeptical and consistent interpretation of each participant's message. This is the case if the set of types that could have sent a given message admits a worst case type, that is a type that no other type for whom the message was available would have been willing to masquerade as. In the previous example, message m 0 has no worst case type, so the social choice function is not implementable by a reading mechanism.

In this paper, we will assume that the first condition, the evidence base condition, is always satisfied.

Whether this condition is satisfied or not depends on the evidence structure, agents' preferences, and on the social choice function that the designer would like to implement. However, it is always satisfied under the assumption that agents are able to certify their type and in particular if everything is certifiable. Our focus is to study precisely when the second condition, the existence of a worst case type, is satisfied.

The literature on evidence, or hard information, starts with the sender-receiver models of [START_REF] Grossman | Disclosure Laws and Takeover Bids[END_REF], [START_REF] Grossman | The Informational Role of Warranties and Private Disclosure about Product Quality[END_REF] and [START_REF] Milgrom | Good News and Bad News: Representation Theorems and Applications[END_REF]. One branch of the ensuing literature has tried to identify conditions that preclude the full disclosure result of the seminal papers [START_REF] Milgrom | Relying on the Information of Interested Parties[END_REF][START_REF] Shin | Disclosures and Asset Returns[END_REF][START_REF] Wolinsky | Information Transmission when the Sender's Preferences are Uncertain[END_REF][START_REF] Dziuda | Strategic Argumentation[END_REF]. More importantly for this paper, another branch has sought to extend the full revelation result to more general settings: Okuno-Fujiwara, Postlewaite, and Suzumura (1990) consider information disclosure preceding a game, while [START_REF] Seidmann | Strategic Information Transmission with Verifiable Messages[END_REF] and [START_REF] Giovannoni | Secrecy, Two-Sided Bias and the Value of Evidence[END_REF] consider sender-receiver games à la [START_REF] Crawford | Strategic Information Transmission[END_REF] and introduce the notion of worst case type which we use in this paper. [START_REF] Hagenbach | Certifiable Pre-Play Communication: Full Disclosure[END_REF] work with this notion to build a theory that includes and extends former full revelation results, and develop ideas that play an important role in this paper. [START_REF] Lipman | Robust Inference in Communication Games with Partial Provability[END_REF] give full revelation results in a different environment, with symmetrically informed senders and sequential communication.

The literature on mechanism design with evidence starts with [START_REF] Green | Partially Verifiable Information and Mechanism Design[END_REF]. In a principal agent model, they provide a necessary and sufficient condition on the evidence structure (the nested range condition) for a revelation principle to hold. [START_REF] Singh | Implementation with Partial Verification[END_REF] show how to implement social choice functions without this condition but with state-independent preferences in the allocation. [START_REF] Bull | Hard Evidence and Mechanism Design[END_REF], [START_REF] Deneckere | Mechanism Design with Partial State Verifiability[END_REF] and [START_REF] Strausz | Mechanism Design with Partially Verifiable Information[END_REF] extend the revelation principle to more general mechanism design setups and message structures, while [START_REF] Forges | Communication Equilibria with Partially Verifiable Types[END_REF] develop similar results for communication games. [START_REF] Glazer | On Optimal Rules of Persuasion[END_REF] and Glazer and Rubinstein (2006) consider the role of evidence in a simple persuasion problem in which an informed sender seeks to persuade an uninformed receiver to take an action that she only wishes to take in particular circumstances. [START_REF] Glazer | On Optimal Rules of Persuasion[END_REF] considers a mechanism in which the sender first declares her type, and then may be asked to produce evidence. They develop a linear programming approach that allows them to characterize an optimal mechanism which is of the claim and verify form, and show how the receiver can benefit from randomization at the verification stage. Closer to our paper, Glazer and Rubinstein (2006) assume that the sender directly sends evidence, so a mechanism is a persuasion rule that states which messages are deemed convincing by the receiver. They show that randomization is not needed, and provide a procedure to find an optimal persuasion rule. In both papers, the optimal mechanism is shown to be credible in the sense that the behavior of the sender and the receiver constitutes a perfect Bayesian equilibrium of an associated disclosure game (see also [START_REF] Sher | Credibility and Determinism in a Game of Persuasion[END_REF], 2014[START_REF] Hart | Evidence Games: Truth and Commitment[END_REF], Ben-Porath, Dekel, and Lipman, 2017).

With the exception of Ben-Porath et al., 2017, all the articles mentioned in the paragraph above assume that agents have state-independent preferences. Under this assumption, implementation with a reading mechanism is trivial once the evidence base condition is satisfied because the designer can punish an agent who does not use a message from the evidence base by choosing the least preferred action of the agent. Our contribution is to significantly relax the assumptions of these articles on preferences, by providing and applying general conditions for implementation by a reading mechanism.

However, we put strong requirements on evidence structures to obtain our results.

Ben-Porath et al., 2017 allow for type-dependent preferences, and show that the mechanism designer is equally well off whether or not she can commit, with or without robust incentive compatibility, and with or without randomization. By contrast with our approach, they do not put any restriction on the evidence structure and consider optimal mechanism design rather than implementation. They consider a restricted class of preferences, but in this respect comparison is difficult as their class of preferences can cover environments that give rise to masquerading cycles, which would be problematic in our environment, but fails to cover many situations without cycles that our results cover. Finally, the mechanism itself does not require commitment in our case, whereas they make the more subtle but weaker claim that there is a perfect Bayesian equilibrium that yields the same payoff to the principal as the optimal mechanism.

For simplicity, the main text only contains sufficient conditions for ex-post implementation. In the appendix, we present the analogue of our general results for interim implementation, and we provide necessary and sufficient conditions for interim and ex-post implementation under additional constraints.

The Model

There is a set N of n agents indexed by i, and a set of alternatives denoted by A. Each agent has a type t i which encodes her privately observed information. The set of possible realizations of this random variable is a finite set T i , and T = T 1 × • • • × T n is the set of type profiles. The utility of agent i when alternative a is implemented is u i (a; t), where t = (t 1 , • • • , t n ). We say that i has private values

if u i (a; t) is independent of t -i .
The evidence structure is defined by a finite message space M i , and a correspondence M i :

T i ⇒ M i
for each agent, where M i (t i ) is the set of messages available to agent i of type

t i . A subset S i ⊆ T i is certified by a message m i if M -1 i (m i ) = S i , where M -1 i (m i ) ≡ t i ∈ T i | m i ∈ M i (t i
) . S i is certifiable if there exists a message m i that certifies S i , that is, a message which is available to all the types in S i , and to none other. We say that the evidence structure M i , M i n i=1 satisfies own type certifiability if, for every agent i, and every t i ∈ T i , the set {t i } is certifiable.

The set of consistent interpretations of a message profile m, which we call the set of readings of m, is given by R

(m) = M -1 1 (m 1 ) × • • • × M -1 n (m n ) ⊆ T .
A reading of the evidence is a function ρ : M → T such that, for every m, ρ(m) ∈ R(m). It is an interpretation of each possible message profile as a type profile that is consistent with the evidence.

A social choice function is a mapping f : T → A. We consider only deterministic and static mechanisms. Since we take the evidence structure as given, a mechanism is then simply given by a deterministic outcome function g : M → A, which determines the alternative chosen by the designer following every possible message profile. In the game defined by the mechanism g(•), each agent chooses a messaging strategy µ i :

T i → M i such that µ i (t i ) ∈ M i (t i ).
A messaging strategy profile µ(•) is an ex post equilibrium of the game generated by the mechanism g(•) if, for every type profile t, every agent i, and every message

m i ∈ M i (t i ), u i g(µ(t)); t ≥ u i g(m i , µ -i (t -i )); t . A mechanism g(•)
ex post implements the social choice function f (•) if there exists an ex post equilibrium µ(•) of the game generated by g(•), such that g µ(t) = f (t) for every t ∈ T .

In the remainder of the paper, we will refer to ex post implementation simply as implementation, and to ex post equilibrium as equilibrium. 2

A mechanism g(•) is a reading mechanism if the alternative chosen by the mechanism designer is always consistent with the messages she receives and the social choice function she wants to implement; that is, for every message profile m ∈ M, there exists a type profile t ∈ R(m) such that g(m) = f (t).

The outcome function of a reading mechanism is completely pinned down by a reading of the evidence. Indeed, the outcome function g(•) of a reading mechanism can always be defined as the action f ρ(m) for some reading ρ(•). In such mechanisms, the designer only decides how to read the evidence, and that determines the outcome. To each reading corresponds a unique reading mechanism, but different readings may generate the same mechanism if the social function is not one to one.

We say that a reading mechanism ρ(•) implements f (•) with accurate readings (on the equilibrium path) if there exists a strategy profile µ(•) that forms an equilibrium of the game induced by ρ(•) and satisfies ρ(µ(t)) = t, for every t ∈ T .

The payoff for agent i to masquerade as another type s i when she is really of type t i , under a social choice function f (•), is given by the following masquerading payoff function:

v i (s i |t i ; t -i ) = u i f (s i , t -i ); t i , t -i .
These payoff functions represent the incentives of agents of given types to masquerade as other 2 Interim implementation is discussed in the appendix.

types. These incentives are determined by the social choice function and the preferences of the agents.

For each agent i, and each type profile t -i , they can be summarized by an oriented graph on T i , such that a type t i points to a type s i if t i has an incentive to masquerade as s i . Following [START_REF] Hagenbach | Certifiable Pre-Play Communication: Full Disclosure[END_REF], we call the relation that defines this graph a masquerade relation: we say that t i wants to masquerade as s i given t -i , denoted by t i

M[t -i ] ----→ s i , if and only if v i (s i |t i ; t -i ) > v i (t i |t i ; t -i ).
For a generic masquerade relation, we will use the notation -→. Notice that the masquerading relation is not necessarily transitive.

We can use this relation to define a worst-case type (given t -i ) for S i ⊆ T i as a type in S i that no other type in S i would like to masquerade as. We denote the set of such types as

wct(S i |t -i ) := s i ∈ S i | ∄ t i ∈ S i , t i M[t -i ] ----→ s i .
Graphically, a worst case type is a type in S i with no incoming arc from any other type in S i . The set of worst case type may be empty, or have more than one element. A masquerade relation

-→ on T i admits a cycle (t 1 i , . . . , t k i ) if t 1 i -→ t 2 i , t 2 i -→ t 3 i . . . , t k i -→ t 1 i .
Lemma 1 (Acyclicity and Worst Case Types). Let -→ be a masquerade relation on an individual type set T i . The following points are equivalent: (i) -→ is acyclic; (ii) Every nonempty subset S i ⊆ T i admits a worst case type; (iii) There exists a function w :

T i → Ê such that t i -→ s i ⇒ w(s i ) > w(t i ).
Proof. See Proposition 1 in [START_REF] Hagenbach | Certifiable Pre-Play Communication: Full Disclosure[END_REF].

If condition (iii) holds, we say that the masquerade relation is weakly represented by the function w(•). The representation is weak because we have an implication rather than an equivalence. If it were an equivalence, the masquerade relation would be a linear ordering of types, as with the utility representation of rational preferences.

An evidence base for agent i is a set of messages E i ⊆ M i such that there exists a one-to-one

function e i : T i → E i that satisfies e i (t i ) ∈ M i (t i ) and t i ∈ t -i ∈T -i wct M -1 i e i (t i ) t -i for every t i .
Hence, whether an evidence base is available for an agent is a property of a social choice function together with the evidence structure and the agent's preferences. Whenever own type certifiability is satisfied for an agent, her message correspondence admits an evidence base, regardless of preferences and the social choice function under consideration.

Example 1 (Evidence Base). As an illustration, consider a single privately informed agent i with three possible types, T i = {t 1 , t 2 , t 3 }, whose masquerade relation is given by t

1 -→ t 2 , t 2 -→ t 3 . The message correspondence M i (t 1 ) = {m 1 , m 3 , m 4 }, M i (t 2 ) = {m 1 , m 2 , m 4 }, M i (t 3 ) = {m 1 , m 2 , m 3 }
admits two evidence bases:

E i = {m 1 , m 2 , m 3 } and E i = {m 4 , m 2 , m 3 }. On the contrary, the message correspondence M i (t 1 ) = {m 1 , m 4 }, M i (t 2 ) = {m 1 , m 2 , m 3 , m 4 }, M i (t 3 ) = {m 1 , m 3 } does not admit
any evidence base because type t 3 has no message certifying an event for which it is a worst case type.

⋄

In the usual mechanism design formulation, the designer is allowed to design a space of messages that are accessible for free to all types. We have not done that because if such messages exist, they can be described in our framework. However, it is interesting to think about the introduction of such messages as a way to relax the evidence base condition in the characterization results of the next sections. To see that, suppose that the designer can create a set of additional messages for each agent that are accessible for free irrespective of types, and let Mi be the set of such messages for agent i. We consider the new evidence structure Mi = M i × Mi in which agent i of type t i can send any message in M i (t i ) × Mi . We refer to structures that can be obtained in this way as cheap talk completions of

M i , M i (•) n i=1 .
Proposition 1. There exists a cheap talk completion of M i , M i (•) n i=1 such that agent i has an evidence base if and only if, for every t i , there exists a message

m i ∈ M i such that t i ∈ t -i wct M -1 i (m i )|t -i .
Proof. Suppose that there exists a cheap talk completion with an evidence base for agent i. Since all types of i have access to the messages in Mi , the fact that t i has a message (m i , mi ) ∈ Mi for which it is a worst case type, implies that it is a worst case type of the set certified by m i ∈ M i (t i ). Suppose now that every type has a message such that it is a worst case type of the set certified by this message.

Then the only reason why an evidence base may not exist in the initial evidence structure would be that several types, say two types t i and s i , share a unique message m i for which they are worst case types. But then, allowing t i and s i to send message m i together with another cheap talk message, mi for t i , and m′ i for s i , would mean that, in the new structure obtained by completing with mi and m′ i , they each have a different message for which they are a worst case type.

Intuitively, when we allow for such completions, we will have an evidence base for agent i as long as any type of agent i has access to a piece of evidence that rules out any type s i that would like to masquerade as t i , under some profile t -i . In a framework where masquerading incentives are monotonic, as in the seller-buyer model of [START_REF] Milgrom | Good News and Bad News: Representation Theorems and Applications[END_REF], an agent of a given type (for example quality), must be able to rule out any lower type. This condition is related to the distinguishability condition3 in [START_REF] Kartik | Implementation with Evidence[END_REF], and to the incentive compatibility conditions derived in [START_REF] Deneckere | Mechanism Design with Partial State Verifiability[END_REF].

Sufficient Conditions for Implementation

The existence of an evidence base is important for implementation, because it allows the agents to convey their type with a message that no other type would both want and be able to imitate. For implementation to be possible, the second important requirement is for the designer to be able to punish deviators. With reading mechanisms, the designer can only punish a deviator with a consistent but skeptical reading, that is by attributing, for every realization of t -i , the piece of evidence m i sent by the deviator to a type t i which is a worst case type among the types that could have sent m i .

These intuitions are formalized in the following theorem. The proof is by construction, and is similar to the construction of a fully revealing equilibrium in [START_REF] Hagenbach | Certifiable Pre-Play Communication: Full Disclosure[END_REF]. The evidence base of an agent provides a natural candidate for her equilibrium strategy, so we construct a mechanism that reads each message from this evidence base accurately. Then we can complete the reading by interpreting each message profile comprising a unilateral deviation from equilibrium messages as the correct type profile for the non deviators, and a worst case type for the deviator. It is easy to see that such readings make unilateral deviation non profitable.

Theorem 1. There exists a reading mechanism that implements f (•) with accurate readings if the following conditions hold for every agent i: (i) For every t -i ∈ T -i , and every message m i ∈ M i , the set M -1 i (m i ) admits a worst case type given t -i ; (ii) M i (•) admits an evidence base.

Proof. We construct an accurate reading as follows. For every i, let e i : T i → M i be a one-to-one mapping associated with an evidence base of agent i. Consider a message profile m such that for every i = j, the message m i is in the range of e i . Then if m j is also in the range of e j , the reading of the message profile is ρ j (m j , m -j ) = e -1 j (m j ), and ρ i (m j , m -j ) = e -1 i (m i ) for every i = j. If on the other hand, m j is not in the range of e j , then ρ i (m j , m -j ) = e -1 i (m i ) for every i = j, whereas the message of agent j is interpreted as a type in wct M -1 j (m j )|ρ -j (m j , m -j ) . For any message profile m such that two or more agents deviate from (e i ) i∈N , any

Then the strategy profile e is fully revealing. It is also an (ex-post) equilibrium. Indeed if all agents but i use this strategy profile, then a message m i of agent i that does not belong to the range of e i is interpreted as a type in wct M -1 i (m i )|t -i for every t -i . Hence such a deviation does not benefit to agent i. Another possible deviation would be to send a message in the range of e i that differs from e i (t i ), call it e i (t ′ i ), when i's type is really t i . But then this message is interpreted as t ′ i regardless of t -i , and because t ′ i is a worst case type of e i (t ′ i ) given any t -i , agent i does not gain from the deviation if her true type is t i .

In order to do optimal mechanism design, that is to find the optimal contingent plan for a designer with given preferences, it is useful to be able to characterize the set of implementable contingent plans in a tractable manner. The conditions of Theorem 1 are not easy to deal with. Furthermore, it is easier to work with a condition that involves only the preferences of the agent, rather than the message structure. We can characterize the set of social choice functions that are implementable under any message structure that satisfies own type certifiability as being the set of social choice functions that generate acyclic masquerade relations. Lemma 1 provides an easy condition that is equivalent to acyclicity. In [START_REF] Hagenbach | Certifiable Pre-Play Communication: Full Disclosure[END_REF], we provide several easy to check conditions on masquerading payoffs that also ensure acyclicity.

Corollary 1. There exists a reading mechanism that implements f (•) with accurate readings under any message structure that satisfies own type certifiability if for every agent i and every t -i ∈ T -i the masquerade relation

M[t -i ] ----→ is acyclic on T i .
Proof. Own type certifiability ensures that the evidence base condition is satisfied. Then to implement f (•) it is sufficient to satisfy the worst case type condition of Theorem 1. By Lemma 1, we know that it is satisfied for every certifiable subset if and only if the masquerade relation is acyclic.

Evidence and Transfers

In this section, we assume that the agents have quasilinear preferences. The preferences of agent i over alternatives are still represented by the function u i (a; t), which we now interpret as the valuation of the agent. If agent i is given a transfer τ i , her utility is given by u i (a; t) + τ i .

In an evidence-free message structure, every mechanism is a reading mechanism. In this case, the following incentive compatibility conditions are necessary and sufficient conditions for implementability.

Definition 1 (Evidence-Free Incentive Compatibility). A social choice function satisfies ex post incentive compatibility if, for every t ∈ T , every agent i and every

s i ∈ T i v i (s i |t i , t -i ) ≤ v i (t i |t i , t -i ).
(EFIC)

When using transfers, the mechanism designer can modify the incentives of the agents. We will therefore consider ex post transfer functions τ i : T → R, and the corresponding modified masquerading

payoff V i (s i |t i ; t -i ) = v i (s i |t i ; t -i ) + τ i (s i ; t -i ).
We start with a simple example showing that reading mechanisms can sometimes achieve implementation in situations where transfers cannot.

Example 2 (Evidence 1 -Transfers 0). Consider a setup with one agent of two possible types t and t ′ , and an evidence structure that satisfies own type certifiability. The social choice function selects action a when the type is t, and action a ′ when the type is t ′ . The preferences of the agent are given by u(a, t) = u(a ′ , t ′ ) = 0, u(a ′ , t) = 2, u(a, t ′ ) = -1. Therefore t wants to masquerade as t ′ , but t ′ does not want to masquerade as t, hence the masquerade relation is acyclic, and the social choice function is implementable with evidence. It is not implementable with transfers, because any transfer that is sufficient to discourage t from claiming t ′ makes t ′ claim to be t. ⋄

In fact, every social choice function that is implementable with transfers can be implemented by a reading mechanism with accurate readings as long as the evidence base condition is satisfied. The intuition is simple: the worst case type associated with any subset of types is the type that would have received the highest transfer. To see that, note that if some other type, with a lower transfer, could obtain a better outcome by pretending to be this highest transfer type, then this type would be even more incentivized to claim being the highest transfer type under the transfer scheme because she would also get a higher transfer. But then, that would contradict the fact that the transfer scheme implements the social choice function. More precisely, the proof shows that the negative of the transfer function provides a weak representation of the masquerade relation, and then concludes by Lemma 1.

Theorem 2. If f (•) is implementable with transfers and no evidence, it is also implementable with no transfers by a reading mechanism with accurate readings under any evidence structure such that each M i (•) admits an evidence base. Furthermore, there exist social choice functions that are implementable with no transfers by a reading mechanism with accurate readings under any evidence structure such that each M i (•) admits an evidence base, but not with transfers and no evidence.

Proof. The social choice function is implementable with transfers and no evidence if and only if there exists (τ i ) n i=1 such that for every i, every t ∈ T , and every

s i ∈ T i , V i (s i |t i ; t -i ) satisfies (EFIC), i.e., V i (s i |t i ; t -i ) = v i (s i |t i ; t -i ) + τ i (s i ; t -i ) ≤ V i (t i |t i ; t -i ) = v i (t i |t i ; t -i ) + τ i (t i ; t -i ) or, equivalently, v i (s i |t i ; t -i ) -v i (t i |t i ; t -i ) ≤ τ i (t i ; t -i ) -τ i (s i ; t -i ). t i wants to masquerade as s i given t -i if and only if v i (s i |t i ; t -i ) -v i (t i |t i ; t -i ) > 0. From (EFIC), this implies τ i (t i ; t -i ) -τ i (s i ; t -i ) > 0, i.e., -τ i (s i ; t -i ) > -τ i (t i ; t -i ). Hence, -τ i (•; t -i ) is

Efficient Mechanism Design with Private Values

In this section, we consider the problem of implementing an efficient social choice function f (t) ∈ arg max a∈A i u i a; t and allow the mechanism designer to use both evidence and transfers. Given a social choice function f (•), an ex-post transfer scheme τ i for i = 1, . . . , n is individually rational if, for every agent i, and every type profile t, V i (t i |t i ; t -i ) = v i (t i |t i ; t -i ) + τ i (t) ≥ 0. It is budget balanced if, for every type profile t, i τ i (t) ≤ 0. It fully extracts surplus if, for every type profile

t, i τ i (t) = -i v i (t i |t i ; t -i ).
To make it possible to satisfy both individual rationality and budget balance, we assume that, for every type profile t, i v i (t i |t) ≥ 0.

Theorem 3. Assume private values and consider an efficient social choice function together with a transfer scheme such that an evidence base is available for each agent. Then, this social choice function and transfer scheme can be implemented by a reading mechanism with accurate readings. In particular, under own-type certifiability, the transfer scheme can be chosen to satisfy individual rationality and budget balance, and even extract full surplus.

Proof. The proof is related to the classical Vickrey-Clarkes-Groves mechanism. Let h i (t) = τ i (t)j =i u j f (t); t j denote what remains of agent i's transfer after subtracting her externality on other participants. Then i's incentive to masquerade as s i when her type is t i is given by

V i (s i |t i , t -i ) -V i (t i |t i , t -i ) = u i f (s i , t -i ); t i + j =i u j f (s i , t -i ); t j + h i (s i , t -i ) -u i f (t i , t -i ); t i - j =i u j f (t i , t -i ); t j -h i (t i , t -i ) ≤ h i (s i , t -i ) -h i (t i , t -i ),
where the inequality is a consequence of the fact that f (t i , t -i ) maximizes the sum i u i a; t i . But then h i (•, t -i ) is a weak representation of i's masquerade relation given t -i . Hence, by Lemma 1, every subset of types of agent i admits a worst case type. We can conclude with Theorem 1.

In a way, this result is almost a corollary of Theorem 2. Since, under private values, an efficient social choice function can be implemented with transfers by a VCG mechanism, then it can also be implemented by a reading mechanisms with accurate readings, with evidence and no transfers. The value added of Theorem 3 is to show that, with evidence, transfers can be chosen to satisfy individual rationality and budget balance, which is not possible in general with VCG mechanisms.

Since full surplus extraction can be achieved under private values, one might wonder whether, with evidence, it is ever necessary to pay an information rent in order to achieve efficiency. In the next section, we show that full surplus extraction can be achieved in single-object auctions with interdependent valuations, but not in multiple-object auctions. In Section 7 we show that full surplus extraction can be achieved in bilateral trade environments with interdependent valuations.

Auctions

In this section, we explore the consequence of relaxing the private value assumption in auction environments. We also provide examples of situations where reading mechanisms fail.

The agents have quasilinear utilities, and agent i's valuation of the single object for sale is given by a function u i (t) ≥ 0 that depends on the full type profile t. An auction (a social choice function) is a rule for allocating the object to one of the agents α : T → N , and a positive 4 price function π : T → Ê + for the winner of the auction.

An auction is individually rational if it never requires the winner to pay a price higher than her valuation, that is π(t) ≤ u α(t) (t). It is efficient if it allocates the good to one of the agents with the highest valuation, that is α(t) ∈ arg max i u i (t). It is fully extractive if it is efficient and π(t) = u α(t) (t). 4 An auction is therefore budget balanced by definition.

Theorem 4 (Single-Object Auctions). Any individually rational auction such that an evidence base is available for each agent is implementable by a reading mechanism with accurate readings. In particular, under own-type certifiability, the fully extractive auction is implementable by a reading mechanism with accurate readings. Proof. Pick an agent i, and fix t -i . We can split the type set of agent i into two regions, the set of types for which she does not get the good, T 0 i , and the set of types for which she obtains the good, T + i . First, note that any type masquerading as a type in T 0 i forgoes the good and gets a payoff of 0. Second, any type in T + i obtains a nonnegative payoff by masquerading as her true type, because the auction is individually rational. These two observations imply that no type wants to masquerade as a type in T 0 i , and therefore, if the masquerade relation

M[t -i ]
----→ admits a cycle on T i , then all the types involved in the cycle must lie in T + i . Because all types in T + i obtain the good, the gain in payoff obtained by a type t i ∈ T + i by masquerading as another type s i ∈ T + i is given by the difference of prices π(t i , t -i )π(s i , t -i ). This implies that the masquerading relation

M[t -i ] ----→ restricted to T +
i is weakly represented by the function -π(•, t -i ). Then we can conclude by Lemma 1 and Theorem 1.

Note that [START_REF] Dasgupta | Efficient Auctions[END_REF] exhibit an ex post incentive compatible efficient auction in a framework with interdependence and no evidence. However, they must impose a one dimensionality assumption on the type set. The equivalent of a one dimensionality assumption in our framework would be an assumption that the type set of each agent can be linearly ordered so that t i > t ′ i if and only if u i (t i , t -i ) > u i (t ′ i , t -i ), for every t -i . In addition, they assume that each agent's type has more influence on her own valuation than on the valuation of other agents' valuations. We do not need such assumptions with evidence since we impose no restriction on agents' valuation functions. 5Jehiel, Meyer-Ter-Vehn, Moldovanu, and Zame ( 2006) point out that, in environments with multidimensional types, interdependent valuations, transfers and no evidence, the only ex post implementable social choice functions are the constant ones under a minimal assumption on preferences. However, [START_REF] Bikhchandani | Ex Post Implementation in Environments with Private Goods[END_REF] argues that this assumption is not satisfied in private goods allocation models and shows that ex post implementation is possible by a generalized VCG mechanism in a single good allocation problem with multidimensional types and interdependent valuation. His possibility result is obtained in a two-player environment under the assumption that a player's information mat-Environment 1

∅ {1} {2} {1, 2} u 1 (s 1 ) 0 7 3 10 u 2 (s 1 ) 0 5 4 9 u 1 (t 1 ) 0 10 2 12 u 2 (t 1 ) 0 15 1 16 Environment 2 ∅ {1} {2} {1, 2} u 1 (s 1 ) 0 2 8 10 u 2 (s 1 ) 0 0 9 9 u 1 (t 1 ) 0 8 5 13 u 2 (t 1 ) 0 9 1 10
Table 1: Two Multi-Object Auction Environments ters more to her than to the other player. Our result shows that in environments with a rich evidence structure, no other assumptions are needed for ex post implementation.

The next example shows that with multiple objects, individually rational and efficient auctions may generate cycles in the masquerade relations of the agents. This is important for several reasons. First, it shows that, even under own-type certifiability, reading mechanisms do have limitations. Second, when full extraction is not possible it may be possible to achieve efficiency and individual rationality by leaving an information rent to the agents.

Example 3 (Two Multiple-Object Auctions). Consider auction environments with two agents, and two goods. The set of possible bundles that can be allocated to an agent is ∅, {1}, {2}, {1, 2} .

Agent 1 has information, encoded in the type set T 1 = {s 1 , t 1 }, while agent 2 has no information.

We assume that agent 1's information is fully certifiable and consider two payoff environments, for which the valuations of the different bundles are given in Table 1. The squares indicate the efficient allocation. In the first environment, full extraction cannot be achieved, but efficiency and individual rationality can be achieved by foregoing an information rent. In the second one, individual rationality and efficiency cannot be achieved together.

First, consider environment 1. In the fully extractive auction, each agent pays her value for the bundle she receives. Therefore, all agents get a payoff of 0 if the auction proceeds according to the true type of agent 1. Suppose that agent 1 convinces the auctioneer that her type is t 1 instead of s 1 . In this case, agent 1 obtains good 2 instead of good 1, at a price of 2. Since her true type is s 1 , her payoff is u 1 {2}|s 1 -2 = 1 > 0. Therefore, s 1 M -→ t 1 . Now suppose that agent 1 convinces the auctioneer that her type is s 1 instead of t 1 . Then she obtains good 1 instead of good 2, at a price of 7, so her masquerading payoff is

u 1 {1}|t 1 -7 = 3 > 0. Therefore, t 1 M -→ s 1 .
It is, however, possible to find an individually rational and efficient auction that leads to an acyclic masquerade. Consider, for example, changing the price of object 1 from 7 to 6 when the type is s 1 .

Then agent 1 of type s 1 has a payoff of 1 under truthful revelation, and does no longer profit by masquerading as t 1 . This change of price makes the incentive of t 1 to masquerade as s 1 stronger, but this is not a concern since the cycle is broken. The information rent that has to be paid in this auction is 1 if the type is s 1 , and 0 otherwise. It is easy to check that this is in fact the revenue maximizing auction among individually rational efficient auctions. The expected information rent is therefore equal to the probability of type s 1 .

By contrast, for environment 2, no individually rational and efficient auction can prevent a masquerading cycle. Indeed, individual rationality implies that the price of good 1 is at most 2 under s 1 , and the price of good 2 is at most 5 under t 1 . Therefore, the gain of s 1 from masquerading as t 1 is at least (8 -5) -2 = 1, and the gain of t 1 from masquerading as s 1 is at least (8 -2) -5 = 1. If we relax the constraint of positive prices, however, efficiency and individual rationality can be obtained by setting the price of good 1 to -1 in state s 1 . Then, budget balance is also satisfied because the auctioneer can price good 2 at 9 in state s 1 . ⋄

Bilateral Trade

In this section, we consider the bilateral trade problem of [START_REF] Myerson | Efficient Mechanisms for Bilateral Trading[END_REF]. We enlarge the traditional environment by considering interdependent valuations, so that the private information of the seller may enter in the valuation of the buyer, and vice versa. Bilateral trade with evidence has been considered in [START_REF] Singh | Implementation with Partial Verification[END_REF] and [START_REF] Deneckere | Mechanism Design with Partial State Verifiability[END_REF]. Both papers consider Bayesian implementation, and assume private values. Furthermore, the mechanisms they build are not reading mechanisms. We show that implementation by a reading mechanism is possible.

There are two agents with quasilinear preferences and one object. Agent 1 owns the object and is a potential seller, and agent 2 is a potential buyer. The seller's value for the item is given by ς(t 1 , t 2 ) ≥ 0, and the buyer's value for the item is β(t 1 , t 2 ) ≥ 0, where t 1 ∈ T 1 is the type of the seller and t 2 ∈ T 2 is the type of the buyer.

A social choice function for this problem is called a trading rule. It determines whether trade takes place, and the transfers to each agent. Hence, it is characterized by three functions λ : T 1 ×T 2 → {0, 1},

τ 1 : T 1 × T 2 → R and τ 2 : T 1 × T 2 → R
, where λ(t 1 , t 2 ) takes value 1 if trade takes place, and 0 otherwise, and τ 1 (t 1 , t 2 ) and τ 2 (t 1 , t 2 ) are respectively the transfers to the seller and the buyer. Then, the masquerading payoffs of the seller and the buyer are given by v 1 (s

1 |t 1 , t 2 ) = τ 1 (s 1 , t 2 ) + 1 - λ(s 1 , t 2 ) ς(t 1 , t 2 ), and v 2 (s 2 |t 2 , t 1 ) = τ 2 (t 1 , s 2 ) + λ(t 1 , s 2 )β(t 1 , t 2 ).
A trading rule is efficient if trade occurs whenever β(t 1 , t 2 ) > ς(t 1 , t 2 ), and trade does not occur

whenever β(t 1 , t 2 ) < ς(t 1 , t 2 ). It is budget balanced if, for every t 1 , t 2 , we have τ 1 (t 1 , t 2 ) + τ 2 (t 1 , t 2 ) ≤ 0.
It is individually rational if the following implications hold

λ(t 1 , t 2 ) = 1 ⇒ τ 1 (t 1 , t 2 ) ≥ ς(t 1 , t 2 ) and τ 2 (t 1 , t 2 ) ≥ -β(t 1 , t 2 ) λ(t 1 , t 2 ) = 0 ⇒ τ 1 (t 1 , t 2 ) = τ 2 (t 1 , t 2 ) = 0. Let G(t 1 , t 2 ) = β(t 1 , t 2 ) -ς(t 1 , t 2
) denote the gains from trade. We will consider efficient trading rules that split the gains from trade between the seller, the buyer and the designer. Therefore the transfer functions are given by τ

1 (t 1 , t 2 ) = λ(t 1 , t 2 ) ς(t 1 , t 2 ) + α s (t 1 , t 2 )G(t 1 , t 2 ) , and τ 2 (t 1 , t 2 ) = -λ(t 1 , t 2 ) β(t 1 , t 2 ) -α b (t 1 , t 2 )G(t 1 , t 2 ) , where λ(t 1 , t 2 ) is an efficient trading rule, α b (t 1 , t 2 ) ≥ 0 and α s (t 1 , t 2 ) ≥ 0 are such that α b (t 1 , t 2 ) + α s (t 1 , t 2 ) ≤ 1
, and represent the respective shares of the gains from trade obtained by the buyer and the seller. These trading rules thus give a share

α d (t 1 , t 2 ) = 1 -α b (t 1 , t 2 ) -α s (t 1 , t 2
) of the gains from trade to the designer. They are efficient, budget balanced and individually rational by construction. In fact, they span all the set of efficient, budget balanced and individual rational trading rules.

Theorem 5 (Bilateral Trade). Any efficient, budget balanced and individually rational trading rule such that an evidence base is available for each agent is implementable by a reading mechanism with accurate readings.

Proof. We show that these trading rules lead to acyclic masquerade relations for the seller and the buyer. We start with the seller, so we fix the information of the buyer to some type t 2 . First, note that a trading type never wants to masquerade as a non-trading type. Indeed, a trading type t 1 gets more than her value for the good since τ

1 (t 1 , t 2 ) = ς(t 1 , t 2 ) + α s (t 1 , t 2 )G(t 1 , t 2 ) ≥ ς(t 1 , t 2 ), whereas, if
she masqueraded as a non-trading type, she would have to keep the good.

Second, a non-trading type never wants to masquerade as another non-trading type. Indeed, in both cases the seller gets to keep the good so she is indifferent. Therefore, a masquerading cycle can only occur among trading types. However, a trading type t 1 wants to masquerade as another

trading type t ′ 1 if and only if τ 1 (t 1 , t 2 ) < τ 1 (t ′ 1 , t 2 ). But this implies that the function τ 1 (•, t 2 ) is a
weak representation of the masquerade relation restricted to trading types. Hence, by Lemma 1, there cannot exist a masquerading cycle among trading types.

For the buyer, the proof is symmetric. Start by fixing a seller type t 1 . A trading type never wants to masquerade as a non-trading type, because when trading she pays less for the good than her valuation. A non-trading type never wants to masquerade as another non-trading type because it does not change anything. Finally, the masquerade over trading types can be weakly represented by the transfer function τ 2 (t 1 , •), hence there can be no masquerading cycles among trading types.

The intuition of the proof is similar as in the single-object auction case. Fixing the types of the other agent, the type set of an agent, say the seller, can be partitioned into trading types and nontrading types. Trading types do not want to masquerade as non-trading types because individual rationality implies that they are compensated for trading. Therefore a masquerading cycle can only consist of trading types. But a trading type wants to masquerade as another trading type only if she is getting a better transfer by doing so. Therefore the masquerade relation among trading types is governed by transfers, and has no cycle. Figure 1 illustrates this intuition.

Note that the bilateral trade environment satisfies the condition on preferences of [START_REF] Jehiel | The Limits of Ex Post Implementation[END_REF] for their result on impossibility of non-trivial ex post implementation. Therefore our result illustrates the fact that even with an accurate reading mechanism the limits are not as narrow in environments with evidence.

Conclusion

In an environment where agents have access to evidence, we have defined a new class of mechanisms in which the designer must apply the social choice function to a profile of types that is consistent with the received profile of evidence, both along and off the equilibrium path. Such mechanisms are robust to the designer's commitment ability and to her preferences (as long as the social choice function represents her first-best), and they offer a solution to many classical mechanism design problems that are problematic under cheap talk. This is subject to having a rich evidence structure (say, own type certifiability). When this is the case, our results show that the set of implementable policies is considerably enlarged. While, in practice, evidence may not be as widely available as required for our results, they establish a benchmark, and contribute to drawing a picture of what can and cannot be achieved with evidence.

A Appendix

This appendix presents additional definitions to provide necessary and sufficient conditions for interim and ex-post implementation.

A.1 Additional Definitions

The interim belief of agent i about the types of the other agents is given by a distribution p i (•|t i ) ∈ ∆(T -i ). A messaging strategy profile µ : T → M is an interim equilibrium6 of this game if, for every i, every t i , and every m i ∈ M i (t i ),

E u i g(µ(t)); t |t i ≥ E u i g(m i , µ -i (t -i )); t |t i .
A mechanism g(•) interim implements the social choice function f (•) if there exists an interim equilibrium µ(•) of the game generated by g(•), such that g µ(t) = f (t) for every t ∈ T .

The interim masquerading payoff of agent i is given by the function

v i (s i |t i ) = t -i ∈T -i u i f (s i , t -i ); t i , t -i p i (t -i |t i ).
For the interim masquerade relation, we say that t i wants to masquerade as s i , denoted by

t i M -→ s i , if and only if v i (s i |t i ) > v i (t i |t i ). The set of interim worst-case types is denoted by wct(S i ) := s i ∈ S i | ∄ t i ∈ S i , t i M -→ s i
An interim evidence base for agent i is a set of messages E i ⊆ M i such that there exists a oneto-one function e i : T i → E i that satisfies e i (t i ) ∈ M i (t i ), and t i ∈ wct M -1 i e i (t i ) for every t i . If cheap talk completion of the evidence structure is allowed, the condition for an interim evidence base is that, for each t i , there exists m i such that t i ∈ wct M -1 i m i . A reading is independent if for every i the reading of the evidence satisfies ρ i (m i , m -i ) = ρ i (m i , m ′ -i ) for every m i , m -i and m ′ -i . It means that agent i's evidence is interpreted independently of the evidence submitted by other agents. 7 As in the main paper, we say that a reading mechanism implements f (•) with accurate readings if it reads the evidence correctly on the equilibrium path of the corresponding equilibrium.

Definition 2 (Accurate Implementation). A reading mechanism with associated reading ρ(•) accurately (interim or ex post) implements f (•) if there exists an (interim or ex post) equilibrium strategy profile µ(•) such that, for every t ∈ T , ρ µ(t) = t.

Definition 3 (Straightforward Implementation). A reading mechanism with associated reading ρ(•) straightforwardly (interim or ex post) implements f (•) if there exists an (interim or ex post) equilibrium strategy profile µ(•) such that ρ µ(t) = t, and ρ -i µ -i (t -i ), m i = t -i , for every t ∈ T , every i ∈ N , and every m i ∈ M i .

Hence straightforward implementation is more restrictive than accurate implementation. It implies that, if all agents except i use their equilibrium strategy, then the type profile of these non deviators is correctly interpreted. Note also that accurate implementation by an independent reading implies straightforward implementation.

A.2 Necessary and Sufficient Conditions for Implementation

Theorem 6 (Interim Implementation). There exists a reading mechanism that accurately interim implements f (•) with an independent reading if and only if the following conditions hold for every agent i:

(i) For every message m i ∈ M i , the set M -1 i (m i ) admits an interim worst case type.

(ii) M i (•) admits an interim evidence base.

Proof. (⇐) By (ii), we can pick, for each agent i, a one-to-one mapping e i : T i → M i corresponding to an evidence base of i. By (i), we can choose an independent reading ρ(•) such that, for every m i , ρ i (m i ) ∈ wct M -1 i (m i ) and for every t i , ρ i e i (t i ) = t i . Suppose that every agent i adopts e i (•) as her strategy in the game defined by the mechanism associated with ρ(•). Then for every t, the mechanism selects the outcome f ρ(e(t)) = f (t). Hence, if the strategy profile e(•) is an equilibrium of the game, we have succeeded in implementing f (•) with accurate readings. It remains to show that e(•) is indeed an equilibrium. Suppose then that agent i of type t i deviates with a message m i = e i (t i ). Then the implemented outcome is f w i , t -i , where w i ∈ wct M -1 i (m i ) . But then we know that v i (w i |t i ) ≤ v i (t i |t i ), so the deviation is not profitable for i.

(⇒) Let ρ(•) be an independent reading such that the associated mechanism implements f (•) with accurate readings, and let µ * (•) be the associated equilibrium strategy profile. Then, by definition of accurate implementation, ρ µ * (t) = t. Consider some message m i of agent i. The equilibrium condition implies that, for every t

i ∈ M -1 i (m i ), v i (t i |t i ) ≥ E u i f ρ(m i , µ * -i (t -i )) ; t |t i = E u i f ρ i (m i ), t -i ; t |t i = v i ρ i (m i )|t i ,
7 When types are independent, this restriction has the same flavor as the belief consistency requirement "no signaling what you don't know" of a perfect Bayesian equilibrium [START_REF] Fudenberg | Perfect Bayesian Equilibrium and Sequential Equilibrium[END_REF].

where first equality is a consequence of accuracy and independence. Since, by definition of a reading mechanism, ρ i m i ) ∈ M -1 i (m i ), this proves that ρ i m i ∈ wct M -1 i (m i ) . This proves (i). To prove (ii), consider the particular case in which m i = µ * i (s i ) for some type s i ∈ T i . Then ρ i m i , µ * -i (t -i ) = s i , by accuracy and independence, and therefore we have shown that s i is a worst case type of the set certified by µ * i (s i ). The accuracy property also implies that µ * i (s i ) = µ * i (t i ) whenever s i = t i . Otherwise, we would have

t i = ρ i µ * i (t i ) = ρ i µ * i (s i ) = s i .
Therefore, the function µ * i : T i → M i defines an evidence base for i.

It is easy to show that the existence of an evidence base for each agent is necessary for implementation with any mechanism. The worst case type condition, however, is only necessary if we require accurate implementation and independent readings. If the reading is not required to be independent, then ex post instead of interim worst case types could be used (see Theorem 7). To illustrate the importance of accuracy, the following example exhibits a social choice function that is not accurately interim implementable with independent reading, because of a missing interim worst case type, but can nevertheless be implemented by a reading mechanism with independent reading.

Example 4 (Committing to incorrect readings). There are two agents and five alternatives A = {a, b, c, d, e}. The set of agent 1's types is T 1 = {t 0 1 , t

f (•, •) t 0 1 t 1 1 t 2 1 t 3 1 t 4 1 t 1 2 e b a d c t 2 2 e a b c d
Assume that agent 2's utility is maximized when f (•) is implemented (so that he never has an incentive to deviate), and agent 1's utility function is given by the following table, where the squares indicate the outcomes prescribed by the social choice function:

u 1 (•; •) = t 1 2 a b c d e t 0 1 2 2 -1 -1 0 t 1 1 -1 0 -1 2 2 t 2 1 0 -1 -1 -1 -1 t 3 1 2 -1 -1 0 -1 t 4 1 -1 -1 0 -1 -1 t 2 2 a b c d e t 0 1 2 2 -1 -1 0 t 1 1 0 -1 2 -1 2 t 2 1 -1 0 -1 -1 -1 t 3 1 -1 2 0 -1 -1 t 4 1 -1 -1 -1 0 -1
The interim masquerade relations of the agents and the evidence structures are summarized in Figure 2. Agent 1's interim masquerade relation has a cycle. There is an interim evidence base for each agent, but the certifiable set {t 0 1 , t 1 1 , t 2 1 , t 3 1 } has no interim worst case type. Hence, f (•) is not accurately interim implementable with an independent reading. However, it is implemented with the following independent reading and interim equilibrium strategies, where the red lines correspond to incorrect readings given the equilibrium strategies: to t 4 1 , which no type in M -1 1 (m 0123 ) wants to masquerade as. The designer cannot do that directly because such a reading would not be consistent with evidence. But she can emulate that outcome by misreading evidence from agent 2 on the equilibrium path.9 ⋄ For ex post implementation, we weaken the necessary properties of the mechanisms used in the characterization since we require straightforward implementation instead of accurate implementation with an independent reading.

Theorem 7 (Ex Post Implementation). There exists a reading mechanism that straightforwardly ex post implements f (•) if and only if the following conditions hold for every agent i:

(i) For every t -i ∈ T -i , and every message m i ∈ M i , the set M -1 i (m i ) admits a worst case type given t -i .

(ii) M i (•) admits an evidence base.

Proof. (⇐) This part of the proof is the same as the proof of Theorem 1. The straightforwardness property is satisfied by construction of ρ(•).

(⇒) Let ρ(•) be a reading such that the associated mechanism straightforwardly implements f (•), and let µ * (•) be the associated ex post equilibrium strategy profile. Consider some message m i of agent i. The equilibrium condition implies that, for every t -i ∈ T -i , and every t i ∈ M -1 i (m i ), and

v i (t i |t i ; t -i ) ≥ E u i f ρ(m i , µ * -i (t -i )) ; t |t i = E u i f ρ i (m i , µ * -i (t -i )), t -i ) ; t |t i = v i ρ i (m i , µ * -i (t -i ))|t i ,
where the second line comes from the straightforward implementation property. Since, by definition of a reading mechanism, ρ i (m i µ * -i (t -i )) ∈ M -1 i (m i ), this proves that ρ i (m i , µ * -i (t -i )) ∈ wct M -1 i (m i )|t -i . This proves (i). Now, consider the particular case where m i = µ * i (s i ) for some type s i ∈ T i . Then ρ i (m i , µ * -i (t -i )) = s i , by the straightforwardness property, and therefore we have shown that s i is a worst case type of the set certified by µ * i (s i ) given t -i . The straightforwardness property also implies that µ * i (s i ) = µ * i (t i ) whenever s i = t i . Otherwise, we would have t i = ρ i µ * i (t i ), µ * -i (t -i ) = ρ i µ * i (s i ), µ * -i (t -i ) = s i . Therefore, the function µ * i : T i → M i defines an evidence base for i.

Ex post implementability by a reading mechanism implies interim implementability by a reading mechanism. However, the reading used for ex post implementation, even if it satisfies straightforwardness, may not satisfy independence. To illustrate the relations between ex post and interim implementation by reading mechanisms, we provide an example such that the conditions of Theorem 6 and Theorem 7 are not satisfied, but accurate interim implementation by a reading mechanism is possible.

Example 5 (Accurate interim implementation without independence or straightforwardness). Consider two agents. The type sets are T 1 = {t 1 , t ′ 1 } and T 2 = {t 2 , t ′ 2 , t ′′ 2 }. The common prior is that the types of the two agents are independently and uniformly distributed over their respective supports. We assume that the only certifiable sets of agent 2 are the singletons {t 2 }, {t ′ 2 } and {t ′′ 2 }, so that there is no need to incentivize full revelation from agent 2. The certifiable sets for agent 1 are the singletons, {t 1 } and {t ′ 1 }, and the set {t 1 , t ′ 1 }, so that there exists an evidence base, but agent 1 needs to be incentivized to provide precise information. For simplicity, we denote the messages by the sets they certify.

The ex post masquerading relations of agent 1 and her interim masquerading relation are given in Figure 3 with intensities. There is an ex post cycle when the type of agent 2 is t 2 , and there is an interim cycle. Therefore the conditions of Theorem 6 and Theorem 7 are not satisfied. Accurate interim implementation is possible with the following reading:

ρ 1 {t 1 , t ′ 1 }, {t 2 } = ρ 1 {t 1 , t ′ 1 }, {t ′ 2 } = t 1 and ρ 1 {t 1 , t ′ 1 }, {t ′′ 2 } = t ′ 1 .
Indeed, if the type of agent 2 is t ′′ 2 , the uninformative message {t 1 , t ′ 1 } of agent 1 is read as t ′ 1 , which is an ex post worst case type. Hence she has no incentive to be vague conditionally on the type of agent 2 being t ′′ 2 . Agent 1 cannot be given ex post incentives if the type of agent 2 is t 2 , but the designer can dissuade her from being vague by pooling this event with the event in which agent 2 has type t ′ 2 . The expected masquerading gain conditional of agent 2 not being of type t 2 is +6 for a t 1 type masquerading as a t ′ 1 type, and -2 for a t ′ 1 type masquerading as a t 1 type, an therefore interpreting the vague message as t 1 is dissuasive.

⋄ Ex Post Interim t ′ 2 t ′ 2 t ′′ 2 t ′ 1 t 1 +10 +2 t ′ 1 t 1 +2 -6 t ′ 1 t 1 -6 +10 t ′ 1 t 1 +2 +2
Figure 3: Accurate interim implementation without independence or straightforwardness -ex post and interim masquerade relations of agent 1.

  a weak representation of the masquerade relation of agent i given t -i , allowing us to conclude by Lemma 1 and Theorem 1. The second part of the theorem is proved by Example 2.

  Figure 1: Bilateral Trade -intuition for the proof of Theorem 5.

In their work on Nash implementation, a type must be able to disprove any other type such that the pair would violate Maskin monotonicity.

[START_REF] Dasgupta | Efficient Auctions[END_REF] consider a continuum of types. It would not affect our result to work with a continuum of types provided that all certifiable subsets are compact and the auction would have to use a pricing scheme that is upper semi continuous in the type of the agent that is getting the good.

As in[START_REF] Bergemann | Robust Mechanism Design[END_REF] Morris (2005, 2011), we use the term interim instead of Bayesian (equilibrium or implementation) to highlight the fact that we do not assume a common prior.

Note that this function satisfies responsiveness, that is, for every ti = t ′ i , there exists a profile t-i such that f (ti, t-i) = f (t ′ i , t-i).

Note that the conclusion does not change if we modify the evidence structure so as to satisfy the normality condition of[START_REF] Bull | Hard Evidence and Mechanism Design[END_REF],[START_REF] Deneckere | Mechanism Design with Partial State Verifiability[END_REF][START_REF] Deneckere | Mechanism Design with Partial State Verifiability[END_REF][START_REF] Forges | Communication Equilibria with Partially Verifiable Types[END_REF][START_REF] Forges | Communication Equilibria with Partially Verifiable Types[END_REF]. For example, if we complete the above evidence structure with messages certifying the singletons, the allocation f (•) is still implementable with the above readings and messaging strategies, but is not implementable with accurate readings. Interestingly, f (•) is then implemented without asking maximal evidence to the agents: if the designer asks each agent to completely certify her type, then f (•) cannot be implemented with a reading mechanism.