Robust Implementation with Costly Information
Harry Pei∗

Bruno Strulovici†‡

October 23, 2022

Abstract: We design mechanisms that robustly implement any desired social choice function when(i) agents must incur a cost to learn the state of the world, (ii) with small probability, agents’ preferences can be arbitrarily different from some baseline known to the social planner, and (iii) theplanner does not know agents’ beliefs and higher-order beliefs about one another’s preferences.
The mechanisms we propose have a natural interpretation, and are robust to trembles in agents’reporting strategies, to the introduction of a small amount of noise affecting agents’ signals about
the state, and to uncertainty concerning the state distribution and agents’ prior beliefs about thestate. We also establish impossibility results for stronger notions of robust implementation.
Keywords: Robust Implementation, Partial Implementation, Critical Path Lemma.
JEL Codes: D82, D83.

1

Introduction

Theories of robust implementation study whether a state-contingent social choice function, suchas one aiming to convict guilty defendants and acquit innocent ones, can be implemented when
information about the state must be elicited from agents whose objective may be misaligned withthe social choice function, and the planner who designs the mechanism faces uncertainty about
agents’ preferences and their beliefs and higher-order beliefs about one another’s preferences.
Whether a social choice function can be robustly implemented depends on the notion of robustness considered. When robustness is required to hold globally, in the sense that agents’ preferences
and beliefs may be arbitrary, Bergemann and Morris (2005) show that a social choice function
is robustly implementable only if it is ex post incentive compatible. Oury and Tercieux (2012)
consider a less demanding notion of robust implementation, which concerns local perturbations of∗Department of Economics, Northwestern University. Email: harrydp@northwestern.edu
Department of Economics, Northwestern University. Email: b-strulovici@northwestern.edu‡
We thank Gabriel Carroll, Yi-Chun Chen, Eddie Dekel, Nina Fluegel, Dana Foarta, Yingni Guo, Matt Jackson,
Navin Kartik, Takashi Kunimoto, Elliot Lipnowski, Meg Meyer, Stephen Morris, Kota Murayama, Kyohei Okumura,David Rodina, Larry Samuelson, Takuo Sugaya, Satoru Takahashi, Olivier Tercieux, Takashi Ui, Siyang Xiong, andBoli Xu for helpful comments. Pei thanks the NSF Grant SES-1947021 for financial support.
†1

agents’ preferences and beliefs in an interim sense. They require that the desired social choicefunction be approximately implemented for all profiles of agent types close to a given type profile.
They show that robustly implementable social choice functions must satisfy Maskin monotonicity(Maskin 1999)—a demanding property that is violated in a number of settings.

1.1

An Ex Ante Notion of Robust Implementation

This paper proposes a new, ex ante notion of robust implementation, and examines whether a givensocial choice function can be robustly implemented when agents need to incur a cost to learn thestate.1
Our notion of robust implementation builds on the concept of equilibrium robustness introduced
by Kajii and Morris (1997). According to this concept, a Nash equilibrium of a complete information
game is robust if it can be approximated by some equilibria in every incomplete information gameclose to the complete information game in the sense that players’ payoffs match those of the complete
information game with probability close to one. In these incomplete information games, agents canhave arbitrary payoffs with small probability and arbitrary beliefs and higher-order beliefs about
one another’s payoffs as long as these beliefs are consistent with a common prior.
Building on this definition, we propose a local and ex ante notion of robust implementation.
First, we focus on perturbations in which agents’ payoffs differ from those of the unperturbed
environment with small probability. Second, we require that the desired social choice function
be implemented only with probability close to one rather than approximately implemented for all
nearby types. Our notion of robust implementation relaxes some restrictive requirements of the
global and interim notions and thus can potentially avoid some of the most stringent implicationsof these notions, as we will show in this paper.
Our notion of robust implementation departs from Kajii and Morris (1997) by imposing a key
restriction on the set of perturbations considered by the planner: We focus on perturbations inwhich agents’ payoffs do not directly depend on the messages that agents send to the mechanism.
Precisely, we assume that it is common knowledge that messages are cheap talk. This restriction
is motivated by our focus on mechanism design problems, in which agents’ actions amount tomessages designed by the planner, which do not have intrinsic value, and matter only through theoutcomes and transfers in which they result. We do allow perturbations to affect agents’ preferences1

Our mechanisms also work when agents’ costs of learning are zero. Even in this simpler case, we are unaware ofany existing result that solves the robust implementation problem for our notion, except when agents’ payoffs andthe social choice function satisfy a condition that is stronger than Maskin monotonicity (see Chen et al. (2021)).

2

concerning the outcomes implemented as a result of their messages as well as their costs to learn
the state.
Our analysis focuses for simplicity on the case of two agents.2 There are n states of the world.
A planner knows the objective distribution of the state and wishes to implement a social choicefunction that maps each state to a lottery over a set of outcomes. She commits to a mechanism
mapping agents’ messages to lotteries over outcomes and transfers without knowing the state as well
as how the environment is perturbed. Each agent observes the mechanism offered by the planner,
the realized perturbation, and his type under that perturbation. Agents then independently decide
whether to observe the state at some cost and then send messages to the planner.

1.2

Main Results

Our main contribution is to construct mechanisms that robustly implement the desired social choicefunction when there exists a state whose ex ante probability of occurrence is strictly higher thanthat of any other state,3 or when the planner is concerned only about perturbations in which agents’costs of learning are uniformly bounded above by some commonly known bound. The mechanisms
we construct for generic state distributions have three noteworthy features.
First, each agent is given a message space with 2n − 1 messages. One of these messages corresponds to the ex ante most likely state, and is called the status quo message. The remaining 2n − 2
messages are divided into pairs that are associated with each of the n − 1 remaining states. The two
messages corresponding to state θ have the following interpretations: One of them is a confident
message which means “I am confident that the state is θ”. The other one is a confession message
which means “I am uninformed but I would like to implement the desired outcome in state θ.”
Second, the desired outcome in the ex ante most likely state is treated as a status quo outcome.
This outcome is implemented whenever the messages sent by the two agents correspond to different
states. When agents’ messages correspond to the same state, the planner implements the desired
outcome in that state. Therefore, the confession message and the confident message corresponding
to the same state induce the same outcome for any message of the other agent.
2

We construct mechanisms that robustly implement any given social choice function when there are at least two
agents who may have the ability to learn the state. These mechanisms can be easily modified to account for thepresence of more agents, e.g., by applying them to two of the agents and ignoring the reports of remaining agents.
Even when there are three or more agents, it is unclear whether using the majority rule can easily resolve the robust
implementation problem when agents’ learning costs are strictly positive. See footnote 13 on page 16 for details.
3This condition is satisfied for generic state distributions. In Online Appendix A, we extend our robust implementation results to environments with a continuum of states without requiring any equivalent of the genericcondition.

3

Third, if an agent sends any confession message or the status quo message, he receives a strictly
positive transfer as long as the other agent does not send any confident message. If an agent
sends any confident message, then he faces more risk in the sense that he receives a strictly positivetransfer if and only if the other agent sends the same confident message, but the transfer he receives
conditional on matching the other agent’s message is strictly greater than the maximal transfer hecan receive from sending any confession message or the status quo message.
We then address other robustness concerns. First, our mechanisms continue to implement
the desired social choice function when the planner faces uncertainty about the objective state
distribution or about agents’ prior beliefs about the state (Proposition 2 in Section 5.2). Such
uncertainty arises, for instance, when agents observe noisy private signals about the state before
deciding whether to fully learn it at some cost, and the planner does not know agents’ information
structures. Second, robust implementation survives the introduction of trembles when agents send
messages and of a small amount of noise in agents’ information about the state. This may capture
situations in which it is infinitely costly to learn the state perfectly.

1.3

Impossibility Results for Stronger Notions of Robust Implementation

We provide several results pertaining to stronger notions of robust implementation. First, we showthat even if we require only approximate implementation of a non-constant social choice function,
it is impossible to achieve such implementation when agents’ payoffs can differ from those of theunperturbed environment with non-negligible probability.
Second, we examine the possibility of full implementation and virtual implementation. We
show that when agents’ costs of learning the state in the unperturbed environment are above some
cutoff, or when agents’ payoff functions in the unperturbed environment are independent of thestate, under every finite mechanism, there exists an equilibrium in which no agent learns the state.
This result implies that under each of these two conditions, no finite mechanism can virtually
implement any non-constant social choice function.4 We also provide a sufficient condition for full
implementation: When at least one agent’s preference and the social choice function satisfy a strictversion of Rochet (1987)’s cyclical monotonicity condition and this agent’s cost of learning is smallenough, the planner can robustly and fully implement that social choice function by ignoring thereport of the other agent.
4This result echoes Strulovici (2021), who shows in a sequential model of learning that when agents’ preferences
are state independent, implementation is impossible even in a partial sense when signals about the state of the world
are subject to an information attrition condition.

4

Third, we examine the possibility of robust (partial) implementation in an interim sense. We
adapt the notion of robust interim implementation in Oury and Tercieux (2012) to our setting.5
We show that no finite mechanism can robustly implement any non-constant social choice function
when agents’ costs of learning the state in the unperturbed environment are above some cutoff,even when the planner can use unbounded transfers.

1.4

The Cost of Implementation

We construct mechanisms that robustly implement desired social choice functions, but we do notcharacterize the lowest transfer needed to achieve such robust implementation. Although it would
be valuable to determine the lowest cost of implementation, computing this cost seems challenging
because it would require precise knowledge of the set of robust equilibria under every mechanism.
However, to the best of our knowledge, there is no full characterization of the set of Kajii-Morrisrobust equilibria in the existing literature.
We view our results showing that it is possible to robustly implement the desired outcome
via mechanisms with relatively few messages as an important first step for the study of robust
implementation in the ex ante sense.6 These results offer a new perspective on locally robust
implementation. They stand in contrast to impossibility results under interim notions of robust
implementation, such as Theorem 6 in the present paper and the results contained in Oury and
Tercieux (2012). While we do not compute the minimum cost required to robustly implement agiven social choice function in the ex ante sense, the mechanisms that we construct provide an
upper bound on this cost.

1.5

OutlineSection 2 presents an example to illustrate our results. First, mechanisms that (i) reward agentsa fixed amount when their reports match, and (ii) give agents no transfer and randomize acrossoutcomes when their reports mismatch, cannot robustly implement the desired outcome. Second,
we introduce new mechanisms and explain why they are robust against types that are biased in favorof certain outcomes and types that have high costs of learning. The general model is introduced in5Oury and Tercieux (2012) consider environments without costly learning and with bounded utilities, which stands
in contrast to our setting where agents need to learn the state at some cost and agents’ utilities are unbounded.
6This first step is, in spirit, similar to the results of Vickrey, Clarke, and Groves, who show that the socially efficient
outcome is dominant-strategy implementable but leave open the question of finding the lowest cost to implement thesocially efficient outcome. Similarly, in the dynamic mechanism design literature, one of Pavan, Segal and Toikka(2014)’s main contributions is to provide a necessary condition for an allocation to be implementable.

5Section 3. Our main results appear in Section 4. Section 5 extends our results in several directions,allowing for the possibilities that the planner faces uncertainty about the objective state distribution
and about agents’ beliefs about the state, that agents tremble with small probability, and that agentscan only observe noisy signals about the state after paying their learning costs. Section 6 presents
impossibility results for stronger notions of robust implementation. Section 7 reviews the related
literature. Extensions to a continuum of states and general information acquisition technologies
are given in an online appendix.

2

ExampleConsider a planner facing a defendant who is either guilty or innocent of a crime. The state of theworld θ is binary: θ ∈ Θ = {innocent, guilty}. Let q = Pr(θ = guilty) ∈ (0, 1) denote the priorprobability of guilt.
The planner knows q but not θ.7 Her objective is to convict guilty defendants and to acquit
innocent ones. She commits to a mechanism M = {M1 , M2 , g, t1 , t2 } in order to elicit informationfrom two agents in charge of investigating the crime. Here, Mi is a finite set of messages for agenti ∈ {1, 2}, g : M1 × M2 → [0, 1] is a mapping from agents’ messages to the probability of conviction,and ti : M1 × M2 → R+ is the transfer to agent i. We assume that transfers are non-negative.
Importantly, t1 and t2 depend only on agents’ messages, not on the realized state.
Each agent can conduct an investigation at cost c and learn whether the defendant is guilty or
innocent. The decision made by an agent and the information that may result from his investigation
are private: they are observed neither by the planner nor by the other agent.
Agent i’s payoff is ti − cdi , where di ∈ {0, 1} denotes agent i’s decision of whether to conduct
investigation and c > 0 is the agent’s cost of conducting his investigation.
Partial Implementation without Robustness: When agents’ payoffs are common knowledge,
the planner can implement the desired social choice function (convict the guilty and acquit theinnocent) via a Maskin mechanism: Each agent is asked to report whether the defendant is guilty
or innocent (we use italics for messages). The outcome and the transfers are given by:
7

Section 5.2 extends our main results when the planner does not know q precisely or agents prior beliefs about θ.

6

outcome

innocent

guiltytransfers

innocent

guiltyinnocent

acquitconvict with prob 1/2

innocent

R, R

0, 0

guiltyconvict with prob 1/2

convict

guilty0, 0

R, R

When the reward R > 0 is large relative to agents’ cost c, there is an equilibrium in which both
agents conduct investigations and report their findings truthfully.
Failure of Maskin Mechanisms with Biased Agents:

Maskin mechanisms fail to implement

