100%>Yahoo! is not affiliated with the authors of this page or responsible for its content.
Fault Tolerant Implementation
Review of Economic Studies (2002) 69, 589610
0034-6527/02/00230589$02.00
c 2002 The Review of Economic Studies Limited
Fault Tolerant Implementation
KFIR ELIAZ
New York University
First version received 20 March 2000; nal version accepted 28 November 2001
(Eds.)
In this paper we investigate the implementation problem arising when some of the players are
faulty in the sense that they fail to act optimally. The planner and the non-faulty players only know
that there can be at most k faulty players in the population. However, they know neither the identity of
the faulty players, their exact number nor how faulty players behave. We dene a solution concept which
requires a player to optimally respond to the non-faulty players regardless of the identity and actions of
the faulty players. We introduce a notion of fault tolerant implementation, which unlike standard notions
of full implementation, also requires robustness to deviations from the equilibrium. The main result of
this paper establishes that under symmetric information any choice rule that satises two propertiesk-
monotonicity and no veto powercan be implemented by a strategic game form if there are at least three
players and the number of faulty players is less than
1
2
n 1. As an application of our result we present
examples of simple mechanisms that implement the constrained Walrasian function and a choice rule for
the efcient allocation of an indivisible good.
1. INTRODUCTION
Implementation theory studies the problem of a planner who faces a set of agents and wishes
to associate a set of outcomes with each possible prole of the agents preferences (the
correspondence that assigns a set of outcomes to each prole of the agents preferences is called
a choice rule). The standard approach implicitly assumes that each agent is able to correctly
choose his most preferred action. A question arises as to how robust are the conclusions reached
by standard models to slight deviations from the full rationality assumption. If we believe that
decision makers might err, we may be interested in constructing mechanisms that are immune to
possible mistakes that some of the players might make.
This paper explores the question of implementation that is robust to the potential of having
a limited number of agents who make mistakes. An agent who makes mistakes is viewed as a
decision maker who has well dened preferences that are known to others, but who fails for one
reason or another to behave optimally. We refer to such an agent as being faulty. For an observer
who knows the preferences of a faulty player, it would seem as if the player was not acting in
accordance to his preferences.
We concentrate on two aspects of error-prone behavior. First, incorrect decisions are hard
to predict. There are also many potentially incorrect decisions that may be made. Second, the
tendency to make mistakes is usually an unobservable feature of a decision maker. We may have
a very good idea of what the preferences are of an individual (more money is preferred to less,
less pain is preferred to more), but we may have no clue as to how successful this individual is in
making the correct decisions.
The presence of faulty players introduces several complications to the problem of imple-
mentation. If players are aware of the possibility that some players might err, they may take that
into account when considering their course of action. For example, players may wish to exploit
the potential faultiness of some of the players. Thus, the strategic reasoning of the players may
be affected by the mere knowledge that some players may be faulty. In addition, different players
may entertain different beliefs over the identity and behavior of the faulty players. This raises the
589 590
REVIEW OF ECONOMIC STUDIES
question of what is an appropriate notion of equilibrium in such a setting. An equilibrium may
at best describe some stable pattern of behavior by players who are potentially non-faulty. The
planner must take into account that ultimately, the players who turn out to be faulty will behave
in an unpredictable manner and may choose an action contrary to their incentives.
Our objective is to enable a planner to implement choice rules even if some of the agents he
faces are faulty players. We consider the simple case in which the planner is restricted to using
only strategic game forms, and where the agents know their own and other agents true prole of
preferences but the planner does not. We view the preferences of an individual and his tendency
to make mistakes as two independent characteristics in the sense, that one cannot infer an agents
tendency to make mistakes from observing his preferences. We therefore assume that the planner
and the non-faulty players only know that there can be at most k faulty players in the population.
However, they know neither the identity of faulty players, their exact number nor how faulty
players behave. Assuming that the non-faulty players behavior conforms with an appropriate
solution concept, the planners objective is to construct a game form such that for every possible
prole of the agents preferences and regardless of the actions of the faulty players the following
is satised. The set of outcomes, in which any subset with at least n k players execute their
equilibrium strategies, equals the set of outcomes that the choice rule associates with the prole
of preferences. A game form having this property is said to achieve fault tolerant implementation
of the choice rule.
It is important to note that faulty players do not necessarily represent players who make
mistakes. The two central features of faulty players are the unpredictable nature of their behavior
and their unknown identity. Thus, faulty players may also be interpreted as malicious agents
who wish to prevent the planner from attaining his goal. The malicious agents cannot be
identied by the planner or by the normal agents as their preference for harming the mechanism
is unobservable to others. Another interpretation of faulty players is that of a minority with
unknown preferences. This interpretation considers the non-faulty players to be the majority,
a homogeneous group of agents with identical preferences, who only know the preferences of
their own type. From their point of view, any agent who does not share their preferences may
have any preferences.
Fault tolerant implementation can be interpreted as a criterion of robustness against the
worst possible mistakes, mistakes, which would cause some player to deviate from truth-telling.
An alternative interpretation is that the planner requires robustness to any possible beliefs that
players might have about the behavior of faulty players. By imposing such a strong robustness
requirement, we do not need to make explicit assumptions on the set of possible mistakes and on
the probabilities of making mistakes and of being faulty.
Fault tolerant implementation can be relevant in several contexts. Some examples include
the following.
(1) Costly analysis of possible scenariosA fault tolerant mechanism may be preferred in
situations which require robustness to mistakes where it is costly for the planner to identify
all the reasonable mistakes and all the reasonable beliefs that players may have about the
faultiness of others.
(2) Robustness to players with preferences over a richer domainThere may be situations
in which the preferences of some of the players may be dened over a domain, which is
richer than the set of alternatives offered by the mechanism. For example, in the recent
Israeli elections there were only two possible outcomes: Ehud Barak or Ariel Sharon.
Since Barak represented the pro-peace movement led by the left wing, the Israeli Arabs
clearly preferred Barak to Sharon. Therefore, the decision of the Israeli Arabs not to vote
(which in effect is a decision to vote for Sharon) was clearly inconsistent with this groups ELIAZ
FAULT TOLERANT IMPLEMENTATION
591
preferences over the set of candidates. However, the Israeli Arabs preferred an outcome,
which was not offered by the voting mechanism, to their most preferred election outcome:
they preferred to display their ability to punish a government ofcial who mistreated them
(Barak) even at the cost of having their least preferred candidate win the elections. Thus,
fault tolerant implementation offers robustness against the possibility that the behavior of
some players may not be rationalized by their ranking of the alternatives offered by the
mechanism.
(3) Discriminatory mechanismsThere are situations in which a planner cares about the
preferences of only a subset of all the agents in the sense that his choice rule is dened
on the preferences of only the agents in this subset. The agents in this privileged
subset share some common unobservable characteristics such that each member of this
subset cannot be identied by the planner or by the other privileged agents. For example,
these characteristics might be the religion of the agents, their political afliation or their
preferences on objects, other than the ones selected by the mechanism. In most cases the
planner may not be able to condition participation in the mechanism on having certain
characteristics (these characteristics may not be veriable). Under certain conditions (see
the discussion in the nal section of