diff options
| -rw-r--r-- | ps2/main.tex | 20 |
1 files changed, 20 insertions, 0 deletions
diff --git a/ps2/main.tex b/ps2/main.tex index 5cc2b96..b34c74d 100644 --- a/ps2/main.tex +++ b/ps2/main.tex @@ -44,6 +44,26 @@ \maketitle \section*{Exercise 4.13} +In the proof of the prophet inequality, a lower bound on APX is obtained by +conditioning on the event $\mathcal{E}_i$ that all agents different from $i$ +have a value below the threshold $\hat{v}$. + +If this threshold is the monopoly price of the maximum value distribution, then +it is different from the monopoly prices of $\hat{v}_i$ of the individual +agents. However, we believe that is possible to lower bound the probability of +this event: +\begin{displaymath} + \Pr[\mathcal{E}_i] \geq \frac{1}{2} \prod_{j} \Pr[v_j\geq\hat{v}_j] +\end{displaymath} +That is, we lose a factor 2 by going from discriminatory posted prices to an +anonymous posted price. This lower bound probably follows from the regularity +assumption, which should allow us to see that the distribution of the maximum +value is not too ``far'' from each individual distribution. However, we haven't +been able to prove such a lower bound. + +Given such a lower bound, we can finish the proof of the prophet inequality as +in the lecture notes. + \section*{Exercise 4.14*}\begin{claim} For any constant $\beta$, there is a matroid environment and an i.i.d. non-regular distribution such that the approximation ratio of the optimal mechanism with the surplus maximization with anonymous reserve is at least $\beta$. \end{claim} |