the desired social choice function—even approximately—when agents can have biases over outcomeswith small but positive probability.
We illustrate such failures with a class of perturbations inspired by Rubinstein (1989)’s email
game. Suppose that nature draws a random variable ω from a countable set Ω ≡ {ω0 , ω1 , ω2 , ...}
according to the geometric distribution Pr(ω = ωt ) = η(1 − η)t for every t ∈ N, where η > 0 is
a parameter close to 0. We assume that ω is independent of the state θ. Agent 1 observes whichelement of the partition {ω0 }, {ω1 , ω2 }, {ω3 , ω4 }, ... the realized ω belongs to before deciding whether
to conduct his investigation and what message to send. Likewise, agent 2 observes which elementof the partition {ω0 , ω1 }, {ω2 , ω3 }, {ω4 , ω5 }, ... the realized ω belongs to before deciding whether to
conduct his investigation and what message to send. An agent’s type is defined by the partition
cell that he observes. After observing his own type, each agent updates his belief about the otheragent’s type according to Bayes rule.8 The distribution of ω has the property that, whenever anagent observes a cell {ωk , ωk+1 } of his partition, this agent assigns strictly higher probability toω = ωk than to ω = ωk+1 .
Agent 2’s payoff is t2 − cd2 at every ω ∈ Ω. Agent 1’s payoff is t1 − cd1 at every ω 6= ω0 . When
ω = ω0 , agent 1’s payoff is t1 −cd1 +B ·1{defendant is acquitted}, i.e., he receives a benefit B > 0 if
the defendant is acquitted. This perturbation is small when η is close to 0 in the sense that agents’
payoffs coincide with those in the unperturbed environment when ω 6= ω0 , and Pr(ω 6= ω0 ) = 1 − η.
For large enough biases, Maskin mechanisms fail to implement the desired social choice function
even when η is arbitrarily close to 0: For any reward R ∈ R+ , there exists a bias B > R such thatno matter how close η is to 0, the perturbed game has a unique equilibrium in which no agent
conducts any investigation and both agents report innocent regardless of the state.9 As a result,
81For example, the type of agent 2 who knows that ω ∈ {ω0 , ω1 } assigns probability 2−ηto agent 1 being type1
{ω0 }, the type of agent 1 who knows that ω ∈ {ω1 , ω2 } assigns probability 2−η to agent 2 being type {ω0 , ω1 }, etc.
9
For Maskin mechanisms to fail, we do not need type ω0 ’s bias B to be arbitrarily large. Our contagion argument
applies when agent 1’s payoff when ω = ω0 is −cd1 + b · 1{the defendant is acquitted}, i.e., type ω0 of agent 1 is7the defendant is acquitted regardless of his guilt in the unique equilibrium.
This conclusion comes from the following contagion argument. When ω = ω0 , agent 1 is biased
in favor of acquitting the defendant, so he has an incentive to report innocent regardless of θ if B islarge enough. When ω ∈ {ω0 , ω1 }, agent 2 is unbiased, but he believes that agent 1 is biased withprobability greater than 21 , so he believes that agent 1 will report innocent with probability greaterthan 12 for every θ. Since agent 2 maximizes his expected transfer minus his cost of investigation,
he has a strict incentive to report innocent regardless of θ. By induction, all types of both agentswill report innocent regardless of θ in the unique equilibrium of the perturbed game.
In general, agents may be biased in either direction: some agent types may benefit from convicting the defendant while others may benefit from acquitting the defendant, and these biases may
have arbitrary magnitudes. The planner faces uncertainty about the direction and magnitude ofthese biases as well as about agents’ beliefs and higher-order beliefs about each other’s biases. The
planner aims to design a mechanism that can approximately implement the desired social choicefunction under every perturbation where agents are unbiased with probability close to 1, but may
have arbitrary biases with small probability and may entertain arbitrary beliefs and higher-orderbeliefs about these biases, as long as those beliefs can be derived from a common prior.
Status Quo Rule with Ascending Transfers. We propose a mechanism that implements thedesired social choice function when the planner does not know the direction and magnitude of
agents’ biases. From now on, we assume that agents’ costs of learning are commonly known andequal to some constant c. We later introduce mechanisms to address the case in which the planneralso faces uncertainty about the cost of learning.
Our mechanism asks each agent to report the state, i.e., whether the defendant is innocent or
guilty. The outcome and the transfers are given by:outcomeinnocent

guiltytransfers

innocent

guiltyinnocent

acquitacquitinnocent

R1 , R1

0, 0

guiltyacquitconvict

guilty0, 0

R2 , R2c1where the magnitude of transfers R2 and R1 satisfy R2 − R1 > 2cq and R > 1−q .

This mechanism features a status quo outcome, acquit, which is implemented as long as one
purely outcome-driven in the sense that he does not care about the transfers, and receives a strictly positive benefitb > 0 from acquitting the defendant. Maskin mechanisms fail even when b is arbitrarily small. Our Augmented Status
Quo Rule with Ascending Transfers can robustly implement the desired social choice function when perturbations
can also affect agents’ marginal utilities from transfers. The details are available upon request.

8

agent reports innocent. The defendant is convicted if and only if both agents report guilty. Agentsreceive strictly positive transfers only if their reports coincide. Moreover, they receive a larger
transfer when they both report guilty than when they both report innocent.
To see why this mechanism is robust to the existence of biased types, let us revisit the email game
perturbations introduced above: Nature draws a random variable ω from Ω = {ω0 , ω1 , ω2 , ...} according to distribution Π ∈ ∆(Ω) independently of θ. Agent 1’s information partition is {ω0 }, {ω1 , ω2 },{ω3 , ω4 }, ... Agent 2’s information partition is {ω0 , ω1 }, {ω2 , ω3 }, ... Agent 2’s payoff is t2 − cd2 atevery ω. Agent 1’s payoff is t1 − cd1 at every ω 6= ω0 . Therefore, every email game perturbation ischaracterized by the distribution Π and by agent 1’s payoff at ω0 .
1. Suppose first that when ω = ω0 , agent 1 receives a large benefit if the defendant is acquitted.
This type can guarantee outcome acquit by reporting innocent regardless of θ. Since R2 −R1 >2cq , however, there exists λ ∈ (0, 1) such that Π(ω1 ) needs to be less than λΠ(ω0 ) in order for

type {ω0 , ω1 } of agent 2 to have an incentive to report innocent regardless of θ. Likewise,Π(ω2 ) needs to be less than λΠ(ω1 ) in order for type {ω1 , ω2 } of agent 1 to have an incentive
to report innocent regardless of θ, and so on. The upper bounds on these probabilities form
a decaying geometric sequence, so the total probability of types that are infected by type ω0
P1tis at most +∞t=0 λ Π(ω0 ) = 1−λ Π(ω0 ). This expression vanishes to 0 as Π(ω0 ) → 0.
2. Suppose now that when ω = ω0 , agent 1 receives a large benefit if the defendant is convicted.
If Π(ωt ) = η(1 − η)t for every t ∈ N and type ω0 reports guilty regardless of the state, then all
types of both agents have a strict incentive to report guilty regardless of the state, because
R2 > R1 > 0.
However, according to the outcome function specified by the mechanism, the defendant isconvicted only if both agents report guilty. Therefore, an agent who is biased in favor ofconvicting the defendant cannot impose a conviction when the defendant is innocent andthe other agent is truthful. In this case, paying the cost c of learning the defendant’s guilt,
and reporting innocent when the defendant is innocent, leads to a strictly positive transfer.
cMoreover, the expected value of this transfer exceeds the cost of learning c when R1 > 1−q.

Of course, the previous argument only shows why the mechanism we propose may be able to
avoid some type of contagion for some specific perturbations. To address the general case, weshow in the proof of Theorem 1 that under our mechanism, for every perturbation in which both
agents are unbiased with probability close to 1, which includes but is not limited to email game9

perturbations, there always exists an equilibrium in which (i) agents never report guilty when the
defendant is innocent, and (ii) both agents report the state truthfully with probability close to 1.
This equilibrium approximately implements the desired social choice function.
Uncertainty about Agents’ Costs of Learning: The planner may also face uncertainty about
agents’ costs of learning the state. For example, one of the agents may be “inept” in the sense ofbeing unable to conduct investigations.
We show that, as long as the prior probability of guilt q is not exactly equal 21 , there exists a
mechanism that approximately implements the desired social choice function when, with probability
close to 1, agents are unbiased and have cost of learning c, but with some small probability canhave arbitrary biases and costs of learning.
We start by explaining why the Status Quo Rule with Ascending Transfers, which was introduced
earlier to address agents’ biases, is unable to deal with inept types. For any 0 < R1 < R2 , consider
an email game perturbation where agent 1’s payoff at ω0 is t1 − e
cd1 + B · 1{defendant is convicted}.
We consider perturbations where his benefit from convicting the defendant B > 0 and his cost oflearning ec > 0 are large relative to the transfers promised by the mechanism.
When this high-cost biased type of agent 1 believes that agent 2 reports guilty when the defendantis guilty, he prefers to report guilty when the defendant is guilty, since he receives a large benefit B
from convicting the defendant. If this type wants to report innocent when the defendant is innocent,then he needs to conduct an investigation, but his cost of doing so ec outweighs the highest transfer
promised by the mechanism. Hence, this type prefers to report guilty regardless of θ even when hebelieves that agent 2 reports truthfully. Since R2 > R1 , this causes contagion when the distributionof ω satisfies Π(ωt ) = η(1 − η)t for every t ∈ N, no matter how close η is to 0.
Augmented Status Quo Rule with Ascending Transfers:

We propose another mechanism

called the Augmented Status Quo Rule with Ascending Transfers that solves the problem causedby high-cost biased types. Without loss of generality, we focus on the case in which q < 12 . Under
this new mechanism, each agent has a third message, which we denote −guilty, and which weinterpret as the agent confessing that (i) he does not know the state and (ii) he prefers to convict
the defendant. Under this new mechanism, the outcome and transfers are given by:

10

outcome−guilty

innocent

guiltytransfers−guilty

innocent

guilty−guiltyconvictacquitconvict−guilty

R0 , R0

R0 , R00, 0

innocent

acquitacquitacquitinnocent

R0 , R0

R1 , R1

0, 0

guiltyconvictacquitconvict

guilty0, 00, 0R2 , R20≈ 1, and R2 − R1 , R1 − R0 , and R0 are bounded below by some affine function of c.
where R
R2
Notice that (i) the confession message −guilty implements the same outcome as message guilty
regardless of the other agent’s message; (ii) each agent can unilaterally implement the status quo
outcome acquit by reporting innocent; and (iii) coordinating on the confession message leads to alower transfer R0 than coordinating on any other message, but reporting the confession message
leads to a positive transfer as long as the other agent does not report guilty. By contrast, reporting
guilty leads to a positive transfer if and only if the other agent also reports guilty.
We now explain why including the confession message makes the mechanism robust to high-costbiased types. First, we note that if agent 1 believes that agent 2 will never send message guilty when
the defendant is innocent (but agent 2 may send −guilty and innocent), then regardless of agent
1’s preference over outcomes and his cost of learning, agent 1 prefers sending −guilty in both states
to sending guilty in both states. The reason is that (i) both strategies induce the same outcome
regardless of agent 2’s message, (ii) none of the two strategies requires any cost of learning, and(iii) agent 1’s expected transfer for sending −guilty in both states equals R0 Pr(m2 6= guilty) andagent 1’s expected transfer for sending guilty in both states equals R2 Pr(m2 = guilty). As long as
agent 2 does not send message guilty when the defendant is innocent, we have Pr(m2 6= guilty) ≥0

Pr(θ = innocent) = 1 − q and Pr(m2 = guilty) ≤ Pr(θ = guilty) = q. Since q < 21 and R≈ 1,
R2
reporting −guilty in both states leads to a higher expected transfer than reporting guilty in bothstates. Hence, the high-cost biased type prefers sending −guilty in both states over sending guilty
in both states.
The second key observation is that when a type sends −guilty in both states, the total probabilityof types that it can infect is bounded above by a linear function of the probability of this type. Thisis because sending message −guilty leads to a transfer of at most R0 , while coordinating on message
innocent or coordinating on message guilty results in strictly greater transfers R1 and R2 . Everytype of agent i ∈ {1, 2} whose payoff is ti − cdi prefers to conduct his investigation and to reportinnocent when the defendant is innocent and to report guilty when the defendant is guilty, as longas he believes that (i) no type of the other agent reports guilty when the defendant is innocent, and(ii) with probability at least 21 , the other agent reports innocent when the defendant is innocent
11and reports guilty when the defendant is guilty.
The proof of Theorem 2, which covers perturbations in which agents may have arbitrarily highlearning costs, generalizes the argument of the previous paragraph and shows that under every
perturbation in which, with probability close to 1, agents are unbiased and have costs of learning
equal to c, there is an equilibrium in which (i) agents never send guilty when the defendant is
innocent, and (ii) with probability close to 1, agents send guilty when the defendant is guilty andsend innocent when the defendant is innocent. Such an equilibrium implements the desired social
choice function with probability close to 1.
High-probability cost perturbations: Although we focus for simplicity on perturbations inwhich agents’ costs of learning coincide with their costs in the unperturbed environment withprobability close to 1, our mechanisms are in fact also robust as long as agents’ costs of learning
are no more than c with probability close to 1. Even if the planner does not know agents’ exact
learning cost, knowing some upper bound that applies with probability close to 1 suffices to achieverobust implementation. See Footnote 11 of Section 3 for details.
Cheap-talk messages:

We assume throughout that it is common knowledge that messages arecheap talk. In the example, this means that we rule out types who directly benefit, say, from sending
message guilty. If we allowed such types, and the benefit for sending guilty were large enough, thensending guilty regardless of θ is these types’ dominant strategy, which would cause contagion since
R2 > R1 > R0 > 0.

3

Model

Unperturbed Environment: A planner wants to implement a social choice function f : Θ →∆(Y ) where Θ is a finite set of states and Y is a set of outcomes.10 The typical elements in thesesets are θ ∈ Θ and y ∈ Y . Let n ≡ |Θ| be the number of states. Let q ∈ ∆(Θ) be the objective
distribution of θ, with q(θ) the probability of state θ. We assume that q(θ) > 0 for every θ ∈ Θ.
10

In general, agents’ ability to learn the state of the world may be limited, creating a discrepancy between what
agents can learn and what the planner cares about. In this case, we interpret θ as what agents can learn, since itis the only information that can be elicited from any mechanism. Moreover, our results extend when agents observe
noisy private signals about the state after paying their costs of learning, as shown in Proposition 1. Our main result
also holds when there is a continuum of states, as shown in Online Appendix A, under the assumption that the social
choice function f and agents’ payoff functions in the unperturbed environment (u1 , u2 ) are continuous with respect
to θ.

12

The planner knows q but does not know θ. She commits to a mechanism M ≡ {M1 , M2 , t1 , t2 , g}in order to elicit θ from two agents, where Mi is a finite set of messages for agent i, ti : M1 × M2 →R+ is the transfer to agent i, and g : M1 ×M2 → ∆(Y ) is the implemented outcome. Our restriction
to finite mechanisms makes our robust implementation results stronger. It is also motivated by thefact that mechanisms with infinitely many messages have undesirable properties.
After observing M, agents simultaneously and independently decide whether to observe θ atsome cost. Let di ∈ {0, 1} be agent i’s decision to obtain information, where di = 1 represents
agent i obtaining information about θ and vice versa. Let ci ≥ 0 be agent i’s cost of learning.11 We
assume that learning is covert in the sense that neither agent −i nor the planner can observe di .
Agents then simultaneously send messages (m1 , m2 ) ∈ M1 × M2 to the planner, after which theplanner makes transfers and implements an outcome according to M. Agent i’s payoff is:ui (θ, y) − ci di + ti .

