diff options
Diffstat (limited to 'final')
| -rw-r--r-- | final/main.tex | 12 |
1 files changed, 7 insertions, 5 deletions
diff --git a/final/main.tex b/final/main.tex index 6da4e59..ab1afaf 100644 --- a/final/main.tex +++ b/final/main.tex @@ -52,7 +52,7 @@ \author{Thibaut Horel \and Paul Tylkin} \title{The Additive Single Buyer Problem\\ with Ex-Ante Allocation Constraints \\ \vskip0.1in {\sc Economics 2099 Project}} -\date{Fall 2014} +\date{} \begin{document} \maketitle @@ -262,7 +262,7 @@ The question we introduced in Section~\ref{sec:intro} can then be formulated for the two-part tariff mechanism: $$\text{\emph{is $\TPRev(\hat{x}, F)$ a constant approximation to $\Rev(\hat{x}, F)$?}}$$ -The following simple Lemma shows that at least in the unconstrained case, the +The following Lemma shows that at least in the unconstrained case, the answer to the previous question is positive. In fact, the proof shows that the two-part tariff mechanism is rich enough to simulate both bundle pricing and separate posted pricing. Using the notation from \citep{babaioff}, let us write @@ -345,7 +345,7 @@ Unfortunately, this approach breaks at step 1. To see why, consider for simplicity a discrete type space $T\subset \R_+^m$ and assume that the support of $F$ is exactly $T$. Writing $T = T_1\times\dots\times T_m$ and $F = F_1\times\dots\times F_m$, consider an ex-ante constraint $\hat{x}$ such that -for all $i\in[m]$, $0<\hat{x}_i < \min_{t_i\in T_i} f_i(t)$, then this forces the +for all $i\in[m]$, $0<\hat{x}_i < \min_{t_i\in T_i} f_i(t)$. Then, this forces the associated $\beta_i$ to be such that $\beta_i > \max_{t_i\in T_i} t_i$ for all $i\in [m]$. But a $\beta$-exclusive mechanism for such a $\beta$ will never allocate any item and hence will have a revenue of $0$. Hence the optimal @@ -368,8 +368,8 @@ The goal of this section is to compare the two ways of constraining the single buyer problem that we discussed: namely $p$-exclusivity and ex-ante allocation 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} +\subsection{\citep{yao}'s Approach} The notion of $p$-exclusivity introduced by \citep{yao} was crucial in his reduction from the $m$-item $n$-buyer setting to the $m$-item single buyer setting. He describes a mechanism known as \emph{Best-Guess Reduction}, which @@ -382,6 +382,8 @@ mechanism. He then defines another mechanism, \emph{Second-Price Bundling}, which is meant to heuristically approximate this combined mechanism, and shows that its revenue is also a constant approximation to the optimal mechanism. +We will step through his results in greater detail, and also improve the approximation ratio in one of his lemmas, using the result from the published version of \citep{babaioff}. + \bibliographystyle{abbrvnat} \bibliography{main} \end{document} |