Final version

1 files changed, 8 insertions, 1 deletions

diff --git a/final/main.tex b/final/main.tex
index 6d5b6b6..3ae2d0e 100644
--- a/final/main.tex
+++ b/final/main.tex
@@ -375,6 +375,9 @@ buyer problem that we discussed: namely $\beta$-exclusivity and ex-ante allocati
 constraints and draw a parallel in how these two notions are used to construct
 $n$-to-1 bidders reductions in \citep{yao} and \citep{alaei} respectively.
 \subsection{\citep{alaei}'s Approach}
+To reduce the $m$-item, $n$-buyer mechanism to multiple instances of an $m$-item, single buyer mechanism is accomplished within \citep{alaei} in two different ways. The first method, which he calls \emph{prerounding}, and we can abbreviate by $\text{PR}^+$, first sets an arbitrary order to serve the buyers (this could also be interpreted, as he points out, as a problem where the agents arrive sequentially). Then, for each buyer, the single-buyer mechanism is run on some subset of items still available, setting the allocation probabilities to 0 for items not in that subset. Under the assumption that there is no cross-item complementarity (meaning that the revenue from a bundle of items is at most the sum of the revenue of the single items; a counterexample would be if one of the items was a television set and another was a remote control that only worked with that television), the mechanism is shown to be DSIC and, assuming that there are at least $k$ of each of the $m$ items, to allocate a given item to a particular buyer with probability at least $1 - \frac{1}{\sqrt{k+3}}$.
+
+The second method, which \citep{alaei} refers to as \emph{postrounding}, and we can abbreviate by $\text{PR}^-$, independently runs the single buyer mechanism for each buyer simultaneously. This will result in some overallocation, so the mechanism then takes away items that have already been allocated from some buyers (not charging buyers for the items that have been deallocated), such that the probability of an item being taken away is uniform over all buyers. The mechanism is shown to be BIC, and, similarly to $\text{PR}^+$, assuming that there are at least $k$ of each of the $m$ items, allocates and does not ultimately take away a given item to a particular buyer with probability at least $1 - \frac{1}{\sqrt{k+3}}$.
 \subsection{\citep{yao}'s Approach}
 The notion of $\beta$-exclusivity introduced by \citep{yao} was crucial in his
 reduction from the $m$-item $n$-buyer setting to the $m$-item single buyer
@@ -438,10 +441,14 @@ If we denote the revenue from this mechanism by $\Rev_{\text{DBGR}^+}(F)$, then
 
 \begin{lemma}[\citep{yao}, combination of Theorem 3 and Corollary to Theorem 2] \ \\ Let $F =F_1\times\dots\times F_m$. Then, $$\Rev(F) \leq 69 \cdot \Rev_{\text{DBGR}^+}(F)$$ \end{lemma}
 
-While this mechanism 
+While this mechanism's revenue does indeed provide a constant approximation to the revenue of the optimal mechanism (and thereby establishes the desired $n$-to-1 buyer reduction, it is not very simple to implement: namely, it uses $n$ different $\beta$-bundling mechanisms and $n$ second-price Vickrey auctions, and each buyer is charged a (potentially different) $\hat{v}_0$, depending on his type. To avoid this, \citep{yao} proposes a mechanism called \emph{Second-Price Bundling} (SPB) which offers all of the items for which buyer $i$ had the maximum value (breaking ties uniformly at random) to him as a single bundle at the price of $w+\sum p_{2nd}(t)$, where $w$ is a common price (\lq\lq entry fee\rq\rq) posted to all buyers. As observed in \citep{yao}, Section 9.2, setting $w$ to 0 makes the SPB mechanism equivalent to selling each item separately at the Vickrey 2nd price auction price. By proving an upper and lower bound on $\Rev_{\text{SPB}}(F)$, the revenue of the SPB mechanism relative to $\Rev(F)$, he then shows that $$\Rev_{\text{SPB}}(F) = \Theta(\Rev(F)),$$ which indicates that the SPB mechanism is a suitable substitute for the complexity of the $\text{DBGR}^+$ mechanism, and hence that the $n$-to-1 bidder reduction has been successfully accomplished.
+
+\subsection{Connections} Interestingly, while the approaches of \citep{alaei} and \citep{yao} use quite different methodology, the overall idea of running separate allocation-constrained single-buyer mechanisms to approximate the revenue of an $n$-buyer $m$-item mechanism suggests that there is something very natural (and important) in the use and general understanding of allocation constraints for $m$-item single buyer mechanisms.
 
 \section{Conclusion}
 
+We have discussed the problem of selling $m$ heterogeneous items, with ex-ante allocation constraint $\hat{x}$, to a single buyer with additive utility, having type drawn from the distribution $F$. Following a suggestion by J.D. Hartline, we have proposed a mechanism $\M$ based on a two-part tariff approach (in which the price charged to the buyer consists of an entrance fee plus posted prices for the items) and then drew a connection with a technique from \citep{yao}, in which we relate this mechanism to a $\beta$-exclusive mechanism. We also surveyed the $n$-to-1 buyer reduction techniques within \citep{alaei} and \citep{yao}, unifying the exposition and terminology. Our proposed mechanism $\M$ can be viewed as a generalization of the work of \citep{babaioff}, but with the addition of allocation constraints. We showed, via a counterexample, that the approximation ratio of the revenue for the optimal $\beta$-exclusive mechanisms to the optimal revenue of the two-party tariff mechanism $\M$ is unbounded. Whether the optimal revenue of the two-party tariff mechanism is a constant approximation to the revenue of the optimal mechanism with allocation constraints remains an open and interesting path for future research.
+
 \bibliographystyle{abbrvnat}
 \bibliography{main}
 \end{document}