(3.1)

Robust Implementation: We examine whether the planner can robustly implement f when
agents’ preferences over outcomes, their costs of learning the state, and their beliefs and higherorder beliefs about each other’s payoffs can differ from those of the baseline setting.
Following Kajii and Morris (1997), a perturbation G ≡ {Ω, Π, Q1 , Q2 , ue1 , ue2 , ec1 , ec2 } consists ofa countable set of circumstances Ω, a distribution Π ∈ ∆(Ω) over the set of circumstances which
we assume is independent of θ, a partition Qi of Ω such that agent i ∈ {1, 2} knows which elementof the partition Qi the realized ω belongs to, as well as mappings u
ei : Ω × Θ × Y → R, andeci : Ω → [0, +∞] for i ∈ {1, 2}, where eci (ω) = +∞ means that agent i does not have the ability tolearn θ at ω. Agent i’s payoff under perturbation G isuei (ω, θ, y) − eci (ω)di + ti .

(3.2)

For given c > 0, we say that G is a c-bounded perturbation if eci (ω) ≤ c for every i and ω.
For every ω ∈ Ω, let Qi (ω) be the partition element of Qi that contains ω, which we call agent
i’s type. Type Qi (ω) is a normal type if uei (ω 0 , θ, y) = ui (θ, y) and eci (ω 0 ) = ci for every ω 0 ∈ Qi (ω),
i.e., type Qi (ω) of agent i knows that his payoff in the perturbed environment coincides with his
11

In our baseline model, each agent either fully learns the state or learns nothing. Proposition 1 in Section 5
generalizes the main result to situations where agents can only observe noisy signals about the state after paying
their learning costs. In Online Appendix B, we generalize our result by allowing agents to choose any partition of
the state space as their information structures, and different partitions may incur different costs.

13

payoff in the unperturbed environment. We introduce our notion of small perturbations:η-Perturbation. For every η ∈ (0, 1), we say that G is an η-perturbation ifΠ both agents are normal types ≥ 1 − η.

(3.3)

We say that G is a c-bounded η-perturbation if G is an η-perturbation and is c-bounded.
Intuitively, a perturbation is small if agents’ payoffs coincide with those in the unperturbed
environment with probability close to one, but their payoffs can be very different from the unperturbed environment with small but positive probability. Even though every normal-type agent’s
payoff coincides with his payoff in the unperturbed environment, he may believe that the otheragent is not normal, and may believe that the other agent thinks that he is not normal, and so on.
The email game perturbations considered in Section 2 are η-perturbations since both agents arenormal types when ω ∈ Ω\{ω0 }, and the event Ω\{ω0 } occurs with probability 1 − η under Π.
The planner faces uncertainty about the perturbation G when she designs the mechanism. Afterobserving the perturbation G and the mechanism M, the two agents are playing an incomplete
information game, which we denote by (M, G). A typical strategy profile of this game is denotedby σ. Let gσ (θ) ∈ ∆(Y ) be the implemented lottery over outcomes conditional on the state being
θ when the planner commits to outcome function g and agents behave according to σ.
Like Oury and Tercieux (2012), we focus on partial implementation: the planner requires onlythat f be implemented in at least one equilibrium, not necessarily all equilibria. Our main resultsin Section 4 examine whether the planner can design a mechanism that approximately implements
f for all small enough perturbations.12
1. We say that M robustly implements f if for every ε > 0, there exists η > 0 such that for every
η-perturbation G, there exists an equilibrium σ(G) of the game induced by (M, G), such thatmax ||gσ(G) (θ) − f (θ)||TV < ε,
θ∈Θ

(3.4)

where || · ||T V is the total variation distance between two distributions.
Theorems 1 and 2 extend to a larger class of perturbations in which uei (ω 0 , θ, y) = ui (θ, y) and eci (ω 0 ) ≤ ci withprobability close to 1, i.e., to settings in which the planner knows that agents’ costs of learning are (with probability
close to 1) no more than c1 and c2 , but may not know agents’ exact learning costs. The proof uses similar ideas, but
the analysis is more cumbersome as one needs to redefine agents’ strategies as mappings from states and learning
costs to messages.
1214

2. We say that M robustly implements f for all c-bounded perturbations if for every ε > 0, there
exists η > 0 such that for every c-bounded η-perturbation G, there exists an equilibrium σ(G)of the incomplete information game induced by (M, G) such that inequality (3.4) holds.
We do not characterize the lowest expected transfer needed to robustly implement f . Doing sowould likely require knowing the set of games for which there exist robust equilibria that implementf . However, to the best of our knowledge, there is no characterization of the set of games that have
Kajii-Morris robust equilibria. We do compute the expected aggregate transfer that is needed torobustly implement f under the mechanisms we propose. This transfer may be viewed as an upperbound on the cost needed to robustly implement f . Formally, say that mechanism M robustly
implements f with cost no more than T ∈ R+ if for every ε > 0 and ξ > 0, there exists η > 0 suchthat for every η-perturbation G, there exists an equilibrium σ(G) of the game induced by (M, G)hisuch that inequality (3.4) is satisfied and, moreover, E t1 (m1 , m2 )+t2 (m1 , m2 ) M, G, σ(G) ≤ T +ξ.
Relation to the Existing Literature: In our analysis, the planner cannot condition transferson the realized state. This assumption stands in contrast to existing works on contracting withcostly information acquisition, such as Zermeno (2011), Carroll (2019), and Clark and Reggiani(2021), where transfers can depend on the realized state. Our model fits situations (and, in thisrespect, is consistent with the large literature on implementation) where either the planner cannot
verify the state ex post, or additional information about the state takes a long time to arrive sothat rewarding agents based on such information is impractical.
We also restrict attention to perturbations in which agents’ payoffs are quasi-linear and do
not directly depend on their messages. These assumptions are commonly made in the mechanism
design literature, including Rochet (1987), Chung and Ely (2007), and Bergemann and Morris(2009). Our assumption that messages are cheap talk stands in contrast to the literature on robust
prediction in games such as Kajii and Morris (1997) and Ui (2001), in which players’ actions candirectly affect their payoffs. Since, in our mechanism design setting, agents’ message spaces areendogenously chosen by the planner, these messages have no meaning per se and we thus believethat it is reasonable to view them as cheap talk.
Oury and Tercieux (2012), Chen, Kunimoto and Sun (2020), and Chen, Mueller-Frank and Pai(2022) adopt an interim approach to study robust partial implementation. Similar to our paper,
these works all assume that agents’ messages are cheap talk. These papers examine whether there
exists a mechanism that partially implements a desired social choice function for all nearby interim
15

types. By contrast, we take an ex ante approach and examine whether the planner can robustly
implement a desired social choice function with probability close to one when she knows that agents’beliefs are derived from a common prior and that the agents’ payoff functions coincide with somecommonly known baseline with probability close to one.
Knowledge about the Realized Perturbation:

We assume that the realized perturbation iscommon knowledge among the agents but is unknown to the planner. This assumption is standard
in the robust mechanism design literature (e.g., Chung and Ely 2007). It fits applications in which(i) the planner sets rules (the mechanism) in advance without knowing the specific circumstancesthat the society will be facing (e.g., when designing laws, constitutions, or corporate rules) but (ii)agents do know the particular circumstances they are facing when they decide on how to react tothe mechanism.
Since both agents can observe the perturbation G, one may wonder whether the planner could
ask both agents to report G, and punish both agents if their reports do not coincide (e.g., byimplementing a particular outcome or by giving them negative transfers).
Although this possibility would be worth exploring, we make two observations. First, our focus
on finite mechanisms precludes such a possibility, since there are infinitely many perturbations.
Soliciting information about the realized perturbation requires the use of infinite mechanisms.
Moreover, asking agents to report complicated objects such as the realized perturbation may bedifficult and intractable in practice. Second, when only two agents can learn the state, it is unclear
whether there exists a mechanism that can induce all agent types to report the realized perturbation
truthfully. The reason is that agents’ preferences in the perturbed environment can be arbitrary,so it is impossible to design a punishment that deters all types from lying. For example, theoutcome that punishes some types may constitute an arbitrarily large reward for other types whoare strongly biased in favor of this outcome, and may encourage these latter types to lie about
the perturbation they observed just for the sake of getting this outcome implemented. Moreover,agents’ coordination motives would then imply that a type’s incentive to lie about the perturbation
may encourage other types to lie as well.
The Case of Zero Learning Cost: While our mechanisms achieve robust implementation withpositive learning costs, we are unaware of similar results even when agents have zero learning cost.13
13

When there are three or more agents and the planner is concerned about perturbations for which the learning
costs of all types are equal to zero, there is a trivial solution to the robust implementation problem. The solution16

If c1 = c2 = 0 and u1 (θ, y) and u2 (θ, y) are independent of θ, there is a trivial solution to
the robust implementation problem: The planner promises agent 1 a transfer of −u1 (y) and agent
2 a transfer of −u2 (y) whenever she implements outcome y. The normal type of each agent is
indifferent between all messages, so there exists an equilibrium where all normal types learn thestate and report it truthfully. However, this solution does not work when u1 or u2 depends on θ,or when agents have positive costs of learning.
When c1 = c2 = 0, and (f, u1 , u2 ) satisfies a Maskin monotonicity* condition, which is strictly
stronger than the Maskin monotonicity condition in Maskin (1999), Chen, Kunimoto, Sun, andXiong (2021) show that there exists a finite mechanism that fully implements f under the solution
concept of correlated rationalizability, which implies that their mechanism can fully implement f
under the solution concept of correlated equilibrium. According to Proposition 3.2 in Kajii andMorris (1997), the mechanism in Chen et al (2021) can robustly implement f when (f, u1 , u2 )satisfies Maskin monotonicity*. By contrast, our results in Section 4 construct a different class offinite mechanisms that can robustly implement f without any restriction on (f, u1 , u2 ).

4Main Results

This section presents two main results. Theorem 1 shows that every f is robustly implementable
when agents’ costs of learning are uniformly bounded from above across all the perturbations
considered by the planner. Theorem 2 shows that even when arbitrarily large (or infinite) learning
costs are allowed, every f is robustly implementable, as long as the state’s prior distribution satisfies
a generic assumption.

4.1

Robust Implementation with Bounded Perturbations

Theorem 1. For every c > 0 and f : Θ → ∆(Y ), there exists a mechanism with n ≡ |Θ|messages for each agent that robustly implements f for all c-bounded perturbations.
For simplicity, in the main text, we prove all our results under the assumptions that u1 (θ, y) =u2 (θ, y) = 0 and c1 = c2 = c, i.e., that each normal type’s payoff is equal to his transfer minus
consists in using the majority rule and zero transfers. In this case, no agent is pivotal when other agents are truthfuland truthtelling is an equilibrium. However, such mechanisms can fail when some types have positive costs of learningin the perturbed environment. To see this, note that When a type has a positive learning cost, he has no incentive tolearn the state if he believes that he is never pivotal. For example, suppose that there are three agents and that type
{ω0 } of agent 1 and type {ω0 , ω1 } of agent 2 both have positive learning costs. These types’ messages do not dependon the state when these types believe that they are not pivotal. This, in turn, affects agent 3’s incentive to make astate-contingent report. The contagion process that ensues may lead to an undesirable implementation outcome.

17

his cost of learning and the normal types of both agents face the same cost c. Types that are notnormal can have arbitrary uei (ω, θ, y) and eci (ω). The proofs for general utility functions (u1 , u2 )and heterogeneous costs of learning are in Appendix A and do not present additional conceptual
challenges.
Proof. We propose a mechanism called the Status Quo Rule with Ascending Transfers. Let Θ ≡{θ1 , ..., θn }. Each agent’s message space is given by M1 = M2 ≡ M ≡ {1, 2, ..., n}. The outcome
function isg(m1 , m2 ) = f (θm1 )if m1 = m2

 f (θ1 )otherwise.

(4.1)

The transfer function for agent i ∈ {1, 2} isti (mi , m−i ) = Rj

if m1 = m2 = j 0otherwise,

where R1 > q(θc1 ) , Rj > R1 for every j ≥ 2, andPn

j=2 (R(4.2)

j − R1 )q(θ j ) > 2c.14

In the unperturbed game induced by our mechanism, an agent’s pure strategy can be described
as an n-dimensional vector (m1 , ..., mn ), where mj ∈ M is the message that the agent sends when
the state is θj . If agent 1 uses strategy (m11 , ..., mn1 ) and agent 2 uses strategy (m12 , ..., mn2 ), thenagent i’s expected payoff equals
n
X

o 

n
q(θj ) ti (mj1 , mj2 ) + ui (θj , g(mj1 , mj2 )) − 1 − 1{m1i = ... = mni } ci .

(4.3)

j=1

When u1 = u2 = 0 and c1 = c2 = c—the case we focus on in the main text—agent i’s expected
payoff is equal to

n
X



q(θj )ti (mj1 , mj2 ) − 1 − 1{m1i = ... = mni } c.

(4.4)

j=1

In the perturbed game induced by our mechanism and G = {Ω, Π, Q1 , Q2 , ue1 , ue2 , ec1 , ec2 }, a type’s
pure strategy is also given by (m1 , ..., mn ), where mj ∈ M is the message that this type sends
when the state is θj . A pure strategy profile {(m1i (ω), ..., mni (ω))}i∈{1,2},ω∈Ω describes each agent i’smessage mji (ω) for each state θj and circumstance ω, and must satisfy the restriction that mji (ω)
be measurable with respect to Qi for every i ∈ {1, 2} and j ∈ {1, 2, ..., n}. For every i ∈ {1, 2} and
14

The mechanism for general (u1 , u2 , c1 , c2 ) has the same outcome function. The transfers satisfy (A.1) and (A.2).

18

ω ∗ ∈ Ω, the expected payoff for type Qi (ω ∗ ) of agent i’s is given by
n
X

h


i
q(θj )Eω ti (mj1 (ω), mj2 (ω)) + u
ei ω, θj , g(mj1 (ω), mj2 (ω)) Qi (ω ∗ )

j=1


 h
i
− 1 − 1{m1i (ω ∗ ) = ... = mni (ω ∗ )} Eω eci (ω) Qi (ω ∗ ) .

(4.5)

