%Paper: ewp-game/9703010
%From: vkrishna@psu.edu
%Date: Tue, 25 Mar 97 14:51:22 CST
%Date (revised): Tue, 28 Apr 1998 12:38:37 -0400


\documentclass[12pt]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{sw20elba}

%TCIDATA{OutputFilter=LATEX.DLL}
%TCIDATA{Created=Thu Apr 09 14:25:00 1998}
%TCIDATA{LastRevised=Thu Apr 23 14:44:50 1998}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="DocumentShell" CONTENT="Journal Articles\Vijay">}
%TCIDATA{CSTFile=LaTeX article (bright).cst}

\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}{Acknowledgement}
\newtheorem{algorithm}{Algorithm}
\newtheorem{axiom}{Axiom}
\newtheorem{case}{Case}
\newtheorem{claim}{Claim}
\newtheorem{conclusion}{Conclusion}
\newtheorem{condition}{Condition}
\newtheorem{conjecture}{Conjecture}
\newtheorem{corollary}{Corollary}
\newtheorem{criterion}{Criterion}
\newtheorem{definition}{Definition}
\newtheorem{example}{Example}
\newtheorem{exercise}{Exercise}
\newtheorem{lemma}{Lemma}
\newtheorem{notation}{Notation}
\newtheorem{problem}{Problem}
\newtheorem{proposition}{Proposition}
\newtheorem{remark}{Remark}
\newtheorem{solution}{Solution}
\newtheorem{summary}{Summary}
\newenvironment{proof}[1][Proof]{\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\input{tcilatex}

\begin{document}

\author{\textsc{Vijay Krishna} \\
%EndAName
Pennsylvania State University \and \textsc{Motty Perry} \\
%EndAName
The Hebrew University of Jerusalem}
\title{Efficient Mechanism Design\thanks{%
We thank the Koret Foundation and the National Science Foundation for
research support and the Center for Rationality at the Hebrew University for
its hospitality. We are grateful to S. Hart for his generous help and
encouragement and to P. Reny for many useful discussions. We have also
benefited from the comments of J.-P. Beno\^{i}t, T. Gresik, J. Morgan and R.
Rosenthal.}}
\date{April 14, 1998}
\maketitle

\begin{abstract}
We study Bayesian mechanism design in situations where agents' information
may be multi-dimensional, concentrating on mechanisms that lead to efficient
allocations. Our main result is that a generalization of the well-known
Vickrey-Clarke-Groves mechanism maximizes the planner's ``revenue'' among
all efficient mechanisms. This result is then used to study multiple object
auctions in situations where bidders have privately known ``demand curves''
and extended to include situations with complementarities across objects or
externalities across bidders. We also illustrate how the main result may be
used to analyze the possibility of allocating both private and public goods
efficiently when budget balance considerations are important. The
generalized VCG mechanism, therefore, serves to unify many results in
mechansim design theory.
\end{abstract}

\section{Introduction}

Mechanism design theory now forms an integral part of modern economics.%
\footnote{%
For instance, see the extensive and unified account of mechanism design
theory in Mas-Colell \emph{et al. }(1995). This is also an excellent source
for references.} Its varied applications include the theory of monopoly
pricing, optimal tax theory and the provision of public goods. Perhaps its
most successful application has been to the theory of auctions, a central
theme of this paper. With a few exceptions, however, mechanism design theory
in general, and auction theory in particular, to date has restricted
attention to the case when agents' private information is one dimensional.
Consideration of multi-dimensional types poses substantial technical
difficulties and results of any generality seem to be non-existent. The
complications are not of a technical nature alone: many of the economic
insights from the single-dimensional theory do not extend in any natural
fashion. (See Armstrong (1996), McAfee and McMillan (1988) and Wilson
(1993)).

An important strand of traditional mechanism design theory is concerned with
the design of \emph{optimal} mechanisms (or auctions), that is,
mechanisms/auctions which maximize the expected revenue of the seller
(Myerson (1981), Wilson (1993), among others). A second strand of the
theory, however, is concerned with the design of \emph{efficient} mechanisms
(Vickrey (1961), Mirrlees (1971), Groves (1973), among others). Here the
primary objective of the planner is not revenue maximization but rather
social efficiency.

Our approach combines the two considerations, placing greater weight on
efficiency. We are interested in revenue maximizing mechanisms but restrict
attention to mechanisms that allocate efficiently. Our main result derives
the revenue maximizing mechanism (or auction) in the class of efficient
mechanisms (auctions): this is a generalization of the well-known
Vickrey-Clarke-Groves (VCG) mechanism. Thus while optimal auctions are
difficult to characterize when types are multi-dimensional, we are able to
make progress in this area by focusing on efficient mechanisms and are able
to extend the extant theory to multi-dimensional types.

With this characterization in hand, we can then address a variety of other
questions. For instance, we show that budget balancing mechanisms exist 
\emph{if and only if} the generalized VCG mechanism runs an expected surplus
for the planner.

The fact that the generalized VCG provides a necessary and sufficient
condition for the existence of balanced budget efficient mechanism results
in simple and unified proofs of some impossibility results concerning (a)
efficient bilateral trade; and (b) efficient provision of public goods.

Our set up is abstract. The abstraction leads to a simple formulation and
also has the virtue that most of our results are then derived in a very
general setting. For example, in the context of multiple object auctions we
make very weak assumptions on the structure of the valuations of the
bidders. In particular, our results are applicable in situations of
non-identical goods with complementarities, issues that have been the focus
of much recent attention in auction theory.

The analysis of multiple object auctions forms both a major motivation for
this paper and a major area of application of the results.

\paragraph{Multiple Object Auctions and Privatization:}

Although Vickrey's (1961) classic paper on auctions was concerned with the
question of efficiency, starting with Myerson (1981), auction theory has
primarily been occupied with the question of revenue. Attempts to extend
Myerson's beautiful results to the case of multiple objects have been
largely unsuccessful. Indeed, in order make the problem tractable, most of
the research in this area has made the assumption that even with multiple
objects the private information of the buyers is still one dimensional
(Wilson (1979), Maskin and Riley (1990), Ausubel and Cramton (1995), Branco
(1996) among others).

The recent spurt in interest in the study of multiple object auctions is
largely the result of large scale privatization of socially held assets by
governments. These include the sales of industrial enterprises in Eastern
Europe and the former Soviet Union, radio spectra in the United States and
the railway system in Britain. There is a vast literature in this area.
Recent work on the theoretical aspects of privatization includes Maskin
(1992), McMillan (1994) and Milgrom (1997).

The primary goal of these privatizations is not the maximization of revenue
but rather that the assets being sold are allocated efficiently. Of course,
because of the vast sums involved the revenue question is not without
interest but it does seem to be of secondary import.

Why should efficiency be the primary goal of privatization? It may be argued
that governments should not be concerned about efficiency at all since there
is likely to be secondary market for these assets and that transactions in
these secondary markets will in the end result in an efficient allocation.
Thus, following this line of argument, governments may as well maximize
revenue and not worry about how the assets are allocated.

However, because of the nature and size of the assets being privatized,
secondary trades are likely to be the result of bilateral (or possibly
multilateral) bargaining rather than from trade on well functioning thick
markets. And this bargaining will take place under conditions of incomplete
information. But it is well understood that bargaining under incomplete
information is unlikely to lead to efficient trade (as shown by Myerson and
Satterthwaite (1983), for instance). Thus, it may be argued that in order to
ensure that the assets are allocated efficiently, the government cannot rely
on secondary markets.

Indeed, in the well publicized sale of radio spectra in the United States,
the Federal Communications Commission was specifically mandated by Congress
to sell the licenses in a way that ensured an ``efficient and intensive use
of the electromagnetic spectrum.'' The designers of the auction rules
interpreted this as ``putting licenses in the hands of those who value them
the most,'' (Milgrom (1997)). Revenue issues, while not entirely absent,
played a subsidiary role at best.

It is well-known that the twin goals of optimality (revenue maximization)
and social efficiency (welfare maximization) may be in conflict. For
instance, consider the design of an optimal auction for a single good as in
Myerson (1981). First, the optimal auction allocates the object to the agent
with the highest ``priority level'' (see Myerson (1981)) and since this is
not necessarily the person who assigns the highest value to the object, the
allocation may be inefficient. Second, even in cases where the ranking
according to priority levels agrees with the ranking according to values,
the optimal auction typically involves a reserve price. Now with positive
probability the seller retains the object even though there are unrealized
gains from trade. Thus the optimal auction need not be socially efficient.

\paragraph{The Main Results:}

Our paper derives the following results in the context of independent
multi-dimensional types and quasi-linear preferences:

\begin{enumerate}
\item  \emph{Revenue Maximization}: Our main result is that a generalized
version of the well-known Vickrey-Clarke-Groves mechanism maximizes the
planners' expected revenue among all efficient mechanisms (Theorem \ref
{payment} below) that are incentive compatible and individually rational.
This result is derived in a very general context.

\item  \emph{Multiple Object Auctions}: We show how the main result may be
applied to multiple object auctions. In situations where the objects are
identical and bidders have decreasing marginal valuations (``downward
sloping demand curves'') it implies that the Vickrey\ (1961) auction
maximizes the seller's revenue among all auctions that are efficient
(Proposition \ref{revmax}). We then show how our abstract set up can also
accommodate, very simply, non-identical objects, complementarities
(``synergies'') among the objects and consumption externalities.

