A Constructive Proof of Border's Theorem for Optimal Multi-dimensional Mechanism Design
Yang Cai\thanks{Supported by NSF Award CCF-0953960 (CAREER) and CCF-1101491.}
EECS
MIT
Constantinos Daskalakis\thanks{Supported by a Sloan Foundation Fellowship and NSF Award CCF-0953960 (CAREER) and CCF-1101491.}
S. Matthew Weinberg\thanks{Supported by a NSF Graduate Research Fellowship and a NPSC Graduate Fellowship.}
We obtain a {\em characterization} of feasible, Bayesian, multi-item multi-bidder mechanisms with independent, {additive} bidders as {\em distributions over hierarchical mechanisms}. {Combined with cyclic-monotonicity our results provide a complete characterization of feasible, Bayesian Incentive Compatible mechanisms for this setting. } Our characterization is enabled by a novel, constructive proof of Border's theorem~\cite{border}, and a new generalization of this theorem to independent (but not necessarily identically distributed) bidders, improving upon the results of \cite{border2007,CKM}. For a single item and independent (but not necessarily identically distributed) bidders, we show that any feasible reduced form auction can be implemented as a distribution over hierarchical mechanisms. We also give a polynomial-time algorithm for determining feasibility of a reduced form auction, or providing a separation hyperplane from the set of feasible reduced forms. To complete the picture, we provide polynomial-time algorithms to find and exactly sample from a distribution over hierarchical mechanisms consistent with a given feasible reduced form. {All these results generalize to multi-item reduced form auctions for independent, additive bidders.} Finally, for multiple items, {additive bidders with hard demand constraints, and arbitrary value correlation across items or bidders,} we give a proper generalization of Border's Theorem, {and} characterize feasible reduced form auctions as multi-commodity flows in related multi-commodity flow instances. {We also show that our generalization holds for a broader class of feasibility constraints, including the intersection of any two matroids.} As a corollary of our results we obtain revenue-optimal, Bayesian Incentive Compatible (BIC) mechanisms in multi-item multi-bidder settings, when each bidder has arbitrarily correlated values over the items and additive valuations over bundles of items, and the bidders are independent. Our mechanisms run in time polynomial in the total number of bidder types (and {\em not} type profiles). This running time is polynomial in the number of bidders, but potentially exponential in the number of items. We improve the running time to polynomial in both the number of items and the number of bidders by using recent structural results on optimal BIC auctions in item-symmetric settings~\cite{DW}.
IID.tex
\section{Single Item, I.I.D. Bidders, {Bidder-Symmetric Reduced Forms}}\label{app: iid}
We provide the details and proofs of the techniques discussed in Section~\ref{sec:overview iid}, beginning with some technical lemmas.

%\begin{theorem}\label{thm: iidhierarchy} Every symmetric feasible reduced form auction for i.i.d. bidders and a single item can be implemented as a distribution over well-ordered hierarchical mechanisms.
%\end{theorem}

\begin{lemma}\label{lem: iidhierarchy} Every feasible bidder-symmetric reduced form auction $\pi$ for i.i.d. bidders and a single item can be implemented (not necessarily exactly implemented) as a distribution over well-ordered {w.r.t. $\pi$} hierarchical mechanisms.
\end{lemma}

\begin{proof} Our proof is by induction on the number of distinct non-zero values {in $\{\pi(A)\}_{A \in T}$.}

{\em Base Case:} There is a single non-zero value in this set, {equal to some $x \leq 1$}. The mechanism that gives the item {uniformly at random to a bidder whose reported type $A$ satisfies $\pi(A) = x$ (if such bidder shows up)} implements this reduced form as long as it is feasible.

{\em Inductive Hypothesis:} For all $0 < k < {\theta}$, every feasible reduced form with $k$ distinct non-zero values in {$\{\pi(A)\}_{A \in T}$} can be implemented as a distribution over well-ordered {w.r.t. $\pi$} hierarchical mechanisms.

{\em Inductive Step:} {We show that the inductive hypothesis extends to the case where there are exactly $\theta$ distinct non-zero values in $\{\pi(A)\}_{A \in T}$.} Let $X$ denote the {set} of all distributions over well-ordered w.r.t. $\pi$ hierarchical mechanisms. Then $X$ can be interpreted as a closed, bounded subset of {$\mathbb{R}^{2^{\theta}}$}, where each coordinate denotes the probability of using one of the {$2^{\theta}$} well-ordered w.r.t. $\pi$ hierarchical mechanisms. Therefore, $X$ is compact. {For a distribution over }hierarchical mechanisms $M \in X$, denote by $M(A)$ the probability that {a bidder reporting type $A$} receives the item under $M$. Define the function $F: X\rightarrow \mathbb{R}$ as:

$$F(M) = \max_{A} \{\pi(A) - M(A)\}.$$

{Let us use the Euclidean distance in $X$ as a subset of {$\mathbb{R}^{2^\theta}$}.} As {$X$} is a compact space, and $F$ is a continuous function, $F$ attains its minimum {in $X$}. Let $M$ denote one such minimizer of $F$. Then if $F(M) \leq 0$, $M$ implements the reduced form. If $F(M) > 0$, we will show a contradiction. Let $S$ denote the subset of types $\argmax_A \{\pi(A)-M(A)\}$, i.e. the subset of types who are the most unsatisfied by $M$.

We show first that, if $S$ contains every non-zero type, then the reduced form is infeasible. We may, w.l.o.g., assume that $M$ always awards the item to a non-zero type if one shows up, as this will not decrease $M(A)$ for any non-zero $A$. Therefore, we know that
$$\sum_{A:\pi(A)\neq 0} \Pr[A]M(A) = \Pr[\text{see a non-zero type}].$$
However, if $\pi(A) - M(A) > 0$ for all non-zero types, then we must have $\sum_{A:\pi(A)\neq 0} \Pr[A]\pi(A) > \Pr[\text{see a non-zero type}]$ and the reduced form is infeasible. So if the reduced form is feasible, $S$ must be missing at least one non-zero type. 

Now let $s = |\{\pi(A)\}_{A \in S}|$ be the number of distinct non-zero values assigned by $\pi$ to types in $S$. We argue that $s < \theta$. To see this, it suffices to observe the following:  for all types $B$ and $B'$, $\pi(B) = \pi(B')$ implies that $M(B) = M(B')$ (this is because, by definition, all hierarchical mechanisms $H$ in the support of $M$ satisfy $H(B) = H(B')$). So in particular either $B,B' \in S$ or $B,B' \notin S$, but it cannot be that one of $B,B'$ is in $S$ and the other is not. And because $S$ is missing at least one non-zero type, $s<\theta$.

To show a contradiction to $F(M)>0$, let us define a new reduced form $\pi'$ as follows. For all $A \in S$, set $\pi'(A) = \pi(A)$. For all $A \notin S$, set $\pi'(A) = \max_{B \in S | \pi(B) < \pi(A)}\{ \pi(B)\}$, {unless $\{B~|~B\in S \wedge \pi(B) < \pi(A)\}$ is empty} in which case we set $\pi'(A) = 0$. Observe that the number of distinct non-zero values in $\{\pi'(A)\}_{A \in T}$ is exactly  $s <\theta$. So it follows by our inductive hypothesis that $\pi'$ can be implemented by a distribution over well-ordered (with respect to $\pi'$) hierarchical mechanisms. In fact, as $\pi(A) \geq \pi(A') \Rightarrow \pi'(A) \geq \pi'(A')$, every hierarchical mechanism that is well-ordered with respect to $\pi'$ is also well-ordered with respect to $\pi$. Call $M'$ the distribution over well-ordered hierarchical mechanisms implementing $\pi'$. Now, set $\epsilon = (F(M)-\argmax_{A \notin S}\{\pi(A) - M(A)\})/2$, and consider the distribution $M'' = (1-\epsilon)M + \epsilon M'$ (with probability $(1-\epsilon)$ sample from $M$, with probability $\epsilon$ sample from $M'$).

What is $M''(A)$? If $A \in S$, then $M'(A) = \pi(A)$, so $M''(A) = (1-\epsilon)M(A) + \epsilon\pi(A)$. So for all $A \in S$, $M''(A) > M(A)$, hence $\pi(A) - M''(A) < F(M)$.

If $A \notin S$, then $M'(A) \geq 0$, so $M''(A) \geq (1-\epsilon)M(A)\geq M(A)-\epsilon$, so we get $\pi(A) - M''(A) \leq \pi(A)-M(A) + \epsilon < F(M)$. Putting both observations together, we see that $F(M'') < F(M)$, a contradiction. 

So we must have $F(M) \leq 0$, meaning $M$ implements the reduced form, completing the inductive step and the proof of the lemma.
\end{proof}

\begin{corollary}\label{cor: iidhierarchy} Every feasible bidder-symmetric  reduced form $\pi$ can be exactly implemented as a distribution over well-ordered w.r.t. $\pi$ hierarchical mechanisms.
\end{corollary}
\begin{proof} 
It follows from Lemma~\ref{lem: iidhierarchy} that $\pi$ can be implemented as a distribution over well-ordered w.r.t. $\pi$ hierarchical mechanisms.  Let then $X$ denote the set of distributions over well-ordered w.r.t. $\pi$ hierarchical mechanisms that implement ${\pi}$.  As in Lemma~\ref{lem: iidhierarchy} the set $X$, viewed as a subset of $\mathbb{R}^{2^\theta}$, {where $\theta$ is the number of distinct non-zero values in $\pi$, is compact.} We can also define the function $G: X \rightarrow \mathbb{R}$ as:

$$G(M) = \max_A \{M(A) - \pi(A)\}.$$
{Equipping $X$ with the Euclidean distance of {$\mathbb{R}^{2^\theta}$}, $G$ is a continuous function on $X$. As $X$ is compact and $G$ continuous, $G$ attains its minimum in $X$.} 

{We show that the minimum of $G$ is exactly $0$ (i.e. that a minimizer of $G$ exactly implements $\pi$), following an induction similar to the one used in Lemma~\ref{lem: iidhierarchy} in terms of the number of distinct non-zero values in $\{\pi(A)\}_{A \in T}$. We sketch the steps involved for the inductive step.} Take any minimizer $M$ of $G$. If $G(M) \leq 0$, then because $M$ has to implement $\pi$, $M$ must exactly implement $\pi$. If $G(M) > 0$, then let $S = T - \argmax_A \{M(A) - \pi(A)\}$.  Then, for all $A \in S$, define $\pi'(A) = \pi(A)$. For all  $A \notin S$, define $\pi'(A) = \max_{B \in S| \pi(B) \leq \pi(A)} \{\pi(B)\}$, unless $\{B: B\in S \wedge \pi(B) \le \pi(A)\}$ is empty, in which case set $\pi'(A)=0$. As $\argmax\{M(A) - \pi(A)\}$ can't possibly be empty {the number of distinct non-zero values in $\{ \pi'(A)\}_{A \in T}$ is smaller than that in $\{ \pi(A)\}_{A \in T}$. (We still use the observation that, for all types $B$ and $B'$, $\pi(B)=\pi(B')$ implies that $M(B)=M(B')$). The rest of the inductive step proceeds identically with that in the proof of Lemma \ref{lem: iidhierarchy}, resulting in a contradiction. Hence, it can't be that the minimizer of $G$ satisfies $G(M)>0$.}
\end{proof}

{To proceed we need a definition. Let $>:= A_1 > A_2 > \ldots > A_k$ be a total ordering of a set $T_k:=\{A_1,\ldots,A_k\}$ of $k$ types, and consider a setting where we have $m$ bidders whose types are distributed i.i.d. over $T_k$. We say that a bidder-symmetric reduced form $\pi: T_k \rightarrow [0,1]$ respects $>$ iff $\pi(A_1)\ge \pi(A_2) \ge \ldots  \ge \pi(A_k)$. We also say that an hierarchical mechanism $H$ on $T_k$ is well-ordered with respect to $>$ iff $H(A_1) \le H(A_2) \le \ldots \le H(A_k)$.~\footnote{
{Notice that this definition of well-ordered hierarchical mechanism (with respect to $>$) is very similar to its counterpart in the main body (with respect to $\pi$), but different. Being well-ordered with respect to $\pi$ certainly imposes the same constraints as being well ordered with respect to any $>$ that $\pi$ respects. The difference is that being well-ordered with respect to $\pi$ may also impose some equality constraints, if $\pi(A) = \pi(B)$ for types $A \neq B$.}} With respect to these definitions we show the following proposition. }

{\begin{proposition}\label{prop: iidcorners} Consider $m$ bidders whose types are distributed i.i.d. over $T_k :=\{A_1,\ldots,A_k\}$ and a total ordering $>:=A_1 > A_2 > \ldots >A_k$ of $T_k$. The set of feasible bidder-symmetric reduced forms that respect $>$ is a $k$-dimensional polytope whose corners are exactly the $2^k$ hierarchical mechanisms that are well-ordered with respect to $>$.
\end{proposition}}

\begin{proof} 
As a corollary of Theorem~\ref{thm:border}, a reduced form respects $>$ and is feasible if and only if 
\begin{align}
\pi(A_i) &\geq \pi(A_{i+1}) &\forall i \in [k]; \\
\sum_{j \leq i} m\cdot \Pr[A_j]\pi(A_j) &\leq 1 - \left(1-\sum_{j\leq i}\Pr[A_j]\right)^m &\forall i \in [k];
\end{align}
where for notational convenience we denote $\pi(A_{k+1}) = 0$. We have hence shown that the set of feasible bidder-symmetric reduced forms that respect $>$ is a $k$-dimensional polytope. 

We proceed to show that each well-ordered w.r.t. $>$ hierarchical mechanism is a corner. Let $H$ be such a mechanism and $\pi$ be the reduced form that it induces. Then, for all $i$ (including $i = k$, denoting  $H(A_{k+1}) = \lose$) we either have $H(A_i) = H(A_{i+1})$, in which case $\pi(A_i) = \pi(A_{i+1})$, or $H(A_i) < H(A_{i+1})$, in which case {$\sum_{j \leq i} m \cdot \Pr[A_j]\pi(A_j) = 1 - (1-\sum_{j\leq i}\Pr[A_j])^m$}, because the item is always awarded to one of the top $i$ types whenever one is present. Therefore, at least $k$ of the inequalities defining the polytope are tight. {And it is easy to see that there is a unique reduced form making these inequalities tight.} It is also clear that every well-ordered w.r.t. $>$ hierarchical mechanism is inside the polytope. So every well-ordered w.r.t. $>$ hierarchical mechanism is a corner of the polytope.

Finally, we show that there are no other corners. Assume for contradiction that there was a corner $\pi$ of the polytope that is not a well-ordered w.r.t. $>$ hierarchical mechanism. Then by Corollary~\ref{cor: iidhierarchy}, we know that $\pi$ can be written as a convex combination of {well-ordered w.r.t. $\pi$ hierarchical mechanisms, and hence as a convex combination of well-ordered w.r.t. $>$ hierarchical mechanisms. (As $\pi$ respects $>$ a hierarchical mechanism that is well-ordered w.r.t. $\pi$ will also be well-ordered w.r.t. $>$).} As every well-ordered w.r.t. $>$ hierarchical mechanism is a corner of the polytope, and $\pi$ is not one of them, this means that $\pi$ can be written as a convex combination of \emph{other} corners of the polytope, which contradicts that $\pi$ is itself a corner.

Therefore we have shown that every feasible bidder-symmetric reduced form respecting $>$ lies inside the afore-described polytope, every well-ordered w.r.t. $>$ hierarchical mechanism is a corner of this polytope, and there are no other corners. This establishes the proposition.
\end{proof}

Now we can put everything together to prove Theorems \ref{thm: iidhierarchy} and \ref{thm:grand theorem symmetric}.

\begin{prevproof}{Theorem}{thm: iidhierarchy}
{Suppose that the bidders' types are sampled i.i.d. from $T$ according to ${\cal D}_1$, and let $\pi$ be a feasible bidder-symmetric reduced form. We do the following preprocessing operation on the set of types $T$:

\bigskip \begin{minipage}{15cm}
{\sc TypeMerge}:  Find a maximal set of types $A_1,\ldots,A_{\ell} \in T$ such that $\pi(A_1)=\ldots=\pi(A_{\ell})$. Then remove types $A_1,\ldots,A_{\ell}$ from $T$ and add super-type $\langle A_1,\ldots,A_{\ell} \rangle$ into $T$; change ${\cal D}_1$ to never sample any of $A_1,\ldots,A_{\ell}$ and sample the super-type $\langle A_1,\ldots,A_{\ell} \rangle$ with probability $\sum_i \Pr[A_i]$; and set $\pi(\langle A_1,\ldots,A_{\ell}\rangle)=\pi(A_1)$. Repeat this procedure until every type in $T$ has different $\pi$ value, i.e. until the set $\{ \pi(A)\}_{A \in T}$ has cardinality $|T|$.
\end{minipage}

\bigskip Let $T'$, $\pi'$, ${\cal D}'_1$ be the type-set, reduced-form, type-distribution resulting from the {\sc TypeMerge} operation on input $\pi$. We claim that:
\begin{enumerate}
\item $\pi'$ is a feasible bidder-symmetric reduced form for bidders sampled i.i.d. from ${\cal D}'_1$. This follows immediately from the feasibility of $\pi$. Indeed it follows from Theorem~\ref{thm:border} and our discussion in Section~\ref{sec:overview iid} that a sufficient condition for the feasibility of $\pi'$ is for it to satisfy Eq.~\eqref{eq:border's condition} for all subsets of types of the form $\{A~|~A\in T' \wedge  \pi'(A) \ge x\}$. On the other hand the feasibility of $\pi$ implies that $\pi$ satisfies Eq.~\eqref{eq:border's condition} for all subsets of types of the form $\{A~|~A\in T \wedge  \pi(A) \ge x\}$. This together with the nature of our {\sc TypeMerge} operation implies that $\pi'$ satisfies the afore-mentioned sufficient conditions for feasibility.
\item A mechanism that exactly implements $\pi'$ immediately gives a mechanism exactly implementing $\pi$. Indeed, to implement $\pi$ we just run the mechanism implementing $\pi'$ after replacing in the reported type vector every type $A$ that was removed from $T$ by {\sc TypeMerge} by its corresponding super-type.

\item A hierarchical mechanism $H'$ that is well-ordered w.r.t. $\pi'$ can be {\em expanded} into a hierarchical mechanism $H$ that is well-ordered w.r.t. $\pi$. Indeed, if super-type $\langle A_1,\ldots,A_{\ell} \rangle$ replaced types $A_1,\ldots,A_{\ell}$ during the {\sc TypeMerge} operation we set $H(A_i):= H'(\langle A_1,\ldots,A_{\ell} \rangle)$, for all $i=1,\ldots,\ell$. On the other hand, if a type $A$ belongs in both $T$ and $T'$, we set $H(A):=H'(A)$. Moreover, if $\pi_{H'}$, $\pi_H$ are respectively the reduced forms induced by $H'$ and $H$, the following property is satisfied. If super-type $\langle A_1,\ldots,A_{\ell} \rangle$ replaced types $A_1,\ldots,A_{\ell}$ during the {\sc TypeMerge} operation, then $\pi_H(A_i):= \pi_{H'}(\langle A_1,\ldots,A_{\ell} \rangle)$, for all $i=1,\ldots,\ell$. On the other hand, if a type $A$ belongs in both $T$ and $T'$, then $\pi_H(A):=\pi_{H'}(A)$. \label{step:expansion}
\end{enumerate}

Now, suppose that the cardinality of $T'$ is $k$. Given that $\pi'$ assigns a distinct probability to every type in $T'$, it induces a total ordering on $T'$. In particular, suppose that $T':=\{A_1,\ldots,A_k\}$, where $\pi'(A_1) > \pi'(A_2)>\ldots>\pi'(A_k)$. By Proposition \ref{prop: iidcorners}, $\pi'$ lies inside a $k$-dimensional polytope  whose corners are exactly the $2^k$ hierarchical mechanisms that are well-ordered with respect to the order $>:=A_1>\ldots>A_k$. By Carath\'eodory's Theorem, every point in the polytope can be written as a convex combination of at most $k+1$ corners. As a convex combination of corners is exactly a distribution over well-ordered hierarchical mechanisms w.r.t. $>$, we get that $\pi'$ can be written as a distribution over hierarchical mechanisms that are well-ordered w.r.t. $>$, and hence also w.r.t. $\pi'$. Now we can expand all hierarchical mechanisms in the support of the distribution, according to the procedure described in Step~\ref{step:expansion} above, to obtain that $\pi$ can be written as a distribution over hierarchical mechanisms that are well-ordered w.r.t. $\pi$.}
\end{prevproof}