Let Σ ≡ {1, 2, ..., n}n denote the set of pure strategies. Agent i ∈ {1, 2} is truthful if he uses
strategy (1, 2, ..., n), i.e., if he truthfully reports the index of the realized state. We define Σ∗ ⊂ Σas:noΣ∗ ≡ (m1 , ..., mn ) ∈ Σ such that mj ∈ {1, j} for every j ≥ 1 .

(4.6)

If an agent’s strategy belongs to Σ∗ , then in every state θj , this agent either sends the status
quo message 1 or reports the state truthfully by sending message j. For example, when n = 2,
Σ∗ = {(1, 1), (1, 2)} while Σ = {(1, 1), (1, 2), (2, 1), (2, 2)}. The rest of the proof consists of threesteps.
Step 1:

The first step examines a restricted game without perturbation where both agents are

only allowed to use (mixed) strategies in ∆(Σ∗ ) and it is common knowledge that agents’ payoffs
are t1 − cd1 and t2 − cd2 . For any given γ ∈ [0, 1], a γ-dominant equilibrium is a Nash equilibrium
where every agent finds it strictly optimal to play his equilibrium strategy when he believes thatthe other agent will play their equilibrium with probability at least γ.
Lemma 1. In the restricted game without perturbation, there exists γ < 21 such that both agents
being truthful is a γ-dominant equilibrium.
Proof. In the restricted game without perturbation, agents can only send message 1 conditional onθ = θ1 and, for every j ≥ 2, agents can only send message 1 or message j conditional on θ = θj .
• If agent 1 sends message j in state θj , his expected transfer equals Pr(m2 = j|θj )Rj .
• If agent 1 sends message 1 in state θj , his expected transfer equals Pr(m2 = 1|θj )R1 .
Suppose agent 2 is truthful with probability at least 12 , Pr(m2 = j|θj ) ≥ 12 and Pr(m2 = 1|θj ) ≤1
2.

Since Rj > R1 for every j ≥ 2, agent 1 strictly prefers strategy (1, 2, ..., n) to any otherP
strategy (m1 , ..., mn ) that belongs to Σ∗ but is neither (1, 2, ..., n) nor (1, 1, ..., 1). Since nj=2 (Rj −R1 )q(θj ) > 2c, agent 1’s expected payoff under (1, 2, ..., n) minus that under (1, 1, ..., 1) is at least

19

Pn

1
j
1
j
j=2 2 (R − R )q(θ ) − c, which is strictly positive. Since each agent strictly prefers (1, 2, ..., n) to

any other strategy in Σ∗ when he believes that the other agent is truthful with probability at least1
1
2 , there exists γ < 2 such that both agents being truthful is a γ-dominant equilibrium.

Step 2: For any G, consider a restricted game with perturbation G where agent i ∈ {1, 2}’s payoffis uei (ω, θ, y) − eci (ω)di + ti , and agents are only allowed to use strategies in ∆(Σ∗ ). Since there
exists γ < 21 such that both agents being truthful is a γ-dominant equilibrium in the restricted
game without perturbation, the Critical Path Lemma in Kajii and Morris (1997) implies that:
Lemma 2. For every ε > 0, there exists η > 0, such that for every η-perturbation G, there
exists an equilibrium σ(G) in the restricted game with perturbation G, under which the probability
with which both agents being truthful is greater than 1 − ε.
Since g(j, j) = f (θj ) for every j ∈ {1, 2, ..., n}, f is implemented when both agents are truthful,which occurs with probability at least 1 − ε when agents behave according to σ(G).
Step 3: We show that for every G, the equilibrium σ(G) constructed in the previous step remains
an equilibrium under perturbation G when agents can use any strategy in the set ∆(Σ).
Suppose by way of contradiction that there exists a type Q1 (ω) who strictly prefers (m1 , ..., mn ) ∈/Σ∗ to all strategies in Σ∗ when agent 2 behaves according to σ(G). Let us define a new strategy(m1∗ , ..., mn∗ ) for agent 1 as follows:

mj∗ ≡


 mj

if mj ∈ {1, j} 1

if mj ∈
/ {1, j}for every j ∈ {1, 2, ..., n}.

By construction, (m1∗ , ..., mn∗ ) ∈ Σ∗ . We compare type Q1 (ω)’s expected payoff from (m1 , ..., mn )to his expected payoff from (m1∗ , ..., mn∗ ).
1. First, (m1 , ..., mn ) and (m1∗ , ..., mn∗ ) lead to the same joint distribution of (θ, y) when agent 2’s
strategy belongs to ∆(Σ∗ ). This is because mj∗ = mj when mj ∈ {1, j}; and when mj ∈/ {1, j},agent 2 sends either 1 or j when the realized state is θj . Given the outcome function (4.1),
the implemented outcome is f (θ1 ) whenever agent 1 sends a message other than j.
2. Second, conditional on each state, (m1∗ , ..., mn∗ ) gives a weakly greater transfer to agent 1
than does (m1 , ..., mn ). This is because when the state is θj and agent 2’s message belongsto {1, j}, agent 1 receives zero transfer when he sends any message that is neither 1 nor j.
20

3. Third, if (m1∗ , ..., mn∗ ) requires a strictly greater learning cost compared to (m1 , ..., mn ), thenm1 = ... = mn ≥ 2. Conditional on θ = θj , the transfer under m1∗ is R1 and the transfer under
m1 is 0 when the other agent’s strategy belongs to ∆(Σ∗ ). Since q(θ1 )R1 ≥ c, the expectedtransfer from (m1∗ , ..., mn∗ ) is greater than c plus the expected transfer from (m1 , ..., mn ).
Since each agent’s learning cost is no more than c when G is a c-bounded perturbation, every
type prefers (m1∗ , ..., mn∗ ) to (m1 , ..., mn ). This contradicts the hypothesis that type Q1 (ω) strictlyprefers (m1 , ..., mn ) to all strategies in Σ∗ . Since σ(G) is an equilibrium in the restricted game with
perturbation when agents are only allowed to use strategies in ∆(Σ∗ ), σ(G) remains an equilibriumin the unrestricted game with perturbation G in which agents can use any strategy in ∆(Σ).
Implementation Cost:

We bound the expected cost to implement f focusing on the case where

u1 = u2 = 0 and c1 = c2 = c. The cost for the general case is in Appendix A. The expected costP
2c
E[t1 + t2 ] under our mechanism equals 2 nj=1 q(θj )Rj , which can be as low as maxθ∈Θq(θ) + 4c.
cThis is because when θ1 maximizes q(θ), R1 can be as low as maxθ∈Θq(θ) , and the requirement that
Pn
P
Pn
n
j
j
j
1
j
1
j
j=2 q(θ ).
j=2 q(θ )R can be as low as 2c + R
j=2 (R − R )q(θ ) > 2c implies that

4.2

Robust Implementation with an Ex Ante Most Likely StateWe show that as long as the objective state distribution q ∈ ∆(Θ) satisfies a generic condition,stated below, every f is robustly implementable even when some types have arbitrarily large biases
or learning costs, or when some types are inept in the sense that they do not have the ability tolearn the state.
Definition 1. q ∈ ∆(Θ) is generic if there exists θ∗ ∈ Θ such that q(θ∗ ) > q(θ0 ), ∀θ0 6= θ∗ .
When there are two states, for instance, this condition rules out the prior q that assigns probability 12 to each state, but allows any other full support distribution. In Online Appendix A, we
generalize our result to environments in which (i) there is a continuum of states, (ii) the objective
distribution q has no atom, and (iii) (f, u1 , u2 ) are continuous with respect to the state. In thatenvironment, the generic condition is no longer required and our result holds for all full support
distributions.
Theorem 2. Suppose q is generic. For every social choice function f : Θ → ∆(Y ), there exists
a mechanism with 2|Θ| − 1 messages for each agent that robustly implements f .

21

Proof. We propose a mechanism called the Augmented Status Quo Rule with Ascending Transfers.
When q is generic, we can write Θ ≡ {θ1 , ..., θn } such that q(θ1 ) > q(θ2 ) ≥ ... ≥ q(θn ) > 0.
Consider a mechanism where each agent’s message space is given by M1 = M2 = M ={−n, ..., −2} ∪ {1} ∪ {2, ..., n}. The outcome function isg(m1 , m2 ) = f (θ|m1 | )if |m1 | = |m2 | f (θ1 )otherwise.

(4.7)

The transfer function for agent i ∈ {1, 2} is



Rj


ti (mi , m−i ) =
R0



 0

if m1 = m2 = j ≥ 1(4.8)

if m1 , m2 ≤ 1 but (m1 , m2 ) 6= (1, 1)
otherwise,

where Rn , ..., R0 satisfy min{Rn , ..., R2 } > R1 > R0 > 0,nXq(θj )(Rj − R1 ) > 2c,(4.9)

q(θj )
R0>
for every j ≥ 2.
Rj
q(θ1 )(4.10)

j=2

and

When q is generic, there exist Rn , ..., R0 that satisfy these inequalities. Our mechanism when there
are two states is presented in Section 2. When there are three states, our mechanism is given by:
g

−3

−2

1

2

3

t1 , t2

−3

−2

1

2

3

−3

f (θ3 )f (θ1 )f (θ1 )f (θ1 )f (θ3 )

−3

R0 , R0

R0 , R0

R0 , R0

0, 0

0, 0

−2

f (θ1 )f (θ2 )f (θ1 )f (θ2 )f (θ1 )

−2

R0 , R0

R0 , R0

R0 , R0

0, 0

0, 0

1

f (θ1 )f (θ1 )f (θ1 )f (θ1 )f (θ1 )

1

R0 , R0

R0 , R0

R1 , R1

0, 0

0, 0

2

f (θ1 )f (θ2 )f (θ1 )f (θ2 )f (θ1 )

2

0, 0

0, 0

0, 0

R2 , R2

0, 0

3

f (θ3 )f (θ1 )f (θ1 )f (θ1 )f (θ3 )

3

0, 0

0, 0

0, 0

0, 0

R3 , R3

An agent’s (or an agent type’s) pure strategy is (m1 , ..., mn ), where mj ∈ M represents themessage he sends when the state is θj . He pays the cost of learning unless m1 = ... = mn . The
truthful strategy is (1, 2, ..., n), according to which the agent reports the index of the realized state.

22

Let Σ ≡ {−n, ..., −2, 1, 2, ..., n}n be the set of pure strategies. LetnoΣ∗ ≡ (m1 , ..., mn ) ∈ Σ such that mj ∈ {−n, ..., −2, 1} ∪ {j} for every j ≥ 1 .

(4.11)

By definition, if an agent’s strategy belongs to Σ∗ , then conditional on each state θj , he either sends
a negative message, or sends the status quo message 1, or sends message j. For example, whenSn = 2, Σ∗ = {(−2, −2), (−2, 1), (−2, 2), (1, −2), (1, 1), (1, 2)} while Σ = Σ∗ {(2, −2), (2, 1), (2, 2)}.
Step 1:

We examine a restricted game without perturbation in which it is common knowledge

that payoffs are t1 − cd1 and t2 − cd2 ,15 and both agents are only allowed to use strategies in ∆(Σ∗ ).
We show that there exists γ < 21 such that both agents being truthful is a γ-dominant equilibrium in the restricted game without perturbation. Suppose agent 1 believes that agent 2 plays(1, 2, ..., n) with probability at least 21 and that agent 2’s strategy belongs to ∆(Σ∗ ).
• For every j ≥ 2, conditional on θ = θj , agent 1’s expected transfer equals Pr(m2 = j|θj )Rj if
he sends message j, and is at most Pr(m2 ≤ 1|θj )R1 if he sends message 1 or any negative
message. If he believes that agent 2 is truthful with probability at least 21 , then Pr(m2 =j|θj )Rj > Pr(m2 ≤ 1|θj )R1 given that Rj > R1 .
• Conditional on θ = θ1 , agent 1’s expected transfer equals Pr(m2 = 1|θ1 )R1 + Pr(m2 ≤−2|θ1 )R0 if he sends message 1 and equals R0 if he sends any negative message. If hebelieves that agent 2 is truthful with probability at least 12 , then Pr(m2 = 1|θ1 )R1 + Pr(m2 ≤−2|θ1 )R0 > R0 given that R1 > R0 .
The discussion above implies that agent 1 strictly prefers the truthful strategy to any other nonconstant strategy that belongs to Σ∗ . Agent 1’s expected payoff from using a constant strategyPin Σ∗ is at most nj=1 q(θj )R1 Pr(m2 ≤ 1|θj ), while his expected payoff from being truthful is atPP
least nj=1 q(θj )Rn Pr(m2 = j|θj ). Inequality (4.9) implies that nj=1 q(θj )Rn Pr(m2 = j|θj ) >
Pn
1
j
1
j
j=1 q(θ )R Pr(m2 ≤ 1|θ ) when agent 2 is truthful with probability at least 2 . Since agent 1
strictly prefers to be truthful when he believes that agent 2 is truthful with probability at least 12 ,there exists γ < 12 such that agent 1 strictly prefers (1, 2, ..., n) to any other strategy in Σ∗ when
agent 2’s strategy belongs to ∆(Σ∗ ) and is truthful with probability at least γ.
15

Recall that in the main text, our proof focuses on the case where u1 = u2 = 0 and c1 = c2 = c. We explain how
to generalize our proof to arbitrary u1 (θ, y) and u2 (θ, y), and to heterogeneous costs of learning in Appendix A.

23

Step 2:For any perturbation G, consider a restricted game with perturbation G where agent i’s

payoff is uei (ω, θ, y) − eci (ω)di + ti , and agents are only allowed to use strategies in ∆(Σ∗ ).
Since there exists γ < 12 such that both agents being truthful is a γ-dominant equilibrium inthe restricted game without perturbation, the Critical Path Lemma implies that for every ε > 0,
there exists η > 0, such that for every η-perturbation G, there exists an equilibrium σ(G) in the
restricted game perturbed by G in which both agents are truthful with probability more than 1 − ε.
Since g(j, j) = f (θj ) for every j ∈ {1, 2, ..., n}, f is implemented when both agents are truthful,which occurs with probability more than 1 − ε when agents behave according to σ(G).
Step 3: We show that when q is generic and {Rn , ..., R1 , R0 } satisfy (4.9) and (4.10), the equilibrium σ(G) in the restricted game with perturbation G remains an equilibrium in the unrestricted
game with perturbation G in which agents can use any strategy in ∆(Σ), not just those in ∆(Σ∗ ).
For this purpose, we only need to show that for every pure strategy that does not belong to Σ∗ ,there exists a pure strategy that belongs to Σ∗ such that every type of agent 1 weakly prefers thelatter to the former when he believes that agent 2 plays according to σ(G). We consider two cases.
First, for every (m1 , ..., mn ) ∈/ Σ∗ that is non-constant, let (m1∗ , ..., mn∗ ) be defined as

