From c059a66195ec638e3c757be0da8b5b8e8a4040d7 Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Sun, 4 Nov 2012 16:25:44 -0800
Subject: lower bound mentioned in frac rel

---
 main.tex | 16 +++++-----------
 1 file changed, 5 insertions(+), 11 deletions(-)

(limited to 'main.tex')

diff --git a/main.tex b/main.tex
index 3d89d16..0448dab 100644
--- a/main.tex
+++ b/main.tex
@@ -150,7 +150,6 @@ The resulting mechanism for \EDP{} is presented in Algorithm~\ref{mechanism}. Th
         \EndIf
     \end{algorithmic}
 \end{algorithm}
-
 We can now state our main result:
 \begin{theorem}\label{thm:main}
     There exists an absolute constant $C$ such that the mechanism described in Algorithm~\ref{mechanism} is truthful, individiually rational 
@@ -164,7 +163,6 @@ We can now state our main result:
         & \simeq 19.68V(S^*) + \varepsilon
     \end{align*}
 \end{theorem}
-
 %\stratis{Add lowerbound here too.}
 Note that this implies we construct a poly-time mechanism with accuracy arbitrarily close to 19.68, by taking $\varepsilon = \ldots$\stratis{fix me}.
 In addition, we prove the following lower bound.
@@ -178,19 +176,15 @@ Suppose, for contradiction, that such a mechanism exists. Consider two experimen
 
 \subsection{Proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm}
 \stratis{individual rationality???}
-
-
 %The proof of the properties of the mechanism is broken down into lemmas.
 We now present the proof of Theorem~\ref{thm:main}.
 Monotonicity and budget feasibility follows from the analysis of Chen \emph{et al.} \cite{chen};  we briefly restate the proofs for the sake of completeness.
  Our proof of the approximation ratio and uses a bound on our concave relaxation
 $L_\mathcal{N}$ (Lemma~\ref{lemma:relaxation}). This is our main technical
 contribution; the proof of this lemma can be found in Section~\ref{sec:relaxation}.
-
 \begin{lemma}\label{lemma:monotone}
 The mechanism is monotone.
 \end{lemma}
-
 \begin{proof}
     Consider an agent $i$ with cost $c_i$ that is
     selected by the mechanism, and suppose that she reports
@@ -217,11 +211,9 @@ The mechanism is monotone.
     Reporting $c_{i^*}'\leq c_{i^*}$ does not change $V(i^*)$ nor
     $L_{\mathcal{N}\setminus \{i^*\}}(xi) \leq C V(i^*)$; thus $s_{i^*}(c_{i^*}',c_{-i^*})=1$. 
 \end{proof}
-
 \begin{lemma}\label{lemma:budget-feasibility}
 The mechanism is budget feasible.
 \end{lemma}
-
 \begin{proof}
 Suppose that $L_{\mathcal{N}\setminus\{i^*\}}(\xi) < C V(i^*)$. Then the mechanism selects $i^*$; as the bid of $i^*$ does not affect the above condition, the threshold payment of $i^*$ is $B$ and the mechanism is budget feasible.
 Suppose thus that $L_{\mathcal{N}\setminus\{i^*\}}(\xi) \geq C V(i^*)$. 
@@ -263,15 +255,17 @@ Hence, the total payment is bounded by the telescopic sum:
 \end{proof}
 
 Finally, we prove the approximation ratio of the mechanism. We use the
-following lemma, which gives an approximation ratio of the function
-$L_\mathcal{N}$. 
+following lemma, which establishes the optimal fractional relaxation
+$L_\mathcal{N}$ is not too far from $OPT(V,\mathcal{N},B)$.  
 \begin{lemma}\label{lemma:relaxation}
     %\begin{displaymath}
      $   OPT(L_\mathcal{N}, B) \leq 4 OPT(V,\mathcal{N},B)
         + 2\max_{i\in\mathcal{N}}V(i)$
     %\end{displaymath}
 \end{lemma}
-Its proof is our main technical contribution, and can be found in Section \ref{sec:relaxation}.
+Note that the lower bound $OPT(L_\mathcal{N}, B) \geq  OPT(V,\mathcal{N},B)
+$ also holds trivially, as $L_{\mathcal{N}}$ is a fractional relaxation of $V$ over $\mathcal{N}$.
+The proof of Lemma~\ref{lemma:relaxation} is our main technical contribution, and can be found in Section \ref{sec:relaxation}.
 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)
-- 
cgit v1.2.3-70-g09d2