\item  \emph{Budget Balance}: Even though the VCG mechanism typically does
not balance the planner's budget, we show that there exists an efficient,
incentive compatible and individually rational mechanism that also balances
the budget if and only if the generalized VCG mechanism runs an expected
surplus (Theorem \ref{bal}). The proof is constructive.

\item  \emph{Other Applications}: The result on necessary and sufficient
conditions for budget balance is applied to two allocation problems, one
with private goods and one with public goods. It leads to very elementary
proofs of (a) the impossibility of an efficient trade of a single object
among a buyer and a seller (Proposition \ref{ms}); and (b) the impossibility
of efficient provision and financing of a public project (Proposition \ref
{pub}).
\end{enumerate}

Our analysis depends crucially on a technical result which shows that any
two incentive compatible mechanisms which implement the same allocation rule
must be ``payoff equivalent,'' that is, the expected payoff to an agent can
differ in the two mechanisms by at most an additive constant (Lemma \ref
{main} below). This result is thus a generalization of Myerson's (1981)
payoff equivalence result to the case of when agents' private information is
multi-dimensional. It is derived without making any differentiability
assumptions on the mechanism and is thus applicable to situations (e.g.,
auctions) where such assumptions are not natural. The proof of Lemma 1 is
relegated to an appendix.

\section{Preliminaries}

There is a set $K$ of a finite number of social alternatives. Suppose that $%
K=\left\{ 1,2,...,K\right\} $ with generic element $k.$ There are $I$
individual agents, indexed $i=1,2,...,I$\textbf{.}

Each agent $i$ then has a $K$-dimensional \emph{type} $t_i=\left( t_i\left(
1\right) ,t_i\left( 2\right) ,...,t_i\left( K\right) \right) \in $ $\mathbf{R%
}^K.$ The payoff to agent $i$ of type $t_i$ is \emph{quasi-linear}, that is,
it is of the form 
\[
t_i\left( k\right) -x_i 
\]
where $x_i$ is a monetary transfer made by $i$ to a planner or a central
agency. Let $T_i$ denote the set of possible types for $i$. We assume that
for all $i$, $T_i$ is a compact and convex subset of $\mathbf{R}^K$.

For example, in a problem of how to allocate a finite number of indivisible
objects, the alternatives may represent allocations of the objects to the
individuals and the type of an agent may represent how much value or utility
the agent derives from the various alternatives. Notice that the abstract
model is general enough to allow for a variety of specifications including
complementarities among goods and externalities among agents.\textbf{\ }

As usual, the vector $t=\left( t_1,t_2,...,t_I\right) $ denotes the types of
all agents and the vector $t_{-i}=\left(
t_1,t_2,...,t_{i-1},t_{i+1},...,t_I\right) $ the types of all agents other
than $i.$ Correspondingly, $T=\times _{j=1}^IT_j$ and $T_{-i}=\times _{j\neq
i}T_j$ denote the sets of all types and all types other than $i,$
respectively. The vector $\left( s_i,t_{-i}\right) =\left(
t_1,t_2,...,t_{i-1},s_i,t_{i+1},...,t_I\right) .$

Let $f_i$ denote the density of $t_i$ on $T_i.$ We suppose that $f_i$ is
continuous and that the support of $f_i,$ denoted by $\limfunc{supp}f_i,$ is 
$T_i.$ The types $t_i$ are assumed to be independently distributed across
agents.

The environment considered here is thus one of independent ``private
values.''

\paragraph{Mechanisms:}

A\emph{\ direct mechanism }is a pair $\left( \kappa ,\mu \right) $ where $%
\kappa :T\rightarrow K$ is an \emph{allocation rule} and $\mu :T\rightarrow 
\mathbf{R}^I$ is a \emph{payment rule}. Thus, given reports $s\in T,$ $%
\kappa \left( s\right) $ is the chosen alternative and $\mu _i\left(
s\right) $ is the transfer payment made by $i.$ A mechanism $\left( \kappa
,\mu \right) $ is said to be (Bayesian) \emph{incentive compatible} if the
identity function (``truth-telling'') is a Bayesian equilibrium of the
resulting game. By the revelation principle, the restriction to direct
mechanisms will be without loss of generality.

Let $\Delta \left( K\right) $ denote the set of probability distributions
over $K$. Given an allocation rule $\kappa :T\rightarrow K,$ define $%
Q_i\left( \kappa ,\cdot \right) :T_i\rightarrow \Delta \left( K\right) $ as
the function whose $k$th component is 
\begin{equation}
Q_i^k\left( \kappa ,t_i\right) =\limfunc{Prob}\left\{ s_{-i}\in
T_{-i}:\kappa \left( t_i,s_{-i}\right) =k\right\} ,  \label{defQ}
\end{equation}
that is, the \emph{conditional probability} that alternative $k$ will be
chosen by $\kappa \left( \cdot \right) $ when agent $i$'s type is $t_i.$%
\footnote{%
Although we have assumed that the allocation rule $\kappa :T\rightarrow K$
is deterministic it would make no difference in what follows if it were
random, that is, $\kappa :T\rightarrow \Delta \left( K\right) .$ In that
case, $Q_i^k\left( t_i\right) $ would again be defined as before but its
computation would incorporate the randomness of the allocation rule also.}

In much of what follows, we will fix an allocation rule $\kappa \left( \cdot
\right) $ and thus, in order to economize on notation, suppress the
dependence of $Q_i$ on $\kappa \left( \cdot \right) $ by writing $Q_i\left(
t_i\right) $ instead of $Q_i\left( \kappa ,t_i\right) .$

Given a mechanism, the \emph{expected payoff} to agent $i$ from reporting $%
s_i $ when his type is $t_i$ and all other agents are reporting truthfully
is 
\begin{equation}
E_{t_{-i}}\left[ t_i\left( \kappa \left( s_i,t_{-i}\right) \right) -\mu
_i\left( s_i,t_{-i}\right) \right] =Q_i\left( s_i\right) \cdot t_i-m_i\left(
s_i\right)  \label{defpi}
\end{equation}
where 
\[
m_i\left( s_i\right) =E_{t_{-i}}\left[ \mu _i\left( s_i,t_{-i}\right) \right]
\]
is the \emph{expected payment} of $i$ when reporting $s_i.$

It is convenient to define the \emph{equilibrium payoff function } 
\begin{equation}
U_i\left( \kappa ,\mu ,t_i\right) =Q_i\left( t_i\right) \cdot t_i-m_i\left(
t_i\right) .  \label{defU}
\end{equation}
It may be useful to think of $U_i$ as an indirect utility function.

Once again, in order to economize on notation, we suppress the dependence of 
$U_i$ on the specific mechanism $\left( \kappa ,\mu \right) $ and write $%
U_i\left( t_i\right) $ instead of $U_i\left( \kappa ,\mu ,t_i\right) .$

Our first result, Lemma \ref{main} below, provides a characterization of the
equilibrium payoff functions $U_{i}$ that can result from an incentive
compatible mechanism. It shows that the equilibrium payoff functions from
two such mechanisms with the same allocation rule $\kappa \left( \cdot
\right) $ can differ at most by an additive constant. It is a generalization
of the ``revenue equivalence'' result (Myerson (1981)) and Riley and
Samuelson (1981) to the case of multi-dimensional types. Under stronger
hypotheses, the conclusion of Lemma 1 has been obtained by for general
allocation rules by Armstrong (1996) and Jeheil et al. (1996), and for the
particular case of efficient rules, by d'Aspremont and G\'{e}rard-Varet
(1979b) and Williams (1997).

\begin{lemma}
\label{main}\emph{(Payoff Equivalence) }Suppose the mechanism $\left( \kappa
,\mu \right) $ is incentive compatible. Then the expected payoff function $%
U_{i}$ is determined by $Q_{i}$ up to an additive constant. For all $%
t_{i},s_{i}\in T_{i}$, 
\begin{equation}
U_{i}\left( t_{i}\right) =U_{i}\left( s_{i}\right) +\int_{0}^{1}Q_{i}\left(
rt_{i}+\left( 1-r\right) s_{i}\right) \cdot \left( t_{i}-s_{i}\right) dr.
\label{payeq}
\end{equation}
\end{lemma}

%TCIMACRO{
%\TeXButton{Proof}{\proof%
%}}%
%BeginExpansion
\proof%
%
%EndExpansion
See the Appendix. 
%TCIMACRO{
%\TeXButton{End Proof}{\endproof%
%}}%
%BeginExpansion
\endproof%
%
%EndExpansion
\bigskip

Since $U_i\left( t_i\right) =Q_i\left( t_i\right) \cdot t_i-m_i\left(
t_i\right) ,$\ we have that $U_i\left( 0\right) =-m_i\left( 0\right) $. Then
(\ref{payeq}) can be rewritten as, 
\begin{equation}
m_i\left( t_i\right) =m_i\left( 0\right) +Q_i\left( t_i\right) \cdot
t_i-\int_0^1Q_i\left( rt_i\right) \cdot t_idr,  \label{reveq}
\end{equation}
which just states that all incentive compatible mechanisms with the same
allocation rule $\kappa \left( \cdot \right) $\ are also ``revenue (or
payment) equivalent'' up to an additive constant.