mj∗ ≡


 mj

if mj ∈ {−n, ..., −2} ∪ {1, j} −mj

if mj ∈
/ {−n, ..., −2} ∪ {1, j}

for every j ∈ {1, 2, ..., n}.

(4.12)

By construction, (m1∗ , ..., mn∗ ) ∈ Σ∗ . Since (m1 , ..., mn ) is non-constant, (m1∗ , ..., mn∗ ) does notincrease the cost of learning compared to (m1 , ..., mn ). The outcome function (4.7) ensures that,regardless of whether agent 1 uses strategy (m1∗ , ..., mn∗ ) or strategy (m1 , ..., mn ), he will induce
the same joint distribution of (θ, y) regardless of agent 2’s strategy. When agent 1 believes thatagent 2’s strategy belongs to ∆(Σ∗ ), which is the case when agent 2 plays according to σ(G), agent
1 receives a weakly greater transfer from (m1∗ , ..., mn∗ ) compared to (m1 , ..., mn ). This is because
sending any message that does not belong to {−n, ..., −2} ∪ {1, j} leads to a transfer of 0 in stateθj when agent 2’s message in state θj belongs to {−n, ..., −2} ∪ {1, j}.
Second, for every (m1 , ..., mn ) ∈/ Σ∗ that satisfies m1 = ... = mn , there exists k ∈ {2, 3, ..., n}such that (m1 , ..., mn ) = (k, ..., k). Let us compare the expected payoff that any given type of agent
1 receives with strategies (k, ..., k) and (−k, ..., −k). The outcome function in (4.7) implies that(k, ..., k) and (−k, ..., −k) lead to the same joint distribution over (θ, y). None of these strategies
requires agent 1 to learn θ. The expected transfer is Pr(m2 = k)Rk if agent 1 uses strategy (k, ..., k),24and is Pr(m2 ≤ 1)R0 if he uses strategy (−k, ..., −k). When every type of agent 2’s strategy belongsto ∆(Σ∗ ), we have Pr(m2 ≤ 1) ≥ q(θ1 ) and Pr(m2 = k) ≤ q(θk ). Condition (4.10) then implies
that Pr(m2 = k)Rk ≤ q(θk )Rk < q(θ1 )R0 ≤ Pr(m2 ≤ 1)R0 . Hence, type Q1 (ω)’s expected transfer
is weakly greater under (−k, ..., −k) compared to that under (k, ..., k).
Implementation Cost:

In the case where u1 = u2 = 0 and c1 = c2 = c, the expected costP
E[t1 + t2 ] under our mechanism equals 2 nj=1 q(θj )Rj . A tight lower bound for this is
4c
+ 4c.
1
j
j=2 (q(θ ) − q(θ ))Pn(4.13)

The calculations are in Appendix A, together with the implementation cost in the general case.

5

Trembles, Noisy Signals, & Unknown State Distributions

Section 5.1 modifies our mechanism so that it can robustly implement f when (i) agents tremble
with small probability, and (ii) agents observe noisy private signals about the state after paying
their costs of learning. This extension captures situations in which learning the state perfectlyis prohibitively costly and agents can only learn an imperfect signal about the state. Section 5.2
examines the robustness of our results when the planner does not know the state distribution q
or faces uncertainty about agents’ beliefs about the state (e.g., when agents receive noisy private
signals about the state before observing the mechanism and the planner does not know the agents’
information structures).

5.1

Robustness to Trembles and Noisy Information

In the proofs of Theorems 1 and 2, we construct equilibria in which no type uses any strategy that
does not belong to ∆(Σ∗ ). One may wonder whether our results are robust when agents tremble
with small probability or when agents cannot perfectly observe θ even after paying their costs oflearning, in which case agents may not know each others’ private beliefs. This section shows that
our results are robust when the trembling probabilities and the noise in agents’ private signals are
small.
Trembles:For any mechanism M, suppose for every i ∈ {1, 2}, when agent i intends to send

message mi ∈ Mi , the planner receives mi with probability 1 − τ and receives a message that is25

drawn according to Fi ∈ ∆(Mi ) with probability τ , where τ ∈ (0, 1) is the probability with which
agents tremble. Throughout this section, we distinguish between an agent’s intended message andhis realized message. We suppress the dependence of Fi on M in order to simplify notation.
Imperfect Signals about the State:

Suppose q ∈ ∆(Θ) is generic. Let Θ ≡ {θ1 , ..., θn } such|S |that q(θ1 ) > q(θ2 ) ≥ ... ≥ q(θn ) > 0. For every i ∈ {1, 2}, let Si ≡ {s1i , ..., si i } be agent i’s signal
space. Note that |Si | can be any finite number, i.e., we do not impose any upper bound on thenumber of signal realizations. Let π ∈ ∆(Θ × S1 × S2 ) be the joint distribution of the state andagents’ private signals. For every τ > 0, we say that π is of size τ if(a) The marginal distribution of π on Θ is q ∈ ∆(Θ).
(b) There exists a mapping hi : Si → {1, 2, ..., n} for every i ∈ {1, 2} such that
π h−i (s−i ) = hi (si ) si ≥ 1 − τ for every si ∈ Si ,
and

n
X

X

π(θj , si ) ≥ 1 − τ .

(5.1)

(5.2)

j=1 si ∈{hi (si )=j}

Our first requirement is that the marginal distribution on θ be consistent with the objective
state distribution q. Our second requirement is reminiscent of Chung and Ely (2003), Aghion,
Fudenberg, Holden, Kunimoto and Tercieux (2012), and Sugaya and Takahashi (2013), in which
every signal that can be observed by agent i ∈ {1, 2} is linked to a particular state, given by themapping hi . One can think about hi as endowing each of agent i’s realized signal with a meaning,where each meaning corresponds to a state. According to requirement (b), the mappings fromrealized signal to their meanings satisfy (i) no matter which signal an agent observes, he believes
that the other agent receives a signal with the same meaning with probability close to 1, and (ii)the meaning of each agent’s signal coincides with the state with probability close to 1.
The planner knows neither G nor {τ, F1 , F2 , π}. She would like to design a mechanism M that
can approximately implement f for all small enough perturbations, small enough trembles, andsmall enough noise in agents’ private signals. Agent i knows the mechanism M, the perturbationG, his information about ω under G, as well as {τ, F1 , F2 , π}. He decides whether to pay a cost ci
in order to learn si and, after this decision and possibly the observation of si , which message in Mi
he intends to send. The planner observes the realized messages but not the intended messages.
26

Proposition 1. Suppose q is generic. For every f : Θ → ∆(Y ), there exists a mechanismwith 2|Θ| − 1 messages for each agent, such that for every ε > 0, there exist η > 0 and τ > 0such that for every trembling probability τ < τ , every (F1 , F2 ), every π that is of size τ , and every
η-perturbation G, there exists an equilibrium σ(G) such that maxθ∈Θ ||gσ(G) (θ) − f (θ)||TV < ε.
The proof is in Appendix F. When there are two states, our Augmented Status Quo Rule withAscending Transfers can robustly implement f when agents tremble with small probability andthere is a small amount of noise in their private signals about the state, and the proof is similar tothat of Theorem 2. When there are three or more states, we propose a new mechanism that has
the same outcome function as the mechanism in the proof of Theorem 2 but has a different transfer
function.

5.2

Uncertainty about the State Distribution

Our earlier proofs assume that the planner knows the objective state distribution and that thisprior distribution is equal to both agents’ prior belief before they take their actions—including
their decision of whether to learn the state. In some applications, the planner may face uncertainty
about the state distribution or about agents’ beliefs about the state. This situation may arise, forinstance, if the planner faces Knightian uncertainty about the state, or if each agent privately andfreely observes a noisy signal about the state before deciding whether to pay an additional cost tolearn θ and the planner does not know agents’ information structures.
To model this situation, suppose that agent i’s belief is qi ∈ ∆(Θ) when he decides whether
to pay cost ci in order to fully learn θ. We assume these beliefs are obtained as follows: agents
have a prior belief q about θ, and form their respective interim beliefs q1 and q2 after receiving
some informative signals. Intuitively, agent i ∈ {1, 2} privately observes a signal si for free andhis interim belief qi is derived according to Bayes rule. We allow q1 and q2 to have arbitrarycorrelations as long as they satisfy the martingale condition E[q1 ] = E[q2 ] = q.
The planner knows neither q nor the realizations of q1 and q2 . She only knows that q, q1 , and q2
belong to a subset q ⊂ ∆(Θ). Our baseline model from earlier sections corresponds to the special
case in which q is a singleton. In the more general formulation, the planner need not know theexact state distribution. Rather, she knows that this distribution belongs to some subset. This
formulation also allows agents to have more information about the state relative to the planner,even before they decide whether to pay the cost and to learn the state. The planner does notknow the agents’ information structures but knows that their interim beliefs belong to a certain
27

range. The planner’s objective is to design a mechanism M that can robustly implement f for all(q1 , q2 ) ∈ q × q and for all small enough (c-bounded) perturbations.
Whether the planner can achieve her objective depends on q, i.e., on the extent to which sheknows the agents’ interim beliefs. When q is larger, the robust implementation problem becomes
harder. We say that q is interior if there exists τ > 0 such that q(θ) > τ for every θ ∈ Θ andnoq ∈ q. Let B(q, τ ) ≡ q 0 ∈ ∆(Θ) ||q 0 − q||T V ≤ τ denote the τ -neighbourhood of q.
Proposition 2. For any given social choice function f : Θ → ∆(Y ):1. Suppose q is interior. For every c > 0, there exists a mechanism with n messages for eachagent that robustly implements f for all c-bounded perturbations.
2. For every generic q ∈ ∆(Θ), there exists τ > 0 such that if q ⊂ B(q, τ ), then there exists a
mechanism with 2n − 1 messages for each agent that robustly implements f .
The proof is in Online Appendix D. Proposition 2 implies that even when (i) the planner does
not know precisely what the objective state distribution is and (ii) agents may know more about
the state than the planner does even before they pay the cost of learning, the desired social choicefunction is still robustly implementable as long as one of the two conditions is satisfied:
1. The planner is confident that agents’ interim beliefs are not arbitrarily precise (i.e., assign
probability close to 0 to some states) and agents’ costs of learning are bounded from above.
2. The planner knows what the ex ante most likely state is and is confident that the signals
freely received by the agents are sufficiently noisy.
Proposition 2 can be extended to the case in which q includes degenerate beliefs that assign
probability 1 to some particular state. Nevertheless, we do need to rule out situations such as thefollowing one: (i) Θ = {θ1 , θ2 , θ3 }, (ii) the planner knows that the agents can rule out one state forfree before paying the information acquisition cost but, (iii) the planner does not know which state
the agents rule out.

6

Stronger Notions of Robust Implementation

This section considers the robust implementation of non-constant social choice functions, defined
as follows.

28Definition 2. Social choice function f is non-constant if there exist θ, θ0 such that f (θ) 6= f (θ0 ).
Section 6.1 shows that the planner cannot robustly implement any non-constant social choicefunction when we allow for perturbations where agents’ payoffs do not coincide with those in the unperturbed environment with high probability. Sections 6.2 and 6.3 show that when agents’ costs oflearning in the unperturbed environment are above some cutoff, the planner cannot approximately
implement any non-constant social choice function in all equilibria, and she cannot robust-partially
implement any non-constant social choice function in an interim sense.

6.1

Impossibility of Global Implementation

First, suppose that perturbations for which eci (ω) is arbitrarily large are allowed, and that agents’
payoffs may differ from those in the unperturbed environment with probability bounded away fromzero. In this case, it is easy to see that no finite mechanism can approximately implement any nonconstant social choice function. To this end, fix any finite mechanism M. Clearly, no agent has
any incentive to learn the state when agents’ learning costs exceed the maximal transfer promisedby mechanism M plus their maximal benefit from implementing specific outcomes. This implies
that f cannot be implemented conditional on this event, which can occur with probability bounded
above 0.
Next, we show that even when we only consider c-bounded perturbations, or even when we only
consider perturbations where it is common knowledge that agents’ costs are c1 and c2 , no finite
mechanism can approximately implement any non-constant social choice function if the probabilityof normal types is not close to 1. To state the result formally, we will say that mechanism M
globally implements f for all c-bounded perturbations if for every ε > 0 and every c-bounded
perturbation G, there exists an equilibrium σ(G) of incomplete information game (M, G) such thatmaxθ∈Θ ||gσ(G) (θ) − f (θ)||TV < ε.
Theorem 3. For every c > 0 and every f : Θ → ∆(Y ) that is non-constant, there exists nofinite mechanism that can globally implement f for all c-bounded perturbations.
The proof is in Appendix B. Here we provide some general intuition. For every f that is nonconstant, one can find θ ∈ Θ such that f (θ) does not belong to the convex hull of {f (θ0 )}θ0 6=θ . Fora mechanism M to implement f in a perturbation where all types of agent 1 dislike f (θ) and likeoutcomes in {f (θ0 )}θ0 6=θ , there must exist a distribution of agent 2’s messages under which agent
1’s payoff cannot exceed his payoff from f (θ) no matter which message he sends. This implies that29

under another perturbation where all types of agent 2 like f (θ), agent 2 can guarantee his payofffrom f (θ) regardless of agent 1’s message, which means that mechanism M cannot implement any
outcome in {f (θ0 )}θ0 6=θ .
In fact, the proof of Theorem 3 implies the following corollary, which shows that even if one
focuses on virtual implementation, no mechanism can virtually implement f when payoff perturbations have a probability that is bounded away from zero.
Corollary 1. For every f : Θ → ∆(Y ) that is non-constant, there exists k(f ) > 0 such that forevery finite mechanism M and every η > 0, there exists a c-bounded η-perturbation G, such thatfor every equilibrium σ(G) of the game (M, G), we have maxθ∈Θ ||gσ(G) (θ) − f (θ)||TV ≥ ηk(f ).
Corollary 1 shows that for every finite mechanism M, there exists a perturbation G under which
every equilibrium of the incomplete information game induced by (M, G) implements a social choicefunction that is bounded away from f . This corollary shows that, even if one focuses on partial
and virtual implementation, robust implementation is possible only if the perturbed environmentis close to the unperturbed environment.

6.2

Full Implementation and Virtual Implementation

