From 340d8855e7dd38e6c9fef2a8ea81f0418677343d Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Sun, 4 Nov 2012 16:14:40 -0800
Subject: proofofthm1

---
 main.tex | 67 +++++++++++++++++++++++++++++-----------------------------------
 1 file changed, 30 insertions(+), 37 deletions(-)

(limited to 'main.tex')

diff --git a/main.tex b/main.tex
index a91e67e..657454d 100644
--- a/main.tex
+++ b/main.tex
@@ -128,7 +128,7 @@ be to prove that $OPT(L_\mathcal{N}, B)$ is close to $V(S_G)$. To do so, our
 main technical contribution is to prove that $L_\mathcal{N}$ has a bounded
 approximation ratio to the value function $V$ (Lemma~\ref{lemma:relaxation}).
 
-The resulting mechanism for \EDP{} is presented in Algorithm~\ref{mechanism}. The constant $C$ is an absolute constant, that we determine in Section~\ref{...} (See \eqref{...}).
+The resulting mechanism for \EDP{} is presented in Algorithm~\ref{mechanism}. The constant $C$ is an absolute constant, that we determine in Section~\ref{sec:proofofmainthm} (see \eqref{eq:C}).
 \begin{algorithm}
     \caption{Mechanism for \EDP{}}\label{mechanism}
     \begin{algorithmic}[1]
@@ -176,7 +176,7 @@ There is no $2$-approximate, truthful, budget feasible, individionally rational
 Suppose, for contradiction, that such a mechanism exists. Consider two experiments with dimension $d=2$, such that $x_1 = e_1=[1 ,0]$, $x_2=e_2=[0,1]$  and $c_1=c_2=B/2+\epsilon$. Then, one of the two experiments, say, $x_1$, must be in the set selected by the mechanism, otherwise the ratio is unbounded, a contradiction. If $x_1$ lowers its value to $B/2-\epsilon$, by monotonicity it remains in the solution; by  threshold payment, it is paid at least $B/2+\epsilon$. So $x_2$ is not included in the solution by budget feasibility and individual rationality: hence, the selected set attains a value $\log2$, while the optimal value is $2\log 2$.
 \end{proof}
 
-\subsection{Proof of Theorem~\ref{thm:main}}
+\subsection{Proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm}
 \stratis{individual rationality???}
 
 
@@ -274,25 +274,23 @@ $L_\mathcal{N}$.
     %\end{displaymath}
 \end{lemma}
 Its proof is our main technical contribution, and can be found in Section \ref{sec:relaxation}.
-\begin{lemma}\label{lemma:approx}
+Using this lemma, we can complete the proof of Theorem~\ref{thm:main} by showing that, %\begin{lemma}\label{lemma:approx}
     %C_{\textrm{max}} = \max\left(1+C,\frac{3e}{e-1}\left( 1 + \frac{8e}{C
     %(e-1) -10e  +2}\right)\right)
-    For any $\varepsilon > 0$, if $L(x^*)$ has been computed to a precision
+    for any $\varepsilon > 0$, if $L(x^*)$ has been computed to a precision
     $\varepsilon$, then the set $S^*$ allocated by the mechanism is such that:
-    \begin{displaymath}
+    \begin{align}
         OPT(V,\mathcal{N}, B)
-         \leq \frac{14e-3 + \sqrt{160e^2-48e + 9}}{2(e-1)} V(S^*)+ \varepsilon
-    \end{displaymath}
-\end{lemma}
-
-\begin{proof}
-    Let $x^*\in [0,1]^{n-1}$ be the true maximizer of $L_{\mathcal{N}\setminus\{i^*\}}$ subject to the budget constraints. Assume that on line 2 of algorithm~\ref{mechanism}, a quantity
+         \leq \frac{14e\!-\!3 + \sqrt{160e^2\!-\!48e\!+\!9}}{2(e\!-\!1)} V(S^*)\!+\! \varepsilon \label{approxbound}
+    \end{align}
+%\end{lemma}
+    To see this, let $x^*\in [0,1]^{n-1}$ be the true maximizer of $L_{\mathcal{N}\setminus\{i^*\}}$ subject to the budget constraints. Assume that on line 2 of algorithm~\ref{mechanism}, a quantity
     $\tilde{L}$ such that $\tilde{L}-\varepsilon\leq L_{\mathcal{N}\setminus {i^*}}(x^*) \leq
     \tilde{L}+\varepsilon$ has been computed (lemma~\ref{lemma:complexity}
     states that this  is computed in time within our complexity guarantee).
     If the condition on line 3 of the algorithm holds, then:
     \begin{displaymath}