Until now our analysis has been fairly standard and followed conventional
mechanism design theory. In what follows our concern shifts to \emph{%
efficient }mechanisms.

\section{Efficient Mechanisms}

We now examine properties of incentive compatible mechanisms such that the
allocation rule is socially efficient.

Since agents' payoffs are quasi-linear, an allocation rule is socially
efficient if and only if the chosen alternative maximizes the sum of agents'
payoffs.

\begin{definition}
An allocation rule $\kappa ^{\ast }:T\rightarrow K$ is \emph{(ex post)
efficient} if for all $t\in T,$ the chosen alternative $\kappa ^{\ast
}\left( t\right) $ maximizes social welfare $\sum_{i=1}^{I}t_{i}\left(
k\right) $ over $K.$\footnote{%
There may be more than one alternative that maximizes social welfare. Since
such ties occur with zero probability, which one is chosen will not affect
our results.}
\end{definition}

We call any mechanism $\left( \kappa ^{*},\mu \right) $ with an efficient
allocation rule $\kappa ^{*}\left( \cdot \right) $ an \emph{efficient} \emph{%
mechanism}.

It is convenient to define 
\begin{equation}
SW\left( t\right) =\sum_{i=1}^It_i\left( \kappa ^{*}\left( t\right) \right)
\label{sw}
\end{equation}
as the maximized value of \emph{social welfare} from an efficient allocation
when the types are $t,$ and 
\begin{equation}
SW_{-i}\left( t\right) =\sum_{j\neq i}t_j\left( \kappa ^{*}\left( t\right)
\right)  \label{sw-i}
\end{equation}
as the \emph{social welfare }of individuals other than $i$ from an efficient
allocation when the types are $t.$

\section{Participation Constraints}

Thus far we have concentrated on incentive compatibility, implicitly
assuming that all agents participate in the workings of the mechanism, that
is, provide their private information, $t$, and pay $\mu \left( t\right) .$
In many applications, however, it is natural to assume that agents have
outside options and that if their expected payoff from the mechanism is not
superior to their outside option, agents can choose to not participate in
the workings of the mechanism. Exercising their option to not participate in
the mechanism may violate social efficiency.

For instance, consider the problem of allocating a single indivisible good
by means of an auction. If there is an individual $i$ whose interim expected
payoff from participating is worse than his outside option he will not
participate in the auction. Now, ex post, there will be instances where $i$
has the highest valuation and the socially efficient allocation would be to
award $i$ the object. However, this fact cannot be determined since his
private information, $t_i$, is not available to the planner.

Thus, in such situations an \emph{efficient} mechanism must guarantee that
individuals will not be worse off by participating in the mechanism. This
constrains the range of feasible mechanisms.

In many situations it is simplest to model this by assuming that every
agent's payoff from not participating is $0.$ This may be appropriate, for
instance, when considering the auction of a privately consumed good with no
consumption externalities. In other situations, however, it is more
appropriate to model the payoff from not participating as itself being \emph{%
type dependent }(and hence private information). For instance, in an
allocation problem where one of the agents is a producer of some goods the
decision to participate may depend on the cost of production itself, that
is, on the ``type'' of the agent.

We will suppose that the ``break-even'' expected payoff of agent $i$ is
exogenously given by a \emph{continuous} function $IR_i:T_i\rightarrow 
\mathbf{R.}$

\begin{definition}
A mechanism $\left( \kappa ,\mu \right) $ is \emph{(interim) individually
rational} if for all $i$ and $t_{i}\in T_{i},$%
\[
U_{i}\left( t_{i}\right) \geq IR_{i}\left( t_{i}\right) .
\]
\end{definition}

Our specification is general enough to allow for the possibility that $%
IR_{i} $ also depends on the allocation rule $\kappa ^{\ast }$. This may be
the result of externalities exerted by participants on \emph{non}%
-participants. As an example, suppose that a valuable technology is being
allocated to one of the firms in an industry by means of an auction. Since
how this technology is allocated will affect competition among all firms in
the industry, including those that choose not to participate in the auction,
the underlying allocation rule may affect the expected payoff from not
participating.

An extensive treatment of auctions with externalities and a discussion of
participation constraints in such an environment can be found in Jeheil et
al. (1996).

\section{The VCG Mechanism and a Generalization}

In this section we study the properties of a well-known mechanism due to
Vickrey (1961) and Clarke (1971). We then provide a generalization.

\subsection{The VCG Mechanism}

In his pioneering study of auctions Vickrey (1961) introduced a mechanism to
efficiently allocate $L$ identical multiple objects in a context where each
bidder has declining marginal values for the objects (or in other words, a
downward sloping demand function). In the Vickrey auction each of $I\geq 2$
bidders submits $L$ bids in decreasing order and the $l$th bid represents
the marginal amount the bidder is willing to pay for the $l$th object. Out
of the $I\times L$ bids the $L$ highest bids are awarded objects and of
course, $I\times \left( L-1\right) $ bids are rejected. If bidder $i$ gets $%
l_i$ objects, he is asked to pay the $l_i$ highest rejected bids that are
not his own. Vickrey (1961) showed that in his auction it was a weakly
dominant strategy to bid one's vector of marginal values honestly and as a
result the auction was efficient.

Subsequently, in his analysis of the efficient provision of public goods,
Clarke (1971) introduced the so called ``pivotal mechanism'' that leads to
an efficient allocation in that context. Clarke (1971) showed that in the
pivotal mechanism it was a dominant strategy to report one's value of the
public good honestly and the mechanism was efficient.

These mechanisms were later generalized by Groves (1973). The Vickrey (1961)
auction and the Clark (1971) pivotal mechanism are, in fact, just special
cases of a single abstract mechanism that we will refer to as the
Vickrey-Clarke-Groves (or VCG) mechanism.

The VCG mechanism, denoted by $\left( \kappa ^{*},\mu ^V\right) ,$ is
defined by the payment rule: 
\begin{eqnarray}
\mu _i^V\left( t\right) &=&\sum_{j\neq i}t_j\left( \kappa ^{*}\left(
0,t_{-i}\right) \right) -\sum_{j\neq i}t_j\left( \kappa ^{*}\left( t\right)
\right)  \nonumber \\
&=&SW_{-i}\left( 0,t_{-i}\right) -SW_{-i}\left( t\right)  \label{muv}
\end{eqnarray}
where $\kappa ^{*}\left( 0,t_{-i}\right) $ is an efficient alternative that
would result if $i$ were to report $t_i=0$ (or equivalently, in many
settings, if $i$ were not present).

Observe that the amount $\mu _i^V\left( t\right) $ represents the \emph{%
externality} that $i$ exerts on the other $I-1$ agents by his presence in
society. It is the difference between the welfare of the others ``without
him'' and the welfare of the others ``with him.'' Notice that in both the
Vickrey (1961) auction for private goods and the Clarke (1971) mechanism for
public goods each agent pays the externality he exerts on the other $I-1$
agents.

Fix some $t_{-i},$ the types of agents other than $i.$ In the VCG mechanism
the payoff to $i$ of type $t_i$ when he reports $s_i$ is: 
\begin{equation}
\sum_{j=1}^It_j\left( \kappa ^{*}\left( s_i,t_{-i}\right) \right)
-\sum_{j\neq i}t_j\left( \kappa ^{*}\left( 0,t_{-i}\right) \right)
\label{dom}
\end{equation}
The second term is independent of the report $s_i$ and the first is
maximized by choosing $s_i=t_i.$ Thus, as is well known, ``truth-telling''
is a weakly dominant strategy in the VCG mechanism. Thus, \emph{a fortiori},
the VCG mechanism is \emph{incentive compatible}.

Using (\ref{dom}) agent $i$'s \emph{ex post} payoff in equilibrium (when $%
s_i=t_i$) is just $SW\left( t\right) -SW\left( 0,t_{-i}\right) $, that is,
the difference in social welfare when $i$ reports $t_i$ versus when he
reports $0.$

\subsection{The Generalized VCG Mechanism}

The payment in the VCG mechanism is exactly the externality that $i$ exerts
on other agents from reporting $t_i$ rather than zero (see (\ref{muv})). In
this subsection we use this interpretation to generalize the original VCG
mechanism. This generalization will play a central role in our analysis.

Fix a vector of types $s=\left( s_1,s_2,...,s_n\right) \in T,$ one for each
player. The \emph{VCG mechanism with basis} $s$, is defined by 
\begin{eqnarray}
\mu _i^{*}\left( t\mid s_i\right) &=&s_i\left( \kappa ^{*}\left(
s_i,t_{-i}\right) \right) +\sum_{j\neq i}t_j\left( \kappa ^{*}\left(
s_i,t_{-i}\right) \right) -\sum_{j\neq i}t_j\left( \kappa ^{*}\left(
t\right) \right) -IR_i\left( s_i\right)  \nonumber \\
&=&\left[ SW\left( s_i,t_{-i}\right) -SW_{-i}\left( t\right) \right]
-IR_i\left( s_i\right)  \label{mustar}
\end{eqnarray}
It is routine to verify that truth-telling is a weakly dominant strategy in
the generalized VCG mechanism and thus it is also incentive compatible.

