[ps2] 4.13

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}