\begin{prevproof}{Theorem}{thm:grand theorem symmetric} It follows from our discussion in Section~\ref{sec:overview iid} that a bidder-symmetric reduced form $\tilde{\pi}$ is infeasible if and only if it violates Eq.~\eqref{eq:border's condition} for a subset of types of the form $\{A~|~A\in T \wedge  \tilde{\pi}(A) \ge x\}$. Since there are at most $c \equiv |T|$ such sets we can efficiently determine feasibility of a given reduced from $\tilde{\pi}$ or provide a hyperplane separating it from the set of feasible reduced forms. 

We now need to describe how to efficiently find a mechanism implementing a reduced form $\tilde{\pi}$ that is feasible. {In view of the {\sc TypeMerge} operation defined in the proof of Theorem~\ref{thm: iidhierarchy}, we can w.l.o.g. assume that $\tilde{\pi}$ assigns a distinct probability to every type in $T$. (Otherwise we can always run {\sc TypeMerge} to merge types sharing the same $\tilde{\pi}$-probability to super-types and apply the procedure outlined below to the output of the {\sc TypeMerge} operation, and then go back to the original $\tilde{\pi}$). Under the assumption that $\tilde{\pi}$ assigns distinct probabilities to all types in $T$,} Proposition~\ref{prop: iidcorners} implies that $\tilde{\pi}$ lies inside a $c$-dimensional polytope, $P$, whose corners are the well-ordered w.r.t. $\tilde{\pi}$ hierarchical mechanisms. Therefore we can directly apply Theorem~\ref{thm: polytope} of Appendix~\ref{app: polytope} to write $\tilde{\pi}$ as a convex combination of such hierarchical mechanisms, as long as we can describe the boundary oracle $BO$, corner oracle $CO$ and separation oracle $SO$ that are needed for Theorem~\ref{thm: polytope}. $BO$ is trivial to implement, {as we just have to include in the set of halfspaces defining the boundary of $P$ those inequalities described in the proof of Proposition~\ref{prop: iidcorners}.} For $CO$, on input $B$, we first check that every hyperplane $h \in B$ satisfies $BO(h) = \text{yes}$. If not, output no. Otherwise we need to check if $\bigcap_{h \in B} h$ contains a corner of $P$. We know that the corners of $P$ are exactly the well-ordered w.r.t. $\tilde{\pi}$ hierarchical mechanisms.  So none of the corners lies in the intersection of the hyperplanes $\pi(A_i) = \pi(A_{i+1})$ and $\sum_{j \leq i} m \cdot \Pr[A_j] \pi(A_j) = 1 - (1-\sum_{j \leq i} \Pr[A_j])^m$, for any $i$. ({Indeed, for a hierarchical mechanism $H$ and its induced reduced form $\pi$,} $\pi(A_i) = \pi(A_{i+1})$ implies that $H(A_i) = H(A_{i+1})$, yet $\sum_{j \leq i} m \cdot \Pr[A_j] \pi(A_j) = 1 - (1-\sum_{j \leq i} \Pr[A_j])^m$ implies $H(A_i) > H(A_{i+1})$). So, if $B$ contains any pair of  hyperplanes of this form, output no. Otherwise, for all $i$ such that $\pi(A_i)=\pi(A_{i+1}) \in B$, set $H(A_i) = H(A_{i+1})$, otherwise set $H(A_i) = H(A_{i+1})-1$. This defines a well-ordered w.r.t. $\tilde{\pi}$ hierarchical mechanism that is in $\bigcap_{h \in B} h$, so have $CO$ output $H$. Finally, $SO$ is easy to implement as we can just check each of the $2 \cdot c$ inequalities written in the proof of Proposition~\ref{prop: iidcorners} one by one.

So because we can implement $BO, CO, SO$ in polynomial time, we can apply Theorem \ref{thm: polytope} to write $\tilde{\pi}$ as a convex combination of at most $c+1$ corners, which is exactly a distribution over at most $c+1$ well-ordered w.r.t. $\tilde{\pi}$ hierarchical mechanisms in polynomial time.
\end{prevproof}


bibliography.tex
\begin{thebibliography}{1}

\bibitem{alaei} S.~Alaei. Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers. {\em Proceedings of FOCS} 2010.

\bibitem{AFHHM} S.~Alaei, H.~Fu, N.~Haghpanah, J.~Hartline, A.~Malekian. { Personal Communication} 2011.

%\bibitem{AFHHM} S.~Alaei, H.~Fu, N.~Haghpanah, J.~Hartline, A.~Malekian. Optimal Mechanism Design via Reduced Form Auctions. {\em arXiv Report} 2011.

\bibitem{BH} X. Bei, Z. Huang. Bayesian Incentive Compatibility via Fractional Assignments. {\em Proceedings of SODA} 2011.          

\bibitem{BGGM} S.~Bhattacharya, G.~Goel, S.~Gollapudi and K.~Munagala. Budget Constrained Auctions with Heterogeneous Items. {\em Proceedings of STOC} 2010.

\bibitem{border} K.~C.~Border. Implementation of Reduced Form Auctions: A Geometric Approach. {\em Econometrica,} 59(4): 1175--1187, 1991.

\bibitem{border2007}  K.~C.~Border. Reduced form Auctions Revisited. {\em Economic Theory}, 31:167--181, 2007.
%    \bibitem{BCKW} P.~Briest, S.~Chawla, R.~Kleinberg and S.~M.~Weinberg. Pricing Randomized Allocations. {\em Proceedings of SODA} 2010.

%    \bibitem{BK} P.~Briest and P.~Krysta. Buying Cheap is Expensive: Hardness of Non-Parametric Multi-Product Pricing. {\em Proceedings of SODA} 2007.

\bibitem{CD} Y.~Cai and C. Daskalakis. Extreme-Value Theorems for Optimal Multidimensional Pricing. {\em Proceedings of FOCS} 2011.

\bibitem{CH} Y.~Cai and Z.~Huang. Simple and Nearly Optimal Multi-Item Auction. {\em Manuscript}, 2011.

\bibitem{CHK} S.~Chawla, J.~D.~Hartline and R.~D.~Kleinberg. Algorithmic Pricing via Virtual Valuations. {\em Proceedings of EC} 2007.

\bibitem{CHMS} S.~Chawla, J.~D.~Hartline, D.~Malec and B.~Sivan. Multi-Parameter Mechanism Design and Sequential Posted Pricing. {\em Proceedings of STOC} 2010.


\bibitem{CMS} S.~Chawla, D.~Malec and B.~Sivan. The Power of Randomness in Bayesian Optimal Mechanism Design. {\em Proceedings of EC} 2010.

\bibitem{CKM} Y.~Che, J.~Kim and K.~Mierendorff. Generalized Reduced-Form Auctions: A Network-Flow Approach. {\em University of Z\"urich, ECON-Working Papers,}  2011.
%\\ {\tt http://www.econ.uzh.ch/static/workingpapers.php}.

\bibitem{clarke} E.~Clarke. Multipart Pricing of Public Goods. {\em Public Choice,}  18:19--33, 1971. 


\bibitem{DW} C.~Daskalakis and S.~M.~Weinberg. On Optimal Multi-Dimensional Mechanism Design. {\em arXiv Report,} 2011.
 
 \bibitem{DFK} S.~Dobzinski, H.~Fu and R.~D.~Kleinberg. Optimal Auctions with Correlated Bidders are Easy. {\em Proceedings of STOC} 2011.
 
  
    %\bibitem{DR} S.~Dughmi and T.~Roughgarden. Black-Box Randomized Reductions in Algorithmic Mechanism Design. {\em FOCS} 2010.

\bibitem{groves} T.~Groves. Incentives in Teams. {\em Econometrica,}  41:617--631, 1973.

%    \bibitem{Hart} J.~D.~Hartline. Approximation in Mechanism Design. {\tt econ-www.mit.edu/files/6135}.
%
 \bibitem{HKM} J. Hartline, R. Kleinberg, A. Malekian. Multi-Parameter Bayesian Algorithmic Mechanism Design. {\em Proceedings of SODA} 2011.

\bibitem{HL} J.~D.~Hartline and B.~Lucier. Bayesian Algorithmic Mechanism Design. {\em Proceedings of STOC} 2010.

%    \bibitem{HR} J.~Hartline and T.~Roughgarden. Optimal mechanism design and money burning. {\em Proceedings of STOC}, 2008.

%    \bibitem{bundles} A.~M.~Manelli and D.~R.~Vincent. Bundling as an Optimal Selling Mechanism for a Multiple-Good Monopolist. {\em Journal of Economic Theory,} 127(1):1--35, 2006.

\bibitem{optimal:econ}  A.~M.~Manelli and D.~R.~Vincent. Multidimensional Mechanism Design: Revenue Maximization and the Multiple-Good Monopoly. {\em Journal of Economic Theory,} 137(1):153--185, 2007.  

\bibitem{maskinriley} E. Maskin and J. Riley. Optimal Auctions with Risk Averse Buyers. {\em Econometrica,} 52(6): 1473--1518, 1984.

\bibitem{matthews} S.~A.~Matthews. On the Implementability of Reduced Form Auctions. {\em Econometrica,} 52(6):1519--1522, 1984.

\bibitem{myerson} R.~B.~Myerson. Optimal Auction Design. {\em Mathematics of Operations Research,} 1981.

%    \bibitem{N} J.~Nash.
%    \newblock Noncooperative Games.
%    \newblock {\em Annals of Mathematics}, 54:289--295, 1951.

\bibitem{AGTbook} N.~Nisan, T.~Roughgarden, E.~Tardos and V.~V.~Vazirani (eds.). {\em Algorithmic Game Theory}. Cambridge University Press, 2007.

    %\bibitem{PV} M.~Pai and R.~Vohra. Optimal auctions with financially constrained bidders. {\em Working Paper,} 2008.

%    \bibitem{Than} J.~Thanassoulis. Haggling over substitutes. {\em Journal of Economic Theory,} 117(2):217�245, 2004.

\bibitem{Schrijver03} A.~Schrijver. \emph{Combinatorial Optimization - Polyhedra and Efficiency}. Springer, 2003.

\bibitem{vickrey} W.~Vickrey. Counterspeculations, Auctions, and Competitive Sealed Tenders. {\em J. Finance,}  16:15--27, 1961. 

%    \bibitem{Wil} R.~B.~Wilson. {\em Nonlinear Pricing.} Oxford University Press, 1997.



\end{thebibliography}
borderExtension.tex
\section{Generalization of Border's Theorem: Non-Negative Linear Feasibility Constraints} \label{app:generalization of Border}
We provide details from Section~\ref{sec: generalized border} and prove Theorem~\ref{thm: general}. Throughout the section, we let $P$ denote a type-profile, $\Pr[P]$  the probability of seeing profile $P$, and $P_i$  the type of bidder $i$ in $P$. \\


\begin{prevproof}{Theorem}{thm: general} It is clear that this is a necessary condition for a reduced form to be feasible. Indeed, if $M$ implements the reduced form, then we have:
$$\pi_{ij}(A)\Pr[t_i = A] \leq M_{ij}(A)\Pr[t_i = A]\ \forall\ i,j,A \in T_i;$$
and therefore for any weights $W_{ij}(A)$:
\begin{align*}
\sum_{i,j} \sum_{A \in T_i} W_{ij}(A)\pi_{ij}(A)\Pr[t_i = A] &\leq \sum_{i,j} \sum_{A \in T_i} W_{ij}(A)M_{ij}(A)\Pr[t_i = A]\\
&\leq  \sum_P \Pr[P]\cdot \max_{\vec{\phi}(P) \in F}\left\{\sum_i \sum_j W_{ij}(P_i) \cdot \phi_{ij}(P)\right\},
\end{align*}
\noindent where the last inequality comes from observing that $M$ defines a feasible mechanism, and therefore for every profile provides a valid choice of $\vec{\phi}(P) \in F$ for the maximization.

Now, we argue that if the reduced form is infeasible, we can find {\em constricting weights}, {i.e. weights making the inequality in the statement of the theorem fail}. For any mechanism $M$, define the value of $M$, $V(M)$ as follows:

$$V(M) = \sum_i \sum_j \sum_{A \in T_i} \min \{M_{ij}(A)\Pr[t_i = A], \pi_{ij}(A)\Pr[t_i = A]\}.$$ 

We can now say that $M$ implements the reduced form if and only if:

$$V(M) = \sum_i \sum_j \sum_{A \in T_i} \pi_{ij}(A)\Pr[t_i = A].$$

By our assumption on the feasibility constraints, there exist some set of linear constraints $H$, with all $c_{ij}(h) \geq 0$ {and $d(h)\ge 0$, for all $h\in H$,} such that a mechanism is feasible if and only if its induced $\{\phi(P)\}_P$ satisfies the following for all profiles $P$:

$$\vec{\phi}(P) \cdot \vec{c}(h) \leq d(h)\ \forall h \in H ~~\wedge~~ \vec{\phi}(P)\ge \vec{0}.$$

Therefore, the mechanism $M$ maximizing $V(M)$ is a solution to the following LP:
\\
\noindent \textbf{Primal LP 1}\\
\noindent \textbf{Variables:}
\begin{itemize}
\item $\phi_{ij}(P)$, for all bidders $i$, items $j$ and profiles $P$.
\end{itemize}
\textbf{Constraints:}
\begin{itemize}
\item $\vec{\phi}(P) \cdot \vec{c}(h) \leq d(h)$ for all $P,h \in H$. Rewritten as: $$\Pr[P] \cdot \vec{\phi}(P) \cdot \vec{c}(h) \leq \Pr[P] \cdot d(h).$$
{\item $\phi_{ij}(P)\geq 0$, for all $i,j, P$.}
\item $\sum_{P | P_i = A} \phi_{ij}(P)\cdot \Pr[P] \leq \pi_{ij}(A)\cdot \Pr[t_i = A]$, for all $i,j,A \in T_i$.
\end{itemize}
\textbf{Maximizing:}
\begin{itemize}
\item $\sum_{i,j,P} \phi_{ij}(P)\cdot \Pr[P]$.
\end{itemize}

\medskip In other words, for any feasible mechanism $M$, Primal LP 1 modifies $M$ to {sometimes} throw away an item rather than have $M_{ij}(A) > \pi_{ij}(A)$, then counts the expected number of items that $M$ awards. Primal LP 1 maximizes the expected number of items awarded by a feasible mechanism subject to these constraints. Consider now the dual to this LP:

\medskip \noindent \textbf{Dual LP 1}\\
\noindent \textbf{Variables:}
\begin{itemize}
\item $x_h(P)$, for all $h \in H$, and profiles $P$.
\item $y_{ij}(A)$, for all $i,j$ and $A \in T_i$.
\end{itemize}
\textbf{Constraints:}
\begin{itemize}
\item $\sum_{h \in H}\Pr[P] \cdot c_{ij}(h) \cdot x_h(P) + \Pr[P] \cdot y_{ij}(P_i) \geq \Pr[P]$, for all $i,j,P$. Rewritten as: $$\sum_{h \in H} c_{ij}(h) \cdot x_h(P) + y_{ij}(P_i) \geq 1.$$
{\item $x_h(P)\geq 0$, for all $P, h\in H$.
\item $y_{ij}(A)\geq 0$, for all $i,j$ and $A \in T_i$.}
\end{itemize}
\textbf{Minimizing:}
\begin{itemize}
\item $\sum_{i,j} \sum_{A \in T_i} y_{ij}(A) \pi_{ij}(A) \Pr[t_i = A] + \sum_P \Pr[P] \cdot \sum_{h \in H} d(h) \cdot x_h(P)$.
\end{itemize}



\medskip {By setting all $\phi_{ij}(P)$ to 0, we know Primal LP 1 is feasible. Also, Dual LP 1 is feasible, as we can set all $x_{h}(P)$ to $0$ and $y_{ij}(A)$ to 1. Hence, by strong LP duality, we know the values of the two LPs are the same, so the value of Dual LP 1 is strictly smaller than $\sum_{i,j} \sum_{A \in T_i} \pi_{ij}(A)\Pr[t_i = A]$ if and only if the reduced form is infeasible. Now let us consider Dual LP 1 and try to find the constricting weights.} 

Observe first, that there is always an optimal solution to Dual LP 1 with $y_{ij}(A) \leq 1$ for all $i,j,A$. This is because each $y_{ij}(A)$ has a non-negative coefficient in the objective function, each $c_{ij}(h) \geq 0$, and each $x_h(P) \geq 0$. So decreasing $y_{ij}(A)$ from above $1$ to $1$ does not violate any feasibility constraints, or increase the value of the objective function.

Next, we claim that in Dual LP 1 the optimal feasible choice of $x_h(P)$ to minimize the objective function depends only on the values $y_{ij}(P_i)$ and $x_{h'}(P)$ for other $h' \in H$, \emph{but not on $x_{h'}(P')$ for any other profile $P'$}. This is easy to see, as there are no inequalities with non-zero coefficients for both $x_{h}(P)$ and $x_{h'}(P')$ for any inequalities $h,h'$ and profiles $P \neq P'$. Therefore, if we are given a choice of $y_{ij}(A)$ for all $i,j,A$, we can find the optimal choices of $x_h(P)$ for all $h,P$ \emph{independently for each profile $P$} (but still considering all $h \in H$ at once). In particular, once the $y_{ij}(A)$s are fixed, the optimal choice of $x_h(P)$ for a fixed profile $P$ is just a solution to the following LP:

\medskip \noindent \textbf{Primal LP 2}\\
\textbf{Variables:}
\begin{itemize} 
\item $x_h(P)$ for all $h \in H$ {($P$ is fixed for the purposes of this LP)}.
\end{itemize}
\textbf{Constraints:}
\begin{itemize}
\item $\sum_{h \in H} c_{ij}(h) \cdot x_h(P) \geq 1 - y_{ij}(P_i)$, for all $i,j$.
{\item $x_{h}(P)\geq 0$ for all $h\in H$.}
\end{itemize}
\textbf{Minimizing:}
\begin{itemize}
\item $\Pr[P] \cdot \sum_{h \in H} d(h) \cdot x_h(P)$.
\end{itemize}

We can now take the dual of Primal LP 2, for a fixed profile $P$:

\smallskip \noindent \textbf{Dual LP 2}\\
\textbf{Variables:}
\begin{itemize} 
\item $\gamma_{ij}(P)$, for all $i,j$.
\item $\phi_{ij}(P)$, for all $i,j$. Extra variables satisfying $\Pr[P] \cdot \phi_{ij}(P) = \gamma_{ij}(P)$, used for convenience.
\end{itemize}
\textbf{Constraints:}
\begin{itemize}
\item $\sum_{i,j} \gamma_{ij}(P)\cdot c_{ij}(h) \leq \Pr[P] \cdot d(h)$. Replacing $\gamma_{ij}(P)$ with $\Pr[P]\cdot \phi_{ij}(P)$ yields: $$\vec{\phi}(P) \cdot \vec{c}(h) \leq d(h).$$
{\item $\Pr[P] \cdot \phi_{ij}(P) = \gamma_{ij}(P)$ for all $i,j$.
\item $\phi_{ij}(P)\geq 0$ for all $i,j$.}
\end{itemize}
\textbf{Maximizing:}
\begin{itemize}
\item $\sum_{i,j} \gamma_{ij}(P) \cdot (1-y_{ij}(P_i))$. Replacing $\gamma_{ij}(P)$ with $\Pr[P] \cdot \phi_{ij}(P)$ yields: $$\Pr[P] \cdot \sum_{i,j} \phi_{ij}(P) \cdot (1-y_{ij}(P_i)).$$
\end{itemize}

We now make our key observation. For a fixed profile $P$, and for a fixed choice of $y_{ij}(A)$ for all {$i,j,A$}, Dual LP 2 is \emph{exactly} trying to maximize the weighted sum $\sum_{i,j} (1-y_{ij}(P_i)) \cdot \phi_{ij}(P)$, subject to the same constraints guaranteeing that $\vec{\phi}(P) \in F$. By the strong LP duality (it is again easy to verify that both Primal LP 2 and Dual LP 2 are feasible), we know that the value of this maximum weighted feasible allocation is exactly the value attained by the optimal solution to Primal LP 2. Therefore, we may now claim that, for any choice of $y_{ij}(A)$s in Dual LP 1, the minimum value of Dual LP 1 subject to this choice is exactly:

$$\sum_{i,j} \sum_{A \in T_i} y_{ij}(A) \cdot \pi_{ij}(A) \cdot \Pr[t_i = A] + \sum_P \Pr[P] \cdot \max_{\vec{\phi}(P) \in F} \sum_{i,j} (1-y_{ij}(P_i))\cdot \phi_{ij}(P_i).$$

Finally, as the reduced form is infeasible, there is some {optimal solution $\{x^{*}_{h}(P), y^{*}_{ij}(A)\}$ to Dual LP 1 with all $y^{*}_{ij}(A) \in [0,1]$ whose value is strictly less than $\sum_{i,j} \sum_{A \in T_i} \pi_{ij}(A) \cdot \Pr[t_i = A]$. Therefore, if we take this choice of $y^{*}_{ij}(A)$ and set $W_{ij}(A) = 1-y^{*}_{ij}(A)$ we obtain:

\begin{align*}
&\sum_{i,j} \sum_{A \in T_i} y^{*}_{ij}(A) \cdot \pi_{ij}(A) \cdot \Pr[t_i = A] + \sum_P \Pr[P] \cdot \max_{\vec{\phi}(P) \in F}\sum_{i,j} (1-y^{*}_{ij}(P_i)) \cdot \phi_{ij}(P_i) \\
=&\sum_{i,j} \sum_{A \in T_i} y^{*}_{ij}(A) \pi_{ij}(A) \Pr[t_i = A] + \sum_P \Pr[P] \cdot \sum_{h \in H} d(h) \cdot x^{*}_{h}(P)\\
<& \sum_{i,j} \sum_{A \in T_i} \pi_{ij}(A) \cdot \Pr[t_i = A].
\end{align*}
}
By subtracting {$\sum_{i,j} \sum_{A \in T_i} y^{*}_{ij}(A) \cdot \pi_{ij}(A) \cdot \Pr[t_i = A]$} from both sides, we obtain a proof of the theorem:

$$\sum_P \Pr[P] \cdot \max_{\vec{\phi}(P) \in F} \sum_{i,j} W_{ij}(P_i) \cdot \phi_{ij}(P_i) < \sum_{i,j} \sum_{A \in T_i} W_{ij}(A) \cdot \pi_{ij}(A) \cdot \Pr[t_i = A].$$
\end{prevproof}

\subsection{A Special Case: Many Items, Demand Constraints, Correlated Bidders}

{Recall the definition of our multi-commodity flow instance outlined in Section~\ref{sec: demandConstraints}. Let us make it more precise:}

\smallskip \noindent \textbf{Nodes:}
\begin{itemize}
\item $S(j)$, for all items $j$, these are sources.
\item $I(P)$, for all possible profiles.
\item $T(i,A)$ for all $i$ and $A \in T_{i}$, these are sinks.
\end{itemize}
\textbf{Edges:}
\begin{itemize}
\item From $S(j)$ to $I(P)$ of capacity $\Pr[P]$, for all items $j$ and profiles $P$.
\item From $I(P)$ to $T(i,P_i)$ of capacity $C_{i}\Pr[P]$, where $C_{i}$ is bidder $i$'s demand, for all bidders $i$ and profiles $P$. 
\end{itemize}
\textbf{Commodities:}
\begin{itemize}
\item $G_{ij}(A)$ for all bidders $i$, items $j$ and all types $A \in T_{i}$ with a demand of $\Pr[t_i = A]\pi_{ij}(A)$.
\end{itemize}

\medskip \noindent {We observe that the feasibility of the above multi-commodity flow instance is equivalent to the feasibility of the reduced form $\pi$.}

\begin{proposition} The above multi-commodity flow problem has a feasible solution satisfying every demand if and only if the reduced form $\vec{\pi}$ is feasible.
\end{proposition}

\begin{proof} Say the reduced form is feasible. Then there exist variables $\phi_{ij}(P)$ such that:
\begin{enumerate}
\item $\sum_j \phi_{ij}(P) \leq C_i$, for all $i,P$.
\item $\sum_i \phi_{ij}(P) \leq 1$, for all $j,P$.
\item {$\sum_{P | P_i = A} \phi_{ij}(P)\cdot \Pr[P] = \pi_{ij}(A)\cdot \Pr[t_i = A]$}, for all $i,j,A$.
\end{enumerate}
So along the edges from $S(j)$ to $I(P)$ and $I(P)$ to $T(i,P_i)$, we will send {$Pr[P]\cdot \phi_{ij}(P)$} of commodity $G_{ij}(P_i)$. It is clear that by the conditions on the $\phi$s that all of the edge capacities are respected, {and that the total amount of commodity $G_{ij}(A)$ received by node $T(i,A)$ is exactly $\pi_{ij}(A)\cdot \Pr[t_i = A]$, i.e. matching its demand.}

Taking the inverse of this procedure {(by interpreting as $\Pr[P]\cdot \phi_{ij}(P)$ the amount of commodity $G_{ij}(A)$ that is sent through the edge $(S(j),I(P)$)} shows how to take any feasible flow satisfying every demand {and capacity constraint} and turn it into a set of $\phi$s that implement the reduced form {(by just reading out the $\phi_{ij}(P)$'s from the edges of the flow network, using the afore-mentioned interpretation)}.
\end{proof}

\subsection{False Extensions}

A short discussion is warranted on why this is the right extension of Border's Theorem. There are stronger, more natural extensions that one might hope to be true. For instance, below are two natural extensions that are \textbf{not} true, \emph{even in the special case that the feasibility constraints are only demand constraints}.
\begin{enumerate} 
\item \textbf{False Extension 1.} If the demand constraints are met for every type in expectation, and it is feasible to allocate each item individually, then the reduced form is feasible. Formally,
\begin{align*}
\sum_j \pi_{ij}(A) &\leq C_i\ \forall i,A \in T_i\\
\sum_i \sum_{A \in S_i} \pi_{ij}(A) &\leq 1-\prod_i(1-Pr[t_i \in S_i])\ \forall j, \forall i, S_i \subseteq T_i
\end{align*}
\item \textbf{False Extension 2.} Theorem \ref{thm: general} holds when we only consider $\{W_{ij}(A)\}$ such that $W_{ij}(A) = W_{ij'}(A)$ for all bidders $i$, items $j,j'$, and $A \in T_i$. I.E. the weights for a type of bidder $i$ does not depend on the item. 
\end{enumerate}

\begin{proposition} Both False Extensions are indeed false, even when all bidders are i.i.d. and when the feasibility constraints are just demand constraints.
\end{proposition}
\begin{proof} First, consider the case with three unit-demand i.i.d. bidders and two items. {Every bidder has two possible types $A,B$, and $\Pr[A] = \epsilon$, $\Pr[B] = 1-\epsilon$. We use $\pi_{j}(t)$ to denote the probability that a bidder with type $t$ receives item $j$.} Let $\pi_1(A) = \pi_2(A) = 1/2$. $\pi_1(B) = \pi_2(B) = 0$. Then clearly the hypotheses of False Extension 1 are met. No type receives more than one item in expectation, and it is feasible to allocate each item individually. However, as each bidder is unit-demand, and type $A$ wants exactly one item in expectation, $A$ must always leave with an item every time they show up to the auction to possibly satisfy the $\pi$s. Clearly this is not possible, as  it is possible for all three $A$'s to show up at once, but there are only two items. So we cannot possibly give $A$ an item every time they show up. Therefore, False Extension 1 is indeed false.

To get a counterexample to the second false extension, modify the above example by adding a third item, with $\pi_3(A) = \pi_3(B) = 0$. {Once we have $W_i(A) = W_{i1}(A) = W_{i2}(A) = W_{i3}(A)$ for all $i$, the LHS of the constricting-weights inequality in the statement of Theorem~\ref{thm: general} becomes:
$$\sum_{i,j}\sum_{t\in T_{i}} W_{i}(t)\pi_{j}(t) \Pr[t_{i}=t]=\epsilon(W_1(A)+W_2(A) + W_3(A)).$$
This is because $\pi_{ij}(B) = 0$ for all $i,j$, and $Pr[t_i = A] = \epsilon$ for all $i$. 

Now consider setting $\phi_{ii}(P) = 1$ for all $P$, and $\phi_{ij}(P) = 0$ for all $P$ and $i \neq j$. For any choice of weights $W_i(A), W_i(B)$, the RHS of the inequality (the expected weights induced by the $\phi$s) will be:

$$\epsilon(W_1(A) + W_2(A) + W_3(A)) + (1-\epsilon)(W_1(B) + W_2(B) + W_3(B)).$$ 

This is because we always give exactly one item to each bidder. When the type of bidder $i$ is $A$, we get weight $W_i(A)$, when it is $B$ we get weight $W_i(B)$. Because $t_i = A$ with probability $\epsilon$, we get the above calculation. 

Obviously, for any choice of weights, the following holds.
$$\epsilon(W_1(A) + W_2(A) + W_3(A)) + (1-\epsilon)(W_1(B) + W_2(B) + W_3(B))\geq \epsilon(W_1(A)+W_2(A) + W_3(A)).$$
Then if we choose the $\phi$s in a way that it maximizes the expected weights, LHS will still be less than RHS. This shows that there are no constricting weights satisfying $W_{ij}(A) = W_{ij'}(A)$ for all $i,j,j'$. However, we still know that this reduced form is infeasible. The key is that we need to let $W_{i3}(A) = 0$ in order to find constricting weights, without having $W_{i1}$ and $W_{i2} = 0$. So we need different weights for different items.}
\end{proof}
independent.tex
\section{Single Item, Independent Bidders}\label{app:independent}
Here we provide the details of Section~\ref{sec:overview independent}, and the proofs of Theorems \ref{thm: independent}, \ref{thm: independenthierarchy} and \ref{thm:grand theorem independent}, postponing the proof of Theorem~\ref{thm:non-iidhierarchical} to Appendix~\ref{app:hierarchical non iid}. Before proving our theorems, we show that the concept of virtual $\pi$s is necessary. As in, Theorem \ref{thm: independent} would be false if we tried to replace $\hat{\pi}$ with $\pi$. 

\begin{proposition}\label{prop:needvirtual} There exist reduced forms that are infeasible, yet for all $S^i_x$ of the form $S^i_x = \{A\ |\ \pi_{i}(A) > x,\ \forall i\}$:

$$\sum_i \sum_{A \in S^i_x} \pi_{i}(A)\Pr[t_i = A] \leq 1-\prod_{i=1}^m(1-\sum_{A \in S^i_x}\Pr[t_i = A]).$$
\end{proposition}

\begin{proof} Consider the case with two bidders. Bidder $1$ has two types, with $\Pr[t_1 = A] = 1/8$, $\Pr[t_1 = B] = 7/8$, $\pi_{1}(A) = 5/8$, $\pi_{1}(B) = 0$. Bidder $2$ has two types, with $\Pr[t_2 = C] = 1/2$, $\Pr[t_2 = D] = 1/2$, $\pi_{2}(C) = 1$, $\pi_{2}(D) = 3/4$. 

Then this reduced form is infeasible. Indeed, observe that $C$ must always receive the item whenever $t_2 = C$, which happens with probability $1/2$. So if se have $\pi_{2}(C) = 1$, we cannot also have $\pi_{1}(A) > 1/2$. So the set $\{A,C\}$ forms a constricting set. However, the sets of the form $S^i_x$ are $\{C\},\{C,D\},\{C,D,A\},\{C,D,A,B\}$, and they all satisfy the above inequality. \end{proof}

Proposition \ref{prop:needvirtual} shows us that ordering the types of all bidders by decreasing $\pi$ doesn't allow us to correctly determine the feasibility of a reduced form. Similarly, a partial ordering of the types that only orders a single bidder's types by decreasing $\pi$ doesn't give enough structure to efficiently determine the feasibility of the reduced form. What we need is a correct total ordering of the types of all bidders, and we can obtain it using virtual $\pi$s. Here is a quick observation about the virtual $\pi$s, followed by a proof of Theorem \ref{thm: independent}.

\begin{observation}\label{obs: one}For two types $A,B\in T_{i}$, $\hat{\pi}_{i}(A) \geq \hat{\pi}_{i}(B) \Leftrightarrow \pi_{i}(A) \geq \pi_{i}(B)$.
\end{observation}
\begin{proof} If $\pi_{i}(A) \geq \pi_{i}(B)$, then $\Pr[\pi_i(t_i) \leq \pi_{i}(A)] \geq \Pr[\pi_i(t_i) \leq \pi_{i}(B)]$. Therefore, $\hat{\pi}_{i}(A) \geq \hat{\pi}_{i}(B)$. The other direction is identical.
\end{proof}

%\begin{theorem}\label{thm: independent} A reduced form mechanism is feasible if and only if the following inequality holds for all $i$ and all $S^{(i)}_{x} = \{A\in T_{i}\ |\ \hat{\pi}_{i}(A) > x\}$:
%
%$$\sum_i \sum_{A \in S^{(i)}_x} \pi_{i}(A)\Pr[t_i = A] \leq 1-\prod_{i=1}^m(1-\sum_{A \in S^{(i)}_x}\Pr[t_i = A])$$
%\end{theorem} 

\begin{prevproof}{Theorem}{thm: independent} We know from \cite{border2007,CKM}, that if a reduced form mechanism is infeasible, then there is some constricting set of the form $S = \bigcup_{i=1}^{m}S_{x_{i}}$, where $S_{x_i} = \{A\ |\ \pi_{i}(A) \geq x_i, A\in T_{i}\}$. (Forgive the abuse of notation here. Formally, $S$ is a collection of $m$ sets of types, one for each bidder. {To avoid cumbersome notation and take union casually in this proof, let us assume that a type $A \in T_i$ carries the name of bidder $i$, for all $i$.})
%\yangnote{(maybe it's better to use $S=\bigcup_{1}^{m}S_{x_{i}}$, where $S_{x_{i}}=\{A| \pi(A)\geq x_{i},A\in T_{i}\}$, the original one is bit confusing.)}
Now consider any minimal constricting set of this form, i.e. a choice of $x_1,\ldots,x_m$ such that replacing $S_{x_{i}}$ with $S_{x_{i}}-\{A\}$ ($A\in S_{x_{i}}$) results in $S$ no longer being a constricting set.~\footnote{For a minimal set $S$, there could be many possible choices of $x_{1},\ldots,x_{m}$. We simply use any  of them.} Now let ${(i,A)} \in \argmin_{i,\ A\in S_{x_i}} \hat{\pi}_{i}(A)$. Then by Observation \ref{obs: one} and by our choice of $S$, $S - \{A\}$ is not a constricting set. Therefore, adding $A$ to $S- \{A\}$ must increase the left-hand bound by more than it increases the right-hand bound:

$$\Pr[t_i = A]\pi_{i}(A) > \Pr[t_i = A]\prod_{j \neq i}\Pr[\pi_j(t_j) < x_j]$$
$$\implies \frac{\pi_{i}(A)}{\prod_{j \neq i}\Pr[\pi_j(t_j) < x_j]} > 1.$$

Now consider any other $A' \in T_k$, $A' \notin S$ and $\hat{\pi}_{k}(A') \geq \hat{\pi}_{i}(A)$. Observe first that we must have $A'$ from some bidder $k\neq i$, as every $A''\in T_{i}$ with $\hat{\pi}_{i}(A'') \geq \hat{\pi}_{i}(A)$ has $\pi_i(A'') \geq \pi_i(A) \geq x_i$, so we would have $A'' \in S$. So for this $A'$, we have:
\begin{align*}
&\pi_{k}(A')\Pr[\pi_k(t_k) \leq \pi_{k}(A')] \geq \pi_{i}(A)\Pr[\pi_i(t_i) \leq \pi_{i}(A)]\\
\Longrightarrow& \pi_{k}(A')\Pr[\pi_k(t_k) < x_k] \geq \pi_{i}(A)\Pr[\pi_i(t_i)< \pi_{i}(A)]\\
\Longrightarrow& \pi_{k}(A')\Pr[\pi_k(t_k) < x_k] \geq \pi_{i}(A)\Pr[\pi_i(t_i)< x_{i}]\\
\Longrightarrow& \pi_{k}(A')\prod_{j\neq i} \Pr[\pi_j(t_j) < x_j] \geq \pi_{i}(A)\prod_{j \neq k} \Pr[\pi_j(t_j) < x_j]\\
\Longrightarrow& \frac{\pi_{k}(A')}{\prod_{j \neq k} \Pr[\pi_j(t_j) < x_j]} \geq \frac{\pi_{i}(A)}{\prod_{j \neq i}\Pr[\pi_j(t_j) < x_j]}.
\end{align*}
And by our choice of $A$ and the work above, we obtain:
$$\frac{\pi_{k}(A')}{\prod_{j \neq k}\Pr[\pi_j(t_j) < x_j]} > 1$$
$$\implies \Pr[t_k = A']\pi_{k}(A') > \Pr[t_k = A']\prod_{j \neq k} \Pr[\pi_j(t_j) < x_j].$$

This equation tells us directly that {we could add $A'$ to $S$ and still get a constricting set.} In fact, it tells us something stronger. If $S' = \bigcup_j S'_j$, where $S'_j \subseteq T_j$, is any constricting set containing $S$, then we could add $A'$ to $S'$ and still have a constricting set. This is because the change to the left-hand side of the inequality is the same, no matter what set we are adding $A'$ to. It is always $\Pr[t_k = A']\pi_k(A')$. And the change to the right-hand side is exactly $\Pr[t_k = A']$ times the probability that none of the types in $\cup_{j\neq k} S'_j$ show up. As we add more types to $S$, the probability that none of the types in $\cup_{j \neq k}S'_j$ show up {will never increase}. So for any constricting set $S'$ containing $S$, we can add $A'$ to $S'_k$ and still get a constricting set. 

So starting from a constricting set $S$ and a type $A \in T_i$ as above we can add every {$B \in T_j$} with {$\hat{\pi}_{j}(B) \geq \hat{\pi}_i(A)$} to $S$ in order to obtain a constricting set of the form {$S_x = \{B  | B \in T_j \wedge \hat{\pi}_{j}(B) \geq x\}$, where $x=\hat{\pi}_i(A)$}. So every infeasible reduced form has a constricting set of this form. Taking the contrapositive proves the theorem.
\end{prevproof}

We say that a hierarchical mechanism $H$ is \emph{virtually-ordered} if {$\hat{\pi}_i(A) \geq \hat{\pi}_j(A') \Rightarrow H(A,i) \leq H(A',j)$}. While the virtual $\pi$s give us a nice structural theorem about feasible reduced forms and a linear time separation oracle for determining feasibility (see proof of Theorem~\ref{thm:grand theorem independent}), the following observation shows that distributions over virtually-ordered hierarchical mechanisms are not sufficient to implement every feasible reduced form when the bidders are non-i.i.d. 

\begin{observation} There exist feasible reduced forms that are not implementable as distributions over virtually-ordered hierarchical mechanisms.
\end{observation}
\begin{proof} 
Consider the following example with two bidders. Bidder one has a single type, $A$. Bidder two has two types, $B$ and $C$ and is each with probability $1/2$. Then $\pi_1(A) = 1/3$, $\pi_2(B) = 2/3 + \epsilon$, $\pi_2(C) = 2/3-\epsilon$ is a feasible reduced form. However, $\hat{\pi}_1(A) > \hat{\pi}_2(C)$, so no distribution over virtually-ordered hierarchical mechanisms can possibly have $\pi_2(C) > 1/2$.
\end{proof}

Now that we have motivated Theorems \ref{thm: independenthierarchy} and \ref{thm:grand theorem independent}, we proceed to prove them, after providing the key steps as technical lemmas.

\begin{lemma}\label{lem: independenthierarchy} Every feasible reduced form $\pi$ for independent bidders and a single item can be implemented (not necessarily exactly implemented) as a distribution over strict, partially-ordered w.r.t. $\pi$ hierarchical mechanisms.
\end{lemma}

\begin{proof} The proof is almost identical to that of Lemma \ref{lem: iidhierarchy}. Here are the main differences: We do induction on $\sum_i d_i$, where $d_i$ is the number of distinct non-zero values in {$\{\pi_i(A)\}_{A \in T_i}$}. {For the inductive step,} $X$ is now taken to be the set of distributions over strict, partially-ordered hierarchical mechanisms, and it is still compact, viewed as a subset of the Euclidean space. The function $F:X \rightarrow \mathbb{R}$ is now defined as
$$F(M) = \max_{i,A \in T_i} \{\pi_i(A) - M_i(A)\}.$$
{Again, if we use the Euclidean distance on $X$, as a subset of the Euclidean space, $F$ is continuous. Since $F$ is continuous and $X$ is compact, $F$ achieves its minimum inside $X$. Let $M$ be a minimizer.} For all $i$, we define $S_i = \{A \in T_i | \pi_i(A) - M_i(A) = F(M)\}$. In terms of the sets $\{S_i\}_i$ we can define an alternative reduced form $\pi'$ as follows. For all $i$, $A \in T_i$: if $A \in S_i$, then set $\pi'_i(A) = \pi_i(A)$; otherwise, set $\pi'_i(A) = \max_{B \in S_i| \pi_i(A) \geq \pi_i(B)} \{\pi(B)\}$, unless $\{B \in S_i| \pi_i(A) \geq \pi_i(B)\}$ is empty in which case set $\pi'_i(A)$ equal to $0$. With these changes, the proof is truly identical to that of Lemma \ref{lem: iidhierarchy}, and we avoid repeating the steps for brevity.
\end{proof}

\begin{corollary}\label{cor: independenthierarchy} Every feasible reduced form $\pi$ for independent bidders and a single item can be exactly implemented as a distribution over strict, partially-ordered w.r.t. $\pi$ hierarchical mechanisms.
\end{corollary}
\begin{proof}
The proof is identical to that of Corollary \ref{cor: iidhierarchy} after making the same modifications going from Lemma \ref{lem: iidhierarchy} to Lemma \ref{lem: independenthierarchy}.
\end{proof}

{We proceed to prove an analog of Proposition~\ref{prop: iidcorners} in this setting. We need a definition. For all $i$, let $>^{i}:= A_{i,1} >^i A_{i,2} >^i \ldots >^i A_{i,k_i}$ be a total ordering of the set $T_{i}:=\{A_{i,1},\ldots,A_{i,k_i}\}$ of bidder $i$'s types. We say that a reduced form $\pi$ respects $>^{i}$ iff $\pi_i(A_{i,1})\ge \pi_i(A_{i,2}) \ge \ldots  \ge \pi_i(A_{i,k_i})$. We also say that an hierarchical mechanism $H$ is partially-ordered with respect to $>^i$ iff $H(A_{i,1},i) \le H(A_{i,2},i) \le \ldots \le H(A_{i,k_i},i)$.~\footnote{Notice that this definition of partially-ordered hierarchical mechanism (with respect to $\{>^i\}_i$) is similar to its counterpart in the main body (with respect to $\pi$), but different. Being partially-ordered with respect to $\pi$ certainly imposes the same constraints as being partially-ordered with respect to any $\{>^i\}_i$ that $\pi$ respects. The difference is that being partially-ordered with respect to $\pi$ may also impose some equality constraints, if $\pi_i(A) = \pi_i(B)$ for types $A \neq B$.} With respect to these definitions we show the following proposition.}
% With respect to these definitions we show the following proposition.}




\begin{proposition}\label{prop: independentcorners} For all $i$, let $>^{i}:= A_{i,1} >^i A_{i,2} >^i \ldots >^i A_{i,k_i}$ be a total ordering of the set $T_{i}:=\{A_{i,1},\ldots,A_{i,k_i}\}$ of bidder $i$'s types. The set of feasible reduced forms that respect $>^1,\ldots,>^m$ is a $(\sum_i k_i)$-dimensional polytope whose corners are exactly the strict, partially-ordered w.r.t. $>^1,\ldots,>^m$ hierarchical mechanisms. 
\end{proposition}
\begin{proof}
We know from \cite{border2007,CKM} that a reduced form $\pi$ respects $>^1,\ldots,>^m$ and is feasible iff 
\begin{align}
\pi_i(A_{i,j}) &\geq \pi_i(A_{i,j+1}) &\forall i \in [m],j \in [k_i] \label{eq:costas}\\
\sum_i \sum_{j \leq x_i}\Pr[t_{i}=A_{i,j}] \pi_i(A_{i,j}) &\leq 1 - \prod_i\left(1-\sum_{j \leq x_i}\Pr[t_i = A_{i,j}]\right) &\forall x_1 \in [k_1],\ldots,x_m \in [k_m]\label{eq: wasteful}
\end{align}
where for notational convenience we denote $\pi_i(A_{i,k_i+1}) = 0$. In fact, to make our lives easier in a later proof, we will actually replace~\eqref{eq: wasteful} with:
\begin{align}
\sum_i \sum_{j \leq x_i}\Pr[t_{i}=A_{i,j}] \pi_i(A_{i,j}) &\leq 1- \prod_i \left(1-\sum_{j \leq x_i} \Pr[t_i = A_{i,j}]\right) \forall x_1 \in [k_1-1],\ldots,x_m \in [k_m -1] \label{eq: simpler}\\
\sum_i \sum_{j \leq k_i}\Pr[t_{i}=A_{i,j}] \pi_i(A_{i,j}) &\leq 1 \label{eq: better}
\end{align}
In the above above replacement, we are basically observing that if \eqref{eq: better} holds, then so does \eqref{eq: wasteful} for any case where at least one $i$ has $x_i = k_i$. In addition, \eqref{eq: simpler} covers all other cases.  We have hence shown that the set of feasible reduced forms that respect $>^1,\ldots,>^m$ is a $\sum_i k_i$-dimensional polytope. 


We proceed to show that any strict, partially-ordered w.r.t. $>^1,\ldots,>^m$ hierarchical mechanism $H$ whose reduced-form is $\pi$ is a corner. {For convenience in the proof assume that $T_i \cap T_k = \emptyset$, for all $i\neq k$. This is easy to achieve by having every type of bidder $i$ carry the name of bidder $i$, for all $i$.} Let now $y = \min_x \Pr[\exists i, H(t_i,i) \leq x] = 1$, {i.e. the minimum $y$ so that with probability $1$ some bidder $i$ will report a type $A_{i,j}$ such that $H(A_{i,j},i) \le y$.} {In terms of this $y$ we define $y^*$ as follows: $y^*:=y$, if $y \neq \lose$ (case 1), and $y^*:=y-1$, if $y=\lose$ (case 2).}  We observe then that a type $A_{i,j}\in T_{i}$ with $H(A_{i,j},i) > y^*$ cannot possibly win the item, as we are either guaranteed to see some bidder whose type lies on a higher level of the hierarchy (case 1) or the type is mapped to $\lose$ and is hence given no item (case 2). For all such $i, A_{i,j}\in T_{i}$, we therefore have $\pi_i(A_{i,j}) = \pi_{i}(A_{i,j+1})=\cdots=\pi_i(A_{i,k_i+1})=0$.
 
We say that a set of types $S=\cup_i \{A_{i,1},\ldots,A_{i,x_i} \}$ for some $x_1,\ldots,x_m$ is {\em near-constricting}, if the corresponding Inequality~\eqref{eq: wasteful} is tight for $x_1,\ldots,x_m$. Then, for any $i, A_{i,j}\in T_{i}$ with $H(A_{i,j},i) \leq y^*$, we know that $H^{-1}([H(A_{i,j},i)])$ is a near-constricting set, because the item is always awarded to a type in $H^{-1}([H(A_{i,j},i)])$ whenever at least one type from this set is reported. {Moreover, if $H(A_{i,j_1},i)=\ldots=H(A_{i,j_{\ell}},i)$, for some types $A_{i,j_1},\ldots,A_{i,j_{\ell}} \in T_i$, then $\pi_i(A_{i,j_1})=\ldots=\pi_i(A_{i,j_{\ell}})$. Finally, because $H$ is strict, if some $i, A_{i,j} \in T_i$ satisfy $H(A_{i,j},i) \le y^*$, then $H^{-1}(H(A_{i,j},i)) \cap T_k = \emptyset$, for all $k\neq i$.

Let us now define the following mapping from types to tight inequalities:
\begin{itemize}
\item If a type $A_{i,j} \in T_i$ satisfies $H(A_{i,j},i) > y^*$, then we map $A_{i,j}$ to the constraint $\pi_i(A_{i,j}) = \pi_i(A_{i,j+1})$, i.e. the tightness of inequality $\pi_i(A_{i,j}) \ge \pi_i(A_{i,j+1})$.
\item If a type $A_{i,j} \in T_i$ satisfies $H(A_{i,j},i) \le y^*$, then:
\begin{itemize}
\item if $H(A_{i,j},i) = H(A_{i,j+1},i)$, we map $A_{i,j}$ to the constraint $\pi_i(A_{i,j}) = \pi_i(A_{i,j+1})$, i.e. the tightness of inequality $\pi_i(A_{i,j}) \ge \pi_i(A_{i,j+1})$;
\item otherwise, we map $A_{i,j}$  to the tightness of Inequality~\eqref{eq: wasteful} for the set of types $H^{-1}([H(A_{i,j},i)])$.
\end{itemize}
\end{itemize}
The above discussion ensures that our mapping is injective. Hence $\pi$ makes at least $\sum_i k_i$ of the inequalities defining our polytope tight. And it is not hard to see that there is a unique feasible reduced form making these inequalities tight. So $\pi$ is a corner of the polytope. Thus, every strict, partially-ordered w.r.t. $>^1,\ldots,>^m$ hierarchical mechanism is a corner of the polytope. }

We now make the same observation as in Proposition~\ref{prop: iidcorners} to argue that there are no other corners. Corollary \ref{cor: independenthierarchy} implies that every point in the polytope can be written as a convex combination of  strict, partially-ordered w.r.t. $>^1,\ldots,>^m$ hierarchical mechanisms, all of which are corners of the polytope. As no corner of the polytope can be written as a convex combination of \emph{other} corners of the polytope, there must not be any other corners.
\end{proof}

And now we are ready to prove Theorems \ref{thm: independenthierarchy} and \ref{thm:grand theorem independent}.

\begin{prevproof}{Theorem}{thm: independenthierarchy}
{Using a similar argument as in the proof of Theorem~\ref{thm: iidhierarchy} we can assume without loss of generality that, for all $i$, ${\pi}$ assigns a distinct probability to every type in $T_i$. (Otherwise we can define a similar {\sc TypeMerge} operation, like the one defined in the proof of Theorem~\ref{thm: iidhierarchy}, whereby types in $T_i$ that receive the same ${\pi}$ value are merged into super-types.) Under this assumption, Proposition~\ref{prop: independentcorners} implies that ${\pi}$ lies} inside a $(\sum_i |T_i|)$-dimensional polytope, $P$, whose corners are the strict, partially-ordered w.r.t. ${\pi}$ hierarchical mechanisms. By Carath\'eodory's Theorem, every point in the polytope can be written as a convex combination of at most $(\sum_i |T_i|)+1$ corners. As a convex combination of corners is exactly a distribution over strict, partially-ordered w.r.t. $\pi$ hierarchical mechanisms, this proves the theorem.
\end{prevproof}

\begin{prevproof}{Theorem}{thm:grand theorem independent}
{The first part of the theorem follows immediately as a corollary of Theorem~\ref{thm: independent}.}


We now need to describe how to efficiently find a mechanism implementing a reduced form $\tilde{\pi}$ that is feasible. {Using a similar argument as in the proof of Theorem~\ref{thm:grand theorem symmetric} we can assume without loss of generality that, for all $i$, $\tilde{\pi}$ assigns a distinct probability to every type in $T_i$. (Otherwise we can merge types in $T_i$ that receive the same $\tilde{\pi}$ value into super-types, like we did in the proof of Theorem~\ref{thm:grand theorem symmetric}, then run the procedure outlined below, and finally un-merge types.) Under this assumption, Proposition~\ref{prop: independentcorners} implies that $\tilde{\pi}$ lies inside a $(\sum_i |T_i|)$-dimensional polytope, $P$, whose corners are the strict, partially-ordered {w.r.t. $\tilde{\pi}$} hierarchical mechanisms.} Therefore we can directly apply Theorem~\ref{thm: polytope} of Appendix~\ref{app: polytope} to write $\tilde{\pi}$ as a convex combination of such hierarchical mechanisms, as long as we can describe the boundary oracle $BO$, corner oracle $CO$ and separation oracle $SO$ that are needed for Theorem~\ref{thm: polytope}. $BO$ is trivial to implement, {as we just have to include in the set of halfspaces defining the boundary of $P$ those inequalities described in the proof of Proposition~\ref{prop: independentcorners}. In particular, for convenience in the remaining of the proof, we include the inequalities of the form~\eqref{eq:costas}, \eqref{eq: simpler} and \eqref{eq: better}.} For $CO$, on input $B$, we first check that every hyperplane $h \in B$ satisfies $BO(h) = \text{yes}$. If not, output no. Otherwise, we need to check if $\bigcap_{h \in B} h$ contains a corner of $P$. We know that the corners of $P$ are exactly the strict, partially-ordered w.r.t. $\tilde{\pi}$ hierarchical mechanisms. To check if there is such a corner in $\bigcap_{h \in B} h$ we need to do some work. 

{First, let us use the same notation as in Proposition~\ref{prop: independentcorners}, denoting $T_i=\{A_{i,1},\ldots,A_{i,k_i}\}$, where $k_i=|T_i|$ and $\tilde{\pi}_i(A_{i,1}) > \ldots > \tilde{\pi}_i(A_{i,k_i})$. Also, let us call a set of types $S$ near-constricting if either $S=\cup_i \{A_{i,1},\ldots,A_{i,x_i} \}$ for some $x_1\le k_1-1,\ldots,x_m \le k_m-1$ and Inequality~\eqref{eq: simpler} is tight for $x_1,\ldots,x_m$, or if $S=\cup_i T_i$ and Inequality~\eqref{eq: better} is tight. }

Now given a set $B$ of hyperplanes, if $B$ contains a near-constricting set hyperplane for the sets of types $S_1,\ldots,S_k$, we check first whether these sets satisfy $S_{1} \subset S_{2} \ldots \subset S_{k}$ {(possibly after renaming).} If not, then there are some two near-constricting sets $S_i,S_j$ with $A \in S_i - S_j$, $B \in S_j - S_i$ for some types $A\neq B$. {Because $S_i$ and $S_j$ are different than $\cup_i T_i$ and they are near-constricting they must be of the form making Inequality~\eqref{eq: simpler} tight.} Hence, both $S_i$ and $S_j$ miss at least one type of every bidder, so that the right-hand side of the inequality for $S_i$ must be $< 1$ and similarly the right-hand side of the inequality for $S_j$ must be $<1$. In addition, we cannot have $A$ and $B$ be types of the same bidder, as we only consider near-constricting sets that respect the partial ordering within every bidder's type-set. Therefore, $A$ and $B$ belong to different bidders, and because the probability of seeing a type in $S_i$ is $< 1$ (and the same holds for $S_j$), there is a non-zero probability that $A$ and $B$ are both present, but no other type of $S_i$ or $S_j$ is present. Then the near-constricting set equation for set $S_i$ requires that we must give the item to $A$,~\footnote{{Recall that a way to interpret a near-constricting set equation for set $S$ is the following: whenever at least one bidder reports a type in $S$ to the mechanism, the mechanism gives the item to a bidder who reported a type in $S$, with probability $1$.}} and the near-constricting set equation for $S_j$ requires that we must give the item to $B$, which is impossible. So if we do not have $S_1 \subset S_2 \ldots \subset S_k$, the hyperplanes do not intersect in a feasible mechanism, and therefore $CO$ should output no. 

Otherwise, $CO$ looks at the other hyperplanes (of the form $\pi_i(A_{i,j}) = \pi_i(A_{i,j+1})$) that belong to $B$, and chooses an arbitrary strict, partially-ordered w.r.t. $\tilde{\pi}$ hierarchical mechanism that satisfies the following constraints:
\begin{enumerate}
\item $H(A,i) < H(A',i')$ for all $(A,i) \in S_j, (A',i') \in S_{j+1} - S_j$, for all $j$.
\item $H(A,i) < H(A',i')$ for all $(A,i) \in S_k, (A',i') \notin S_k$.
\item {For all $i, A_{i,j} \in T_i$: 
\begin{enumerate}
\item if the hyperplanes $\pi_i(A_{i,j}) = \pi_i(A_{i,j+1})$, $\pi_i(A_{i,j+1}) = \pi_i(A_{i,j+2})$, $\ldots$, $\pi_i(A_{i,k_i}) = 0 (=\pi_i(A_{i,k_i+1}))$ are all in $B$, then $H(A_{i,j},i) = \lose$;
\item otherwise, if $\pi_i(A_{i,j}) = \pi_i(A_{i,j+1})$ is in $B$, then either $H(A_{i,j} ) = H(A_{i,j+1})=\lose$ or $H(A_{i,j} ) \ge H(A_{i,j+1})-1$.
\end{enumerate}}
\end{enumerate}


{We claim that an $H$ satisfying the above constraints exists if and only if $\bigcap_{h \in B} h \cap P \neq \emptyset$.} By Proposition~\ref{prop: independentcorners}, we know that if there is a corner $\pi$ in $\bigcap_{h \in B} h \cap P$, there is a strict, partially-ordered w.r.t. $\tilde{\pi}$ hierarchical mechanism $H$ that implements it. {Without loss of generality we can make two simplifying assumptions about $H$: (i) For all $t \neq \lose$, $|H^{-1}(t)|\leq 1$. Indeed, suppose that $|H^{-1}(t)|>1$ for some $t \neq \lose$. Then because $H$ is strict, location $t$ of the hierarchy defined by $H$ only contains types belonging to the same bidder $i$. And because $H$ is partially ordered w.r.t. $\tilde{\pi}$ these types are consecutive in $T_i$. So we can change $H$ to ``expand'' cell $t$ of the hierarchy into consecutive cells containing a single type each in the right order. This has no effect in the mechanism defined by $H$. (ii) If $H$ awards  the item to bidder $i$ of type $A_{i,j}$ with probability $0$, we can assume that $H(A_{i,j},i) = \lose$. 
%(iii) $H$ has the sets $S_1',\ldots, S_k'$ near-constricting. Indeed, a strict, partially ordered w.r.t. $\tilde{\pi}$ hierarchical mechanism $H$ that satisfies (i), (ii) and has the set $S_{\ell}$ near-constricting, must also have the set $S_{\ell}'$ near-constricting, for all $\ell$. 
Now given (i) and the nature of $S_1,\ldots,S_k$,~\footnote{in particular, the fact that the sets $S_1,\ldots,S_k$ respect the ordering of the type sets as follows: For all $\ell$, $A_{i,j} \in S_{\ell}$ implies $A_{i,j'} \in S_{\ell}$, for all $j' \le j$.} for $H$ to have the sets $S_1,\ldots,S_k$ near-constricting it must satisfy the first two constraints above. Indeed for these constraints not to be satisfied there must exist $\ell$, $i, A_{i,j}$, $i', A_{i',j'}$, $i\neq i'$ such that $H(A_{i,j},i)<H(A_{i',j'},i')$ and $A_{i,j} \notin S_{\ell}$ while $A_{i',j'}\in S_{\ell}$. But then it must be $\pi(A_{i,j}) >0$ (because of assumption (ii)), so there is a positive probability that bidder $i$ of type $A_{i,j}$ is the highest in the hierarchy when every bidder except for $i'$ has declared a type. Still, given that $H(A_{i,j},i)<H(A_{i',j'},i')$, even if $i'$ declares $A_{i',j'}$, $i$ will get the item, contradicting that $S_{\ell}$ is near-constricting.}  We argue next that $H$ also needs to satisfy the third constraint above. That constraint 3(a) is satisfied follows immediately from assumption (ii). We argue next that 3(b) needs to be satisfied. Indeed, suppose there exist $A_{i,j}, A_{i,j+1} \in T_i$ and  $A_{i',j'} \in T_{i'}$ such that $\pi_i(A_{i,j}) = \pi_i(A_{i,j+1}) >0$ and $H(A_{i,j},i) < H(A_{i',j'},i') < H(A_{i,j+1},i)$. As $\pi_i(A_{i,j+1}) >0$, it follows that $H(A_{i,j+1},i)< \lose$, so $H(A_{i',j'},i') <\lose$, which implies that $\pi_{i'}(A_{i',j'}) >0$ (otherwise it would be that $H(A_{i',j'},i') = \lose$ given (ii)). Now, because bidder $i'$ wins the item with non-zero probability as type $A_{i',j'}$, there is a non-zero probability that $A_{i',j'}$ is on the highest level of the hierarchy after sampling from all bidders except for $i$. In this case, $i$ will win the item by reporting $A_{i,j}$, and lose by reporting $A_{i,j+1}$. In all other cases, $i$ is at least as likely to win the item by reporting $A_{i,j}$ as $A_{i,j+1}$, and therefore we see that bidder $i$ gets the item strictly more often when reporting $A_{i,j}$ than $A_{i,j+1}$, violating the constraint $\pi_i(A_{i,j}) = \pi_i(A_{i,j+1})$. So if there is a corner $\pi$ in $\bigcap_{h \in B} h \cap P$ it can be implemented by a strict, partially-ordered w.r.t. $\tilde{\pi}$  hierarchical mechanism  $H$ satisfying the above constraints. The other direction of our claim is even simpler. If a strict, partially-ordered w.r.t. $\tilde{\pi}$ hierarchical mechanism $H$ satisfies all constraints above, then its induced reduced-form $\pi$ will immediately satisfy all equalities in $B$. 

%From Proposition~\ref{prop: independentcorners}, we know that all strict, partially-ordered hierarchical mechanisms are corners, so this one is also a corner.  
 
 Hence to implement $CO$ {one} just needs to check if there is a strict, partially-ordered w.r.t. $\tilde{\pi}$ hierarchical mechanism $H$ satisfying the four constraints above. This task is easy to do efficiently. If a mechanism is found it satisfies all equalities in $B$ and it is a corner of the polytope by Proposition~\ref{prop: independentcorners}. 
 
 $SO$ is also simple to implement. {On input $\vec{\pi}$, we first check that Inequalities~\eqref{eq:costas} are satisfied (i.e. that $\vec{\pi}$ respects the total orderings on the bidders' type-spaces induced by $\tilde{\pi}$). Then we use the separation oracle provided by Theorem~\ref{thm: independent} to verify that $\vec{\pi}$ is feasible.} As all three oracles $BO, CO, SO$ run in polynomial time, we can apply Theorem~\ref{thm: polytope} to write $\tilde{\pi}$ as a convex combination of at most $\sum_i |T_i| + 1$ corners, which is exactly a distribution over at most $\sum_i |T_i| + 1$ strict, partially-ordered hierarchical mechanisms in polynomial time. 
\end{prevproof}
main.tex
\documentclass[11pt,times]{article}
\usepackage{amsfonts}
\usepackage{amssymb,amsmath,amsthm}
\usepackage{epsfig}
\usepackage{color}
\usepackage{latexsym}
\usepackage{enumerate}
\usepackage{algorithm}
\usepackage{algorithmic}
\newcommand{\ind}{\mathbbm{1}}
\usepackage{tweaklist}
\renewcommand{\enumhook}{\setlength{\topsep}{2pt}%
  \setlength{\itemsep}{-2pt}}
\renewcommand{\itemhook}{\setlength{\topsep}{2pt}%
  \setlength{\itemsep}{-2pt}}
%\usepackage[dvips, paper=letterpaper, top=0.95in, bottom=.75in, left=0.9in, right=0.95in, nohead, includefoot, footskip=.25in]{geometry}
\usepackage[dvips, paper=letterpaper, top=1in, bottom=.75in, left=1in, right=1in, nohead, includefoot, footskip=.25in]{geometry}


\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{conjecture}{Conjecture}
\newtheorem{claim}{Claim}
\newtheorem{proposition}{Proposition}
\newtheorem{fact}{Fact}
\newtheorem{definition}{Definition}
\newtheorem{assumption}{Assumption}
\newtheorem{observation}{Observation}
\newtheorem{example}{Example}
\newtheorem{remark}{Remark}
\newtheorem{question}{Question}
\newtheorem{hypothesis}{Hypothesis}
\newtheorem{informaltheorem}{Informal Theorem}
%%%\newcommand{\qed}{\rule{7pt}{7pt}}
%%%\newcommand{\order}[1]{O(#1)}
\newenvironment{prevproof}[2]{\noindent {\em {Proof of {#1}~\ref{#2}:}}}{$\Box$\vskip \belowdisplayskip}

%\newenvironment{proof}{\ni {\em Proof:}}{\hfill $\Box$ \bigbreak}
%\newcommand{\qed}{\hfill $\Box$}
%%%\newenvironment{example}{{\bf Example:}}{\hfill $\Box$ \bigbreak}

\newcommand{\mychoose}[2]{\left( \begin{array}{c} #1 \\ #2 \end{array} \right)}
\newcommand{\junk}[1]{}
\junk{
\newcommand{\pict}[3]
   { \begin{figure}
     \refstepcounter{figure}
     \addtocounter{figure}{-1}
     \label{#3}
     \begin{center}
     \input{#1}
     \caption{#2}
     \end{center}
     \end{figure}
   }
}

\newcommand{\N}{\ensuremath{\mathbb{N}}} % The naturals
\newcommand{\Z}{\ensuremath{\mathbb{Z}}} % The integers
\newcommand{\R}{\ensuremath{\mathbb{R}}} % The reals
\newcommand{\Q}{\ensuremath{\mathbb{Q}}} % The rationals
\newcommand{\lose}{\text{LOSE}}
\newcommand{\poly}{\text{poly}}
\newcommand{\costasnote}[1]{{\color{red}{#1}}}
\newcommand{\mattnote}[1]{{\color{blue}{#1}}}
\newcommand{\yangnote}[1]{{\color{green}{#1}}}

\DeclareMathOperator{\Prob}{Pr}
\DeclareMathOperator{\E}{E}

\def \ni {\noindent}
\def \bfm {\bf \boldmath}
\def \TT  {{\cal T}}
\def \PP  {{\cal P}}
\def \GG  {{\cal G}}
\def \OO  {{\cal O}}
\def \NN  {{\cal N}}
\def \LL  {{\cal L}}
\def \BB  {{\cal B}}
\def \VV  {{\cal V}}
\def \EE  {{\cal E}}
\def \ee {\varepsilon}
\def \t  {\tilde}
\def \FF  {{\cal F}}
\def \SS  {{\cal S}}


\def \pc   {{\sf P}}                              %%% P complexity class
\def \npc  {{\sf NP}}                             %%% NP complexity class
\def \ncc  {{\sf NC}}                             %%% NC complexity class
\def \zppc  {{\sf ZPP}}                           %%% ZPP complexity class
\def \qpc  {{\sf DTIME}(n^{O({\sf polylog}(n))})} %%% QusiPoly complexity class
\def \snp  {{\sf Max SNP}}                        %%% Max SNP complexity class
\def \ptas {{\sf PTAS}~}
\def \gr   {{\sf Greedy-1}}
\def \grr   {{\sf Greedy}}

\DeclareMathOperator{\argmax}{argmax}
\DeclareMathOperator{\argmin}{argmin}

\def \ee {{\rm e}} % Euler number

\definecolor{MyGray}{rgb}{0.8,0.8,0.8}

\newcommand{\graybox}[2]{\begin{figure}[t]
\colorbox{MyGray}{
\begin{minipage}{\textwidth}
{#2}
\end{minipage}
}\caption{{#1}}
\end{figure}
}

\begin{document}
%\setlength{\parskip}{1.5ex plus0.5ex minus0.5ex}
%\setlength{\parindent}{0em}
\title {A Constructive Proof of Border's Theorem for Optimal Multi-dimensional Mechanism Design} 
\title{An Algorithmic Characterization of Multi-Dimensional Mechanisms}
\author {Yang Cai\thanks{Supported by NSF Award CCF-0953960 (CAREER) and CCF-1101491.}\\
EECS, MIT \\
\tt{ycai@csail.mit.edu}
\and
Constantinos Daskalakis\thanks{Supported by a Sloan Foundation Fellowship and NSF Award CCF-0953960 (CAREER) and CCF-1101491.}\\
EECS, MIT \\
\tt{costis@mit.edu}
\and
S. Matthew Weinberg\thanks{Supported by a NSF Graduate Research Fellowship and a NPSC Graduate Fellowship.}\\
EECS, MIT\\
\tt{smw79@mit.edu}
}
\addtocounter{page}{-1}
\maketitle
\begin{abstract}
We obtain a {\em characterization} of feasible, Bayesian, multi-item multi-bidder mechanisms with independent, {additive} bidders as {\em distributions over hierarchical mechanisms}. {Combined with cyclic-monotonicity our results provide a complete characterization of feasible, Bayesian Incentive Compatible mechanisms for this setting. }

Our characterization is enabled by a novel, constructive proof of Border's theorem~\cite{border}, and a new generalization of this theorem to independent (but not necessarily identically distributed) bidders, improving upon the results of \cite{border2007,CKM}. For a single item and independent (but not necessarily identically distributed) bidders, we show that any feasible reduced form auction can be implemented as a distribution over hierarchical mechanisms. We also give a polynomial-time algorithm for determining feasibility of a reduced form auction, or providing a separation hyperplane from the set of feasible reduced forms. To complete the picture, we provide polynomial-time algorithms to find and exactly sample from a distribution over hierarchical mechanisms  consistent with a given feasible reduced form. 
{All these results generalize to multi-item reduced form auctions for independent, additive bidders.}
Finally, for multiple items, {additive bidders with hard demand constraints, and arbitrary value correlation across items or bidders,} we give a proper generalization of Border's Theorem, {and} characterize feasible reduced form auctions as multi-commodity flows in related multi-commodity flow instances. {We also show that our generalization holds for a broader class of feasibility constraints, including the intersection of any two matroids.}

As a corollary of our results we obtain revenue-optimal, Bayesian Incentive Compatible (BIC) mechanisms in multi-item multi-bidder settings, when each bidder has arbitrarily correlated values over the items and additive valuations over bundles of items, and the bidders are independent. Our mechanisms run in time polynomial in the total number of bidder types (and {\em not} type profiles). This running time is polynomial in the number of bidders, but potentially exponential in the number of items. We improve the running time to polynomial in both the number of items and the number of bidders by using recent  structural results on optimal BIC auctions in item-symmetric settings~\cite{DW}.  
\end{abstract}
\thispagestyle{empty}

\newpage

\section{Introduction} \label{sec:intro}

In its most general form mechanism design is the task of selecting outcomes and charging prices in a way that maximizes some objective such as revenue or social-welfare. Accordingly, to specify a mechanism one needs to provide two, possibly randomized, functions: one that maps bids to outcomes, and another mapping bids to prices charged to the bidders. Consider, e.g., a setting where $n$ items are (simultaneously) auctioned to $m$ bidders. For every possible collection of bids the mechanism needs to specify (a) a possibly randomized allocation of items to bidders; and (b) a possibly randomized collection of prices charged to them. {The latter can be typically summarized by its expectation, which is just a vector of real numbers, recording the price charged to each bidder.} But the former is a distribution over allocations and, in principle, would require $(m+1)^n$ probabilities to be specified,  making such explicit specification completely impractical. It turns out that this calculation is too pessimistic, and the Birkhoff-von Neumann decomposition theorem allows one to {summarize} a randomized allocation by just providing its marginal allocation probabilities $\phi=\{\phi_{ij}\}_{ij}$, where $\phi_{ij}$ is the probability that item $j$ is given to bidder $i$ ~\cite{DFK}. All that these probabilities need to satisfy to be consistent with a joint allocation distribution is that no item is given out more than once in expectation, and no bidder gets more items than she wants (if she has any demand constraints).

Yet, the above description is  still too demanding as, even when every bidder can place $c$ possible bids to specify her preferences over the items, there are $c^m$ possible bid vectors, and the mechanism needs to specify what to do for each. To decrease the specification complexity to linear in the number of bidders one can use the {\em reduced form of the mechanism}, which specifies a pair of possibly randomized allocation and price functions {\em per bidder}. In particular, if ${ T}_i$ denotes the possible bids that bidder $i$ can submit,~\footnote{We won't make any assumptions about ${ T}_i$, except that it is measurable. In particular, it won't necessarily be a subset of ${\mathbb{R}}$, unless otherwise specified.} the reduced form of the mechanism provides a collection ${\cal R}:=\{ (\pi_i: { T}_i \rightarrow [0,1]^n, p_i:{ T}_i \rightarrow \mathbb{R}) \}_i$ of functions such that, for all $t_i \in { T}_i$ and all $j$, $\pi_{ij}(t_i)$ is the marginal probability (over the randomness in the mechanism and the uncertainty about the bids submitted by the other bidders) that item $j$ is allocated to bidder $i$ when she reports $t_i$, and $p_i(t_i)$ is the expected price she pays. Indeed, the functions $\pi_i$ and $p_i$ provide sufficient information for the bidder to decide what bid in ${ T}_i$ optimizes her utility in expectation. The trouble is that, unless the uncertainty over the other bids can be modeled probabilistically, the notion of a marginal allocation probability $\pi_{ij}$ is ill-defined. 


%the auctioneer should not make promises she cannot meet. If, e.g., there exists a pair of bids $t_1 \in {\cal T}_1$ and $t_2 \in {\cal T}_2$ that bidders 1 and 2 could submit, satisfying $\pi_{1j}(t_1)+\pi_{2j}(t_2) >1$ for some item $j$, there is no way that the auctioneer can implement the promised marginal allocation probabilities. Indeed, it takes little thought to realize that, under worst-case assumptions, there are very stringent conditions that one needs to place on the reduced form ${\cal R}$ for it to be feasible, and the space of mechanisms that can be described via a feasible reduced form is much smaller than the space of all mechanisms$\ldots$

Indeed, Economists go around this obstacle by making average-case assumptions about the preferences of bidders~\cite{myerson}. In particular, it is assumed that every bidder has a {\em type} $t_i \in { T}_i$ (forgive the temporary overload of notation), and that the joint type profile of the bidders is sampled from some known, joint distribution ${\cal D}$ over $\times_i { T}_i$. Now, the Revelation Principle implies that every auction is strategically equivalent to one where bidders submit not generic bids, but truthfully report their exact type. Hence w.l.o.g. we can  restrict our attention to mechanisms where the bid space of bidder $i$ is just ${ T}_i$ ({\tt EndOf overload of notation}), and where the distribution of bids that bidders submit is exactly ${\cal D}$.  For such auctions, the reduced form is perfectly well-defined. But a challenge remains: What conditions are necessary and sufficient for a reduced form $\{\pi_i\}_i$ to be feasible, i.e. correspond to a feasible auction (that never over-allocates items)? Can these conditions be verified efficiently? And, given a feasible reduced form can we efficiently compute an auction implementing it?

\smallskip Before studying these questions, why do we even care? Even without answers, mechanism design has  made great progress in designing auctions, which optimize various objectives in a wide-range of  settings. When the objective is social-welfare, there is an optimal auction with a very clean allocation rule, namely the VCG auction~\cite{vickrey,clarke,groves}. The auction always chooses the welfare-maximizing allocation, and just charges prices to ensure incentive compatibility. When the objective is revenue, things get more murky. Still, when we are auctioning a single item to bidders whose values are independently sampled from known distributions, we can employ Myerson's celebrated,  revenue-optimal auction~\cite{myerson}. Its allocation rule is still rather clean: it always chooses the allocation that maximizes virtual surplus, and just charges prices to ensure incentive compatibility.  

 %, even if there are only two goods and each bidder's value for each good is sampled i.i.d. from the same known distribution. 

While in the above cases we have clean allocation rules, these results remain quite exceptional. In particular, there is no known simple characterization of the set of all feasible single-item mechanisms, and {(prior to this work)} it is unclear if there is one. {Additionally, it seems unlikely that there is a clean allocation rule implementing the revenue-optimal multi-item mechanism. Understanding the set of feasible multi-item mechanisms is therefore a crucial step along the path to understanding revenue-optimal mechanisms in this setting.} Indeed, in the past decades a large body of research in Economics has been devoted to finding revenue-optimal mechanisms (extending Myeson's result) to multi-item settings, but progress has been sporadic (see survey~\cite{optimal:econ} and its references). More recently the problem has entered theory of computation, and there has been a number of papers obtaining constant factor approximations~\cite{alaei,BGGM,CHMS}. Our slow progress on this front is intimately related to the lack of a characterization result of feasible mechanisms. Loosely speaking, all known algorithms optimize using relaxed feasibility constraints for the reduced form of the mechanism, such as  ``every item can be awarded at most once in expectation'' \cite{alaei,BGGM} or ``the expected number of items awarded from every subset must not exceed its rank'' \cite{CHMS}. Using such relaxed feasibility constraints, the optimal (possibly infeasible) reduced form is found. To turn this into a feasible reduced form, some ``rounding procedure'' is applied; this procedure may be just scaling the allocation probabilities down by a constant so that no item is over-allocated~\cite{alaei,BGGM}, or may invoke prophet inequalities~\cite{alaei,CHMS}. However, rounding comes with a loss in revenue. In view of this computational experience with the problem, it is crucial to try to characterize the feasible reduced forms exactly in a way that makes optimization efficient.

In this paper we carry out this program. We obtain strong characterization results for the set of all feasible single-item mechanisms (for independent bidders), as well as the set of all feasible multiple-item mechanisms when the bidders have arbitrarily correlated additive valuations over bundles of items (but there is no correlation across bidders). Our characterization result (explained in Section~\ref{sec:characterization}) is based on obtaining novel, constructive proofs of Border's theorem~\cite{border} and recent extensions of this theorem~\cite{border2007,CKM}, which are overviewed in Section~\ref{sec:reduced}. Using  these constructive proofs and our characterization result, we obtain revenue-optimal, Bayesian Incentive Compatible (BIC) mechanisms in multi-item multi-bidder settings, when each bidder has arbitrarily correlated values over the items and additive valuations over bundles of items, and the bidders are independent. Our mechanisms run in time polynomial in the total number of bidder types, $\sum_i |{ T}_i|$. This running time is polynomial in the number of bidders, but potentially exponential in the number of items. We improve the running time to polynomial in both the number of items and the number of bidders, by using recent  structural results on optimal BIC auctions in symmetric settings~\cite{DW}.  These results are overviewed in Section~\ref{sec:optimal}. {In Section~\ref{sec: generalized border} we present a generalization of Border's theorem to the multi-item setting where values are arbitrarily correlated across items or bidders, and bidders have additive valuations with hard demand constraints, and provide a multi-commodity flow interpretation of this problem. }{In addition, we show that our generalization holds for a much broader class of feasibility constraints. Simply put, our generalization holds in all instances where the feasibility constraints can be written as a system of inequalities that are linear in allocation marginals ($\phi_{ij}$'s). This includes feasibility constraints that are the intersection of any two matroids, as well as many other set systems \cite{Schrijver03}.}
%Most of the proofs are in the Appendix due to space constraints. 

After a brief enumeration of our theorems and a couple of figures summarizing our results, we fix our notation and proceed to the technical sections.
We show the following  theorems (and several auxiliary ones along the way): (a) Theorems~\ref{thm:grand theorem symmetric} and \ref{thm:grand theorem independent} state our algorithmic results: If a reduced form auction for independent bidders and a single item is given to us as input, we can efficiently determine if the auction is feasible or not. If it is feasible, we efficiently compute an efficient process that implements it. If it is infeasible, we efficiently provide a hyperplane separating it from the set of feasible mechanisms. These results extend to multi-item settings with additive, independent bidders and arbitrary correlation in the values of each bidder for the items. (b) Theorems~\ref{thm: iidhierarchy} and \ref{thm:non-iidhierarchical} are the core of our characterization result: Every feasible reduced form auction for a single item and independent bidders can be implemented as a distribution over hierarchical mechanisms. Using these theorems we obtain a clean, characterization of the allocation rule of all multidimensional mechanisms for multi-item settings with independent, additive bidders and arbitrary correlation in the values of each bidder for the items. Our characterization result is provided in Section~\ref{sec:characterization}. (c) Theorem~\ref{thm: independent} provides our analog of Myerson's virtual values. It states that we can transform the marginal probabilities $\pi$s of a reduced form into \emph{virtual $\pi$s} such that the total ordering of the types (across different bidders) induced by the virtual $\pi$s allows us to, in linear time, verify the feasibility of a reduced form auction or output a hyperplane separating it from the set of feasible reduced forms. {(d) Theorem \ref{thm: general} proves a generalization of Border's Theorem {to a broad class of feasibility constraints that includes} the case of many items, many additive bidders with hard demand constraints, and arbitrary value correlation across items or bidders.}

{Figures~\ref{fig: feasibility} and~\ref{fig:optimal} summarize the current state of affairs on the two fronts studied in this paper. The first is on {efficiently implementing as well as characterizing the allocation rule of} feasible reduced forms, while the second is on efficiently solving the optimal multi-dimensional mechanism design problem. The second only records mechanisms that achieve optimal or near-optimal revenue, i.e. come $\epsilon$-close to optimal revenue for arbitrary accuracy $\epsilon$. In particular, we do not quote constant factor approximations~\cite{alaei,BGGM,CHMS}, which are not the focus of this work. The ``Item-Symmetric'' column of the second figure refers to settings that are symmetric with respect to the items (see Section~\ref{sec:optimal} for a formal definition of such settings and~\cite{DW} for a discussion), while the ``Bidder-Symmetric'' column to settings that are symmetric with respect to the bidders (see Section~\ref{sec:optimal} and~\cite{DW} for a formal definition/discussion). Moreover, the ``Many items, Few bidders'' row refers to settings where the number of bidders is an absolute constant but the number of items, $n$, is allowed to scale, and the ``Few items, Many bidders'' row refers to settings where the number of items is held constant but the number of bidders, $m$, is allowed to scale. Finally, in the cells of the same table we stress components of the running time/the setting that are the best we could hope for, and do not stress components that could be improved, leaving these improvements to future work.}
\begin{figure}[h!]
\centering
\begin{tabular}{|c|c|c|c|}
\hline & Necessary\&Sufficient  & Efficient & Characterization of\\
& Feasibility Conditions & Implementation & Feasible Mechanisms\\
\hline
Independent Bidders, & \cite{border,border2007,CKM} & {\bf [this work]}  & {\bf [this work]} \\
No Demand Constraints & & (\& independently~\cite{AFHHM}, & \\
 & & for single-item auctions)  & \\

\hline
Correlated Bidders, & {\bf [this work]} & Open Question & Open Question \\
Demand Constraints, & & & \\
{and Broader Settings}$^{\dag}$& & &\\
\hline
\end{tabular}
{\footnotesize
 \begin{enumerate}
 \item[$\dag$:] See Section~\ref{sec: generalized border}.
\end{enumerate}}
\caption{{Feasibility, Efficient Implementation and Characterization of Reduced Form Multi-Item Auctions. The bidders are additive up to (if stated) some hard demand constraint. Both lines allow correlation of values across different items, but the first row assumes that bidders have independent valuations while the second also allows correlation across bidders.}} \label{fig: feasibility}
\end{figure}
\begin{figure}[h!]
\noindent \begin{tabular}{|c|c|c|c|}
\hline
&Item-Symmetric&Bidder-Symmetric&\textbf{No Symmetries}\\
\hline
\textbf{Many items,}& \textbf{ poly(n)}$^{\dag}$, &  & \textbf{ poly(n)}$^{\S}$,\\
Few bidders & \textbf{demand constraints}, & Same as $\longrightarrow$ & no demand constraints,\\
& \textbf{item correlation} \cite{DW} & & MHR independent items~\cite{CH}\\
\hline
Few items, & Same as below  & \textbf{poly(m)}$^{\dag}$, & Same as below  \\
\textbf{Many bidders} & {\bf [this work]} & \textbf{demand constraints}, & {\bf  [this work]}\\
& & \textbf{item correlation} \cite{DW} &\\
\hline 
\textbf{Many items} & \textbf{poly(n,m)}$^{\dag}$, &  & \textbf{poly}($\sum_i |T_i|$)$^{\ddag}$,\\
\textbf{Many bidders} & no demand constraints, &Same as $\longrightarrow$  & no demand constraints,\\
 & \textbf{item correlation}  & {\bf [this work]}& \textbf{item correlation} \\
 &  {\bf [this work]} & &  {\bf  [this work]}\\
 \hline
 \end{tabular}
 {\footnotesize
 \begin{enumerate}
 \item[$\S$:] For all $\epsilon >0$, a $(1-\epsilon)$-fraction of the optimal revenue is achieved in the quoted running time. $1/\epsilon$ appears in the exponent of the running time.
\item[$\dag$:] Exactly optimal revenue is achieved in the quoted running time, when every marginal of the bidders' value distributions has constant size support. The size of the support appears in the exponent of the running time. When the size of the support is non-constant/infinite/unbounded, two types of PTAS's are obtained:
\begin{itemize}
\item When every marginal is MHR, a $(1-\epsilon)$-fraction of the optimal revenue is achieved in the quoted running time, for all $\epsilon>0$.
\item When the value distributions are bounded and normalized to $[0,1]^n$, an additive approximation to the optimal revenue is achieved in the quoted running time, for all $\epsilon>0$. The approximation error is $\epsilon \cdot \min\{n, \sum_i C_i\}$, where $C_i$ is the demand constraint of bidder $i$ (if any).
\end{itemize}
\item[$\ddag$:] Exactly optimal revenue is achieved in the quoted running time, where recall that $T_i$ is the support of the value distribution of bidder $i$. When the supports are infinite/unbounded
we can alternatively obtain two types of approximation schemes:
\begin{itemize}
\item When every marginal of the bidders' value distributions is MHR, a $(1-\epsilon)$-fraction of the optimal revenue is achieved in time polynomial in $m$ and $(1/\epsilon)^n$, for all $\epsilon>0$.
\item When the value distributions are bounded and normalized to $[0,1]^n$, an additive approximation to the optimal revenue is achieved in time polynomial in $m$ and $(1/\epsilon)^n$, for all $\epsilon>0$. The approximation error is $\epsilon \cdot n$.
\end{itemize}
\end{enumerate}
 }
\caption{{Efficient Solution to the Optimal Multi-Dimensional Mechanism Design Problem with Independent Bidders. The bidders are additive up to (if stated) some hard demand constraint.}
} \label{fig:optimal}
\end{figure}

\bigskip {\noindent {\bf Parallel Work}: We have been informed that, independently from us, \cite{AFHHM} also obtained polynomial-time algorithms for checking the feasibility of a given { single-item} reduced form auction, when the bidders are independent, as well algorithms for efficiently implementing the reduced form, if it is feasible. (See Figure~\ref{fig: feasibility} for where their results fit with respect to our results). \cite{AFHHM} apply their algorithms to ``service constrained'' multi-dimensional mechanism design environments, which are orthogonal to the mechanism design settings considered here.}

%(a) In Theorem~\ref{thm:grand theorem symmetric}, we state that if  a feasible bidder-symmetric reduced form auction is given to us as an input, we can efficiently implement it. (b) In Theorem~\ref{thm: iidhierarchy}, we state a characterization result that if the bidders are i.i.d., then every bidder-symmetric reduced form can be implemented by a distribution over hierarchical mechanisms. (c) In Theorem~\ref{thm: independent}, we show that we can construct virtual $\pi$s, based on the $\pi$s from the reduced form auction. The virtual $\pi$s provide a total ordering of the types (across different bidders) that allow us to, in linear time, verify the feasibility of a reduced form mechanism, or output a hyperplane separating it from the space of feasible reduced forms. (d) Theorem ~\ref{thm:grand theorem independent} states that we can find and implement any feasible auction for independent bidders in polynomial-time (e) In Theorem~\ref{thm:non-iidhierarchical}, we extend the result in Theorem~\ref{thm: iidhierarchy} to independent but not necessarily identical bidders. (f) In Theorem \ref{thm: general}, we prove a generalization of Border's Theorem to the case of many items and arbitrarily correlated bidders with demand constraints.
%\costasnote{REMOVE? In brush strokes, they work as follows: Find some relaxed feasibility constraints that the reduced form of a feasible mechanism must satisfy, such as ``every item can be awarded at most once in expectation'' \cite{alaei,BGGM} or ``the expected number of items awarded from every subset must not exceed its rank'' \cite{CHMS}. Then come up with a ``rounding'' procedure that takes a reduced form satisfying the relaxed feasibility constraints and turns it into an auction whose revenue is only a constant factor less; this procedure may divide the reduced form satisfying the relaxed constraints by a constant \cite{alaei,BGGM}, or solve a prophet inequality \cite{alaei,CHMS}. To put everything together, write some convex program~\cite{alaei,BGGM} or make a reduction to Myerson's auction in a related setting~\cite{CHMS} to find a reduced form satisfying the relaxed feasibility constraints whose revenue upper bounds the revenue of the optimal auction (in the original setting). Then use your rounding procedure to turn this into a feasible reduced form at a loss in revenue. At the end of the day, the best we can hope for  is a constant factor approximation, as we have relaxed the feasibility constraints on the reduced form in order to be able to optimize efficiently. In view of this computational experience with the problem, it natural to try to characterize the feasible reduced forms exactly in a way that makes optimization efficient. }

\section{Preliminaries and notation}\label{sec:notation}
Throughout the paper, we denote the number of bidders by $m$ and the number of items by $n$. We also use $T_i$ to denote the types of bidder $i$. We make no assumptions about $T_i$ except that it is measurable. In particular, it is not assumed that $T_i$ is a subset of $\mathbb{R}$, and it could well be multidimensional; e.g., {when a bidder has additive valuations,} the type of the bidder could  be just a vector specifying how much she values each of the items. To obtain computationally meaningful results, we assume in Sections~\ref{sec:reduced},~\ref{sec:characterization} and~\ref{sec: generalized border} that the type sets $\{T_i\}_i$ are finite (as opposed to continuous/infinite, but not of constant size), and in this case use $c$ as a shorthand for $\max_i |T_i|$. However, our results in Section~\ref{sec:optimal} apply also to continuous type spaces, since {when the type distributions are bounded or when they are unbounded but satisfy the \textsl{Monotone Hazard Rate} tail condition,~\footnote{We say that a one-dimensional differentiable distribution $F$ satisfies Monotone Hazard Rate, or succinctly MHR, if $\frac{f(x)}{1-F(x)}$ is monotonically non-decreasing in its domain, where $f = F'$ is the probability density function.} we can truncate and discretize the support of the distribution and still get nearly optimal $\epsilon$-BIC mechanisms (Definition~\ref{def:BIC}) using the techniques of~\cite{CD} or~\cite{DW}. We can then employ the $\epsilon$-BIC to BIC reduction of~\cite{DW} to get nearly optimal BIC mechanisms. See Section~\ref{sec:optimal} for details.}

To ease notation, we  just use $A$ ($B$, $C$, etc.) to denote the \emph{type} of a bidder, without emphasizing whether it is a vector or a scalar. The elements of $\times_i T_i$ are called {\em type profiles}, and specify a type for every bidder. We assume type profiles are sampled from a distribution ${\cal D}$ over $\times_i T_i$. We denote by ${\cal D}_i$ the marginal of this distribution on bidder $i$'s type, and use ${\cal D}_{-i}$ to denote the marginal of ${\cal D}$ over the types of all bidders, except bidder $i$.  We use $t_i$ for the random variable representing the type of bidder~$i$. So when we write $\Pr[t_i = A]$, we mean the probability that bidder $i$'s type is $A$. In the i.i.d. case, because $\Pr[t_i = A]$ is the same for all $i$, we will just write $\Pr[A]$.

The {\em reduced form} of a mechanism is {a vector function $\pi(\cdot)$,} specifying values $\pi_{ij}(A)$, for all items $j$, bidders $i$ and types $A \in T_i$. $\pi_{ij}(A)$ is the probability that bidder $i$ receives item $j$ when reporting type $A$, where the probability is over the randomness of all other bidders' types and the internal randomness of the mechanism, assuming that the other bidders report their true types to the mechanism. When we only consider a single item (case $n=1$), we  drop the item subscript from the $\pi_{ij}$'s,  writing $\pi_i(A)$ for the probability that the item is allocated to bidder $i$.  {In this case we may  think of ${\pi}(\cdot)$ as a vector in {$[0,1]^{\sum_{i} |T_{i}|}$}. %$\mathbb{R}^{\sum_i |T_i|}$. 
 To emphasize the vector-view of the reduced form we may write $\vec{\pi}$ for the reduced form.}

Sometimes we will  be considering settings where the bidders are i.i.d., i.e. $T_i=T_{i'}=T$, for all $i$ and $i'$, and ${\cal D}$ is a product distribution over $\times_i T_i$ with the same marginal on every bidder. In such settings, we may be looking at {\em bidder-symmetric} reduced forms, satisfying $\pi_{ij}(A) = \pi_{i'j}(A)$, for all $j,i,i', A\in T$. In such cases, we will drop the bidder subscript from the $\pi_{ij}$'s, writing $\pi_j(A)$, for the probability that a bidder of type $A \in T$ receives item $j$, over the randomness of the mechanism and the types of the other bidders, {assuming that the other bidders report their true types to the mechanism.} If there is a single item and the reduced form is bidder-symmetric, we will drop both subscripts writing $\pi(A)$ for the same probability. {In this case, we may think of the reduced form as a vector $\vec{\pi}$ in {$[0,1]^{ |T|}$}.}
 
Given a reduced form ${\pi}$ of a mechanism we will be interested in whether the form can be ``implemented''.  By this we mean designing a feasible mechanism $M$ (i.e. one that never over-allocates items) such that the probability $M_{ij}(A)$ that bidder $i$ receives  item $j$ when she reports type $A$ to the mechanism is exactly $\pi_{ij}(A)$, where the probability is computed with respect to the randomness in the mechanism and {the randomness in the types of the other bidders, assuming that the other bidders report their true types to the mechanism.} In fact, we will relax this requirement and say that a mechanism $M$ implements the reduced form ${\pi}$ if $M_{ij}(A) \geq \pi_{ij}(A)$, for all $i,j,A$. This is because we can trivially modify such a mechanism so that all constraints are tight. Indeed, if $M_{ij}(A) = x \cdot \pi_{ij}(A)$ for some $i,j,A, x>1$, we can rectify the mechanism as follows: whenever $M$ wants to allocate item $j$ to bidder $i$ when he has reported type $A$, we instead throw the item away  with probability $\frac{x-1}{x}$. It's easy to see that this results in $M_{ij}(A)=\pi_{ij}(A)$. When $M_{ij}(A) = \pi_{ij}(A)$ for all $i,j,A$, we will say that $M$ \emph{exactly} implements $\pi$. Finally, if a reduced form can be implemented by a mechanism, we  say that the reduced form is {\em feasible}.


When a bidder is additive, we may write $\vec{v}_i$ to denote her type, with the convention that $v_{ij}$ represents her value for item $j$ and that her value for a bundle of items is just the sum of her values for the items in the bundle. Then, to fully specify a (direct-revelation) multi-item mechanism for additive bidders, we need to describe, potentially succinctly, for all type profiles $\vec{v} \in \times_i T_i$, and for every bidder $i$, the outcome $M_i(\vec{v}) = (\vec{\phi}_i(\vec{v}), p_i({\vec{v}}))$ given by $M$ to bidder $i$, when the reported bidder types are $\vec{v}$, where $\phi_{ij}(\vec{v})$ is the probability that item $j$ is given to bidder $i$ and $p_i({\vec{v}})$ is the price that $i$ pays. The {\em value} of bidder $i$ for outcome $M_i(\vec{w})$ is just her expected value $\vec{v}_i \cdot \vec{\phi}_i(\vec{w})$ for the bundle allocated to her, while the {\em utility} of bidder $i$ for the same outcome is $U(\vec{v}_i,M_i(\vec{w})):=\vec{v}_i \cdot \vec{\phi}_i(\vec{w}) - p_i(\vec{w})$. Such bidders subtracting price from expected value are called {\em quasi-linear.} The relation between $\phi$'s and $\pi$'s is just the following: for all $i$, $\vec{v}_i \in T_i$: $\pi_{ij}(\vec{v}_i)=\mathbb{E}_{\vec{v}_{-i}\sim {\cal D}_{-i}}[\phi_{ij}(\vec{v}_i~;~\vec{v}_{-i})]$, where the expectation is computed with respect to the values $\vec{v}_{-i}$ of all bidders except $i$ as these are drawn from ${\cal D}_{-i}$. We conclude by formally defining Bayesian Incentive Compatibility:


\begin{definition}[\cite{DW}](BIC/$\epsilon$-BIC Mechanism)\label{def:BIC} A mechanism $M$ is called $\epsilon$-BIC iff the following inequality holds for all $i,\vec{v}_i,\vec{w}_i$:
$$\mathbb{E}_{\vec{v}_{-i} \sim {\cal D}_{-i}}\left[U(\vec{v}_i,M_i(\vec{v}))\right] \ge \mathbb{E}_{\vec{v}_{-i} \sim {\cal D}_{-i}}\left[ U(\vec{v}_i,M_i(\vec{w}_i~;~\vec{v}_{-i})) \right] - \epsilon v_{\max} \cdot \sum_j \pi_{ij}(\vec{w}_i),$$
where $v_{\max}$ is the maximum possible value of any bidder for any item in the support of the value distribution. In other words, $M$ is $\epsilon$-BIC iff when a bidder lies by reporting $\vec{w}_i$ instead of $\vec{v}_i$, they do not expect to gain more than $\epsilon v_{\max}$ times the expected number of items that $\vec{w}_i$ receives. A mechanism is called BIC iff it is $0$-BIC.~\footnote{{This definition differs slightly from the more common definition of \cite{BH,HKM,HL}. We use the definition of \cite{DW} to be correct in applying their results.}}
\end{definition}


{We conclude our preliminaries section noting that the running times of the algorithms obtained in Sections~\ref{sec:overview iid} and~\ref{sec:overview independent} are quoted without accounting for the number of bits needed to represent a coordinate of $\vec{\pi}$. If $\ell$ bits are needed to describe a probability in $\vec{\pi}$, then it suffices to multiply all quoted running times by a ${\rm poly}(\ell)$ factor.}

\section{Overview of Results and Techniques} \label{sec:overview}

\subsection{Feasible Reduced Forms} \label{sec:reduced}

\subsubsection{Single-item, Bidder-Symmetric Reduced Forms, i.i.d. Bidders} \label{sec:overview iid}
In the case of a single item and i.i.d. bidders, Border provided a necessary and sufficient condition for a bidder-symmetric reduced form to be feasible, generalizing prior partial results of Maskin-Riley~\cite{maskinriley} and Matthews~\cite{matthews}. Let us review Border's theorem.
\vspace{-3pt}\begin{theorem}[\cite{border}] \label{thm:border} Suppose that the bidder's types are i.i.d. distributed according to some measure $\mu$ over $T$. Then a bidder-symmetric reduced form ${\pi}$ is feasible if an only if
\begin{align}\forall S \subseteq { T}:~~ m \cdot \int_S \pi(t) d\mu(t) \le 1-(1-\mu(S))^m.\label{eq:border's condition}\end{align}
\end{theorem}
\noindent Simply put,  a reduced form is feasible if and only if the probability that the item is awarded to a type in some set $S$ (as computed by the reduced form) is at most the probability that someone with type from $S$ shows up to the auction (as computed by the type distribution), for all subsets of types $S \subseteq T$. We call a set that violates this condition a {\em constricting set}. Clearly, the existence of a constricting set bears witness that the reduced form is infeasible, as the auctioneer cannot possibly award the item to someone in $S$ if no one in $S$ shows up. Border's theorem states that this is in fact a sufficient condition. 

Border's original paper considered continuous type spaces (hence the integral in~\eqref{eq:border's condition}), and the proof was based on measure theory. The following extension of the theorem was also shown: If there exists a constricting set $S$, then there is also a constricting set of the form $S_x$, where $S_x = \{A | \pi(A) > x\}$, for some $x$. In the case of finite type spaces, we can determine the feasibility of a reduced form auction in {time $O(c\log c + c \cdot m)$}, where $c=|T|$, as after sorting the type space in decreasing $\pi$'s there are only $c$ different subsets of the form $S_x$, and a dynamic program can find us if any of them violates~\eqref{eq:border's condition} in time $O(c\cdot m)$. In other words, determining the feasibility of a bidder-symmetric reduced form, for a single item, and many i.i.d. bidders is easy. However, the following important question was left unanswered: Given a feasible reduced form, can we efficiently obtain a mechanism implementing the reduced form? {Notice that answering this question in the affirmative is absolutely necessary to be able to run the auction specified by the reduced form.} Our first contribution is solving this problem.
% Indeed, it suffices to find a feasible {\em ex-post allocation function} $\phi: \times_i {\cal T}_i \rightarrow [0,1]^m$ satisfying that, for all $i$, $t_i \in {\cal T}_i: \pi_i(t_i)= \mathbb{E}_{t_{-i} \sim {\cal D}_{-i}|t_i} \phi(t_1,\ldots,t_n)$, where ${\cal D}_{-i}|t_i$ is the conditional distribution of all but bidder $i$'s types conditioning on bidder $i$'s type being $t_i$. We interpret $\phi_i(\vec{t})$ as the probability (over the randomness of the mechanism) that the item is allocated to bidder $i$ when the bid vector is $\vec{t}$, and $\pi_i(t_i)$ as the expectation (over the bids of the other bidders and the randomness in the mechanism) of  $\phi_i(\vec{t})$. 

\vspace{-4pt}\begin{theorem}\label{thm:grand theorem symmetric}
Under the same assumptions as Theorem~\ref{thm:border}, given a bidder-symmetric reduced form we can  determine if it is feasible, or find a hyperplane separating it from the set of feasible bidder-symmetric reduced forms, in time {$O(c\cdot(\log c+ m))$}, where $c=|T|$. If the reduced form is feasible, we provide a succinct description of a mechanism implementing the reduced form, in time polynomial in $c \cdot m$. The description of the mechanism is just (at most) $c+1$ probabilities and an equal number of orderings of $T$. \footnote{An ordering may have equalities, but must be total (compare every pair of elements in $T$).}  The mechanism itself runs as follows: given the reported type profile, the mechanism samples a random subset of bidders in time ${\rm poly}(m,c)$, and  the item is allocated uniformly at random to some bidder in that subset, or the item is thrown away.
\end{theorem}

We prove Theorem \ref{thm:grand theorem symmetric} in Appendix~ \ref{app: iid}, as a corollary of Proposition~\ref{prop: iidcorners} and Theorem~\ref{thm: polytope} of Appendices \ref{app: iid} and \ref{app: polytope} respectively. In proving our result, we consider the following type of mechanisms:

\begin{definition}\label{def:hierarchy} 
A \textbf{hierarchical mechanism} consists of a function $H: T \rightarrow [c]\cup \{\lose\}$; one should interpret $\lose$ as a value larger than $c$. On bid vector $(A_1,\ldots,A_m)$, the mechanism has the following behavior: If $H(A_{i})=\lose$ for all $i$, the mechanism throws the item away. Otherwise, the item is awarded uniformly at random to a bidder in $\argmin_i H(A_i)$.
\end{definition}
\noindent In other words, a hierarchical mechanism breaks down the type space into a hierarchy. When the bidders arrive and submit their types, the mechanism finds the highest-priority level of the hierarchy that is populated by the submitted types, and gives the item uniformly at random to a bidder whose type falls in that level of the hierarchy (unless every bidder is a loser, in which case the mechanism throws the item away). We say that a hierarchical mechanism $H$ is \emph{well-ordered} w.r.t. ${\pi}$ if: $\pi(A) \geq \pi(A') \Rightarrow H(A) \leq H(A')$. We prove the following characterization result about feasible bidder-symmetric reduced forms:

\begin{theorem}\label{thm: iidhierarchy} When bidders are i.i.d., every feasible bidder-symmetric reduced form $\pi$ can be exactly implemented as a distribution over at most $c+1$ well-ordered with respect to $\pi$ hierarchical mechanisms.
\end{theorem}

 Theorem~\ref{thm: iidhierarchy} alone is not enough to allow us to implement a given bidder-symmetric reduced form. Indeed, if $\pi(\cdot)$ takes $\theta$ (can be as large as $c$) distinct values, there are $2^\theta$ different well-ordered w.r.t. $\pi$ hierarchical mechanisms. From here, we switch to our vector-view of reduced forms (as vectors $\vec{\pi}$ in {$[0,1]^{|T|}$}) and study the geometry of the space of feasible mechanisms respecting the order on the type-space induced by a given reduced form $\vec{\pi}$, which we will call $P$. We show that, in fact, $P$ is a {$\theta$}-dimensional polytope whose corners are \emph{exactly} the {$2^\theta$} different well-ordered w.r.t. $\vec{\pi}$ hierarchical mechanisms.
 We provide a geometric algorithm in Appendix~\ref{app: polytope} that in polynomial time outputs a representation of $\vec{\pi}$ as a convex combination of at most $c+1$ corners of $P$. This convex combination is exactly a distribution over well-ordered w.r.t. $\vec{\pi}$ hierarchical mechanisms that implements $\vec{\pi}$. Our geometric algorithm runs in time $\poly(m,c)$, and sampling from the distribution output by our algorithm {also takes time ${\rm poly}(m,c)$}. We provide the details of our approach and proofs of the relevant claims in Appendices~\ref{app: iid} and~\ref{app: polytope}.
 
 %However, we show that the crucial information about a distribution over hierarchical mechanisms is really just the probability that there is a level containing the types $A$ through $A'$, for all $A,A'$. This is because we can compute the probability that a bidder of certain type receives the item using only these probabilities. We write linear constraints to determine whether a collection of such probabilities is feasible, and add these constraints into a linear program to find the corresponding probabilities of a distribution over hierarchical mechanisms that implements the reduced form; and once we have these probabilities, it is easy to sample from a distribution over hierarchical mechanisms matching these probabilities. In the end, we obtain an algorithm that runs in time $\poly(m,c)$ and outputs the description of a distribution over hierarchical mechanisms that implements the reduced form, together with a $O(mc)$ algorithm for sampling from this distribution for any given type profile. The details of our approach, and the proofs of the relevant claims are in Section \ref{sec: iid}.

\subsubsection{Single-item, General Reduced Forms, Non-i.i.d. Bidders} \label{sec:overview independent}

Recently, an alternative proof of Border's theorem for distributions with finite support was discovered in~\cite{border2007} and again in~\cite{CKM}, the latter using a clean network-flow interpretation. These proofs extend Theorem~\ref{thm:border} to independent, but not necessarily identical, bidders and non-symmetric reduced forms. In this case, \eqref{eq:border's condition} is replaced by the following necessary and sufficient condition:
\begin{align}\forall S_1 \subseteq { T}_1,\ldots,S_m\subseteq { T}_m: \sum_{i} \sum_{A \in S_i}  \pi_i(A) \Pr[t_i=A] \le 1-\prod_{i}(1-\Pr[t_i \in S_i]).\label{eq:feasibility condition non symmetric}\end{align}
The interpretation of the LHS and RHS of the above inequality is the same as the one given above for~\eqref{eq:border's condition} except generalized to the non-iid non-symmetric setting. In addition to the above condition, \cite{CKM} proves a generalization of Border's extended result: If there is a constricting $S=(S_1, \ldots,S_m)$, then there is also a constricting set of the form $S' = (S^{(1)}_{x_1}, \ldots, S^{(m)}_{x_m})$, where $S^{(i)}_{x_i} = \{A \in T_i | \pi_i(A) > x_i\}$. In other words, each bidder has a different threshold $x_i$, and $S^{(i)}_{x_i}$ contains all types of bidder $i$ with $\pi_i$ above $x_i$. Unfortunately, despite this simplification, there are still {$\prod_i (|{ T}_i|+1)$} possible constricting sets, and testing each of them would take time exponential in the number of bidders. 

One might hope to obtain a stronger theorem that would {only require testing a number of sets polynomial in $c$ and $m$}.
%time polynomial in the number of bidders. 
We prove such a theorem by introducing a notion of a \emph{virtual} $\pi$, defined next. We name it such not because the equation involves hazard rates or looks anything like that for virtual valuations~\cite{myerson}, but because the spirit of the transformation is the same. Myerson observed that he could make the most revenue not from the bidder with the highest valuation, but from the bidder with the highest virtual valuation. Likewise, in our setting, the most difficult types to satisfy are not the types with the highest $\pi$, but the types with the highest virtual $\pi$. The definition of virtual $\pi$, which we denote $\hat{\pi}$, is actually quite simple.  
\begin{definition}\label{def:virtual pi} If $\pi$ is a reduced form, we define its corresponding {\em virtual reduced form $\hat{\pi}$} as follows: for all $i$ and type $A \in T_i$, $\hat{\pi}_i(A):=\Pr[\pi_i(t_i) \leq \pi_i(A)]\pi_i(A)$.
\end{definition}
%\begin{definition} Let $\tau_i$ denote the random variable that equals $\pi_i(t_i)$, where $t_i$ is sampled from $\mu_i$. For all $t_i \in {\cal T}_i$, we define $\hat{\pi}_i(t_i) :=\Pr[\tau_i \leq \pi_i(t_i)]\pi_i(t_i)$. The function $\hat{\pi}_i$ is called {\em virtual $\pi_i$}. 
%\end{definition}
\noindent It turns out that this definition exactly captures which types of different bidders are harder to satisfy. In the bidder-symmetric case of Section~\ref{sec:overview iid}, we were able to compare a pair of types $A$ and $B$ submitted by bidders $i\neq k$ based only on their corresponding $\pi_i(A)$ and $\pi_k(B)$. This is no longer the case in the non-iid case, resulting in the more complicated constricting sets defined above. Nevertheless, we show that $A$ and $B$ can be compared at face value of $\hat{\pi}_i(A)$ and $\hat{\pi}_k(B)$:
\begin{theorem}\label{thm: independent} Suppose that the bidders are independent and there is a single item for sale. A reduced form $\pi$ is feasible if and only if: for all $x$, the sets $S^{(i)}_x = \{A \in T_i|\hat{\pi}_i(A)>x\}$ satisfy:
\begin{align}\sum_{i} \sum_{A \in S^{(i)}_x}  \pi_i(A) \Pr[t_i=A] \le 1-\prod_{i}(1-\Pr[t_i \in S^{(i)}_x]).\label{eq:our virtual feasibility condition}\end{align}
In particular, we can test the feasibility of a reduced form, or obtain a  hyperplane separating the reduced form from the set of feasible reduced forms, in {time linear in {$\sum_i |T_i| \cdot \left(\log\left(\sum_i |T_i|\right)  + m\right)$}}.
\end{theorem}
\noindent Details of the proof can be found in Appendix~\ref{app:independent}. We also prove there two analogues of Theorem~\ref{thm: iidhierarchy} in this setting: Theorem \ref{thm: independenthierarchy}, which is used for our algorithmic results, and Theorem \ref{thm:non-iidhierarchical}, which provides a much stronger characterization. The analog of Definition~\ref{def:hierarchy} is the following:

\begin{definition}
A \textbf{hierarchical mechanism} consists of a function $H: \bigcup_i (T_i \times \{i\}) \rightarrow [\sum_i|T_i|] \cup \{\lose\}$; one should interpret $\lose$ as a value larger than $\sum_i|T_i|$. On bid vector $(A_1,\ldots,A_m)$, if  {$H(A_{i},i)=\lose$} for all $i$, the mechanism throws the item away. Otherwise, the item is awarded uniformly at random to a bidder in {$\argmin_i H(A_i,i)$.}
%On bid vector $(A_1,\ldots,A_m)$, the mechanism awards the item uniformly at random to a bidder in $\argmin_i H(A_i,i)$. If $\argmin_i H(A_i,i)$ is empty because $H(A_i) = \lose$ for all $i$, then the item is thrown away.
\end{definition}

We say that a hierarchical mechanism $H$ for non-identical bidders is \emph{partially-ordered} {w.r.t. $\pi$} if for all $i$ and $A,A' \in T_i$, $\pi_i(A) \geq \pi_i(A') \Rightarrow H(A,i) \leq H(A',i)$. We say that a hierarchical mechanism is \emph{strict} if for all bidders $i,j$ and types $A \in T_i$, $B \in T_j$: { $i \neq j \Rightarrow (H(A,i) \neq H(B,j) \vee H(A,i) = H(B,j) = \lose)$} (i.e. there is always a unique winner in $\argmin_i H(A_i,i)$ if one exists, because each level {(except possibly for \lose)} contains types from only a single bidder). Our algorithmic extension of Theorem~\ref{thm: iidhierarchy} is the following:

\begin{theorem}\label{thm: independenthierarchy} When bidders are independent, but not necessarily identically distributed, every feasible reduced form $\pi$ can be exactly implemented as a distribution over at most $\sum_i |T_i| +1$ strict, partially-ordered w.r.t. $\pi$ hierarchical mechanisms.
\end{theorem}

From here, we take the same geometric approach as in Section \ref{sec:overview iid} and study the geometry of the set of feasible reduced forms that respect the partial-ordering of types induced by a given reduced-form $\pi$. Again we show that this is a {$(\sum_i d_{i})$-dimensional polytope, $P$, where $d_{i}$ (could be as large as $|T_{i}|$) is the number of distinct values that $\pi_{i}(\cdot)$ takes on input from $T_{i}$,} and that the corners of $P$ are \emph{exactly} the strict, partially-ordered w.r.t. $\pi$ hierarchical mechanisms. Writing a point in $P$ as a convex combination of $\sum_i |T_i| +1$ corners is no longer an easy procedure. Not only does $P$ have an exponential number of corners, but there are also exponentially many hyperplanes defining the boundary of $P$ (where there were only $2\cdot c$ such hyperplanes in the i.i.d. case). Luckily, Theorem \ref{thm: independent} provides an efficient separation oracle for membership in $P$. By making use of this separation oracle instead of checking the exponentially-many boundary equations one by one, the geometric algorithm of Appendix \ref{app: polytope} outputs a representation of a given ${\pi}$ as a convex combination of at most $\sum_i |T_i| + 1$ corners of $P$, which is exactly a distribution over the corresponding $\sum_i |T_i| + 1$ strict, partially-ordered w.r.t. $\pi$ hierarchical mechanisms. Putting this approach together with Theorems \ref{thm: independent} and \ref{thm: independenthierarchy}, we obtain in Appendix~\ref{app:independent} the algorithmic result of this section:

\begin{theorem}\label{thm:grand theorem independent} When bidders are independent, given a reduced form we can  determine if it is feasible, or find a hyperplane separating it from the set of feasible reduced forms, in time linear in {$\sum_i |T_i| \cdot \left(\log\left(\sum_i |T_i|\right)  + m\right)$}. If the reduced form is feasible, we can compute a succinct description of a mechanism implementing the reduced form, in time polynomial in $\sum_i |T_i|$. {The description of the mechanism is just {(at most) $\sum_i |T_i| +1$} probabilities and the same number of total orderings of $\bigcup_i (T_i \times \{i\})$.} {The mechanism itself runs as follows: given the reported type profile, the mechanism samples a random total ordering of all bidders' types in {time polynomial in $\sum_i |T_i|$}, and allocates the item to the bidder whose reported type is highest in that ordering, or throws the item away.}
\end{theorem}


{While Theorem \ref{thm: independenthierarchy} does provide some structure to the otherwise unknown set of feasible mechanisms for independent bidders, the result is not as compelling as that of Theorem \ref{thm: iidhierarchy}. One might have hoped that every feasible reduced form can be implemented as a distribution over \emph{virtually-ordered} hierarchical mechanisms (that is, hierarchical mechanisms such that $\hat{\pi}_i(A) \geq \hat{\pi}_j(B) \Rightarrow H(A,i) \leq H(B,j)$). Unfortunately, this is not true, as is shown in Appendix \ref{app:independent}. Despite this, we show that a strong generalization of Theorem \ref{thm: iidhierarchy} holds in this setting. Let $\sigma$ be a total ordering on the elements of $\bigcup_i (T_i \times \{i\})$ {(i.e. a mapping $\sigma:\bigcup_i (T_i \times \{i\}) \rightarrow [\sum_i |T_i|]$)}. We say that $\sigma$ respects ${\pi}$ if $\pi_i(A) > \pi_i(B) \Rightarrow \sigma(A,i) < \sigma(B,i)$. We also say that a hierachical mechanism $H$ is $\sigma$-ordered if $\sigma(A,i) < \sigma(B,j) \Rightarrow H(A,i) \leq H(B,j)$. We prove the following theorem:}





%We will call such a $\sigma$ a {\em global ordering} of the types of the bidders, as it induces an ordering of bidders' types as follows: if $A_i \in T_i$ and $A_k \in T_k$, then we say $A_i \prec_{\sigma} A_k$ iff $\sigma(A_i,i) < \sigma(A_k,k)$. Given a reduced form $\pi$ we say that a global ordering $\sigma$ respects $\pi$ if, for all $i$ and $A, B \in T_i$: $\pi_i(A) \ge \pi_i(B) \implies A \preceq_{\sigma} B$. Finally, if $\sigma$ is a global ordering of bidders' types we call an hierarchical mechanism $\sigma$-ordered if its ranking $H$ satisfies that: for all $i, k, A_i \in T_i, A_k \in T_k$: $A_i \preceq_{\sigma} A_k \Rightarrow H(A_i,i) \leq H(A_k,k)$. We are now ready to state our result:
\begin{theorem}\label{thm:non-iidhierarchical}
If a reduced form ${\pi}$ is feasible, there exists a total ordering $\sigma$ on the elements of $\bigcup_i (T_i \times \{i\})$ that respects ${\pi}$ such that ${\pi}$ can be implemented as a distribution over $\sigma$-ordered hierarchical mechanisms.

\end{theorem}
\noindent We provide the proof of Theorem~\ref{thm:non-iidhierarchical} in Appendix~\ref{app:hierarchical non iid}.
\subsection{A Simple Characterization of Feasible Multi-dimensional Mechanisms} \label{sec:characterization}

The appeal of Myerson's single-item auction is not only its optimality, but its clean allocation rule. Let us revisit it. In a single-item setting the type-space of each bidder is a subset ${ T}_i \subset \mathbb{R}$, as a bidder's type is  how much she values the item. In brush strokes Myerson's allocation rule is as follows:


\smallskip\noindent $\bullet$ {\em The i.i.d. case:} Suppose that the bidders' values are independently and identically distributed  in $T$. Myerson's auction in this setting maintains a ranking $H: { T} \rightarrow [|{ T}|] \cup \{\lose\}$ (take $\lose:=|T|+1$) satisfying: $A \ge A' \implies H(A) \le H(A')$; i.e. the ranking respects the order on ${T}$ (as a subset of $\mathbb{R}$). If $|H^{-1}(k)| >1$ for some $k$, we can think of the types in $H^{-1}(k)$ as having been {\em ironed} over by $H$. In fact, let us refer to $H$ as an {\em ironing} of ${ T}$. Given the ironing, the allocation rule is simple: on bid vector $(A_1,\ldots,A_m)$, the item is allocated uniformly at random to a bidder in $\argmin_i \{ H(A_i) \}$ (other tie-breaking rules are fine too), or thrown away if $H(A_i) = \lose$ for all $i$. 


%, i.e. $\mu_1=\ldots=\mu_m\equiv\mu$ and ${\cal T}_1=\ldots={\cal T}_m={\cal T}$, and let the reported types of bidders be $t_1,\ldots,t_m \in \mathbb{R}$. Suppose also that there exists a pair of bidders $i$, $j$ such that $t_i > t_j$. Given that the bidders are symmetric, it makes sense to expect that the optimal auction should allocate the item to bidder $i$ at least as often as it allocates it to bidder $j$.

%\smallskip \noindent Indeed this is what it going on in the allocation rule. Based on the shape of distribution $\mu$, as a preprocessing step the auctioneer computes a ranking 

\smallskip \noindent $\bullet$  {\em The non-i.i.d. case:} Suppose that the bidders' values are independent but not necessarily identically distributed. In this case, the allocation rule of Myerson's auction is a bit more complicated. The auction maintains an ironing $H: \cup_i (T_i \times \{i\}) \rightarrow [\sum_i |T_i|] \cup \{\lose\}$ (take $\lose:=\sum_i |T_i|+1$) satisfying: for all bidders $i$, $A_i \ge A'_i \implies H(A_i,i) \le H(A'_i,i)$; i.e. the ironing now only respects the order between types belonging to the same bidder. Given the ironing, the allocation rule is simple: on bid vector $(A_1,\ldots,A_m)$, the item is allocated uniformly at random to a bidder in $\argmin_i \{ H(A_i,i) \}$, or thrown away if $H(A_i,i) = \lose$ for all $i$.

%\costasnote{When the bidders are independent but non-i.i.d., it is not clear anymore whether a pair of bids $t_i$, $t_j$ submitted by bidders with different distributions should be compared at face value. I.e. despite $t_i > t_j$, it is not clear if bidder $i$ should receive the item more often than bidder $j$ in the optimal auction.}
\medskip In multi-item auctions, the type spaces of the bidders are subsets ${ T}_i \subset \mathbb{R}^n$, i.e. are multidimensional, and it is a priori not clear whether feasible mechanisms/optimal mechanisms in these settings always have clean allocation rules. Indeed, it is not even clear that all feasible single-item auctions have a clean allocation rule, such as Myerson's allocation rule in terms of ironings described above. We show a surprising characterization result of feasible multi-item auctions when the bidders are independent, each bidder's type is sampled from an arbitrary distribution over her type space (i.e. we do not assume that the bidder's values for the items are necessarily independent), and the bidders have additive valuations over bundles of items. In particular, our results also characterize the set of all feasible single-item mechanisms. 

As our characterization aims to characterize a broader set of mechanisms, the allocation rules it contains are necessarily more involved, albeit slightly. All we do is introduce randomization over ironings. But what are we ironing exactly? We are still ironing the bidders' type spaces. But instead of having a single ironed surface, we maintain, for each item, a distribution over ironed surfaces. Then the allocation rule of the mechanism is rather simple: on a type profile $(A_1,\ldots,A_m)$ we allocate each item independently from the other items, by just sampling an ironed surface for this item, looking at the highest-priority plateau in this surface that is populated by at least one reported type, and giving the item to a random bidder whose reported type falls in this plateau. 

We proceed to explain how the per-item ironed surfaces look. Given that bidder types are multi-dimensional, ironed surfaces are hard to envision. 
%Nevertheless, we claim that any correlation in the allocation of different items can already be deduced from the reduced form of the mechanism. 
Interestingly, for each bidder $i$ and item $j$, the picture is simplified dramatically when we apply $\pi_{ij}(\cdot)$ to embed the type space $T_i$ of bidder $i$ into $\mathbb{R}$. 

\smallskip \noindent \colorbox{MyGray}{
\begin{minipage}{\textwidth} { {\bf Characterization of Multi-Bidder Multi-Item Auctions for Additive Bidders}

\smallskip The allocation rule used by any multi-bidder multi-item auction for additive bidders to allocate item $j$, for all $j$, may w.l.o.g. take the following form (the reader should draw immediate connections to Myerson's allocation rule described above):

\smallskip \noindent $\bullet$ {\em i.i.d. bidders {\tt and} bidder-symmetric reduced forms:} Suppose that the bidders are i.i.d. and the reduced form $\pi_j$ on item $j$ is bidder-symmetric. In this case, the auction maintains a distribution ${\cal H}_j$ over rankings $H_j: { T} \rightarrow [|{ T}|] {\cup \{\lose\}}$ {(take $\lose:=|T|+1$)} satisfying: $\pi_j(A) \ge \pi_j(A') \implies H_j(A) \le H_j(A')$, for all $A,A' \in T$; i.e. each ranking in the support of ${\cal H}_j$ respects the order induced on ${ T}$ by its embedding into $\mathbb{R}$ by $\pi_j(\cdot)$. If $|H_j^{-1}(k)| >1$ for some $k$ and some ranking $H_j$ in the support of ${\cal H}_j$ we think of the types in $H_j^{-1}(k)$ as having been {\em ironed} over by $H_j$.  Given ${\cal H}_j$, the allocation of item $j$ is simple: on bid vector $(A_1,\ldots,A_m)$, a ranking $H_j$ is sampled from ${\cal H}_j$, and the item is allocated uniformly at random to a bidder in $\argmin_i \{ H_j(A_i) \}$, {or thrown away if $H_j(A_i) = \lose$ for all $i$}.

\smallskip \noindent $\bullet$  {\em Non-i.i.d. bidders {\tt or} different reduced forms:} When the bidders are independent but non-i.i.d. or the reduced form on item $j$ is not bidder-symmetric, the auction maintains a distribution ${\cal H}_j$ over rankings $H_j: \cup_i (T_i \times \{i\}) \rightarrow [\sum_i|{ { T}_i}|] {\cup \{\lose\}}$ {(take $\lose:=\sum_i |T_i|+1$)} satisfying: for all bidders $i$, $\pi_{ij}(A) \ge \pi_{ij}(A') \implies H_j(A,i) \le H_j(A',i)$; i.e. each ranking in the support respects the order between types belonging to the same bidder, for whatever order is induced on ${ T}_i$  by its embedding into $\mathbb{R}$ by $\pi_{ij}(\cdot)$. Additionally, if $H_j$ and $H_j'$ are two rankings in the support of ${\cal H}_j$ then, for all $i,i',A_i \in T_i ,A_{i'} \in T_{i'}$: $H_j(A_i,i) < H_j(A_{i'},i') \implies H_j'(A_i,i) \le H_j'(A_{i'},i')$, i.e. all rankings in the support of ${\cal H}_j$ are consistent with a unique total ordering of $\cup_i (T_i \times \{i\})$. Given ${\cal H}_j$, the allocation of item $j$ is simple: on bid vector $(A_1,\ldots,A_m)$, a ranking $H_j$ is sampled from ${\cal H}_j$, and the item is allocated uniformly at random to a bidder in $\argmin_i \{ H_j(A_i,i) \}$, {or thrown away if $H_j(A_i,i) = \lose$ for all $i$}.
}
\end{minipage}
}

\medskip Our characterization result for single-item settings is an immediate corollary of Theorems~\ref{thm: iidhierarchy} (for the i.i.d. case) and~\ref{thm:non-iidhierarchical} (for the independent case). That the above characterization holds for multi-item settings and additive bidders follows by noting that, given the lack of demand constraints, we can allocate items sequentially and the resulting allocation will be feasible as long as the supply constraints on the items are met, i.e. every item is allocated exactly once.


\subsection{Optimal Multi-Dimensional Mechanism Design} \label{sec:optimal}

The additivity of the bidders notwithstanding, we know that optimal mechanisms in multi-item settings may be quite involved. For example, in~\cite{CMS} it is shown that even when there are two items, and a single additive bidder whose values over the items are i.i.d. regular, a mechanism that sells lotteries over the items makes strictly more revenue than a mechanism that sells each item separately. This result implies that: we {\em should not} auction every item separately; and we {\em should} use the values of bidders on item $j$ to decide how to allocate item $j'$. So if bidder $i$ reports higher value on item $j'$ than bidder $i'$, we should not necessarily expect item $j'$ to go to bidder $i$ more often than bidder $i'$, even if the bidders are i.i.d.. To rephrase, for allocating item $j'$, we cannot just rank the bidders according to their bids on that particular item. We need to instead take into account their bids on all the other items.

Despite such complications, it is possible to use Theorems~\ref{thm:grand theorem symmetric} and~\ref{thm:grand theorem independent} to solve the following problem:

\smallskip\noindent  \framebox{
\begin{minipage}{\hsize}
{\bf The BIC many-many problem.} Given as input $m$ arbitrarily correlated distributions $\mathcal{F}_1,\ldots,\mathcal{F}_m$ over valuation vectors for $n$ items, output a BIC mechanism $M$ whose expected revenue is optimal relative to any other, possibly randomized, BIC mechanism, when played by $m$ additive bidders whose valuation vectors are sampled independently from $\mathcal{F}_1,\ldots,\mathcal{F}_m$.
\end{minipage}}

\smallskip Our approach to solving this problem is to use the separation oracle of Theorems~\ref{thm:grand theorem symmetric} and \ref{thm:grand theorem independent} inside the LPs of~\cite{DW}. Doing so we obtain the following:

\begin{theorem}\label{thm:computation main} There is a solution to the BIC many-many problem with runtime polynomial in $n$, $m$, and $\max_{i\in[m]}|\text{supp}(\mathcal{F}_{i})|$. 
\end{theorem}

\begin{theorem}\label{cor:one} {If, for all $i$, $\mathcal{F}_i$ is item-symmetric} (i.e. invariant under permutations of the item names), there exists a solution to the BIC many-many problem with runtime {polynomial in $m$ and $n^c$, where $c=\max_{i,j}|supp({\cal F}_{ij})|$, where ${\cal F}_{ij}$ is the marginal of ${\cal F}_i$ on item $j$.}
\end{theorem}

{
\begin{theorem}\label{cor:one point five} If, for all $i$, $\mathcal{F}_i$ is item-symmetric and supported on $[0,1]^n$ there is an additive PTAS for the BIC many-many problem whose running time is polynomial in $m$ and $n$ (and doesn't depend on the size of the support of $\mathcal{F}_1,\ldots,\mathcal{F}_m$). For all $\epsilon >0$, the PTAS computes a BIC mechanism whose revenue is within an additive $\epsilon \cdot n$ of the optimal revenue achieved by any BIC mechanism.
\end{theorem}
}


\begin{theorem}\label{cor:two} If, for all $i$, $\mathcal{F}_i$ is item-symmetric and its $n$ marginals satisfy the MHR condition, there is a multiplicative PTAS for the BIC many-many problem whose running time is polynomial in $m$ and $n$ (and doesn't depend {on the size of the support of} $\mathcal{F}_1,\ldots,\mathcal{F}_m$). {For all $\epsilon >0$,} the PTAS computes a BIC mechanism whose revenue is  at least a $(1-\epsilon)$-fraction of the optimal revenue achieved by any BIC mechanism.\end{theorem}

\noindent Further details are provided in Appendix~\ref{app:manymany}.




\subsection{Non-negative Linear Feasibility Constraints} \label{sec: generalized border} 
{Aside from the independent results of \cite{AFHHM}, it is unknown whether Border's theorem applies to other settings, or what the proper statement of Border's Theorem might even be as we depart from the single-item setting. On this front, we prove a generalization of Border's Theorem to settings with \emph{Non-negative Linear Feasibility Constraints}. Throughout this section, $P$ denotes a type profile, and $\vec{\phi}(P)$ denotes an \emph{allocation} in terms of the marginal probability of giving bidder $i$ item $j$, $\phi_{ij}(P)$, when the reported type profile is $P$. {We are interested in the form of the {region} $F$ where $\phi(P)$ needs to lie for there to exist a  distribution over {feasible} allocations of items to bidders consistent with the marginal allocation probabilities specified by $\phi(P)$.} In the following definition, we represent an inequality $h$ as a vector of coefficients {$\vec{c}(h)$}, and a right-hand bound $d(h)$. We say that $h$ is non-negative if every coefficient $c_{ij}(h)$ and $d(h)$ are non-negative. 

\begin{definition} A set of feasible allocations $F \subseteq [0,1]^{m \times n}$ has \textbf{Non-negative Linear Feasibility Constraints} if there exists a set $H$ of non-negative inequalities such that {$\vec{\phi}(P) \in F \Leftrightarrow \vec{c}(h) \cdot \vec{\phi}(P) \leq d(h)$, for all $h \in H$, and $\vec{\phi}(P)\geq \vec{0})$.~\footnote{{Here, we talk about feasible allocations, not feasible mechanisms (or allocation rules). A feasible mechanism for $F$ maps every profile $P$ to a feasible allocation $\vec{\phi}(P) \in F$.}}}
\end{definition}

{In a setting where no bidder $i$ should be given more than $C_i$ items and no item $j$ should be given out more than once,} an application of the Birkhoff-Von Neumann Theorem implies that $F$ has non-negative linear feasibility constraints~\cite{DFK,DW}.~\footnote{In particular, the constraints are: a) $\forall\ i$, $\sum_j \phi_{ij}(P) \leq C_i$, b) $\forall\ j$, $\sum_i \phi_{ij}(P) \leq 1$, and c) $\forall\ i,j$, $\phi_{ij}(P) \geq 0$.} In fact, it is shown in~\cite{Schrijver03} that a much broader range of settings have non-negative linear feasibility constraints, 
including settings where the constraint {on the feasible allocations of items to bidders ${\cal S} \subseteq [m] \times [n]$ can be specified as} the intersection of two arbitrary matroids.~\footnote{In this case, let $rk_i(S)$ denote the rank of set $S$ in matroid $i=1,2$. Then the constraints are: a) $\forall S \subseteq [m] \times [n]$, $\sum_{(i,j) \in S} \phi_{ij}(P) \leq rk_1(S)$, b) $\forall S \subseteq [m] \times [n]$, $\sum_{(i,j) \in S} \phi_{ij}(P) \leq rk_2(S)$, and c) $\forall\ i,j$, $\phi_{ij}(P) \geq 0$.} 
 
Below is our generalization of Border's Theorem to this setting, whose proof can be found in Appendix~\ref{app:generalization of Border}. In the statement of the theorem, $i$ ranges over all bidders, $j$ ranges over all items, and $P$ ranges over all possible type-profiles, with $\Pr[P]$ denoting the probability that profile $P$ is sampled from $\mathcal{D}$ and $P_i$ denoting the type of bidder $i$ in $P$.

\begin{theorem}\label{thm: general} Let $F$ be any set of allocations with non-negative linear feasibility constraints, and $\mathcal{D}$ be any (possibly correlated) distribution over types. Then a reduced form $\vec{\pi}$ is feasible if and only if for all weights $\{W_{ij}(A)\}_{i,j,A} \in [0,1]^{{n} \times \sum_i |T_i|}$:

$$\sum_{i} \sum_{j} \sum_{A \in T_i} W_{ij}(A) \cdot \pi_{ij}(A) \cdot \Pr[t_i = A] \leq \sum_P \Pr[P] \max_{\vec{\phi}(P) \in F} \left\{ \sum_i \sum_j W_{ij}(P_i)\cdot \phi_{ij}(P) \right\}.$$

In other words, for fixed weights $\overrightarrow{W}=\{W_{ij}(A)\}_{i,j,A}$, consider the allocation rule $M(\overrightarrow{W})$ that on profile $P$ picks the max-weight allocation (where the weight of giving item $j$ to bidder $i$ is $W_{ij}(P_i)$). Then a reduced form $\vec{\pi}$ is feasible if and only if for all weights $\overrightarrow{W}$, {the LHS} is at most the expected weight of items awarded by $M(\overrightarrow{W})$.
\end{theorem}

Like in the single-item setting, it is clear that this is a necessary condition. The expected weight of items awarded by any mechanism that implements $\vec{\pi}$ is exactly the {LHS}, and this value clearly must be less than the expected weight of items awarded by $M(\overrightarrow{W})$, as $M$ maximizes this value over all feasible mechanisms. The content of the theorem is that these conditions are indeed sufficient.}

{In addition to a proof of Theorem \ref{thm: general}, we provide in Appendix \ref{app:generalization of Border} two false generalizations of Border's Theorem that fail even for unit-demand i.i.d. bidders in order to motivate the statement of Theorem \ref{thm: general}.}


\subsubsection{Correlated Bidders, Demand Constraints}\label{sec: demandConstraints}


As mentioned previously, without demand constraints {and without correlation among bidders' valuations}, the multi-item allocation problem is no more difficult than the single-item allocation problem, as each item can just be allocated separately {and independently from the other items}. However, either demand constraints or correlation among bidders negates all known results ({including those of Section \ref{sec:reduced}}) about feasible allocations. On this front, we give a multi-commodity flow interpretation of the problem for arbitrarily correlated bidders with demand constraints, which is similar to the network flow interpretation of \cite{CKM}. Simply put, the commodities/goods in our multi-commodity flow problem are denoted $G_{ij}(A)$, for all items $j$, bidders $i$, and types $A \in T_i$. We have a source node for every item, an intermediate node for every possible profile, and a sink node for every type. We put edges from every item node to every intermediate node and every intermediate node to every sink node. The capacities on the source-intermediate edges are chosen to ensure that each item is only given out once. The capacities on the intermediate-sink edges are chosen to ensure that no bidder violates his demand constraint. We then demand that a $\pi_{ij}(A){\cdot \Pr[t_i = A]}$ amount of commodity $G_{ij}(A)$ is sent from source node $j$ to sink node $(i,A)$. We give the details of our flow network and the values of the capacities on its edges in Appendix~\ref{app:generalization of Border}, and also explain how to view any solution to the multi-commodity flow problem as a mechanism that implements the reduced form and vice versa. 




\input{bibliography}




\appendix
\input{polytope}
\input{IID}
\input{independent}
\input{non-iidHierarchical}
\input{manymany}
\input{borderExtension}

\end{document}
manymany.tex
\section{Optimal multi-dimensional mechanisms}\label{app:manymany}

We sketch how to use our results from the previous sections and recent results of~\cite{DW} to obtain the proofs of Theorems~\ref{thm:computation main},~\ref{cor:one},~\ref{cor:one point five} and~\ref{cor:two}. Simply put, \cite{DW} provides a LP formulation for the problem of finding the optimal BIC mechanism for value distributions of finite support. In addition, \cite{DW} exploits any symmetry that may exist in the value distribution to reduce the size of the resulting LPs. However, without a separation oracle to determine the feasibility of the $\pi$s, these LP formulations will have size exponential in the number of bidders in the settings we consider, even when the bidders are i.i.d., {because the LPs need to maintain variables for the ex-post allocation rule described by the $\phi$'s (See Section~\ref{sec:notation}). Using the separation oracles of Theorems~\ref{thm:grand theorem symmetric} and~\ref{thm:grand theorem independent}, we can eliminate the need for $\phi$'s in these LPs, turning the number of variables to polynomial in the number of bidders, and solving them in time polynomial in $m$, $n$ and $\max_i |supp({\cal F}_i)|$, thereby establishing Theorem~\ref{thm:computation main}. Theorem~\ref{cor:one} follows immediately  by combining our separation oracles with the symmetric LPs of Section 5 of~\cite{DW}. Theorem~\ref{cor:one point five} follows by discretizing the value distributions, applying the aforementioned symmetric LPs and the $\epsilon$-BIC to BIC reduction of Section 6 of~\cite{DW}. Finally, Theorem~\ref{cor:two} is obtained by truncating and discretizing the value distributions, running the symmetric LP on the resulting distributions, and using the $\epsilon$-BIC to BIC reduction of Section 6 of~\cite{DW}. (This procedure is described in detail in Appendix~J of~\cite{DW}.)}

For completeness, in Figure~\ref{fig:LP} we describe how to modify the LP of~\cite{DW} to exploit our separation oracles. We only describe the LP for the item-symmetric case to illustrate some extra work that is needed to handle symmetries. It is clear how to ``un-symmetrize'' the LP to treat the non-symmetric problem.  The LP shown in Figure~\ref{fig:LP} is identical to the item-symmetric LP of~\cite{DW} except that we have replaced the na\"ive feasibility constraints for the reduced form used in~\cite{DW} (these were {explicitly finding consistent $\vec{\phi}(P)$'s for every profile}) with a separation oracle $SO$ that takes as input a reduced form and decides whether it is feasible or not, in which case it also provides a separation hyperplane from the feasible set. The reader should refer to~\cite{DW} for the correctness of the unmodified LP. So we only need to justify here that our separation oracle works properly. While this is obvious in the non-symmetric case (as it follows directly from Theorem~\ref{thm:grand theorem independent}), it is slightly trickier for the symmetric LP of Figure~\ref{fig:LP}, as the LP does not explicitly maintain the whole reduced form. In particular, for every bidder $i$, we only maintain the reduced form for all types of bidder $i$ in the set $E_i = \{ \vec{v}_i~|~v_{i1} \geq \ldots \geq v_{in}\}$, and it is assumed that (because of symmetries)  the reduced form of a type $\vec{w}_i \notin E_i$ is just $\{\pi_{ij}(\vec{w}_i)=\pi_{i \sigma^{-1}(j)}(\vec{v_i})\}_j$ for whatever $\vec{v}_i \in E_i$ and $\sigma \in S$ satisfy $\sigma(\vec{v}_i)=\vec{w}_i$, where $S$ is the set of all item permutations. (For why it is OK to assume that such symmetries are satisfied by the optimal reduced form, the reader is referred to~\cite{DW}.)


We proceed to describe how our separation oracle works in the item-symmetric case. The input to $SO$ is the succinct description $\{\pi_{ij}(\vec{v}_i)\}_{i,j,\vec{v}_i \in E_i}$ of a reduced form and the value distribution $\mathcal{D}$. If we define {$\Pi := \cup_{i,j,\vec{v}_i \in E_i} \{\hat{\pi}_{ij}(\vec{v}_i)\}$}, where the $\hat{\pi}$'s are as in  Definition~\ref{def:virtual pi}, it follows from Theorem~\ref{thm: independent} and the symmetries satisfied by the complete reduced form (which is implied by the succinct one provided in the input to $SO$) that, for each item $j$, we only need to check $|\Pi|$ constricting sets for  feasibility. (In fact, because the mechanism is item-symmetric, it suffices to only check these constraints for a single item.) Checking a particular set can be done in time polynomial in $|\Pi|$, i.e. without explicitly listing all types that belong to the set, due to the symmetries. If none of the sets is found constricting, output ``yes.'' Otherwise, output the linear constraint violated by the constricting set. This is a hyperplane certifying that the $\pi_{ij}(\vec{v}_i)$'s are infeasible. If $SO$ outputs ``yes,'' this means that it is possible to allocate each item individually and satisfy the $\pi_{ij}(\vec{v}_i)$s. Because bidders have no demand constraints, this also means that we can simultaneously satisfy the $\pi_{ij}(\vec{v}_i)$'s of all items by simply allocating each item independently. It is now clear that $SO$ acts correctly as a separation oracle determining whether or not the $\pi_{ij}(\vec{v}_i)$s are feasible. Moreover, notice that $|E_i| = \poly(n^c)$, for all $i$, where $c= |supp({\cal F}_{ij})|$. Hence,  $|\Pi|$ is polynomial in $m$ and $n^c$. So our $SO$ runs in time polynomial in $m$ and $n^c$.


Our LP has size polynomial in $m$, $n^c$ and our separation oracle runs in time polynomial in $m$, $n^c$. So we can solve the LP to compute the optimal reduced form, $\{\pi_{ij}(\vec{v}_i)\}_{i,j,\vec{v}_i \in E_i}$. To execute the mechanism corresponding to the computed reduced form, we use Theorem~\ref{thm:grand theorem independent}{, treating each item separately and allocating each item independently of the others}.



\begin{figure}[h]
\colorbox{MyGray}{
\begin{minipage}{\textwidth} {
\noindent\textbf{Variables:}
\begin{itemize}
\item $\pi_{ij}(\vec{v}_i)$, for all bidders $i$, items $j$, and $\vec{v}_i \in E_i$ ($mn|E_i|$), the ex-interim probability that bidder $i$ gets item $j$ when reporting type $\vec{v}_i$.
\item $q_i(\vec{v}_i)$, for all bidders $i$, $\vec{v}_i \in E_i$ ($m|E_i|$), the ex-interim expected price that bidder $i$ pays when reporting type $\vec{v}_i$.
\end{itemize}
\textbf{Constraints:}
\begin{itemize}
\item $0 \leq \pi_{ij}(\vec{v}_i) \leq 1$, for all $i,j,\vec{v}_i \in E_i$, guaranteeing that each $\pi_{ij}(\vec{v}_i)$ is a probability ($mn|E_i|$).
\item $\sum_{j} v_{ij}\pi_{ij}(\vec{v}_i) - q_i(\vec{v}_i) \geq 0$, for all $i,\vec{v}_i \in E_i$, guaranteeing that the mechanism is ex-interim Individually Rational ($m|E_i|$).
\item $\sum_j v_{ij}\pi_{ij}(\vec{v}_i) - q_i(\vec{v}_i) \geq \sum_j v_{ij}\pi_{ij}(\vec{v}'_i) - q_i(\vec{v}'_i)$, for all $i,\vec{v}_i \in E_i,\vec{v}'_i \in E_i$, guaranteeing that the mechanism is BIC ($m|E_i|^2$).
\item $SO(\{\pi_{ij}(\vec{v}_i)\}_{i,j,\vec{v}_i},\mathcal{D}) = $ ``yes'', guaranteeing that there is a feasible mechanism implementing the $\pi_{ij}(\vec{v}_i)$s.
\end{itemize}
\textbf{Maximizing:}\\
$\sum_{i,\vec{v}_i \in E_i} q_i(\vec{v}_i)Pr[\vec{w}_i \leftarrow \mathcal{D}_i, \vec{w}_i \in \cup_{\sigma \in S} \{\sigma(\vec{v}_i)\}]$, the expected revenue.}
\end{minipage}} \caption{LP of \cite{DW} for the item-symmetric setting, where we use a separation oracle to determine feasibility of the reduced form. In parentheses at the end of each line is the number of such variables/constraints .}\label{fig:LP}
\end{figure}
non-iidHierarchical.tex
\section{Implementation of General Reduced Forms via Hierarchical Mechanisms} \label{app:hierarchical non iid}

Here we provide the proof of Theorem~\ref{thm:non-iidhierarchical}.\\
\begin{prevproof}{Theorem}{thm:non-iidhierarchical}
   Let $\sigma$ be a total ordering over all possible types, $\sigma: \cup_i (T_i \times \{i\}) \rightarrow [\sum_i|T_i|]$. Define the unhappiness $F_{\sigma}(M)$ of a distribution over $\sigma$-ordered hierarchical mechanisms, $M$, as follows:
$$F_{\sigma}(M)=\max_{i,A\in T_i}(\pi_i(A)-M_i(A)).$$
{As we argued formally in earlier sections $F_{\sigma}$ can be viewed as a continuous function over a compact set. Hence it achieves its minimum inside the set.} Let  then $M^{\sigma} \in \argmin_{M} F_{\sigma}(M)$ {(where the minimization is over all distributions over $\sigma$-ordered hierarchical mechanisms)} and define the set $S_{\sigma}$ to be the set of maximally unhappy types under $M^{\sigma}$; formally, $S_{\sigma}=\argmax_{i,A}\{\pi_i(A)-M^{\sigma}_i(A)\}$. {If for some $\sigma$ there are several minimizers $M^{\sigma}$, choose one that minimizes $|S_{\sigma}|$.} Now, let $MO$ be the set of the orderings $\sigma$ that minimize $F_{\sigma}(M^\sigma)$. Further refine $MO$ to only contain $\sigma$'s minimizing $|S_\sigma|$. Formally, we first set $MO=\argmin_{\sigma}\{ F_{\sigma}(M^\sigma)\}$ and then {refine $MO$ as $MO_{\rm new} = \argmin_{\sigma \in MO} \{|S_\sigma|\}$. We drop the subscript ``${\rm new}$'' for the rest of the proof.}

From now on, we call a type $(A,i)$ {\em happy} if $M_i(A)\geq \pi_i(A)$, otherwise we call $(A,i)$ {\em unhappy}. Intuitively, here is what we have already done: For every ordering $\sigma$, we have found a distribution over $\sigma$-ordered hierarchical mechanisms $M^\sigma$ that minimizes the maximal unhappiness {and subject to this, the number of maximally unhappy types}. We then choose from these $(\sigma, M^{\sigma})$ pairs those that minimize 
{the maximal unhappiness, and subject to this,} the number of maximally unhappy types. We have made these definitions because we want to eventually show that there is an ordering $\sigma$, such that $F_{\sigma}(M^\sigma)\leq 0$, and it is natural to start with the ordering that is ``closest'' to satisfying this property. We are one step away from completing the proof. What we will show next is that, if $\tau \in MO$ does not make every type happy, then we can find some other ordering $\tau'$, such that $F_{\tau'}(M^{\tau'})=F_{\tau}(M^\tau)$, $|S_{\tau'}|=|S_{\tau}|$, and $S_{\tau'} = \{\tau^{-1}(1),\ldots,\tau^{-1}(|S_{\tau'}|)\}$. In other words, only the top $|S_{\tau'}|$ types in $\tau$ are maximally unhappy. From here, we will show that because $\tau' \in MO$, that $S_{\tau'}$ is a constricting set and get a contradiction.

First, if the maximally unhappy types in $S_{\tau}$ are not the top $|S_{\tau}|$ ones, let $i$ be the smallest $i$ such that $\tau^{-1}(i+1) \in S_{\tau}$ but $\tau^{-1}(i) \notin S_{\tau}$. We proceed to show that by changing either the distribution $M$ or the ordering $\tau$, we can always move $\tau^{-1}(i)$ into $S_\tau$ and $\tau^{-1}(i+1)$ out without changing $|S_\tau|$ or the value $F_{\tau}(M)$. Then by repeating this procedure iteratively, we will get the $\tau'$ we want. 

Before we describe the procedure, we introduce some terminology. We say there is a \emph{cut} between $\tau^{-1}(i)$ and $\tau^{-1}(i+1)$ in a fixed $\tau$-ordered hierarchical mechanism $H$ if $H(\tau^{-1}(i)) < H(\tau^{-1}(i+1))$, i.e. if $\tau^{-1}(i)$ and $\tau^{-1}(i+1)$ are on different levels of the hierarchy. For the remainder of the proof, we will let $l$ be the level of $\tau^{-1}(i)$ ($H(\tau^{-1}(i))$). When we talk about adding or removing a cut below $i$, we mean increasing or decreasing $H(\tau^{-1}(j))$ by $1$ for all $j > i$. We now proceed with a case analysis, for fixed $\tau^{-1}(i) \notin S_\tau$, $\tau^{-1}(i+1) \in S_\tau$. We let $(A,j) = \tau^{-1}(i)$ and $(B,k) = \tau^{-1}(i+1)$.

\begin{itemize}
\item \textbf{Case 1:} $j = k$.

Since $\tau$ is a linear extension of the bidder's own ordering, then $\pi_j(A)\geq \pi_j(B)$, but we know that 
$$\pi_j(A)-M^\tau_j(A)<\pi_j(B)-M^\tau_j(B),$$
 thus $M^\tau_j(A)>M^\tau_j(B)\geq 0$. Because $A$ and $B$ are types for the same bidder $j$, when $A$ and $B$ are in the same level, they get the item with equal probability. Therefore, there must exist some $H \in \text{supp}(M^\tau)$ with a cut below $A$, and in which $A$ gets the item with non-zero probability. We modify $M^\tau$ {by modifying the mechanisms $H$ in its support as follows.} 
 
 Let $H$ be a hierarchical mechanism in the support of $M^\tau$. If there is no cut below $A$, we do nothing. If all of the types on level $l$ \emph{and} level $l+1$ are from bidder $j$, we remove the cut below $A$. This does not affect $H_{q}(C)$ (the probability that {$(C,q)$} gets the item under $H$) for any {$q,C \in T_q$}, because it was impossible for two types in the combined level to show up together anyway. {As we have not changed $H_q(C)$ for any $q,C$ in the mechanisms we have touched so far, yet none of these mechanisms has a cut between levels $l$ and $l+1$, there must still be some $H \in \text{supp}(M^{\tau})$ with a cut below $A$ and in which $A$ gets the item with non-zero probability (otherwise it couldn't be that $M^\tau_j(A)>M^\tau_j(B) \ge 0$).} For such an $H$, there is at least one type not from bidder $j$ in level $l$ or $l+1$. {We distinguish two sub-cases:} 
\begin{itemize}

\item Every bidder has at least one type in level $l+1$ or larger (in other words, every type in level $l+1$ wins the item with non-zero probability). Consider now moving the cut from below $i$ to below $i-1$. Clearly, $A$ will be less happy if we do this. Every type not from bidder $j$ in $l$ will be strictly happier, as now they do not have to share the item with $A$. Every type not from bidder $j$ in $l+1$ will be strictly happier, as they now get to share the item with $A$. It is also not hard to see that all types {$\neq A$} from bidder $j$ in level $l$ and $l+1$ are not affected by this change, as they never share the item with $A$ in either case. So in particular $B$ is unaffected. Consider instead moving the cut from below $i$ to below $i+1$. Then {$B$ is happier}, every type not from bidder $j$ in $l+1$ is less happy than before (as they now don't get to share with $B$),  every type not from bidder $j$ in $l$ is also less happy than before (because now they have to share with $B$), and all types {$\neq B$} from bidder $j$ in level $l$ and $l+1$ are not affected by the change (as they never share the item with $B$ in either case). To summarize, we have argued that, when we move the cut to below $i+1$, $B$ becomes strictly happier, and every type that becomes less happy by this change becomes strictly happier if we move the cut to below $i-1$ instead. Also, $B$ is unaffected by moving the cut to $i-1$. So with a tiny probability $\epsilon$, move the cut from below $i$ to below $i-1$, whenever $H$ is sampled from $M^{\tau}$. This makes all of the types not from bidder $j$ in level $l$ or $l+1$ strictly happier. With a tinier probability $\delta$, move the cut from below $i$ to below $i+1$, whenever $H$ is sampled from $M^{\tau}$. Choose $\epsilon$ to be small enough that we don't make $A$ maximally unhappy, and choose $\delta$ to be small enough so that we don't make any types besides $A$ less happy than they were {in $H$}. Then we have strictly increased the happiness of $B$ without making $A$ maximally unhappy, or decreasing the happiness of any other types. Therefore, we have reduced $|S_\tau|$, a contradiction. 

\item If there is a bidder $j'$ whose types are all in levels $1,\ldots,l$ (call such bidders {\em high}), then no type in level $l+1$ can possibly win the item. We also know {that: every high bidder} has at least one type in level $l$ by our choice of $H$ {(otherwise $A$ would get the item with probability $0$)}; and all high bidders are different than $j$, since $B$ is in level $l+1$. Now we can basically use the same argument as above. The only difference is that when we move the cut to below $i-1$ or the cut to below $i+1$, types in level $l+1$ {that are different than $B$} will remain unaffected {(i.e. the affected types different from $B$ are only those in level $l$)}. But {since every high bidder} has a type in level $l$, B will be unaffected in the first case but strictly happier in the second, {and it is still the case that every type who is made unhappier by moving the cut to below $i+1$ is made strictly happier by moving the cut to below $i-1$}.  So we can carry over the same proof as above, {and get a contradiction}.

\end{itemize}
Therefore, it can not be the case that $j = k$.

\item \textbf{Case 2:} $j \neq k$ and there is never a cut below $A$.

This case is easy. If we switch $(A,j)$ and $(B,k)$ in $\tau$, then the set $S_\tau$ is exactly the same, and the distribution $M^\tau$ is exactly the same. However, we have now relabeled the types in $S_\tau$ so that $\tau^{-1}(i) \in S_\tau$ and $\tau^{-1}(i+1) \notin S_\tau$.

\item \textbf{Case 3:} $j \neq k$ and there is sometimes a cut below $A$.

Pick a mechanism $H$ in the support of $M^{\tau}$ that has a cut between $A$ and $B$ and in which $A$ gets the item with positive probability. (If such a mechanism doesn't exist we can remove the cut between $i$ and $i+1$ in all mechanisms in the support without changing the allocation probabilities and return to Case 2). Let now $i^* = \max_{i' < i} \{i' | \tau^{-1}(i') \in S_\tau\}$. By our choice of $i$ (specifically, that it is the smallest $i$ such that $\tau^{-1}(i+1) \in S_{\tau}$ but $\tau^{-1}(i) \notin S_{\tau}$), we see that $\tau^{-1}(i') \in S_\tau$ for all $i' \leq i^*$, and $\tau^{-1}(i') \notin S_\tau$ for all $i^* < i' \leq i$. There are again two sub-cases:
\begin{itemize}
\item $H(\tau^{-1}(i^*)) < l$. By our choice of $i^*$, this means that everyone in level $l$ is \emph{not} maximally unhappy. By our choice of $H$, everyone in level $l$ receives the item with non-zero probability, {so there is at least one type from each bidder in level $l$ or larger}. If we pick a tiny $\epsilon$, and with probability $\epsilon$ remove the cut from below $i$ (whenever $H$ is sampled from $M^{\tau}$), then everyone in level $l+1$ is happier, everyone in level $l$ is unhappier, and everyone else is unaffected. In particular, $B$ will be strictly happier with this change, as he now gets to share with $A$ (and possibly others). If we choose a sufficiently small $\epsilon$, no one in level $l$ will be made maximally unhappy, and $(B,k)$ will be removed from $S_\tau$, a contradiction.

\item $H(\tau^{-1}(i^*)) = l$. In this case, introduce a cut below $i^*$ with some  probability $\epsilon$ whenever $H$ is sampled from $M^{\tau}$. The only types who may become happier by this change are those in level $l$ with $\tau(C,q) \leq i^*$. The only types who may become unhappier by this change are those in level $l$ with $\tau(C,q) > i^*$. {Everyone else is unaffected by this change. But, if we can make any type happier, then we can choose $\epsilon$ small enough, so that we remove this type from $S_{\tau}$ (this type must be in $S_\tau$ as all types in level $l$ with $\tau(C,q) \leq i^*$ are) without making any new type maximally unhappy (as all types that can possibly become unhappier with this change are \emph{not} in $S_\tau$). Again, we obtain a contradiction because this would decrease $|S_\tau|$ without increasing $F_\tau(M^\tau)$.}  Thus, this change cannot make anyone happier, and therefore cannot make anyone unhappier. So we may modify $M^\sigma$ by introducing a cut below $i^*$ with {probability $1$} whenever $M^\tau$ samples $H$, thereby removing $H$ from the support of $M^\tau$ (without making anyone happier or unhappier) and replacing it with $H'$ satisfying: $H'(\tau^{-1}(i^*)) < H'(\tau^{-1}(i)) < H'(\tau^{-1}(i+1))$ and $H'$ awards the item to $\tau^{-1}(i)$ with non-zero probability. After this modification, we may return to the previous sub-case to obtain a contradiction.
\end{itemize}

{Hence, it can not be the case that  $j \neq k$ with sometimes a cut below $A$.}
\end{itemize}

At the end of all three cases, we see that if we ever have $\tau^{-1}(i) \notin S_\tau$ and $\tau^{-1}(i+1) \in S_\tau$, then these types must belong to different bidders, and {no mechanism in the support of $M^{\tau}$ ever places a cut between these types}. Hence, we can simply swap these types in $\tau$ (as we described in Case 2 above), and we do that repeatedly until we have $S_\tau = \{\tau^{-1}(1),\ldots,\tau^{-1}(|S_\tau|)\}$. Once such a $\tau$ has been found, let $k = |S_\tau|$. {Now consider a mechanism in the support of $M^{\tau}$ that has no cut below $k$,} and consider putting a cut there with some tiny probability $\epsilon$ whenever this mechanism is sampled. The only effect this {\em might} have is that when the item went to a type outside $S_\tau$, it now goes with some probability to a type inside $S_\tau$. Therefore, if anyone gets happier, it is someone in $S_\tau$. However, if we make anyone in $S_\tau$ happier and choose $\epsilon$ small enough so that we don't make anyone outside of $S_\tau$ maximally unhappy, we decrease $|S_\tau|$, getting a contradiction. Therefore, putting a cut below $k$ cannot possibly make anyone happier, and therefore cannot make anyone unhappier. So we may w.l.o.g. assume that {there is a cut below $k$ in all mechanisms in the support of $M^{\tau}$}. But now we get that the item always goes to someone in $S_\tau$ {whenever someone in $S_\tau$ shows up}, yet everyone in this set is unhappy. Therefore, $S_{\tau}$ is a constricting set, {certifying that the given $\pi$ is infeasible}. 

Putting everything together, we have shown that if there is no $\sigma$ with $F_\sigma(M^\sigma) \leq 0$ then the reduced form is infeasible. So there must be some $\sigma$ with $F_\sigma(M^\sigma) \leq 0$, and such an $M^\sigma$ implements the reduced form by sampling only $\sigma$-ordered hierarchical mechanisms, completing the proof.
\end{prevproof}
polytope.tex
\section{A Geometric Algorithm}\label{app: polytope}
Carath\'eodory's theorem states that every point $\vec{x}$ inside an $n$-dimensional polytope $P$ can be written as a convex combination of at most $n+1$ corners of $P$. In this section, we provide an efficient algorithm for coming up with such a combination. We will consider polytopes that are described {as an intersection of half-spaces. Each half-space is defined by a hyperplane $h$ together with a choice of a side. We use $B(P)$ to denote the set of half-spaces, but overload notation using $B(P)$ to also denote the set of boundary hyperplanes of the polytope $P$. We reserve the symbol $h$ to denote hyperplanes.} In addition, we consider cases where $|B(P)|$ may be exponentially large, and we only have an implicit description of $B(P)$. That is, we have access to a \emph{boundary oracle} $BO$ that outputs yes on input $h$ if $h \in B(P)$, and no otherwise. We also have access to a separation oracle, $SO$, that outputs yes on input $\vec{x}$ if $\vec{x} \in P$, and outputs some $h \in B(P)$ if $\vec{x}$ is on the wrong side of $h$ (and therefore not in $P$). We will talk about one more algorithm related to $P$:

\begin{definition} $CO$ is a \textbf{corner oracle} for $P$ if it has the following behavior. Given as input a set of hyperplanes $B$, $CO$ outputs no if $B \not \subseteq B(P)$, or $\left(\bigcap_{h \in B} h\right) \bigcap P = \emptyset$ (i.e. the hyperplanes are not boundary hyperplanes of $P$, or they are boundary hyperplanes, but do not intersect inside $P$). Otherwise, $CO$ outputs a corner of $P$ inside $\bigcap_{h \in B} h$.
\end{definition}

It is clear that $CO$ has well-defined behavior on all inputs. If $B$ contains only boundary hyperplanes of $P$, and the intersection of these hyperplanes with $P$ is non-empty, this region must contain a corner of $P$. Now we describe our algorithmic problem in terms of these algorithms:

\begin{question}\label{q: polytope} Given as input a boundary oracle, $BO$, separation oracle $SO$, and corner oracle $CO$ for some $n$-dimensional polytope $P$, and a point $\vec{x}$, output no if $\vec{x} \notin P$. Otherwise, output $c_1,\ldots,c_{n+1}$, $\vec{a}_1,\ldots,\vec{a}_{n+1}$ such that $\vec{a}_i$ is a corner of $P$ for all $i$, $\sum_i c_i = 1$, and $\sum_i c_i \vec{a}_i = \vec{x}$.
\end{question}

{It follows from Carath\'eodory's theorem}%~\footnote{\costasnote{Used to be: ``is a well-known corollary of'': isn't it obvious or am I missing something here?} }
 that such $c_i,\vec{a}_i$ exist whenever $\vec{x} \in P$. We provide an algorithm to find such a solution whenever it exists. At a high level, we begin with the input $\vec{x}$ and maintain at all times two points $\vec{y} \in P$, $\vec{z} \in P$, such that $\vec{x} = c\vec{y} + (1-c)\vec{z}$, for some $c \in [0,1]$. After step $t$ of the algorithm is completed, $\vec{y}$ is the convex combination of at most $t$ corners of $P$, and $\vec{z}$ lies in the $(n-t)$-dimensional intersection of $t$ hyperplanes of $B(P)$. Hence, after at most $n$ steps, $\vec{z}$ will lie in a $0$-dimensional space, and therefore must be a corner, so the algorithm will terminate after at most $n+1$ steps. 

To go from step $t$ to step $t+1$, we pick an arbitrary corner, $\vec{a}_t$, that lies in the intersection of the $t$ hyperplanes where $\vec{z}$ lies. Then, we let $c_t$ be as large as possible without pushing the point $\frac{(1-\sum_{j < t}c_j)\vec{z} - c_t\cdot\vec{a}_t}{1-c_t-\sum_{j < t}c_j}$ outside of $P$. {We update $\vec{z}$ to $\vec{z}_{\rm new}=\frac{(1-\sum_{j < t}c_j)\vec{z}_{\rm old} - c_t\cdot\vec{a}_t}{1-c_t-\sum_{j < t}c_j}$ and update $\vec{y}$ appropriately to include $\vec{a}_t$ in its convex combination of corners.} The new $\vec{z}$ must lie at the intersection of the original $t$ hyperplanes where the old $\vec{z}$ lied, as well as a new $h \in B(P)$ that stopped us from further increasing $c_t$. Below is a formal description of the algorithm. In the description, $E$ denotes the set of hyperplanes whose intersection contains $\vec{z}$ (the empty intersection is the entire space).

\begin{algorithm}[h]
        \caption{Algorithm for writing $\vec{x}$ as a convex combination of at most $n+1$ corners}
    \begin{algorithmic}[1]\label{alg: convex}
        \STATE Initialize: $i := 1$, {$\vec{y} := \vec{0}$}, $\vec{z} := \vec{x}$, $E := \emptyset$, $c_i := 0,\vec{a}_i := \vec{0}$ $\forall i \in [n+1]$.
        \STATE\label{step: inv} Invariants: $c := \sum_i c_i$, $\vec{y} := \frac{1}{c} \sum_i c_i\vec{a}_i$, or $\vec{0}$ if $c = 0$, $c\vec{y} + (1-c)\vec{z} = \vec{x}$. \\
        \IF{$SO(\vec{x}) \neq \text{yes}$}
        	\STATE Output no.\\
        \ENDIF
        \WHILE{$c < 1$}
            \STATE Set $\vec{a}_i := CO(E)$. \\
            \IF{$\vec{a}_i = \vec{z}$}
            	\STATE Set $c_i := 1-c$.  \\
            	\STATE Output $c_1,\ldots,c_{n+1}$, $\vec{a}_1,\ldots,\vec{a}_{n+1}$.\\
            \ELSE
            	\STATE\label{step: LP} Set $D := \max\{d~\vline~(1+d)\vec{z} - d\vec{a}_i \in P\}$.\\
            	\STATE\label{step: SO} Set $E_i = SO((1+D+\epsilon)\vec{z}-(D+\epsilon)\vec{a}_i)$ for sufficiently small $\epsilon > 0$. {{\em /* the appropriate choice of $\epsilon$ is explained in the proof of Theorem~\ref{thm: polytope}*/}}\\
            	\STATE\label{step: update} Update: $c_i := (1-\frac{1}{1+D})(1-c)$, $\vec{z} := \frac{1-c}{1-c-c_i} \vec{z} - \frac{c_i}{1-c-c_i}\vec{a}_i$, $\vec{y} := \frac{c}{c+c_i}\vec{y} + \frac{c_i}{c+c_i}\vec{a}_i$, $c := c+c_i$, $E := E \cup E_i$, $i := i+1$.\\
            \ENDIF
        \ENDWHILE
     \end{algorithmic}
\end{algorithm}
\begin{theorem}\label{thm: polytope} Algorithm \ref{alg: convex} correctly answers Question \ref{q: polytope}. Furthermore, if $b$ is the maximum number of bits used in the description of any coefficient of any hyperplane $h \in B(P)$ {and any coordinate of $\vec{x}$}, then the runtime of Algorithm \ref{alg: convex} is polynomial in $n$, $b$ and the runtimes of $SO$ and $CO$. 
\end{theorem}

\begin{proof} First, we  describe how to execute Steps \ref{step: LP} and \ref{step: SO} of the algorithm, as it is clear how to execute every other step. Step \ref{step: LP} can be done by solving a linear program using $SO$. Explicitly, maximize $d$ subject to $(1+d)\vec{z} - d\vec{a}_i \in P$. For Step \ref{step: SO}, {we will explain later in the proof how to choose an $\epsilon$ small enough} so that the following property is satisfied: 

\medskip \begin{minipage}{16cm}{(P): for all $h \in B(P)$ and for whatever $D$ is computed in Step~\ref{step: LP} of the algorithm, if $(1+D)\vec{z} - D\vec{a}_i$ is not contained in $h$}, then {$(1+D+\epsilon)\vec{z} - (D+\epsilon)\vec{a}_i$} is on the same side of $h$ as {$(1+D)\vec{z} - D\vec{a}_i$}. 
\end{minipage}

\medskip \noindent We will explain later why (P) suffices for the correctness of the algorithm, {how to choose an $\epsilon$ so that (P) holds, and why its description complexity is polynomial in $n$ and $b$.}

We start with justifying the algorithm's correctness, {assuming that $\epsilon$ is chosen so that (P) holds}. We observe first that $\sum_i c_i \leq 1$ always. If the algorithm ever increases $c$, it is because $\vec{z} \neq \vec{a}_i$. If this is the case, then $D$ from Step \ref{step: LP} will have some finite positive value. So $(1-\frac{1}{1+D})(1-c) < 1-c$, and adding $c_i$ to $c$ will not increase $c$ past $1$. We also observe that all the invariants declared in Step \ref{step: inv} hold throughout the course of the algorithm. This can be verified by simply checking each update rule in Step~\ref{step: update}. Finally, we argue that every time the algorithm updates $E$, the dimension of $\bigcap_{h \in E} h$ decreases by $1$, and $(\bigcap_{h \in E} h) \bigcap P \neq \emptyset$ is maintained. Because $\vec{a}_i$ and $\vec{z}$ both lie in $\bigcap_{h \in E}$ when Step~\ref{step: SO} is executed, none of the hyperplanes in this intersection can possibly be violated at $(1+D+\epsilon)\vec{z} - (D+\epsilon)\vec{a}_i$. Therefore, the hyperplane output by $SO( (1+D+\epsilon)\vec{z} - (D+\epsilon)\vec{a}_i)$ must reduce the dimension of $\bigcap_{h \in E} h$ by $1$ when added to $E$ at Step~\ref{step: update}. Furthermore, because $E_i$ is violated at $(1+D+\epsilon)\vec{z} - (D+\epsilon)\vec{a}_i$, but not at $(1+D)\vec{z} - D\vec{a}_i$, it must be the case that $(1+D)\vec{z} - D\vec{a}_i$ lies in the hyperplane $E_i$. {(This holds because we will guarantee that our $\epsilon$ satisfies Property (P), described above.)} Because this point is clearly in $P$, in the hyperplane $E_i$, and in all of the hyperplanes in $E$, it bears witness that we maintain $(\bigcap_{h \in E} h) \bigcap P \neq \emptyset$ always. {Hence after at most $n$ iterations of the while loop, the dimension of the remaining space is $0$, and we must enter the case where $\vec{a}_i = \vec{z}$. The algorithm then exits outputting a convex combination of corners equaling $\vec{x}$.}

{It remains to argue that a choice of $\epsilon$ satisfying Property (P) is possible.} Assuming the correctness of our algorithm, we show first that all the coefficients $c_i$ computed by the algorithm have low bit complexity. Indeed, let $\vec{b}_{i}=(\vec{a}_{i},1)$ for all $i$. Once we know the algorithm is correct, the $c_i$'s satisfy 
\begin{align*}\label{prog:convexcombination}
\sum_i c_i \vec{b}_i &= (\vec{x},1),
\end{align*} 
where $c_{i}$ and $\vec{a}_i$ are outputs of our algorithm. We will argue that, for these $\vec{a}_{i}$s, the above system of linear equations has a unique solution. If not, let $\vec{c}$ and $\vec{c}~'$ be two different solutions, and $d_{i}=c_{i}-c'_{i}$. We will show by induction on $i$ that $d_{i}=0$ for all $i$. In the base case, consider the hyperplane in $E_{1}$. We can write a corresponding $(n+1)$ dimensional vector $\vec{t}_{1}$, such that for all {$\vec{x'}\in P$, $(\vec{x'},1)\cdot \vec{t}_{1}\leq 0$}, and for all $i>1$, $\vec{b}_{i}\cdot \vec{t}_{1}=0$. But $\vec{b}_{1}\cdot \vec{t}_{1}\neq 0$, otherwise, for any $D$, $(1+D)\vec{z}-D\vec{a}_{1}$ does not violate the constraint in $E_{1}$. On the other hand, $\sum_i d_i \vec{b}_i\cdot \vec{t}_{1}=0$, therefore $d_{1}=0$. Now assume when $i<k$, $d_{i}=0$, we will argue that $d_{k}=0$. Let $\vec{t}_{k}$ be the corresponding vector for the hyperplane in $E_{k}$. For any $j>k$, $\vec{b}_{k}\cdot\vec{t}_{k}=0$, and by the Inductive Hypothesis, for any $i<k$, $d_{i}=0$, therefore $d_{k}\vec{b}_{k}\cdot\vec{t}_{k}=0$. But we know $\vec{b}_{k}\cdot\vec{t}_{k}\neq 0$, otherwise, for any $D$, $(1+D)\vec{z}-D\vec{a}_{k}$ does not violate the constraint in $E_{k}$. So $d_{k}=0$. Thus, $d_{i}=0$ for all $i$.

So we have argued that the $c_i$s are in fact the unique solution to the above linear system. We also know that the corners $\vec{a}_i$ (in fact all corners of the polytope) have ${\rm poly}(n,b)$ bit complexity. Applying the theory of Gaussian elimination, we deduce that each $c_i$ can be described using no more than $\poly(n,b)$ bits, so the coefficients output by our algorithm have low bit complexity. {Hence the $\vec{z}$ maintained by the algorithm has ${\rm poly}(n,b)$ bit complexity.  So the intersections $d_h$ of the ray $R(d)= \{(1+d) \vec{z} - d \vec{a}_i\}$ with the hyperplanes $h \in B(P)$ that do not contain both $\vec{z}$ and $\vec{a}_i$ (and hence the whole ray)  also have ${\rm poly}(n,b)$ bit complexity.} This guarantees that we can chose $\epsilon$ to be $2^{-\poly(n,b)}$ to satisfy Property (P).

 The above reasoning justifies the correctness of the algorithm. It is also now clear that every step runs in time polynomial in $b,n$, the runtime of $SO$ and the runtime of $CO$, and each step is executed at most $n+1$ times. So the entire algorithm runs in polynomial time.
\end{proof}
1112.4572.extracted_bib
\begin{thebibliography}{1}

\bibitem{alaei} S.~Alaei. Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers. {\em Proceedings of FOCS} 2010.

\bibitem{AFHHM} S.~Alaei, H.~Fu, N.~Haghpanah, J.~Hartline, A.~Malekian. { Personal Communication} 2011.

%\bibitem{AFHHM} S.~Alaei, H.~Fu, N.~Haghpanah, J.~Hartline, A.~Malekian. Optimal Mechanism Design via Reduced Form Auctions. {\em arXiv Report} 2011.

\bibitem{BH} X. Bei, Z. Huang. Bayesian Incentive Compatibility via Fractional Assignments. {\em Proceedings of SODA} 2011.          

\bibitem{BGGM} S.~Bhattacharya, G.~Goel, S.~Gollapudi and K.~Munagala. Budget Constrained Auctions with Heterogeneous Items. {\em Proceedings of STOC} 2010.

\bibitem{border} K.~C.~Border. Implementation of Reduced Form Auctions: A Geometric Approach. {\em Econometrica,} 59(4): 1175--1187, 1991.

\bibitem{border2007}  K.~C.~Border. Reduced form Auctions Revisited. {\em Economic Theory}, 31:167--181, 2007.
%    \bibitem{BCKW} P.~Briest, S.~Chawla, R.~Kleinberg and S.~M.~Weinberg. Pricing Randomized Allocations. {\em Proceedings of SODA} 2010.

%    \bibitem{BK} P.~Briest and P.~Krysta. Buying Cheap is Expensive: Hardness of Non-Parametric Multi-Product Pricing. {\em Proceedings of SODA} 2007.

\bibitem{CD} Y.~Cai and C. Daskalakis. Extreme-Value Theorems for Optimal Multidimensional Pricing. {\em Proceedings of FOCS} 2011.

\bibitem{CH} Y.~Cai and Z.~Huang. Simple and Nearly Optimal Multi-Item Auction. {\em Manuscript}, 2011.

\bibitem{CHK} S.~Chawla, J.~D.~Hartline and R.~D.~Kleinberg. Algorithmic Pricing via Virtual Valuations. {\em Proceedings of EC} 2007.

\bibitem{CHMS} S.~Chawla, J.~D.~Hartline, D.~Malec and B.~Sivan. Multi-Parameter Mechanism Design and Sequential Posted Pricing. {\em Proceedings of STOC} 2010.


\bibitem{CMS} S.~Chawla, D.~Malec and B.~Sivan. The Power of Randomness in Bayesian Optimal Mechanism Design. {\em Proceedings of EC} 2010.

\bibitem{CKM} Y.~Che, J.~Kim and K.~Mierendorff. Generalized Reduced-Form Auctions: A Network-Flow Approach. {\em University of Z\"urich, ECON-Working Papers,}  2011.
%\\ {\tt http://www.econ.uzh.ch/static/workingpapers.php}.

\bibitem{clarke} E.~Clarke. Multipart Pricing of Public Goods. {\em Public Choice,}  18:19--33, 1971. 


\bibitem{DW} C.~Daskalakis and S.~M.~Weinberg. On Optimal Multi-Dimensional Mechanism Design. {\em arXiv Report,} 2011.
 
 \bibitem{DFK} S.~Dobzinski, H.~Fu and R.~D.~Kleinberg. Optimal Auctions with Correlated Bidders are Easy. {\em Proceedings of STOC} 2011.
 
  
    %\bibitem{DR} S.~Dughmi and T.~Roughgarden. Black-Box Randomized Reductions in Algorithmic Mechanism Design. {\em FOCS} 2010.

\bibitem{groves} T.~Groves. Incentives in Teams. {\em Econometrica,}  41:617--631, 1973.

%    \bibitem{Hart} J.~D.~Hartline. Approximation in Mechanism Design. {\tt econ-www.mit.edu/files/6135}.
%
 \bibitem{HKM} J. Hartline, R. Kleinberg, A. Malekian. Multi-Parameter Bayesian Algorithmic Mechanism Design. {\em Proceedings of SODA} 2011.

\bibitem{HL} J.~D.~Hartline and B.~Lucier. Bayesian Algorithmic Mechanism Design. {\em Proceedings of STOC} 2010.

%    \bibitem{HR} J.~Hartline and T.~Roughgarden. Optimal mechanism design and money burning. {\em Proceedings of STOC}, 2008.

%    \bibitem{bundles} A.~M.~Manelli and D.~R.~Vincent. Bundling as an Optimal Selling Mechanism for a Multiple-Good Monopolist. {\em Journal of Economic Theory,} 127(1):1--35, 2006.

\bibitem{optimal:econ}  A.~M.~Manelli and D.~R.~Vincent. Multidimensional Mechanism Design: Revenue Maximization and the Multiple-Good Monopoly. {\em Journal of Economic Theory,} 137(1):153--185, 2007.  

\bibitem{maskinriley} E. Maskin and J. Riley. Optimal Auctions with Risk Averse Buyers. {\em Econometrica,} 52(6): 1473--1518, 1984.

\bibitem{matthews} S.~A.~Matthews. On the Implementability of Reduced Form Auctions. {\em Econometrica,} 52(6):1519--1522, 1984.

\bibitem{myerson} R.~B.~Myerson. Optimal Auction Design. {\em Mathematics of Operations Research,} 1981.

%    \bibitem{N} J.~Nash.
%    \newblock Noncooperative Games.
%    \newblock {\em Annals of Mathematics}, 54:289--295, 1951.

\bibitem{AGTbook} N.~Nisan, T.~Roughgarden, E.~Tardos and V.~V.~Vazirani (eds.). {\em Algorithmic Game Theory}. Cambridge University Press, 2007.

    %\bibitem{PV} M.~Pai and R.~Vohra. Optimal auctions with financially constrained bidders. {\em Working Paper,} 2008.

%    \bibitem{Than} J.~Thanassoulis. Haggling over substitutes. {\em Journal of Economic Theory,} 117(2):217�245, 2004.

\bibitem{Schrijver03} A.~Schrijver. \emph{Combinatorial Optimization - Polyhedra and Efficiency}. Springer, 2003.

\bibitem{vickrey} W.~Vickrey. Counterspeculations, Auctions, and Competitive Sealed Tenders. {\em J. Finance,}  16:15--27, 1961. 

%    \bibitem{Wil} R.~B.~Wilson. {\em Nonlinear Pricing.} Oxford University Press, 1997.



\end{thebibliography}