Agent $i$'s \emph{ex post} payoff in equilibrium is 
\[
\left[ SW\left( t\right) -SW\left( s_i,t_{-i}\right) \right] +IR_i\left(
s_i\right) 
\]
which is just the \emph{difference} in social welfare that would result if $%
i $ were to report $t_i$ rather than $s_i$ plus the individually rational
level of type $s_i.$

The corresponding expected payoff is 
\begin{equation}
U_i^{*}\left( t_i\mid s_i\right) =E_{t_{-i}}\left[ SW\left( t\right)
-SW\left( s_i,t_{-i}\right) \right] +IR_i\left( s_i\right)  \label{deft1}
\end{equation}
Observe that if for all $i,$ we have $s_i=0$ and $IR_i\left( s_i\right) =0,$
then the VCG mechanism with basis $s_i$ defined in (\ref{mustar}) is the
same as the original VCG mechanism in (\ref{muv}).

\subsection{Optimal Choice of Basic Types}

We have defined the VCG mechanism relative to any basis $s.$ In what follows
it will be important to choose $s$ optimally.

Define 
\begin{eqnarray}
\underline{t}_i &\in &\arg \min_{t_i\in T_i}E_{t_{-i}}\left[
\sum_{j=1}^It_j\left( \kappa ^{*}\left( t\right) \right) \right] -IR_i\left(
t_i\right)  \nonumber \\
&=&\arg \min_{t_i\in T_i}E_{t_{-i}}\left[ SW\left( t\right) \right]
-IR_i\left( t_i\right)  \label{deft2}
\end{eqnarray}
and consider the mechanism $\mu ^{*}\left( t\mid \underline{t}_i\right) $,
that is, the \emph{VCG mechanism with basis} $\underline{t}.$ The type $%
\underline{t}_i$ is the ``most reluctant'' type of agent $i$ in the sense
that his gain from participating in any VCG mechanism is the least among all
types of agent $i.$

Using (\ref{deft1}) we can write: 
\begin{eqnarray*}
U_i^{*}\left( t_i\mid \underline{t}_i\right) &=&Q_i^{*}\left( t_i\right)
\cdot t_i-m_i^{*}\left( t\mid \underline{t}_i\right) \\
&=&Q_i^{*}\left( t_i\right) \cdot t_i+E_{t_{-i}}\left[ SW_{-i}\left(
t\right) -SW\left( \underline{t}_i,t_{-i}\right) \right] +IR_i\left( 
\underline{t}_i\right) \\
&=&E_{t_{-i}}\left[ SW\left( t\right) -SW\left( \underline{t}%
_i,t_{-i}\right) \right] +IR_i\left( \underline{t}_i\right)
\end{eqnarray*}
so that 
\[
U_i^{*}\left( \underline{t}_i\mid \underline{t}_i\right) =IR_i\left( 
\underline{t}_i\right) . 
\]
Next, using (\ref{deft2}), we can write, for all $t_i,$%
\begin{equation}
E_{t_{-i}}\left[ SW\left( t\right) \right] -IR_i\left( t_i\right) \geq
E_{t_{-i}}\left[ SW\left( \underline{t}_i,t_{-t}\right) \right] -IR_i\left( 
\underline{t}_i\right)  \label{uistar}
\end{equation}
and by rearranging (\ref{uistar}) we obtain that 
\begin{eqnarray*}
U_i^{*}\left( t_i\mid \underline{t}_i\right) &=&E_{t_{-i}}\left[ SW\left(
t\right) -SW\left( \underline{t}_i,t_{-t}\right) \right] +IR_i\left( 
\underline{t}_i\right) \\
&\geq &IR_i\left( t_i\right)
\end{eqnarray*}
so that the mechanism $\mu ^{*}\left( \cdot \mid \underline{t}\right) $ is
individually rational.

To summarize, we have argued that for a VCG mechanism with basis $\underline{%
t}=\left( \underline{t}_1,\underline{t}_2,...,\underline{t}_n\right) $
defined in (\ref{deft2}) we have that for all $t_i,$%
\begin{eqnarray}
U_i^{*}\left( t_i\mid \underline{t}_i\right) &\geq &IR_i\left( t_i\right) 
\nonumber \\
U_i^{*}\left( \underline{t}_i\mid \underline{t}_i\right) &=&IR_i\left( 
\underline{t}_i\right) .  \label{vcgpayoff}
\end{eqnarray}

\subsection{Payment Maximizing Efficient Mechanisms}

Our main result is:

\begin{theorem}
\label{payment}\emph{(Payment Maximization) }Among all mechanisms that are
efficient, incentive compatible and individually rational, the VCG mechanism
with basis $\underline{t},$ defined in (\ref{deft2}) maximizes the expected
payments of each agent.
\end{theorem}

%TCIMACRO{
%\TeXButton{Proof}{\proof%
%}}%
%BeginExpansion
\proof%
%
%EndExpansion
As above, let $U_i^{*}\left( \cdot \mid \underline{t}_i\right) $ denote the
expected payoff function for the VCG mechanism with basis $\underline{t}$, $%
\left( \kappa ^{*},\mu ^{*}\left( \cdot \mid \underline{t}\right) \right) $.

Now suppose $\left( \kappa ^{*},\mu \right) $ is any other efficient
mechanism that is incentive compatible and individually rational. If $%
U_i\left( \cdot \right) $ is the expected payoff function corresponding to $%
\left( \kappa ^{*},\mu \right) $ then by the payoff equivalence result
(Lemma \ref{main}), for all $t_i,$ 
\[
U_i\left( t_i\right) -U_i^{*}\left( t_i\mid \underline{t}_i\right)
=U_i\left( \underline{t}_i\right) -U_i^{*}\left( \underline{t}_i\mid 
\underline{t}_i\right) . 
\]
Individual rationality requires that for all $i,$ $U_i\left( \underline{t}%
_i\right) \geq IR_i\left( \underline{t}_i\right) =U_i^{*}\left( \underline{t}%
_i\mid \underline{t}_i\right) $ and consequently, for all $t_i,$ 
\[
U_i\left( t_i\right) \geq U_i^{*}\left( t_i\mid \underline{t}_i\right) . 
\]
Thus, for all $t_i,$%
\[
m_i\left( t_i\right) \leq m_i^{*}\left( t_i\mid \underline{t}_i\right) . 
\]

Thus the VCG mechanism with basis $\underline{t}$ maximizes the expected
payment of the agents. 
%TCIMACRO{
%\TeXButton{End Proof}{\endproof%
%}}%
%BeginExpansion
\endproof%
%
%EndExpansion
\bigskip

Some remarks on Theorem \ref{payment} are in order. 

First, while the salience of the VCG mechanism in the class of efficient 
\emph{dominant strategy} mechanisms is well known (see Laffont and Maskin
(1982), in particular), our results highlight its importance in the larger
class of efficient  \emph{Bayesian }mechanisms as well. In particular,
Theorem \ref{payment} shows that in the class of efficient Bayesian
mechanisms the one that maximizes revenue is, in fact, a dominant strategy
mechanism.\footnote{%
Mookherjee and Reichelstein (1992) study the possibility of using dominant
strategy mechanisms in place of Bayesian mechanisms in a general
environment. In particular, they are not concerned with efficient rules
alone.} 

Second, in general, in order to compute the optimal basis, $\underline{t}$,
as in (\ref{deft2}), the planner needs to know the distribution of types $%
f_{i}$. In many natural applications, however, knowledge of $f_{i}$ may be
unnecessary. For example, if, as often assumed in auction theory, $T_{i}=%
\mathbf{R}_{+}^{K}$ and $IR_{i}\left( t_{i}\right) =0$ then regardless of
the density $f_{i},$ $\underline{t}_{i}=0.$

\section{Multiple Object Auctions}

In this section we illustrate how the main result of the previous section
(Theorem \ref{payment}) may be applied to study auctions of multiple objects
in the original environment studied by Vickrey (1961).

Suppose that there are $K$ identical objects to be auctioned and each bidder
has a downward sloping ``demand curve''\emph{\ }which is privately known.
Let $t_i\left( k\right) \geq 0$ denote the \emph{marginal value }of the $k$%
th object assigned by bidder $i$ of type $t_i$. Thus if $i$ were to obtain $%
L $ objects the total value would be $\sum_{k=1}^Lt_i\left( k\right) .$ It
is natural to call the vector $t_i$ the ``demand curve'' of bidder $i.$ The
set of types $T_i$ is then just the set of possible downward sloping demand
curves so that $T_i=\left\{ t_i\in \mathbf{R}_{+}^k:t_i\left( 1\right) \geq
t_i\left( 2\right) \geq ...\geq t_i\left( K\right) \right\} .$ Suppose
further that each bidder's payoff from not participating in the auction is $%
0.$

Clearly, in this environment the types $\underline{t}_i=0,$and thus the VCG
mechanism with basis $\underline{t}$ is exactly the auction proposed by
Vickrey (1961).\footnote{%
Recently, Ausubel (1995) has proposed an open ascending bid auction which,
in this environment, is outcome equivalent to a Vickrey auction.}

The following result on multiple object auctions is an immediate consequence
of Theorem \ref{payment}:

\begin{proposition}
\label{revmax}\emph{(Revenue Maximization) }Suppose all bidders have
downward sloping demand curves. The Vickrey auction maximizes the expected
revenue of the seller among all auctions that are efficient, incentive
compatible and individually rational.\bigskip 
\end{proposition}