We now examine whether the planner can approximately implement f in all equilibria under all
small enough perturbations. Say that f is virtually implementable if for every ε > 0, there exists
a mechanism Mε , such that ||gσ (θ) − f (θ)||T V ≤ ε for every θ ∈ Θ and every equilibrium σ underMε .16 Our first result provides two sufficient conditions under which every non-constant social
choice function is not virtually implementable, even with no robustness concern.
Theorem 4. Suppose f is non-constant.
1. If (u1 , u2 ) do not depend on θ, then f is not virtually implementable.
2. For every (u1 , u2 ), there exists c > 0 that depends only on (u1 , u2 ) such that f is not virtually
implementable when c1 , c2 > c.
The proof, in Appendix C, shows that as long as c1 and c2 are above some cutoff c > 0, evenwhen the planner can use arbitrarily large transfers, there always exists an equilibrium where no16

Our definition of virtual implementation is similar to that of Abreu and Matsushima (1992) except that we
require the desired outcome to be implemented in every Nash equilibrium while they require the desired outcome
to be implemented in every rationalizable strategy. Since our goal is to show a negative result—every non-constantsocial choice function is not virtually implementable—using a stronger solution concept makes our result stronger.

30

agent learns the state. Intuitively, suppose agent 1’s message does not depend on θ. Since agents’transfers depend only on the messages, the only incentive for agent 2 to learn θ is to induce a morefavorable joint distribution of (θ, y) in order to increase u2 (θ, y). Therefore, agent 2’s benefit fromlearning the state depends only on u2 . When agent 2’s cost of learning outweighs this benefit fromincreasing u2 (θ, y), he has no incentive to learn provided that agent 1’s message does not dependon θ, no matter how large the promised transfers are. This logic gives rise to equilibria where no
agent learns the state and the implemented outcome is the same regardless of the state.
We also provide sufficient conditions under which the desired social choice function f can berobustly implemented in all equilibria. Say that f is robust-fully implementable if there exists
a finite mechanism M such that (i) every equilibrium of M in the unperturbed environment
implements f , and (ii) for every ε > 0, there exists η > 0 such that for every η-perturbation G,||gσ(G) (θ) − f (θ)||T V ≤ ε for every θ ∈ Θ and every equilibrium σ(G) of (M, G).
First, when c1 = c2 = 0 and (f, u1 , u2 ) satisfies Maskin monotonicity∗, a condition that isstrictly stronger than Maskin monotonicity, Chen, Kunimoto, Sun, and Xiong (2021) construct afinite mechanism that fully implements f under the solution concept of correlated rationalizability.
Since the unique correlated equilibrium is robust in the sense of Kajii and Morris (1997), themechanism in Chen, Kunimoto, Sun, and Xiong (2021) robust-fully implements f .
When c1 , c2 > 0, f is robust-fully implementable when one of the agent’s payoff function satisfies
a strict version of Rochet (1987)’s cyclical monotonicity condition and that c1 and c2 are below some
cutoff. Formally, (ui , f ) satisfies strict cyclical monotonicity if for every permutation ξ : Θ → Θ,
we haveXθ∈Θui (θ, f (θ)) ≥Xui θ, f (ξ(θ)) ,

(6.1)

θ∈Θ

with strict inequality for every ξ that satisfies f (ξ(θ)) 6= f (θ) for some θ ∈ Θ. Condition (6.1) isthe cyclical monotonicity condition. The strict inequality condition has no bite when f is constant,but can be violated when f is non-constant (e.g., when ui does not depend on θ).
Theorem 5. If (ui , f ) satisfies strict cyclical monotonicity for some i ∈ {1, 2}, then there exists
c > 0 such that when ci ≤ c, there is a finite mechanism that robust-fully implements f .
The proof is in Appendix D.

31

6.3

Interim Notion of Robust Implementation

