From 16c27442de8c8e211a33e50b770ca2b22e6769e5 Mon Sep 17 00:00:00 2001 From: Paul Date: Wed, 13 May 2015 14:35:06 -0400 Subject: Writing Section 3.2 --- final/main.tex | 11 ++++++++--- 1 file changed, 8 insertions(+), 3 deletions(-) (limited to 'final') diff --git a/final/main.tex b/final/main.tex index b49e959..b778e23 100644 --- a/final/main.tex +++ b/final/main.tex @@ -196,7 +196,7 @@ $\gamma$ is a constant which is at least $\frac{1}{2}$. Given the simplicity of posted-price mechanisms and the fact that they are optimal in the single-agent single-item setting (for a regular distribution $F$), it would be desirable to obtain a mechanism as close as possible to posted-price. -Unfortunately, \citep{hart-nisan} showed that even in the +However, \citep{hart-nisan} showed that even in the unconstrained, regular case, no posted-price mechanism for the single-agent problem has an approximation ratio better than $\Omega(\log n)$. @@ -387,9 +387,14 @@ 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 begin with a definition and a key lemma: -\begin{definition}[$F^+_\beta$, Definition 4.1 in \citep{yao}] \end{definition} +\begin{definition}[$F^+_\beta$, Definition 4.1 in \citep{yao}] Let $F =F_1\times\dots\times F_m$, and let $t_i \sim F_i$. Let $$\Xi \sim \left(\text{Bernoulli}(t_1 > \beta_1),...,\text{Bernoulli}(t_m>\beta_m)\right),$$ i.e. $\xi_i$, which is defined to be the $i^{th}$ coordinate of a random variable with distribution $\Xi$, is 1 with probability $t_i>\beta_i$ and 0 otherwise. Then, let $F^+_\beta$ be defined as follows: the $i^{th}$ coordinate in $F^+_\beta$ is: +$$ F^+_{\beta,i} = \begin{cases} F_i | (F_i > \beta_i) &\text{if } \xi_i = 1 \\ \beta_i &\text{otherwise}\end{cases}$$ + \end{definition} + +Intuitively, this defines a transformation of the distribution $F$ using $\beta$ which can then be used in the following lemma to relate the revenue of the optimal $\beta$-exclusive mechanism to the revenue of the optimal mechanism. + \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} +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 \cdot \xi(F) + \Rev(F_\beta^+ - \beta).$$ \end{lemma} \bibliographystyle{abbrvnat} \bibliography{main} -- cgit v1.2.3-70-g09d2