While Proposition \ref{revmax} applies to the environment originally studied
by Vickrey (1961), Theorem \ref{payment} is applicable to a more general
class of auction problems. For instance, in the case of identical objects it
applies not only when individual demand curves are downward sloping but even
when they are not. Moreover, Theorem \ref{payment} applies as well to
situations when the objects are not necessarily identical and even allows
for the possibility that there are complementarities (or synergies) in
consumption. Indeed, it is general enough to accommodate externalities in
consumption across bidders. This is because in our abstract set up a
particular social alternative, $k$, can denote a complete allocation of the
objects to bidders and a particular bidder may then be sensitive to how the
objects are allocated to his rivals. Finally, we have allowed for the
possibility that the participation constraints are type dependent.

\section{Budget Balance}

In many economic problems a \emph{desideratum} of a mechanism is that for
every realization of types, the transfers from agents sum to zero, that is,
the planner's budget is exactly balanced \emph{ex post. }In our notation, a
mechanism is said to balance the budget if for all $t,$%
\[
\sum_{i=1}^I\mu _i\left( t\right) =0. 
\]

We know from the work of Green and Laffont (1977) that no dominant strategy
mechanism can always balance the budget. However, Arrow (1979) and
d'Aspremont and G\'{e}rard-Varet (1979a) independently showed that there do
exist Bayesian incentive compatible mechanisms with the balanced budget
property.

The Arrow (1979) and d'Aspremont and G\'{e}rard-Varet (1979a) (or AGV)
mechanism (also called the ``expected externality'' mechanism) $\left(
\kappa ^{*},\mu ^A\right) $ is defined by 
\begin{eqnarray}
\mu _i^A\left( t\right) &=&\left( \frac 1{I-1}\right) \sum_{j\neq
i}E_{s_{-j}}\left[ SW_{-j}\left( t_j,s_{-j}\right) \right] -E_{s_{-i}}\left[
SW_{-i}\left( t_i,s_{-i}\right) \right]  \nonumber \\
&=&\left( \frac 1{I-1}\right) \sum_{j\neq i}E_{s_{-j}}\left[ \sum_{l\neq
j}s_l\left( \kappa ^{*}\left( t_j,s_{-j}\right) \right) \right] -E_{s_{-i}}%
\left[ \sum_{j\neq i}s_j\left( \kappa ^{*}\left( t_i,s_{-i}\right) \right) %
\right]  \label{agv}
\end{eqnarray}
so that for all $t,$ $\sum_{i=1}^I\mu _i^A\left( t\right) =0.$

To see that the AGV mechanism is incentive compatible note that the expected
payoff to $i$ from reporting $s_i$ when his type is $t_i$ when all other
agents are reporting truthfully is: 
\[
E_{t_{-i}}\left[ t_i\left( \kappa ^{*}\left( s_i,t_{-i}\right) \right)
+\sum_{j\neq i}t_j\left( \kappa ^{*}\left( s_i,t_{-i}\right) \right) \right]
-\left( \frac 1{I-1}\right) E_{t_{-i}}\left[ \sum_{j\neq i}E_{s_{-j}}\left[
SW_{-j}\left( t_j,s_{-j}\right) \right] \right] 
\]
and since the second term is independent of $s_i$, this is maximized by
setting $s_i=t_i.$

It is easy to see that the AGV mechanism may not satisfy the individual
rationality constraint. The question of whether there are efficient,
incentive compatible, individually rational mechanisms which also balance
the budget can also be answered by means of the VCG mechanism.

\begin{theorem}
\label{bal}There exists an efficient, incentive compatible and individually
rational mechanism that balances the budget if and only if the VCG mechanism
with basis $\underline{t}$ results in an expected surplus, that is, if and
only if 
\begin{equation}
E_{t}\left[ \sum_{i=1}^{I}\mu _{i}^{\ast }\left( t\mid \underline{t}\right) %
\right] \geq 0.  \label{surplus}
\end{equation}
\end{theorem}

%TCIMACRO{
%\TeXButton{Proof}{\proof%
%}}%
%BeginExpansion
\proof%
%
%EndExpansion
The fact that (\ref{surplus}) is necessary follows from Theorem \ref{payment}
above: if the VCG mechanism with basis $\underline{t}$ runs a deficit then
all efficient, incentive compatible and individually rational mechanisms
must run a deficit.

We now show that (\ref{surplus}) is sufficient by explicitly constructing a
mechanism that balances the budget and is individually rational. First,
consider the AGV mechansim $\mu ^A$ defined in (\ref{agv}). From Lemma \ref
{main} we know that there exist constants $c_i^A$ such that: 
\[
U_i^A\left( t_i\right) =E_{t_{-i}}\left[ SW\left( t\right) \right] -c_i^A 
\]

Now consider the VCG mechanism with basis $\underline{t},$ 
\[
\mu _i^{*}\left( t\mid \underline{t}\right) =SW\left( \underline{t}%
_i,t_{-i}\right) -SW_{-i}\left( t\right) -IR_i\left( \underline{t}_i\right) 
\]
Again, from Lemma \ref{main} we know that there exist constants $c_i^{*}$
such that 
\[
U_i^{*}\left( t_i\mid \underline{t}_i\right) =E_{t_{-i}}\left[ SW\left(
t\right) \right] -c_i^{*} 
\]

Next, suppose the VCG mechanism with basis $\underline{t}$ runs an expected
surplus, that is, 
\[
E_t\left[ \sum_{i=1}^I\mu _i^{*}\left( t\mid \underline{t}\right) \right]
\geq 0 
\]
Then we have that 
\[
E_t\left[ \sum_{i=1}^I\mu _i^{*}\left( t\mid \underline{t}\right) \right]
\geq E_t\left[ \sum_{i=1}^I\mu _i^A\left( t\right) \right] 
\]
since the right hand side is exactly $0.$

Equivalently, 
\begin{equation}
\sum_{i=1}^Ic_i^{*}\geq \sum_{i=1}^Ic_i^A  \label{c2star}
\end{equation}

For all $i>1,$ define $d_i=c_i^A-c_i^{*}$ and let $d_1=-\sum_{i=2}^Id_i.$

Consider the mechanism $\overline{\mu }$ defined by 
\[
\overline{\mu }_i\left( t\right) =\mu _i^A\left( t\right) +d_i 
\]
Clearly, $\overline{\mu }$ balances the budget. It is also incentive
compatible since the payoff to each agent in the mechanism $\overline{\mu }$
differs from the payoff from an incentive compatible mechanism, $\mu ^A,$ by
a constant. It remains to verify that $\overline{\mu }$ is individually
rational.

For all $i\neq 1$%
\begin{eqnarray*}
\overline{U}_i\left( t_i\right) &=&U_i^A\left( t_i\right) +d_i \\
&=&U_i^A\left( t_i\right) +c_i^A-c_i^{*} \\
&=&U_i^{*}\left( t_i\right) \\
&\geq &IR_i\left( t_i\right)
\end{eqnarray*}

By construction $\sum_{i=1}^{I}d_{i}=0$ and observe from (\ref{c2star}) that 
\[
d_{1}=-\sum_{i=2}^{I}d_{i}=\sum_{i=2}^{I}\left( c_{i}^{\ast
}-c_{i}^{A}\right) \geq \left( c_{1}^{A}-c_{1}^{\ast }\right) 
\]
and thus 
\begin{eqnarray*}
\overline{U}_{1}\left( t_{1}\right) &=&U_{1}^{A}\left( t_{1}\right) +d_{1} \\
&\geq &U_{1}^{A}\left( t_{1}\right) +c_{1}^{A}-c_{1}^{\ast } \\
&=&U_{1}^{\ast }\left( t_{1}\right) \\
&\geq &IR_{1}\left( t_{1}\right)
\end{eqnarray*}
so that $\overline{\mu }$ is also individually rational. 
%TCIMACRO{
%\TeXButton{End Proof}{\endproof%
%}}%
%BeginExpansion
\endproof%
%
%EndExpansion

\begin{corollary}
\label{coro}If for all $i$, $IR_{i}\equiv 0$ and all $t_{i}\geq 0$ then
there exists an efficient, incentive compatible and individually rational
mechanism that balances the budget.
\end{corollary}

Under these assumptions, for each $i$, $\underline{t}_{i}=0$ and thus the
VCG mechanism with basis $0$ is 
\begin{eqnarray*}
\mu _{i}^{\ast }\left( t\mid 0\right) &=&SW\left( 0,t_{-i}\right)
-SW_{-i}\left( t\right) \\
&\geq &0
\end{eqnarray*}
since, by definition, $SW\left( 0,t_{-i}\right) =\max_{k}\sum_{j\neq
i}t_{j}\left( k\right) .$

Thus the VCG mechanism with basis $0$ always runs a surplus and the result
follows from Theorem \ref{bal}.

Consider the problem of allocating a bundle of \emph{private} goods among a
group of agents in a way that ensures budget balance. For instance, a bundle
of scarce resources may need to be efficiently allocated among the divisions
of a company. While an auction will accomplish this task there may be
situations where a balanced budget mechanism is more natural. Corollary \ref
{coro} implies that such a mechanism always exists. Indeed, such a mechanism
is constructed explicitly in the proof of Theorem \ref{bal}.

\section{Inefficiency Results}