Finally, we show that robust implementation in the interim sense is impossible when the costs oflearning c1 and c2 lie above some cutoff that depends only on the unperturbed preferences u1 andu2 , and which holds regardless of whether the planner can use arbitrarily large transfers.
We adapt the notion of interim robust implementation in Oury and Tercieux (2012) to our
setting. Agents need to pay a cost to learn the state θ ∈ Θ. The planner knows the objective
state distribution q ∈ ∆(Θ) but faces uncertainty about agents’ payoffs and costs of learning, andcan use transfers to motivate the agents. Let Y be the set of outcomes, with y ∈ Y . Let Ω be acountable set of circumstances. Agent i’s payoff is uei (ω, θ, y) − eci (ω)di + ti . Let ω ∗ ∈ Ω be suchthat uei (ω ∗ , θ, y) = ui (θ, y) and eci (ω ∗ ) = ci for every (θ, y) and i ∈ {1, 2}.
A model is denoted by Z ≡ (Z, κ) where Z ≡ Z1 × Z2 is a countable type space and κi (zi ) ∈∆(Ω × Z−i ) is the belief associated with type zi ∈ Zi . For two models Z ≡ (Z, κ) and Z 0 ≡ (Z 0 , κ0 ),0 ) ∩ E] = κ (z 0 )(E) for every z 0 ∈ Z 0 and measurable event
Z 0 ⊂ Z if Z 0 ⊂ Z and κ0i (zi0 )[(Ω × Z−ii iiiE ⊂ Ω × Z−i . For each type zi , one can compute his first-order belief (i.e., his belief about ω), his
second-order belief (i.e., his belief about ω and the first-order belief of agent −i), and so on.17 Let
hki (zi ) denote the kth-order belief of type zi . A sequence of types {zi [n]}+∞n=0 converges to type zi(under the product topology) if for every k ∈ N, hki (zi [n]) converges to hki (zi ) as n → +∞.
The model that corresponds to our unperturbed environment is denoted by Z ∗ = (Z ∗ , κ∗ ) where∗ . That is, ω = ω ∗ isZ ∗ = {(z1∗ , z2∗ )} and κ∗i (zi∗ ) assigns probability 1 to ω = ω ∗ and z−i = z−icommon knowledge in this model. A mechanism M robustly implements f : Θ → ∆(Y ) in theinterim sense if for every model Z with Z ∗ ⊂ Z, there is an equilibrium in the game induced by(M, Z) such that (i) f is implemented when agents’ types are (z1∗ , z2∗ ), and (ii) for every sequenceof types in Z that converge to (z1∗ , z2∗ ), the implemented social choice function converges to f .
Theorem 6. For every (u1 , u2 ) and non-constant f , there exists c > 0 that depends only on(u1 , u2 ) such that when c1 , c2 > c, no finite mechanism robustly implements f in the interim sense.
The proof is in Appendix E.
17

We omit the mathematical details of computing belief hierarchies. We refer readers to Weinstein and Yildiz(2007) and Oury and Tercieux (2012) for rigorous treatments.

32

7

Related Literature

Our paper contributes to the literature on robust implementation. We take an ex ante perspective
and show that all social choice functions are robustly implementable under generic state distributions or under bounded costs of learning.18 We also show that no non-constant social choicefunction is robustly implementable in the interim sense of Oury and Tercieux (2012) when agents’costs of learning are above some threshold, even if the planner can use unbounded transfers.
We require the desired outcome to be implemented with probability close to 1. This is related to
the literature on virtual implementation such as Abreu and Matsushima (1992). They construct,
for each ε, a mechanism that fully implements the desired outcome with probability more than1 − ε. The number of messages in their mechanisms goes to infinity as ε → 0. By contrast, weconstruct for all ε, a mechanism that partially implements the desired outcome with probability
more than 1 − ε when the perturbation on agents’ preferences and costs of learning is small enough.
The number of messages in our mechanism either equals the number of states n, or equals 2n − 1.
Kim (2021) proposes a monotonicity condition and shows that it is necessary for partial implementation in p-dominant strategies when the environment is quasi-linear. By contrast, we showthat every social choice function is robustly implementable. This is because 21 -dominance is only
sufficient but not necessary for equilibrium robustness in the sense of Kajii and Morris (1997).
Indeed, although the truthful equilibrium in our mechanism is robust to small perturbations, it is
not a 21 -dominant equilibrium in the game induced by our mechanism.
Our mechanisms can robustly elicit costly information when the planner (almost) knows agents’learning technologies but faces uncertainty about their payoffs as well as their beliefs and higherorder beliefs.19 Our research question stands in contrast to Carroll (2019)’s which examines robust
contracting when the planner faces uncertainty about the agent’s information acquisition technology. The mechanisms we propose can robustly implement the desired social choice function when
agents can either perfectly observe the state or observe signals that are highly correlated with thestate. As explained in Propositions 1 and 2, our results do not require the planner to know the18

This echoes the findings in the literature on robust predictions in games. Weinstein and Yildiz (2007) show thatan equilibrium is robust in the interim sense if and only if it is strictly dominant. Kajii and Morris (1997) provide
sufficient conditions for an equilibrium to be robust in the ex ante sense, which are more permissible than the onesin Weinstein and Yildiz (2007). Oyama and Tercieux (2010) drop the common prior assumption and show that thetwo approaches become essentially equivalent in terms of the characterization of robust equilibrium outcomes.
19
Our work is related to the literature on the optimal contracts for information acquisition. Zermeno (2011), Clark
and Reggiani (2021), and Larionov, Pham and Yamashita (2021) examine the optimal contracts for informationacquisition in fixed informational environments. By contrast, we examine whether it is possible to implement adesired social choice function in all nearby informational environments.

33

agents’ interim beliefs and are robust to small trembles in agents’ reporting strategies.20
Finally, our work is related to the literature on robust prediction in games (e.g., Rubinstein
1989, Kajii and Morris 1997, Weinstein and Yildiz 2007) and the literature on the robustness ofequilibrium refinements (e.g., Fudenberg, Kreps and Levine 1988). Our notion of robust implementation builds on the notion of robust equilibrium in Kajii and Morris (1997), which is broadly
applied to study the robustness of equilibria in potential games (Ui 2001, Morris and Ui 2005) andsupermodular games (Oyama and Takahashi 2020). The key difference is that in our model, agents’
payoffs do not directly depend on their messages, which are their actions in our mechanism design
setting.

A

Proofs of Theorems 1 and 2: General Utility Functions

We generalize the proofs of Theorems 1 and 2 to arbitrary u1 (θ, y), u2 (θ, y), c1 , and c2 .
Proof of Theorem 1: The outcome function is the same as the Status Quo Rule with Ascending
Transfers in Section 4.1. Agents receive 0 transfer if their messages do not coincide. If both ofthem report message j, then agent i receives Rij which satisfies Ri1 ≥ q(θc1 ) ,Rij + ui (θj , f (θj )) − Ri1 − ui (θj , f (θ1 )) > 0 for every j ≥ 2nXnoq(θj ) Rij + ui (θj , f (θj )) − Ri1 − ui (θj , f (θ1 )) > 2ci .

(A.1)
(A.2)

j=2

We modify the first step of our proof in which we show that both agents using their truthfulstrategies is a γ-dominant equilibrium for some γ < 12 . The second and third steps remain thesame. Let Σ ≡ {1, 2, ..., n}n and letnoΣ∗ ≡ (m1 , ..., mn ) ∈ Σ such that mj ∈ {1, j} for every j ≥ 1 .
In the restricted game without perturbation where agents can only use strategies in ∆(Σ∗ ), they
can only send message 1 conditional on θ = θ1 , and for every j ∈ {2, 3, ..., n}, agents send either
message 1 or message j conditional on θ = θj
• If agent 1 sends message j in state θj , his expected transfer equals Pr(m2 = j|θj )Rj .
• If agent 1 sends message 1 in state θj , his expected transfer equals Pr(m2 = 1|θj )R1 .
If agent 2 is truthful with probability at least 12 , then Pr(m2 = j|θj ) ≥ 12 and Pr(m2 = 1|θj ) ≤ 12 .
Hence, conditional on knowing that θ = θj , agent 1’s expected payoff from sending message j is:Pr(m2 = j|θj ) u1 (θj , f (θj )) + Rj + Pr(m2 = 1|θj )u1 (θj , f (θ1 )),20

Our results are also related to the results in Chung and Ely (2003) and Aghion, Fudenberg, Holden, Kunimoto
and Tercieux (2012), which examine the robustness of undominated strategy and subgame perfect implementation.

34

and his expected payoff from sending message 1 is:Pr(m2 = j|θj )u1 (θj , f (θ1 )) + Pr(m2 = 1|θj ) u1 (θj , f (θ1 )) + R1 .
The former is greater than the latter if (A.1) is satisfied. Inequality (A.2) implies that agent istrictly prefers (1, 2, ..., n) to (1, 1, ..., 1) when he believes that agent −i uses the truthful strategy
with probability at least 21 . Hence, there exists γ < 12 such that agent 1 strictly prefers (1, 2, ..., n)
to any other strategy that belongs to Σ∗ when he believes that agent 2’s strategy belongs to ∆(Σ∗ )and agent 2 is truthful with probability at least γ. The second and third steps are not affectedbyand u2 , which remain the same as in Section 4.1. The expected cost of implementation
P2 u1 Pjnj
j=1 q(θ )Ri can be as low as
i=1
2 n
o
X
X
c
∗
+
2c
+
q(θ)(u
(θ,
f
(θ
))
−
u
(θ,
f
(θ)))
i
i
i
θ ∈Θ
q(θ∗ )

min
∗

i=1

(A.3)

θ∈Θ

Hence, in order to lower the implementation cost, one needs to choose a status quo state θ∗ that
occurs with high ex ante probability but agents receive low utilities from outcome f (θ∗ ) when
θ 6= θ∗ .
Proof of Theorem 2: Without loss of generality, let Θ = {θ1 , ..., θn } with q(θ1 ) > q(θ2 ) ≥ ... ≥q(θn ) > 0. The outcome function remains the same as before. The transfers are similar although
we replace Rj with R1j and R2j for every j ∈ {0, 1, 2, ..., n} such that for every i ∈ {1, 2}
Di (j) ≡ Rij + ui (θj , f (θj )) + min ui (θj , f (θτ )) − Ri1 − 2 max ui (θj , f (θτ )) > 0 for every j ≥ 2, (A.4)ττ

Di (1) ≡ Ri1 + ui (θ1 , f (θ1 )) − Ri0 − max ui (θ1 , f (θτ )) > 0,
τ

n
X
j=2

and

j

q(θ )Di (j) > 2ci ,

n
X

(A.5)



q(θj ) Di (j) + Ri1 − Ri0 + q(θ1 )Di (1) > 2ci ,(A.6)

q(θj )
for every j ≥ 2.
q(θ1 )

(A.7)

j=2

Ri0

>
j

Ri

We modify the first step of our proof in which we show that both agents being truthful is a γdominant equilibrium for some γ < 12 . Consider a restricted game without perturbation where both
agents are only allowed to use strategies that belong to ∆(Σ∗ ) where Σ∗ is defined asnoΣ∗ ≡ (m1 , ..., mn ) ∈ Σ such that mj ∈ {−n, ..., −2, 1} ∪ {j} for every j ≥ 1 .
We show that in the restricted game without perturbation, both agents using (1, 2, ..., n) is a γdominant equilibrium for some γ < 12 . Suppose agent 2 is truthful with probability at least 21 ,• Conditional on θ = θj for every j ∈ {2, 3, ..., n}. Agent 1’s payoff when he sends j is atleast 12 (R1j + u1 (θj , f (θj ))) + 12 minτ u1 (θj , f (θτ )). His payoff when he sends 1 is at mostu1 (θj , f (θ1 )) + 21 R11 , and his payoff when he sends any negative message is at most 12 R10 +maxτ u1 (θj , f (θτ )). Inequality (A.4) implies that his expected payoff is strictly greater when
he sends message j.

35

• Conditional on θ = θ1 . Agent 1’s payoff when he sends 1 is at least u1 (θ1 , f (θ1 )) + 12 (R11 +R10 ) and his payoff when he sends any negative message is at most R10 + 21 u1 (θ1 , f (θ1 )) +11
τ2 maxτ u1 (θ , f (θ )). Inequality (A.5) implies that his expected payoff is strictly greater
when he sends message 1.
The above discussion implies that agent 1 prefers to be truthful compared to any other non-constantstrategy that belongs to Σ∗ . Inequality (A.6) implies that he prefers to be truthful to any constantstrategy that belongs to Σ∗ . Since agent 1 has a strict incentive to be truthful when he believes
that agent 2 is truthful with probability at least 21 , there exists γ < 12 such that both agents being
truthful is a γ-dominant equilibrium in the restricted game without perturbation. The second andthird steps are not affected by u1 and u2 , which remain the same as in Section
4.2.
P P
We provide a tight lower bound on expected cost of implementation 2i=1 nj=1 q(θj )Rij given
constraints (A.4), (A.5), (A.6), and (A.7). First, we bound Ri1 from below. Inequality (A.6) implies
that
2ci <

n
X

n
o
q(θj ) Rij − Ri1 + min ui (θj , f (θτ )) − 2 max ui (θj , f (θτ )) + ui (θj , f (θj )) .
τ

j=2

τ

Inequality (A.7) implies that Ri0 q(θ1 ) > Rij q(θj ) for every j ≥ 2, and using plugging in inequality(A.5) to substitute Ri0 with Ri1 , we obtain:
2ci <

n
n
n
o
X
X
(q(θ1 ) − q(θj ))Ri1 +q(θj ) min ui (θj , f (θτ )) − 2 max ui (θj , f (θτ )) + ui (θj , f (θj ))
j=2

τ

j=2

−

n
X

τ

n
o
q(θ1 ) max ui (θ1 , f (θτ )) − ui (θ1 , f (θ1 )) .

Inequality (A.8) leads to a tight bound on Ri1 . Next, we compute a tight lower bound onnXq(θ )Rij = Ri1 +j

j=1= Ri1 +nX

q(θj )Di (j) +j=2> 2ci + Ri1 +

n
X

n
X

j
j
j=1 q(θ )Ri .

Pnq(θj )(Rij − Ri1 )

j=2

n
o
q(θj ) 2 max ui (θj , f (θj )) − min ui (θj , f (θj )) − ui (θj , f (θj ))
τ

j=2
n
X

(A.8)

τ

j=2

τ

n
o
q(θj ) 2 max ui (θj , f (θj )) − min ui (θj , f (θj )) − ui (θj , f (θj )) .
τ

j=2

τ

Plugging in the tight lower bound on Ri1 , we obtain a tight lower bound on the implementation
cost. In the special case where u1 = u2 = 0 and c1 = c2 = c, the lower bound is given by (4.13).

B

Proof of Theorem 3

For any finite mechanism M ≡ {M1 , M2 , g, t1 , t2 }, letX(M) ≡

max(i,m1 ,m2 )∈{1,2}×M1 ×M2

36

ti (m1 , m2 )

be the highest transfer promised to any agent by M. By definition, X(M) exists. Recall that Y isthe set of outcomes, ∆(Y ) is the set of lotteries over outcomes, and f (θ) ∈ ∆(Y ). We use co(·) todenote the convex hull of a set. Since f is non-constant, there exists θ∗ ∈ Θ such thatf (θ∗ ) ∈/ co {f (θ)}θ∈Θ \{f (θ∗ )} ≡ Y.
According to the separating hyperplane theorem, there
exists v : Y → R suchthat v(f (θ∗ )) <miny∈Y v(y).21 Hence, there exists C > 0 such that miny∈Y v(y) − v(f (θ∗ )) C > 4X(M).
First, consider a perturbation G + in which u
e1 (ω, θ, y) = Cv(y) for all (ω, θ) ∈ Ω × Θ. If M
implements f (θ∗ ) in state θ∗ under perturbation G + , there must exist m∗2 ∈ ∆(M2 ) such thatnomax
Cv(g(m1 , m∗2 )) + t1 (m1 , m∗2 ) ≤Cv(f (θ∗ )) + X(M).
|{z}m1 ∈∆(M1 )agent 1’s highest possible payoff if the planner implements f (θ∗ )(B.1)
This is because otherwise, agent 1 can secure himself a payoff strictly greater than the right-handside of (B.1), in which case f (θ∗ ) cannot be implemented in any state under G + .
Next, consider another perturbation G − where u
e2 (ω, θ, y) = −Cv(y) for all (ω, θ) ∈ Ω × Θ.
∗
Agent 2’s payoff by playing m2 is at leastnomin− Cv(g(m1 , m∗2 )) + t2 (m1 , m∗2 ) .
(B.2)
m1 ∈∆(M1 )Since we have chosen C > 0 in order to satisfy miny∈Y v(y)−v(f (θ∗ )) C > 4X(M) and moreover,
X(M) ≥ |ti (m1 , m2 )| for every i and (m1 , m2 ), inequality (B.1) implies thatnomin
− Cv(g(m1 , m∗2 )) + t2 (m1 , m∗2 ) ≥ −Cv(f (θ∗ )) − 3X(M) > −C min{v(y)} + X(M) .
y∈Y
m1 ∈∆(M1 )
|
{z
}


since

miny∈Y v(y)−v(f (θ∗ )) C>4X(M)Therefore, agent 2 can secure a payoff strictly greater than −C miny∈Y {v(y)} + X(M), which
implies that no outcome in Y can be implemented under perturbation G − . Hence, every finite
mechanism M that can implement non-constant f under G + cannot implement f under G − .

C

Proof of Theorem 4

Suppose that u1 and u2 are independent of θ. Under any finite mechanism M, there always exists
an equilibrium in which both agents use state-independent strategies, since agents’ preferences
over messages are independent of the state regardless of the mechanism. In this equilibrium, theimplemented outcome does not depend on the state, which means that for every non-constant f ,there exists a state θ ∈ Θ such that the implemented outcome is bounded away from f (θ).
Next, we show that f is not virtually implementable when c1 and c2 are above some cutoff cthat depends only on (u1 , u2 ). For every (u1 , u2 ), letnoX(u1 , u2 ) ≡ max max ui (θ, y) − min ui (θ, y) .
i∈{1,2}

θ,y

21

θ,y

For every distribution over outcomes ye ∈ ∆(Y ), we let v(ey ) denote the expected value of v(y) when y is distributed
according to ye.

37Fix any finite mechanism M and, for every m2 ∈ ∆(M2 ), let T (m2 ) ≡ maxm1 ∈M1 t1 (m1 , m2 ) be themaximal transfer received by agent 1 when agent 2’s message is m2 . Suppose that agent 1 believes
that agent 2’s message is m2 regardless of θ. Then, the difference between agent 1’s expected payoff
when he learns θ and when he does not learn θ ishihi
E max {u1 (θ, g(m1 , m2 )) + t1 (m1 , m2 )} − max E u1 (θ, g(m1 , m2 )) + t1 (m1 , m2 ) .
(C.1)
m1 ∈M1m1 ∈M1hi
By definition, if m∗1 ∈ arg maxm1 ∈M1 E u1 (θ, g(m1 , m2 )) + t1 (m1 , m2 ) , then t1 (m∗1 , m2 ) ≥ T (m2 ) −X(u1 , u2 ). This implies that the value of (C.1) is no more than 2X(u1 , u2 ), and therefore, agent 1
has no incentive to learn θ when c1 > 2X(u1 , u2 ). In addition, whenh agent 1 believes that agent 2’simessage is m2 , sending a message that belongs to arg maxm1 ∈M1 E u1 (θ, g(m1 , m2 )) + t1 (m1 , m2 )regardless of the state is one of agent 1’s best replies.
Similarly, suppose c2 > 2X(u1 , u2 ). For every m1 ∈ ∆(M2 ), whenh agent 2 believes that agent 1’si
message is m1 , sending a message that belongs to arg maxm2 ∈M2 E u2 (θ, g(m1 , m2 )) + t2 (m1 , m2 )regardless of the state is one of agent 2’s best replies.
Fix any finite mechanism M and consider an auxiliary two-player normal-form
game wherehagent i ∈ {1, 2} has a finite set of pure strategies Mi and his payoff is Eθ ui (θ, g(m1 , m2 )) +iti (m1 , m2 ) when he uses strategy mi and his opponent uses strategy m−i . Since this auxiliary
game is finite, a Nash equilibrium (m1 , m2 ) ∈ ∆(M1 ) × ∆(M2 ) exists. By construction, agent 1
sending m1 regardless of θ and agent 2 sending m2 regardless of θ is an equilibrium under mechanism
M. This equilibrium implements a constant social choice function. For every non-constant social
choice function f , there exists β > 0 such that for every constant social choice function g, there
exists θ ∈ Θ such that ||f (θ) − g(θ)||T V > β. This implies that f is not virtually implementable.

D

Proof of Theorem 5

If f is constant, then robust-fully implementing f is straightforward. The rest of the proof focuses on
the case where f is non-constant. Consider a mechanism where Mi = Θ, M−i = {1}, g(mi , m−i ) =f (mi ), ti (m1 , m2 ) depends only on m1 , and t−i (m1 , m2 ) = 0. Since f and ui satisfy strict cyclicalmonotonicity, there exists ti : Θ → R such that
1. ti (θ) = ti (θ0 ) for every θ, θ0 ∈ Θ such that f (θ) = f (θ0 ),2. ui (θ, f (θ)) + ti (θ) > ui (θ, f (θ0 )) + ti (θ0 ) for every θ, θ0 ∈ Θ such that f (θ) 6= f (θ0 ).
Under such a mechanism, agent i chooses an outcome in {f (θ)}θ∈Θ and receives a transfer ti (θ)
for implementing f (θ). Under every η-perturbation G, every normal type of agent i has a strict
incentive to learn θ and to choose f (θ) in state θ for every θ ∈ Θ, provided that his cost of learning
ci is small enough. This implies that the above mechanism can robust-fully implement f .

E

Proof of Theorem 6

As shown in the proof of Theorem 4, for every (u1 , u2 ), there exists c > 0 such that for all finite
mechanisms (even when transfers can be arbitrarily large), when ci > c, agent i finds it strictly
suboptimal to learn θ when he believes that agent −i’s message does not depend on θ. Suppose
c1 , c2 > c. For every finite mechanism M, let U ≡ 2 max{i,θ,y,m1 ,m2 } ui (θ, y) + ti (m1 , m2 ) . We
38

construct a sequence of types that converge to (z1∗ , z2∗ ) under the product topology but for which
the implemented outcome is bounded away from f . Let z2 [0] be a type that assigns probability 1
to ω 0 where u
e1 (ω 0 , ·, ·) = u1 (·, ·), ue2 (ω 0 , ·, ·) = u2 (·, ·), ec1 (ω 0 ) = c1 , and ec2 (ω 0 ) > U . Let z1 [0] be a
type that assigns probability β to player 2 being type z2 [0] and probability 1 − β to ω = ω ∗ , whereβ is close enough to 1 such that it is strictly suboptimal for type z1 [0] to learn the state, regardlessof his belief about type z2 [0]’s message. For every j ≥ 1, let z2 [j] be a type who knows that ω = ω ∗but assigns probability β to player 1 being type z1 [j − 1] and probability β to player 1 being typez1 [j], and let z1 [j] be a type who knows that ω = ω ∗ but assigns probability β to player 2 being
type z2 [j] and probability 1 − β to player 2 being type z2 [j + 1]. These sequence of types converge
to (z1∗ , z2∗ ) under the product topology. By construction, type z2 [0] finds it strictly suboptimal tolearn θ, so his message is independent of θ. Type z1 [j] finds it strictly suboptimal to learn θ sincetype z2 [j]’s message is independent of θ with probability at least β. Type z2 [j] finds it strictly
suboptimal to learn θ since type z1 [j − 1]’s message is independent of θ with probability at leastβ. Therefore, the implemented outcome under this sequence of types is independent of θ, which isbounded away from f since f is non-constant.

F

Proof of Proposition 1

First, we prove Proposition 1 when u1 = u2 = 0 and c1 = c2 . In Online Appendix C, we extend
our proof by allowing for arbitrary u1 , u2 , c1 , c2 . We rank the states according to their ex ante
probabilities, i.e., q(θ1 ) > q(θ2 ) ≥ ... ≥ q(θn ) > 0, where the first strict inequality comes fromour generic assumption. Each agent has 2n − 1 messages with their message space given by M ≡{−n, ..., −2} ∪ {1} ∪ {2, ..., n}. The outcome function is given by:f (θ|m1 | ) if |m1 | = |m2 |g(m1 , m2 ) =(F.1)
f (θ1 )
otherwise
The transfer functions when u1 = u2 = 0 and c1 = c2 = c are given by:
 j
R
if m1 = m2 = j ≥ 1


 0
R
if m1 ≤ 1 but (m1 , m2 ) 6= (1, 1)
t1 (m1 , m2 ) =0−x
Rif m1 ≥ 2 and m2 ≤ 10otherwise
 j
R


 0
R
t2 (m1 , m2 ) = R0 − x0

if m1 = m2 = j ≥ 1
if m2 ≤ 1 but (m1 , m2 ) 6= (1, 1)
if m2 ≥ 2 and m1 ≤ 1otherwise

(F.2)

(F.3)

where Rn , ..., R0 > x > q(θcn ) satisfy
R1 − R0 >and2c,q(θ1 )

Rj − R1 − x >2cfor every j ∈ {2, 3, ..., n},q(θj )xq(θj )>
for every j ∈ {2, 3, ..., n}.
Rj − R0
1 − q(θj )

(F.4)

(F.5)

When there are two states, our Augmented Status Quo Rule with Modified Transfers is given by:

39

g
−2
1
2

−2
f (θ2 )f (θ1 )f (θ2 )1f (θ1 )f (θ1 )f (θ1 )2f (θ2 )f (θ1 )f (θ2 )

−2
R0 , R0
R0 , R0R0 −x, R0

t1 , t2−2
1
2

1
R0 , R0
R1 , R1
R0 −x, R02
R0 , R0 −x
R0 , R0 −x
R2 , R2

When there are three states, our Augmented Status Quo Rule with Modified Transfers is given by:
g
−3
−2
1
2
3
t1 , t2
−3
−2
1
2
3

−3
R0 , R0
R0 , R0
R0 , R0R0 −x, R0
R0 −x, R0−3
f (θ3 )f (θ1 )f (θ1 )f (θ1 )f (θ3 )−2
f (θ1 )f (θ2 )f (θ1 )f (θ2 )f (θ1 )

−2
R0 , R0
R0 , R0
R0 , R0R0 −x, R0
R0 −x, R01
f (θ1 )f (θ1 )f (θ1 )f (θ1 )f (θ1 )2
f (θ1 )f (θ2 )f (θ1 )f (θ2 )f (θ1 )

1
R0 , R0
R0 , R0
R1 , R1
R0 −x, R0
R0 −x, R03
f (θ3 )f (θ1 )f (θ1 )f (θ1 )f (θ3 )

2
R0 , R0 −x
R0 , R0 −x
R0 , R0 −x
R2 , R20, 0

3
R0 , R0 −x
R0 , R0 −x
R0 , R0 −x0, 0R3 , R3

Since M ≡ {−n, ..., −2} ∪ {1} ∪ {2, 3, ..., n}, agent i’s pure strategy is an |Si |-dimensional vector(m1 , ..., m|Si | ) where mk ∈ M represents agent i’s intended message when his private signal about
the state is ski . Hence, conditional on si = ski , agent i’s realized message is mk with probability
1 − τ and is randomly drawn according to Fi ∈ ∆(Mi ) with probability τ . This implies that agent
i prefers m to m0 as his intended message if and only if he receives a higher expected payoff whenm is his realized message compared to when m0 is his realized message. LetnoΣ∗i ≡ (m1 , ..., m|Si | ) ∈ Σ such that for every k ∈ {1, ..., |Si |}, mk ∈ {−n, ..., −2, 1} ∪ {hi (ski )} .
In words, Σ∗i is the set of pure strategies of agent i such that, conditional on each of agent i’s
private signal ski , agent i intends to send either a negative message, or the status quo message 1, or
message hi (ski ) that matches the meaning of his private signal. Agent i intends to be truthful if his
strategy (m1 , ..., m|Si | ) satisfies mk = hi (ski ) for every k ∈ {1, ..., |Si |}, i.e., agent i intends to send
the message that matches the meaning of his private signal for each of his private signals.
First, we show that there exists γ < 21 such that both agents intending to be truthful is aγ-dominant equilibrium in the restricted unperturbed game where agents are only allowed to use
strategies in ∆(Σ∗1 ) and ∆(Σ∗2 ). Suppose agent 2 intends to be truthful with probability at least 12 .
• For every j ≥ 2, conditional on every s1 ∈ S1 with h1 (s1 ) = j, if agent 1’s realized message
is j, then he receives an expected transfer ofPr(m2 = j|s1 )Rj + Pr(m2 ≤ 1|s1 )(R0 − x),and if agent 1’s realized message is no more than 1, then he receives an expected transfer ofPr(m2 = 1|s1 )R1 + Pr(m2 6= 1|s1 )R0 .
Since π(h2 (s2 ) = h1 (s1 )|s1 ) ≥ 1 − τ when π is of size τ , and agent 2 intends to be truthfulwith probability at least 21 , we know that Pr(m2 = j|s1 ) ≥ 1−τ
2 (1 − τ ) and Pr(m2 ≤ 1|s1 ) ≤
1−τ
2c
j
1
1 − 2 (1 − τ ). When R − R − x > q(θj ) , τ is close to 0, and τ ≤ τ , we havenonoq(θj ) Pr(m2 = j|s1 )Rj +Pr(m2 ≤ 1|s1 )(R0 −x) > q(θj ) Pr(m2 = 1|s1 )R1 +Pr(m2 6= 1|s1 )R0 +c.
40

Therefore, if agent 1 believes that agent 2’s strategy belongs to ∆(Σ∗2 ) and that agent 2 intends
to be truthful with probability at least 12 , then agent 1 strictly prefers sending message j oversending the status quo message or any negative message whenever he receives a signal s1 thatsatisfies h1 (s1 ) = j. Moreover, this statement holds even after taking into account agent 1’s
cost of learning the state.
• Conditional on agent 1 receiving a signal s1 such that h1 (s1 ) = 1, his expected transfer when
his realized message is 1 is Pr(m2 = 1|s1 )R1 + Pr(m2 < 0|s1 )R0 and his expected transfer2cwhen his realized message is negative is R0 . When R1 − R0 > q(θ1 ) and τ is close enough to
1

0

R +R
0
0, Pr(m2 = 1|s1 )R1 + Pr(m2 < 0|sgiven that agent 2 is truthful with21 )R is at least
10

probability at least 12 . Since q(θ1 ) R +R
− R0 > c, agent 1 strictly prefers to send message
2
1 to any negative message when agent 2’s strategy belongs to ∆(Σ∗2 ) and agent 2 intends tobe truthful with probability at least 21 , even taking into account his cost of learning c.

Since agent 1 strictly prefers to be truthful when agent 2’s strategy belongs to ∆(Σ∗2 ) and agent
2 intends to be truthful with probability at least 12 , there exists γ < 21 , such that both agents
intending to be truthful is a γ-dominant equilibrium in the restricted game without perturbation.
The second step uses the critical path lemma. We can show that for every ε > 0, there exists
η > 0 such that for every η-perturbation G, there exists an equilibrium σ(G) in the restricted gamewith perturbation G where both agents intend to be truthful with probability more than 1 − 2ε .
Under the outcome function g of our mechanism, if both agents behave according to σ(G) and τ issmall compared to ε, then for every θ, outcome f (θ) is implemented with probability at least 1 − ε.
In the third step, we show that σ(G) remains an equilibrium in the game induced by ourmechanism and perturbation G where agents can use any strategy, not restricted to strategies in∆(Σ∗1 ) and ∆(Σ∗2 ). We consider two cases.
First, for any of agent 1’s strategy (m1 , ..., m|S1 | ) ∈/ Σ∗1 that is non-constant, let us define a new|S |strategy (m1∗ , ..., m∗ 1 ) that belongs to Σ∗1 : km
if mk ∈ {−n, ..., −2, 1} ∪ {h1 (sk1 )}kfor every k ∈ {1, 2, ..., |S1 |}.
m∗ ≡−mk if mk ∈/ {−n, ..., −2, 1} ∪ {h1 (sk1 )}Intuitively, for every signal realization sk1 , mk∗ = mk if mk is no more than 1 or mk coincides withthe meaning of sk1 ; otherwise, mk∗ = −mk . According to the mechanism’s outcome function (F.1),|S |(m1 , ..., m|S1 | ) and (m1∗ , ..., m∗ 1 ) induce the same joint distribution of (θ, y). We compare agent 1’s|S |expected transfer from (m1 , ..., m|S1 | ) and from (m1∗ , ..., m∗ 1 ). When agent 1’s private signal s1 issuch that h1 (s1 ) = j, his expected transfer when his realized message m ∈/ {−n, ..., −2} ∪ {1, j} is:Pr(m2 = m|s1 )Rm + Pr(m2 ≤ 1|s1 )(R0 − x).

(F.6)

Agent 1’s expected transfer when his realized message is −m is R0 . When agent 2’s strategy belongsto ∆(Σ∗2 ), he intends to send message m only if the meaning of his signal is m. When π is of size
τ , we have Pr(m2 = m|s1 ) ≤ 2τ . If this is the case, the value of (F.6) is strictly less than R0 when|S |
τ is close to 0. This implies that every type of agent 1 prefers (m1∗ , ..., m∗ 1 ) to (m1 , ..., m|S1 | ).
Second, for any strategy (m1 , ..., m|S1 | ) ∈/ Σ∗1 that is a constant vector, there exists k ∈1|S|{2, 3, ..., n} such that (m , ..., m 1 ) = (k, ..., k). Compare any given type of agent 1’s expected
payoff from strategies (k, ..., k) and (−k, ..., −k). These strategies induce the same joint distribution
over (θ, y) and neither of them requires any cost of learning. In terms of the transfers, when agent
1’s realized message is k, he receives an expected transfer of Pr(m2 = k)Rk + Pr(m2 ≤ 1)(R0 − x).
41When his realized message is −k, he receives an expected transfer of R0 . When agent 2’s strategy
belongs to ∆(Σ∗2 ), agent 2 intends to send message k only when his signal has meaning k. Therefore,Pr(m2 = k)Rk + Pr(m2 ≤ 1)(R0 − x) ≤ π(h2 (s2 ) = k) + 1 − π(h2 (s2 ) = k) τ Rk + 1 − π(h2 (s2 ) = k) (1 − τ )(R0 − x)(F.7)

When π is of size τ and τ converges to zero, the right-hand-side of (F.7) converges to q(θk )Rk +(1 − q(θk ))(R0 − x), which is strictly smaller than R0 given our condition on the transfers (F.5).
Therefore, the right-hand-side of (F.7) is strictly smaller than R0 for all τ close enough to 0. Thisimplies that when agent 2 behaves according to σ(G), every type of agent 1 receives a strictly
greater transfer from strategy (−k, ..., −k) to strategy (k, k, ...k) for every k ≥ 2.

References[1] Abreu, D., Matsushima, H. (1992) “Virtual Implementation in Iteratively UndominatedStrategies: Complete Information,” Econometrica, Vol. 60, pp. 993–1008.
[2] Aghion, P., Fudenberg, D., Holden, R., Kunimoto, T., Tercieux, O. (2012)“Subgame-Perfect Implementation Under Information Perturbations,” Quarterly Journal of
Economics, Vol. 127, pp. 1843–1881.
[3] Bergemann, D., Morris, S. (2005) “Robust Mechanism Design,” Econometrica, Vol. 73,
pp. 1771–1813.
[4] Bergemann, D., Morris, S. (2009) “Robust Implementation in Direct Mechanisms,” Review
of Economic Studies, Vol. 76, pp. 1175–1204.
[5] Chen, Y., Mueller-Frank, M. Pai, M. (2022) “Continuous Implementation with Direct
Revelation Mechanisms,” Journal of Economic Theory, Vol. 201, 105422.
[6] Chen, Y., Kunimoto, T. Sun, Y., Xiong, S. (2021) “Rationalizable Implementation in
Finite Mechanisms,” Games and Economic Behavior, Vol. 129, pp. 181–197.
[7] Chen, Y., Kunimoto, T. Sun, Y. (2020) “Continuous Implementation with Payoff Knowledge,” Working Paper.
[8] Chung, K.S, Ely, J. (2003) “Implementation with Near-Complete Information,” Econometrica, Vol. 71, pp. 857–871.
[9] Chung, K.S., Ely, J. (2007) “Foundations of Dominant-Strategy Mechanisms,” Review of
Economic Studies, Vol. 74, pp. 447–476.
[10] Carroll, G. (2019) “Robust Incentives for Information Acquisition,” Journal of Economic
Theory, Vol. 181, pp. 382–420.
[11] Clark, A., Reggiani, G. (2021) “Contracts for Acquiring Information,” arXiv:2103.03911.
[12] Fudenberg, D,. Kreps, D., Levine, D. (1988) “On the Robustness of Equilibrium Refinements,” Journal of Economic Theory, Vol. 44, pp. 354-380.
[13] Kajii, A., Morris, S. (1997) “The Robustness of Equilibria to Incomplete Information,”
Econometrica, Vol. 65, pp. 1283–1309.
42

[14] Kim, D. (2021) “p-Dominant Implementation,” Working Paper.
[15] Larionov, D., Pham, H., Yamashita, T. “First Best Implementation with Costly Information Acquisition,” Working Paper.
[16] Maskin, E. (1999) “Nash Equilibrium and Welfare Optimality,” Review of Economic Studies,Vol. 66, pp. 23–38.
[17] Morris, S., Ui, T. (2005) “Generalized Potentials and Robust Sets of Equilibria,” Journalof Economic Theory, Vol. 124, pp. 45–78.
[18] Oury, M., Tercieux, O. (2005) “Continuous Implementation,” Econometrica, Vol. 80,
pp. 1605–1637.
[19] Oyama, D., Takahashi, S. (2020) “Generalized Belief Operator and Robustness in BinaryAction Supermodular Games,” Econometrica, Vol. 88, pp. 693–726.
[20] Oyama, D., Tercieux, O. (2010) “Robust Equilibria under Non-Common Priors,” Journalof Economic Theory, Vol. 145, pp. 752-784.
[21] Pavan, A., Segal, I. Toikka, J. (2014) “Dynamic Mechanism Design: A Myersonian Approach,” Econometrica, Vol. 82, pp. 601-653.
[22] Rochet, J.C. (1987) “A Necessary and Sufficient Condition for Rationalizability in a QuasiLinear Context,” Journal of Mathematical Economics, Vol. 16, pp. 191-200.
[23] Rubinstein, A. (1989) “The Electronic Mail Game: Strategic Behavior Under Almost Common Knowledge,” American Economic Review, Vol. 79, pp. 385–391.
[24] Strulovici, B. (2021) “Can Socitety Function without Ethical Agents? An Informational
Perspective,” Working Paper.
[25] Sugaya, T., Takahashi, S. (2013) “Coordination Failure in Repeated Games with Private
Monitoring,” Journal of Economic Theory,, Vol. 148, pp. 1891–1928.
[26] Ui, T. (2001) “Robust Equilibria of Potential Games,” Econometrica, Vol. 69, pp. 1373–1380.
[27] Weinstein, J., Yildiz, M. (2007) “A Structure Theorem for Rationalizability with Application to Robust Predictions of Refinements,” Econometrica, Vol. 75, pp. 365-400.
[28] Zermeno, L. (2011) “A Principal-Expert Model and the Value of Menus,” Working Paper.

43