diff options
Diffstat (limited to 'final/main.tex')
| -rw-r--r-- | final/main.tex | 37 |
1 files changed, 22 insertions, 15 deletions
diff --git a/final/main.tex b/final/main.tex index ce27f47..b49e959 100644 --- a/final/main.tex +++ b/final/main.tex @@ -31,9 +31,10 @@ \endgroup } -\DeclareMathOperator*{\E}{\mathbb{E}} + +\DeclareMathOperator*{\E}{\mathbf{E}} \let\Pr\relax -\DeclareMathOperator*{\Pr}{\mathbb{P}} +\DeclareMathOperator*{\Pr}{\mathbf{P}} \DeclareMathOperator*{\I}{\mathcal{I}} \DeclareMathOperator*{\TPRev}{\textsc{TPRev}} \DeclareMathOperator*{\Rev}{\textsc{Rev}} @@ -48,12 +49,15 @@ \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} +\newtheorem*{definition}{Definition} \newtheorem*{goal}{Goal} \author{Thibaut Horel \and Paul Tylkin} \title{The Additive Single Buyer Problem\\ with Ex-Ante Allocation Constraints \\ \vskip0.1in {\sc Economics 2099 Project}} \date{} \begin{document} +%include all references +\nocite{*} \maketitle @@ -306,10 +310,9 @@ essentially saying that there is a reserve price for each item. Theorem 6.1 from \citep{yao} shows that for an optimal choice of $\hat{v}_{-1}\geq \beta$ and $\hat{v}_0$, mechanism $\M$ described above is -a constant $7$-approximation to the optimal $\beta$-exclusive mechanism. +a constant $7$-approximation to the optimal $\beta$-exclusive mechanism. We will discuss this in greater detail in Section \ref{sec:reduction}. -There is an easy one-way reduction from $\hat{x}$ ex-ante constrained -mechanisms to $\beta$-exclusive mechanisms captured by the following Lemma. +There is a one-way reduction from mechanisms with ex-ante constraint $\hat{x}$ to $\beta$-exclusive mechanisms captured by the following Lemma. \begin{lemma} If a mechanism is $\beta$-exclusive with $\beta\geq F^{-1}(1-\hat{x})$, then @@ -331,11 +334,12 @@ This is true for all $i\in[m]$ so the mechanism satisfies the ex-ante allocation constraint $\hat{x}$. \end{proof} +Let $\Rev_\beta(F)$ be the revenue of the optimal $\beta$-exclusive mechanism. One could hope to use this reduction to show that $\TPRev(\hat{x}, F)$ is a constant approximation to $\Rev(\hat{x}, F)$ by: \begin{enumerate} \item showing that the revenue of the optimal $\beta$-exclusive - mechanism with $\beta = F^{-1}(1-\hat{x})$ is a constant approximation + mechanism, $\Rev_\beta(F)$, with $\beta = F^{-1}(1-\hat{x})$ is a constant approximation to $\Rev(\hat{x}, F)$. \item using that $\M$ is a constant approximation to the optimal $\beta$-exclusive mechanism (Theorem 6.1 in \citep{yao}). @@ -352,29 +356,29 @@ allocate any item and hence will have a revenue of $0$. Hence the optimal $\beta$-exclusive mechanism for $\beta = F^{-1}(1-\hat{x})$ will have revenue $0$. -However, there is a very simple mechanism which satisfies the $\hat{x}$ ex-ante -allocation constraint: regardless of the type, allocate each item $i\in [m]$ -with probability $\hat{x}_i$ at price $t_i^{min}\eqdef\min_{t_i\in T_i} t_i$. +However, there is a very simple mechanism which satisfies the ex-ante +allocation constraint $\hat{x}$: regardless of the type, allocate each item $i\in [m]$ +with probability $\hat{x}_i$ at price $$t_i^{min}\eqdef\min_{t_i\in T_i} t_i.$$ This mechanism is clearly IR and IC, satisfies the constraint $\hat{x}$ and has -expected revenue $\sum_{i\in [m]} \hat{x}_i t_i^{min}$. The revenue is positive +expected revenue $$\sum_{i\in [m]} \hat{x}_i t_i^{min}.$$ The revenue is positive whenever there exists $i$ such that $t_i^{min}>0$. This example shows that the approximation ratio in step 1. described above is in fact unbounded. \section{$n$-to-1 Bidders Reductions} - +\label{sec:reduction} 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 +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 setting. He describes a mechanism known as \emph{Best-Guess Reduction}, which -conducts $n$ single-buyer $m$-item auctions, using an IR-IC $p$-exclusive -mechanism, for a particular value of $p$ drawn from the joint bid distribution +conducts $n$ single-buyer $m$-item auctions, using an IR-IC $\beta$-exclusive +mechanism, for a particular value of $\beta$ drawn from the joint bid distribution over all buyers conditioned on the bids of all other buyers, and then combines this with the Vickrey second-price auction, showing that this mechanism has revenue that is a constant approximation to the optimal $m$-item, $n$-buyer @@ -382,7 +386,10 @@ 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}. +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}. We begin with a definition and a key lemma: +\begin{definition}[$F^+_\beta$, Definition 4.1 in \citep{yao}] \end{definition} +\begin{lemma}[Lemma 6.1 in \citep{yao}] +Let $F =F_1\times\dots\times F_m$, and let $\Rev_\beta(F)$ be the revenue of the optimal $\beta$-exclusive mechanism. Let $$\xi(F) = (\Pr[t_1> \beta_1],...,\Pr[t_m > \beta_m]).$$ Then, $$Rev_\beta(F) \leq \beta \xi(F) + \Rev(F_\beta^+ - \beta).$$ \end{lemma} \bibliographystyle{abbrvnat} \bibliography{main} |