The revenue maximization result (Theorem \ref{payment} above) shows that the
expected payments in the VCG mechanism $m_i^{*}\left( t_i\right) $ are an
upper bound to the expected payments from any efficient and individually
rational mechanism. In this section we illustrate how this result may be
applied in two settings that are very different from that of an auction.

\subsection{Bilateral Trade}

First, we show that the inefficiency result of Myerson and Satterthwaite
(1983) follows rather simply as a consequence of the revenue maximization
result.

Consider a situation of trade between a seller (agent $1$) and a buyer
(agent $2$). There is a single indivisible good owned by the seller. There
is also a divisible good, money, and as usual, payoffs are quasi-linear. Let
the set of alternatives be $K=\left\{ 1,2\right\} $ where $k=1$ denotes that
there is no trade and the seller keeps the good whereas $k=2$ denotes that
there is trade and the buyer gets the object.

The seller's set of types is $T_1=\left[ 0,1\right] \times \left\{ 0\right\} 
$ and the buyer's set of types is $T_2=\left\{ 0\right\} \times \left[ 0,1%
\right] .$ A seller of type $t_1$ will not participate unless he gets at
least his payoff from no trade and thus $IR_1\left( t_1\right) =t_1\left(
1\right) .$ For the buyer $IR_2\left( t_2\right) =0$ for all $t_2\in T_2.$

Clearly, from the definition of efficiency $\kappa ^{*}\left( t\right) =1$
if $t_1\left( 1\right) >t_2\left( 2\right) $ and $\kappa ^{*}\left( t\right)
=2$ if $t_1\left( 1\right) <t_2\left( 2\right) .$ Thus, $SW\left( t\right)
=t_1\left( 1\right) $ if $t_1\left( 1\right) >t_2\left( 2\right) $ and $%
SW\left( t\right) =t_2\left( 2\right) $ if $t_1\left( 1\right) <t_2\left(
2\right) .$

Now clearly from (\ref{deft2}), we have that $\underline{t}_1=\left(
1,0\right) $ and $\underline{t}_2=\left( 0,0\right) .$

A \emph{trading mechanism} is a mechanism $\left( \kappa ,\mu \right) $
where for each $t\in T,$ $\kappa \left( t\right) $ is an allocation and $\mu
_i\left( t\right) $ are payments satisfying $\mu _1\left( t\right) +\mu
_2\left( t\right) =0.$ Thus a trading mechanism is a mechanism in which
there in no net inflow or outflow of funds and the planner's budget is
balanced.

As in Myerson and Satterthwaite (1983) we ask whether there exists a trading
mechanism that is individually rational and promotes efficient trade among
the agents. Denote by $\kappa ^{*}\left( t\right) $ the allocation that is
efficient when the types are $t.$

We know that the VCG mechanism with basis $\underline{t},$ $\left( \kappa
^{*},\mu ^{*}\left( \cdot \mid \underline{t}\right) \right) $ is efficient.
Let us now compute the payments by the two agents in the VCG mechanism with
basis $\underline{t}$. It is easy to see that if $t_1\left( 1\right)
>t_2\left( 2\right) $ then 
\begin{eqnarray*}
\mu _1^{*}\left( t\mid \underline{t}\right) &=&0 \\
\mu _2^{*}\left( t\mid \underline{t}\right) &=&0
\end{eqnarray*}
whereas if $t_1\left( 1\right) <t_2\left( 2\right) $ then 
\begin{eqnarray*}
\mu _1^{*}\left( t\mid \underline{t}\right) &=&-t_2\left( 2\right) \\
\mu _2^{*}\left( t\mid \underline{t}\right) &=&t_1\left( 1\right)
\end{eqnarray*}
Thus 
\begin{eqnarray*}
\mu _1^{*}\left( t\right) +\mu _2^{*}\left( t\right) &=&-t_2\left( 2\right)
+t_1\left( 1\right) \\
&\leq &0
\end{eqnarray*}
and is strictly less than zero unless the no-trade is itself efficient. Thus
the VCG mechanism with basis $\underline{t}$ runs an expected deficit. From
Theorem \ref{bal}, we infer that \emph{no }individually rational mechanism
will promote efficient trade unless the mechanism injects money into the
economy, that is, it cannot be a trading mechanism.\footnote{%
For the sake of exposition we have assumed that the supports of the values
of the seller and the buyer are the same. It is routine to confirm that the
result continues to hold as long as the supports overlap (as in Myerson and
Satterthwaite (1983)).} Thus we obtain:

\begin{proposition}
\label{ms}In the bilateral trading problem there does not exist an
efficient, incentive compatible and individually rational trading mechanism.
\end{proposition}

Williams (1997) also provides an alternative derivation of the Myerson and
Satterthwaite result which is closely related. In particular, he shows an
equivalence between any efficient mechanism and one in the Groves class; and
that no Groves mechanism can satisfy individual rationality and balance the
budget simultaneously. He then uses the equivalence result to derive very
general results on the possiblity of efficient trade, especially in
situations that involve more than two agents. McAfee (1991) and Makowski and
Mezzetti (1994) also use similar techniques.

These papers, however, do not identify the salience of the VCG mechanism.

\subsection{Public Project Choice}

Next, consider the classic public goods problem. Suppose that a public good
can be either provided or not. Thus the set of social alternatives is $%
K=\left\{ 0,1\right\} $. Let $t_i\geq 0$ denote agent $i$'s utility from the
public good so that for each individual, $T_i=\left[ 0,1\right] .$ Suppose
that for all $i$ and $t_i,$ $IR_i\left( t_i\right) =0$ so that $\underline{t}%
_i=0.$

Suppose that it costs $c$ to produce the public good. It is efficient to
undertake the project ($k=1$) if and only if $\sum_{j=1}^{I}t_{j}\geq c.$

It is known that in no dominant strategy mechanism (such as a VCG mechanism)
can the cost of the public good exactly equal the payments of the agents. In
other words, in such mechanisms the budget cannot be balanced. The AGV
mechanism proposed by Arrow (1979) and d'Aspremont and G\'{e}rard-Varet
(1979a) satisfies the budget balancing property but need not be individually
rational. Mailath and Postlewaite (1991) show that no mechanism that
balances the budget can be individually rational.\footnote{%
Laffont and Maskin (1979) also allude to the difficulty of achieving \emph{%
interim} individual rationality and demonstrate the possibility of achieving 
\emph{ex ante} individual rationality, that is, $E\left[ U_{i}\left(
t_{i}\right) \right] \geq 0.$}

To see how this last result is also a consequence of Theorem \ref{bal} let
us, once again, compute the payments in the VCG mechanism. We have that the
externality exerted by $i$ on the other $I-1$ agents is, in the usual
notation: 
\[
\mu _{i}^{\ast }\left( t\right) =\left[ \sum_{j\neq i}t_{j}\left( \kappa
^{\ast }\left( t_{-i}\right) \right) -c\kappa ^{\ast }\left( t_{-i}\right) %
\right] -\left[ \sum_{j\neq i}t_{j}\left( \kappa ^{\ast }\left( t\right)
\right) -c\kappa ^{\ast }\left( t\right) \right] 
\]
and thus $\mu _{i}^{\ast }\left( t\right) >0$ only if $\kappa ^{\ast }\left(
t_{-i}\right) =0$ and $\kappa ^{\ast }\left( t\right) =1,$ that is, only if $%
i$ is ``pivotal.'' Now, when $\mu _{i}^{\ast }\left( t\right) >0,$%
\[
\mu _{i}^{\ast }\left( t\right) =\left[ c-\sum_{j\neq i}t_{j}\right] \leq
t_{i} 
\]
because $k=1$ only if $\sum_{j=1}^{I}t_{j}\geq c.$ If with positive
probability, it is strictly better to provide the good than not, then the
expected payment in VCG mechanism is less than $c.$ Since the VCG mechanism
maximizes expected payments among all efficient and individually rational
mechanisms we obtain:

\begin{proposition}
\label{pub}Suppose that with positive probability, it is strictly better to
provide the public good than not. Then there does not exist an efficient and
individually rational mechanism which always covers the cost of producing
the public good.
\end{proposition}

\section{Conclusion}

We have shown how a single mechanism, the VCG mechanism with an optimally
chosen basis, provides a unified perspective on many areas of mechanism
design theory. It raises the greatest revenue among auctions that result in
an efficient allocation of multiple objects. It also serves to determine the
possibility of achieving efficiency when other considerations (e.g. budget
balance) are present.

\section{Appendix}

In this appendix we derive some consequences of incentive compatibility. Our
goal is to provide a proof for the payoff equivalence result (Lemma 1).

\begin{definition}
The direct mechanism $\left( \kappa ,\mu \right) $ is \emph{incentive
compatible} if for all $i$ and for all $t_{i},s_{i}\in T_{i}$: 
\begin{equation}
Q_{i}\left( t_{i}\right) \cdot t_{i}-m_{i}\left( t_{i}\right) \geq
Q_{i}\left( s_{i}\right) \cdot t_{i}-m_{i}\left( s_{i}\right) .  \label{ic}
\end{equation}
\end{definition}

