Showing that the beta-exclusivity route doesn't work

1 files changed, 58 insertions, 18 deletions

diff --git a/final/main.tex b/final/main.tex
index 18d0a30..39d9c06 100644
--- a/final/main.tex
+++ b/final/main.tex
@@ -296,31 +296,71 @@ price. Then we have:
     previous paragraph, this implies that $\TPRev(F)\geq \BRev(F)$.
 \end{proof}
 
-\subsection{$p$-exclusivity}
+\subsection{$\beta$-exclusivity}
 
-As noted by \citep{yao}, the above mechanism $\M$ has the additional property of being
-$p$-exclusive, where $p$-exclusivity\footnote{\citep{yao} actually uses the
-notation $\beta$-exclusive for the same thing, but we use $p$ here to have
-consistent notation.} is defined as follows: for a vector $p = (p_1,\dots,p_m)$
-a mechanism is said to be $p$-exclusive if $x_i = 0$ whenever $p_i > t_i$. This
-is essentially saying that there is a reserve price for each item.
+As noted by \citep{yao}, the above mechanism $\M$ has the additional property
+of being $\beta$-exclusive, where $\beta$-exclusivity is defined as
+follows: for a vector $\beta = (\beta_1,\dots,\beta_m)$ a mechanism is said to
+be $\beta$-exclusive if $x_i = 0$ whenever $\beta_i > t_i$. This is
+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.
 
-$p$-exclusivity
-can easily be enforced in the optimization we formulated in Section~\ref{sec:intro},
-by adding the following non-linear constraints:
+There is an easy one-way reduction from $\hat{x}$ ex-ante constrained
+mechanisms 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
+    it is satisfies the ex-ante allocation constrained given by $\hat{x}$.
+\end{lemma}
+
+\begin{proof}
+Let us consider a $\beta$-exclusive mechanism with $\beta\geq
+F^{-1}(1-\hat{x})$, meaning that for all $i\in[m]$: $\beta_i\geq
+F^{-1}(1-\hat{x}_i)$.
+
+For a given $i\in[m]$, we have $\Pr[t_i\geq \beta_i] = (1-F(\beta_i))\leq
+\hat{x}_i$. Since the mechanism only allocates $i$, when $t_i\geq \beta_i$ by
+$\beta$-exclusivity, this implies:
 \begin{displaymath}
-    x_i(t_i - p_i)\geq 0,\quad \forall i\in[m] 
+    \E[x_i(t)]\leq \Pr[t_i\geq\beta _i]\leq \hat{x}_i
 \end{displaymath}
+This is true for all $i\in[m]$ so the mechanism satisfies the ex-ante
+allocation constraint $\hat{x}$.
+\end{proof}
 
-$p$-exclusivity relates to ex-ante allocation constraints through the following
-Lemma.
+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
+        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}).
+\end{enumerate}
 
-\begin{lemma}
-    If a mechanism is $p$-exclusive for some vector $p=(p_1,\dots, p_m)$, then
-    it satisfies the ex-ante allocation constraint defined by $$\hat{x}
-    = \big(F^{-1}(1-p_1), \dots, F^{-1}(1-p_m)\big).$$
-\end{lemma}
+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
+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
+$\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$.
+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
+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}