-        V(i^*) \geq \frac{1}{C}L(x^*)-\frac{\varepsilon}{C} \geq
+        V(i^*) \geq \frac{1}{C}L_{N\setminus \{i\}}(x^*)-\frac{\varepsilon}{C} \geq
         \frac{1}{C}OPT(V,\mathcal{N}\setminus\{i\}, B) -\frac{\varepsilon}{C} 
     \end{displaymath}
     as $L$ is a fractional relaxation of $V$ on $\mathcal{N}\setminus \{i^*\}$. Also,
@@ -303,52 +301,47 @@ Its proof is our main technical contribution, and can be found in Section \ref{s
     \begin{equation}\label{eq:bound1}
         OPT(V,\mathcal{N}, B)\leq (1+C)V(i^*) + \varepsilon
     \end{equation}
-    If the condition of the algorithm does not hold, by applying Lemmas
-    \ref{lemma:relaxation} and \ref{lemma:greedy-bound}:
+    Note that $OPT(L_{\mathcal{N}\setminus\{i^*\}},B)\leq OPT(L_{\mathcal{N}},B)$. If the condition  does not hold, 
+    from Lemmas \ref{lemma:relaxation} and \ref{lemma:greedy-bound}:
     \begin{align*}
-        V(i^*) & \leq \frac{1}{C}L(x^*) + \frac{\varepsilon}{C}\leq \frac{1}{C}
+        V(i^*) & \stackrel{}\leq \frac{1}{C}L_{\mathcal{N}}(x^*) + \frac{\varepsilon}{C}\leq \frac{1}{C}
         \big(4 OPT(V,\mathcal{N}, B) + 2 V(i^*)\big) + \frac{\varepsilon}{C}\\
         & \leq \frac{1}{C}\left(\frac{4e}{e-1}\big(3 V(S_G)
         + 2 V(i^*)\big)
         + 2 V(i^*)\right) + \frac{\varepsilon}{C}
     \end{align*}
-    
-    Thus:
+    Thus, if $C$ is such that $C(e-1) -10e  +2 > 0$,
     \begin{align*}
         V(i^*) \leq \frac{12e}{C(e-1)- 10e + 2} V(S_G) 
         + \frac{(e-1)\varepsilon}{C(e-1)- 10e + 2}
     \end{align*}
-
-    Finally, using again lemma~\ref{lemma:greedy-bound}, we get:
+    Finally, using again Lemma~\ref{lemma:greedy-bound}, we get:
     \begin{multline}\label{eq:bound2}
         OPT(V, \mathcal{N}, B) \leq \frac{3e}{e-1}\left( 1 + \frac{8e}{C
         (e-1) -10e  +2}\right) V(S_G)\\
         +\frac{2e\varepsilon}{C(e-1)- 10e + 2}
     \end{multline}
-
-    Looking at \eqref{eq:bound1} and \eqref{eq:bound2}, we see that the optimal
-    value for $C$ is:
+    To minimize the coefficients of $V_{i^*}$  and $V(S_G)$  in \eqref{eq:bound1} and \eqref{eq:bound2} respectively,
+    we wish to chose for $C=C^*$ such that:
     \begin{displaymath}
         C^* = \argmin_C 
         \max\left(1+C,\frac{3e}{e-1}\left( 1 + \frac{8e}{C (e-1) -10e  +2}
         \right)\right)
     \end{displaymath}
-
     This equation has two solutions. Only one of those is such that:
-    \begin{displaymath}
-        C(e-1) -10e  +2 \geq 0
-    \end{displaymath}
-    which is needed in the above derivation. This solution is:
-    \begin{displaymath}
-        C^* =  \frac{12e-1 + \sqrt{160e^2-48e + 9}}{2(e-1)}
-    \end{displaymath}
-    For this solution we have:
-    \begin{displaymath}
-        \frac{2e\varepsilon}{C(e-1)- 10e + 2}\leq 1
-    \end{displaymath}
-    Plugging the expression of $C^*$ in \eqref{eq:bound1} and \eqref{eq:bound2}
-    gives the approximation ratio in the lemma's statement.
-\end{proof}
+      $  C(e-1) -10e  +2 \geq 0$.
+    %which is needed in the above derivation. 
+This solution is:
+    \begin{align}
+        C^* =  \frac{12e-1 + \sqrt{160e^2-48e + 9}}{2(e-1)} \label{eq:c}
+    \end{align}
+    For this solution,
+ %   \begin{displaymath}
+  $      \frac{2e\varepsilon}{C^*(e-1)- 10e + 2}\leq \varepsilon. $
+ %   \end{displaymath}
+    Placing the expression of $C^*$ in \eqref{eq:bound1} and \eqref{eq:bound2}
+    gives the approximation ratio in \eqref{approxbound}, and concludes the proof of Theorem~\ref{thm:main}.\hspace*{\stretch{1}}\qed
+%\end{proof}
 \subsection{Proof of lemma \ref{lemma:relaxation}}\label{sec:relaxation}
 
 Since $L_\mathcal{N}$ is a relaxation of the value function $V$, we have:
-- 
cgit v1.2.3-70-g09d2