First, observe that incentive compatibility is equivalent to the statement
that for all $t_i$ and $s_i$ in $\limfunc{supp}f_i$ (which is assumed to be $%
T_i)$: 
\begin{eqnarray}
U_i\left( t_i\right) &\geq &Q_i\left( s_i\right) \cdot t_i-m_i\left(
s_i\right)  \nonumber \\
&=&Q_i\left( s_i\right) \cdot s_i-m_i\left( s_i\right) +Q_i\left( s_i\right)
\cdot \left( t_i-s_i\right)  \nonumber \\
&=&U_i\left( s_i\right) +Q_i\left( s_i\right) \cdot \left( t_i-s_i\right) .
\label{ic3}
\end{eqnarray}
By interchanging the roles of $t_i$ and $s_i$ in (\ref{ic3}) we also have 
\begin{equation}
U_i\left( s_i\right) \geq U_i\left( t_i\right) +Q_i\left( t_i\right) \cdot
\left( s_i-t_i\right) ,  \label{ic4}
\end{equation}
and together (\ref{ic3}) and (\ref{ic4}) yield: 
\begin{equation}
Q_i\left( t_i\right) \cdot \left( s_i-t_i\right) \leq U_i\left( s_i\right)
-U_i\left( t_i\right) \leq Q_i\left( s_i\right) \cdot \left( s_i-t_i\right) .
\label{ic5}
\end{equation}

Second, observe that incentive compatibility can be rewritten as: 
\[
U_i\left( t_i\right) =\max_{s_i}\left\{ Q_i\left( s_i\right) \cdot
t_i-m_i\left( s_i\right) \right\} 
\]
For each $s_i,$ the expression in the brackets is an affine function of $t_i$
and since the maximum of a family of affine functions is a convex function, $%
U_i$ is convex (Rochet (1987)). Since $Q_i$ is bounded, taking limits in (%
\ref{ic5}) as $s_i\rightarrow t_i$ establishes that $U_i$ is continuous
everywhere. (The fact that $U_i$ is convex already implies that it is
continuous on the relative interior of its domain.) Thus incentive
compatibility implies that $U_i$ is \emph{convex and continuous.}

\subparagraph{\noindent Proof of Lemma \ref{main}.}

Suppose $\left( \kappa ,\mu \right) $ in incentive compatible. In order to
establish (\ref{payeq}) fix a $t_{i}$ and a $s_{i}$ in $T_{i}$ and define a
function $V_{i}:\left[ 0,1\right] \rightarrow \mathbf{R}$ by 
\[
V_{i}\left( r\right) =U_{i}\left( rt_{i}+\left( 1-r\right) s_{i}\right) 
\]
so that $V_{i}\left( 0\right) =U_{i}\left( s_{i}\right) $ and $V_{i}\left(
1\right) =U_{i}\left( t_{i}\right) .$ Since $U_{i}:T_{i}\rightarrow \mathbf{R%
}$ is convex and continuous and $V_{i}:\left[ 0,1\right] \rightarrow \mathbf{%
R}$ is also convex and continuous.

A convex function is absolutely continuous (Lemma 5.16 in Royden (1968)) and
thus it is differentiable almost everywhere (with respect to Lebesgue
measure) in the interior of its domain. Furthermore, every absolutely
continuous function is the integral of its derivative (Theorem 5.13 in
Royden (1968)) and so we have: 
\begin{equation}
V_i\left( 1\right) =V_i\left( 0\right) +\int_0^1V_i^{\prime }\left( r\right)
dr.  \label{vi}
\end{equation}

Now suppose $r\in \left( 0,1\right) $ is such that $V_i$ is differentiable
at $r.$ From (\ref{ic4}): 
\begin{eqnarray*}
V_i\left( r+\delta \right) -V_i\left( r\right) &=&U_i\left( \left( r+\delta
\right) t_i+\left( 1-r-\delta \right) s_i\right) -U_i\left( rt_i+\left(
1-r\right) s_i\right) \\
&\geq &Q_i\left( rt_i+\left( 1-r\right) s_i\right) \cdot \delta \left(
t_i-s_i\right) .
\end{eqnarray*}

If $\delta >0$ then we get: 
\[
\frac{V_i\left( r+\delta \right) -V_i\left( r\right) }\delta \geq Q_i\left(
rt_i+\left( 1-r\right) s_i\right) \cdot \left( t_i-s_i\right) 
\]
and taking the limit as $\delta \downarrow 0$ we obtain that $V_i^{\prime
}\left( r\right) \geq Q_i\left( rt_i+\left( 1-r\right) s_i\right) \cdot
\left( t_i-s_i\right) .$ On the other hand, if $\delta <0$ we get the
opposite inequality, and taking the limit as $\delta \uparrow 0$ we obtain
that $V_i^{\prime }\left( r\right) \leq Q_i\left( rt_i+\left( 1-r\right)
s_i\right) \cdot \left( t_i-s_i\right) .$ Thus if $V_i$ is differentiable at 
$r\in \left( 0,1\right) ,$ 
\[
V_i^{\prime }\left( r\right) =Q_i\left( rt_i+\left( 1-r\right) s_i\right)
\cdot \left( t_i-s_i\right) . 
\]

Now substituting in (\ref{vi}) we obtain that for all $t_i\in T_i$: 
\[
U_i\left( t_i\right) =U_i\left( t_i^{\prime }\right) +\int_0^1Q_i\left(
rt_i+\left( 1-r\right) t_i^{\prime }\right) \cdot \left( t_i-t_i^{\prime
}\right) dr 
\]
Thus at any point in $T_i,$ $U_i$ is determined by $Q_i$ up to an additive
constant. This completes the proof. 
%TCIMACRO{
%\TeXButton{End Proof}{\endproof%
%}}%
%BeginExpansion
\endproof%
%
%EndExpansion
\bigskip

If $U_i$ were differentiable everywhere then from (\ref{ic5}) we would have $%
\nabla U_i=Q_i$. In that case $U_i$ would be a \emph{potential} of the
vector field $Q_i$ and because the line integral of a function with a
potential is path independent (Apostol (1969)) we could write: 
\[
U_i\left( t_i\right) =U_i\left( 0\right) +\int Q_i\cdot d\alpha 
\]
for any piecewise smooth path $\alpha :\left[ 0,1\right] \rightarrow T_i$
such that $\alpha \left( 0\right) =0$ and $\alpha \left( 1\right) =t_i$. The
conclusion of Lemma \ref{main} would then be immediate.

But $U_i$\ need not be differentiable as the following simple example shows.

\subparagraph{Example 1:\textbf{\ }}

Suppose that there are only two agents $\left( I=2\right) $\ and $K=\left\{
1,2,3\right\} .$\ Let $T_{1}=\left[ 0,1\right] \times \left\{ 0\right\}
\times \left\{ 0\right\} $\ and $T_{2}=\left\{ 0\right\} \times \left[ 0,2%
\right] \times \left[ 0,2\right] $\ and let the types be uniformly
distributed on $T_{1}$\ and $T_{2}.$\ Consider an efficient allocation rule $%
\kappa ^{\ast }$, that is, for all $t,$\ $\kappa ^{\ast }\left( t\right) \in
\arg \max $\ $t_{1}\left( k\right) +t_{2}\left( k\right) $\ and suppose that
the payment functions are $\mu _{i}\left( t\right) =-t_{j}\left( \kappa
^{\ast }\left( t\right) \right) $\ where $j\neq i$. The mechanism $\left(
\kappa ^{\ast },\mu \right) $\ is incentive compatible (truth-telling is a
dominant strategy) but if $\min \left\{ t_{2}\left( 2\right) ,t_{2}\left(
3\right) \right\} >1,$\ $U_{2}\left( t_{2}\right) =\max \left\{ t_{2}\left(
2\right) ,t_{2}\left( 3\right) \right\} $\ and thus $U_{2}$\ is not
differentiable at any $t_{2}$\ such that $t_{2}\left( 2\right) =t_{2}\left(
3\right) >1.$

Also note that in the example above, the resulting $Q_{2}$ is discontinuous
at any $t_{2}$\ such that $t_{2}\left( 2\right) =t_{2}\left( 3\right) >1.$

We emphasize that Lemma \ref{main}, is derived without making any
assumptions about the differentiability of $U_i$ and thus applies even to
the example given above.

Finally, we point out that the assumption that the set of types $T_i$\ is
convex (and that $\limfunc{supp}f_i=T_i$) plays an important role in Lemma 
\ref{main}.

\subparagraph{Example 2:\textbf{\ }}

