9 February 2012: Implementation in Multi-dimensional Dichotomous Domains

Debasis Mishra
Indian Statistical Institute

Abstract:
We study multidimensional mechanism design in private value and
quasi-linear environments, e.g. auction domains, matching problems
with transfers, choosing a public good among multiple public goods
with transfers etc. We restrict attention to deterministic
implementation in dominant strategies. Our focus is on domains where
agents have dichotomous preferences over alternatives. A dichotomous
type of any agent is characterized by a positive real number, which we
call the value of the agent at this type, and a non-empty subset of
alternatives, which we call the acceptable alternatives. The
interpretation is that an agent of dichotomous type gets (the same)
utility equal to his value from each alternative in his acceptable
set, but gets zero utility on any alternative that is not acceptable.
Note that both the value and the set of acceptable alternatives are
private information of the agent. This makes such type spaces
multidimensional. We call a type space a dichotomous domain if every
type belonging to it is a dichotomous type. We characterize the set of
implementable allocation rules in dichotomous domains using a
condition called ``generation monotonicity". Generation monotonicity
is a new (non-trivial) simplification of the ``cycle monotonicity"
condition of Rochet in dichotomous domains.

Our most striking result comes in a particular class of dichotomous
domains. We show that for a large class of dichotomous domains, which
we refer to as ``rich dichotomous domains", a significantly weaker
condition than generation monotonicity characterizes implementability.
We refer to this weaker condition as 2-generation monotonicity, and
show it to be equivalent to 3-cycle monotonicity. 3-cycle monotonicity
is significantly weaker than cycle monotonicity but stronger than
2-cycle monotonicity, a condition used to characterize
implementability in convex domains. A dichotomous domain is not
convex, but still multidimensional. While most of the earlier results
in the literature found domains where 2-cycle monotonicity is
necessary and sufficient for implementability, to our knowledge, this
paper is the first to identify multidimensional domains where we see
K-cycle monotonicity (K > 2) is necessary and sufficient for
implementation. We show, by way of an example, that 2-cycle
monotonicity is not sufficient for implementability in rich
dichotomous domains. We demonstrate the usefulness of our
characterizations by deriving a revenue maximizing mechanism for the
one-sided matching problem where agents have dichotomous preferences
over alternatives.

Date: February 9, 2012
Time: 03:00 P.M.

Venue:
AMEX Conference Room (Second Floor)
Department of Economics,
Delhi School of Economics,
New Delhi-110007(INDIA)

Location:

View Larger Map