Suppose that there is an auction of a single object to two agents. Let the
types indicate the value that each agent assigns to the object and suppose
that $T_{1}=\left[ 0,3\right] $\ whereas $T_{2}=\left[ 0,1\right] \cup \left[
2,3\right] .$\ Let the types be uniformly distributed over $T_{1}$\ and $%
T_{2}.$\ First, consider the VCG mechanism $\left( \kappa ^{\ast },\mu
^{\ast }\right) $\ (which in this environment is the same as a second-price
auction). It may be verified that the associated expected payoff function
for agent $2$\ is: 
\[
U_{2}^{\ast }\left( t_{2}\right) =\frac{1}{6}t_{2}^{2}. 
\]
Second, consider a mechanism $\left( \kappa ^{\ast },\mu \right) $\ which is
the same as a second-price auction except that if agent $2$\ reports a type $%
t_{2}\in \left[ 2,3\right] ,$\ he pays an amount $\frac{1}{6}$\ (as an
``entry fee'') regardless of whether he wins the auction or not. The
mechanism $\left( \kappa ^{\ast },\mu \right) $\ is also incentive
compatible and individually rational (but note that truth-telling is not\ a
dominant strategy). The associated expected payoff function is: 
\[
U_{2}\left( t_{2}\right) =\left\{ 
\begin{array}{cc}
\frac{1}{6}t_{2}^{2} & \text{if }t_{2}\in \left[ 0,1\right] \\ 
\frac{1}{6}t_{2}^{2}-\frac{1}{6} & \text{if }t_{2}\in \left[ 2,3\right]
\end{array}
\right. 
\]
Now $U_{2}^{\ast }$\ and $U_{2}$\ differ by more than an additive constant.
Moreover, the expected payments in $\left( \kappa ^{\ast },\mu \right) $\
exceed\ the expected payments in the VCG mechanism $\left( \kappa ^{\ast
},\mu ^{\ast }\right) $.

Thus the conclusions of Lemma \ref{main} need not obtain if the sets $T_{i}$
are not convex.

\paragraph{Related work}

As mentioned above, the conclusion of Lemma \ref{main} is well known as the
``revenue equivalence theorem'' and was derived under very weak hypotheses
by Myerson (1981) in an environment where types are single dimensional.
(Remarkably, an early example of revenue equivalence can be found in
Vickery's (1961) classic paper.)

Note that Lemma \ref{main} is valid for \emph{any} allocation rule $\kappa $%
, not just for efficient allocation rules $\kappa ^{\ast }$. For efficient
rules, the result has been derived in a multi-dimensional setting by
d'Aspremont and G\'{e}rard-Varet (1979b) under stronger hypotheses that
involve the differentiability of the mechanism $\left( \kappa ^{\ast },\mu
\right) $. These hypotheses preclude the application of their results to
auctions.

Williams (1997) presents a generalization of d'Aspremont and G\'{e}%
rard-Varet's (1979b) equivalence result for efficient rules. In particular,
he does not require the mechanism to be differentiable. Instead, he directly
assumes that the payoff function $Q_{i}\left( s_{i}\right) \cdot
t_{i}-m_{i}\left( s_{i}\right) $ is differentiable in $s_{i}$ at $%
s_{i}=t_{i}.$ Example 2 above shows that even this rather weak assumption
need not be satisfied.\footnote{%
There are other, largely technical, differences between Williams' (1997)
framework and ours. His is more geared toward trading problems rather than
auctions and complements ours nicely.}

\begin{thebibliography}{99}
\bibitem{Apostol}  Apostol, T. M. (1969): \emph{Calculus}, Vol. II (2nd.
edition), New York: Wiley.

\bibitem{Armstong}  Armstrong, M. (1996): ``Multiproduct Nonlinear
Pricing,'' \emph{Econometrica}, 64, 51-77.

\bibitem{Arrow}  Arrow, K. J. (1979): ``The Property Rights Doctrine and
Demand Revelation under Incomplete Information,'' in \emph{Economics and
Human Welfare}, ed. by M. Boskin, New York: Academic Press, 23-39.

\bibitem{dGAV1}  d'Aspremont, C. and L. A. G\'{e}rard-Varet (1979a):
``Incentives and Incomplete Information,'' \emph{Journal of Public Economics}%
, 11, 25-45.

\bibitem{dAGV2}  d'Aspremont, C. and L. A. G\'{e}rard-Varet (1979b): ``On
Bayesian Incentive Compatible Mechanisms,'' in \emph{Aggregation and
Revelation of Preferences}, ed. by J.-J. Laffont, Amsterdam: North-Holland
Publishing Co., 269-288.

\bibitem{Ausubel}  Ausubel, L. (1995): ``An Efficient Ascending-Bid Auction
for Multiple Objects,'' mimeo, University of Maryland, College Park, MD.

\bibitem{AusCram}  Ausubel, L. and P. Cramton (1995): ``Demand Reduction and
Inefficiency in Multi-Unit Auctions,'' mimeo, University of Maryland,
College Park, MD.

\bibitem{Branco}  Branco, F. (1996): ``Multiple Unit Auctions of an
Indivisible Good,'' \emph{Economic Theory}, 8, 77-101.

\bibitem{Clarke}  Clarke, E. (1971): ``Multipart Pricing of Public Goods,'' 
\emph{Public Choice}, 2, 19-33.

\bibitem{GL}  Green, J. and J.-J. Laffont (1977): ``Characterization of
Satisfactory Mechanisms for the Revelation of Preferences for Public
Goods,'' \emph{Econometrica}, 45, 427-438.

\bibitem{Groves}  Groves, T. (1973): ``Incentives in Teams,'' \emph{%
Econometrica}, 41, 617-631.

\bibitem{Jeheil}  Jeheil, P., B. Moldovanu and E. Stacchetti (1996):
``Multidimensional Mechanism Design for Auctions with Externalities,''
mimeo, University of Mannheim, Mannheim.

\bibitem{Laff-Mas}  Laffont, J.-J. and E. Maskin (1979): ``A Differential
Approach to Expected Utility Maximizing Mechanisms,'' in \emph{Aggregation
and Revelation of Preferences}, ed. by J.-J. Laffont, Amsterdam:
North-Holland Publishing Co., 289-308.

\bibitem{Laff-Mas2}  Laffont, J.-J. and E. Maskin (1982): ``The Theory of
Incentives: An Overview,'' in \emph{Advances in Economic Theory}, ed. by W.
Hildenbrand, Cambridge: Cambridge University Press, 31-94.

\bibitem{Mai-Pos}  Mailath, G. and A. Postlewaite (1991): ``Asymmetric
Information Bargaining Problems with Many Agents,'' \emph{Review of Economic
Studies}, 57, 351-369

\bibitem{Mak-Mez}  Makowski, L. and C. Mezzetti (1994): ``Bayesian and
Weakly Robust First Best Mechanisms: Characterization,'' \emph{Journal of
Economic Theory}, 64, 500-519.

\bibitem{MWG}  Mas-Colell, A., M. Whinston and J. Green (1995): \emph{%
Microeconomic Theory}, Oxford: Oxford University Press.

\bibitem{Maskin}  Maskin, E. (1992): ``Auctions and Privatization,'' mimeo,
Harvard University, Cambridge, MA.

\bibitem{MR1}  Maskin, E. and J. Riley (1990): ``Optimal Multi-unit
Auctions,'' in \emph{The Economics of Missing Markets, Information and Games}%
, ed. by F. Hahn, Oxford: Oxford University Press, 312-335.

\bibitem{MaAfee}  McAfee, P. (1991): ``Efficient Allocation with Continuous
Quantities,'' \emph{Journal of Economic Theory}, 53, 51-74.

\bibitem{McMc}  McAfee, P. and J. McMillan (1988): ``Multidimensional
Incentive Compatibility and Mechanism Design,'' \emph{Journal of Economic
Theory}, 46, 335-354.

\bibitem{McMillan}  McMillan, J. (1994): ``Selling Spectrum Rights,'' \emph{%
Journal of Economic Perspectives}, 8, 145-162.

\bibitem{Milgrom}  Milgrom, P. (1997): \emph{Auction Theory for Privatization%
}, Cambridge: Cambridge University Press.

\bibitem{Mirrlees}  Mirrlees, J. (1971): ``An Exploration in the Theory of
Optimal Income Taxation,'' \emph{Review of Economic Studies}, 38, 175-208.

\bibitem{Mookherjee}  Mookherjee, D. and S. Reichelstein (1992): ``Dominant
Strategy Implementation of Bayesian Incentive Compatible Allocation Rules,'' 
\emph{Journal of Economic Theory}, 56, 378-399.

\bibitem{Myerson}  Myerson, R. (1981): ``Optimal Auction Design,'' \emph{%
Mathematics of Operations Research}, 6, 58-73.

\bibitem{MS}  Myerson, R. and M. Satterthwaite (1983): ``Efficient
Mechanisms for Bilateral Trading,'' \emph{Journal of Economic Theory}, 28,
265-281.

\bibitem{RS}  Riley, J. and W. Samuelson (1981): ``Optimal Auctions,'' \emph{%
American Economic Review}, 71, 381-392.

\bibitem{Rochet}  Rochet, J.-C. (1987): ``A Necessary and Sufficient
Condition for Rationalizability in a Quasi-linear Context,'' \emph{Journal
of Mathematical Economics}, 16, 191-200.

\bibitem{Rocka}  Rockafellar, T. (1970): \emph{Convex Analysis}, Princeton:
Princeton University Press.

\bibitem{Royden}  Royden, H. (1968): \emph{Real Analysis}, 2nd edition, New
York: Macmillan.

\bibitem{Vickrey}  Vickrey, W. (1961): ``Counterspeculation, Auctions and
Competitive Sealed Tenders,'' \emph{Journal of Finance}, 16, 8-37.

\bibitem{Williams}  Williams, S. (1997): ``A Characterization of Efficient
Bayesian Incentive Compatible Mechanisms,'' mimeo, University of Illinois,
Urbana-Champaign. (Revised. First version dated 1994).

\bibitem{Wilson1}  Wilson, R. (1979): ``Auctions of Shares,'' \emph{%
Quarterly Journal of Economics}, 94, 675-689.

\bibitem{Wilson3}  Wilson, R. (1993): \emph{Non-linear Pricing}, Oxford:
Oxford University Press.
\end{thebibliography}

\end{document}