From c3bbc02ac28d7019588d0c97e39b9e249ee5442a Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Sun, 4 Nov 2012 22:20:08 -0800
Subject: muthu suggestions

---
 main.tex | 23 ++++++++++++-----------
 1 file changed, 12 insertions(+), 11 deletions(-)

(limited to 'main.tex')

diff --git a/main.tex b/main.tex
index d3ba277..c79ff88 100644
--- a/main.tex
+++ b/main.tex
@@ -149,21 +149,22 @@ approximation ratio to the value function $V$ (Lemma~\ref{lemma:relaxation}).
         \EndIf
     \end{algorithmic}
 \end{algorithm}
+
 The resulting mechanism for \EDP{} is composed of (a) the allocation function
-presented in Algorithm~\ref{mechanism}; the constant $C$ is an absolute
-constant that we determine in Section~\ref{sec:proofofmainthm}
-(see \eqref{eq:c}) (b) the payment function which pays each
-allocated agent $i$ her threshold payment as described in Myerson's theorem
-(see Theorem~\ref{thm:myerson}) and 0 to unallocated agents. In the case where
+presented in Algorithm~\ref{mechanism}, and (b) the payment function which pays each
+allocated agent $i$ her threshold payment as described in Myerson's Theorem. The constant $C$ is an absolute
+constant that determined in Section~\ref{sec:proofofmainthm}
+(see \eqref{eq:c}). 
+ In the case where
 $\{i^*\}$ is the allocated set, her threshold payment is $B$ (she would be have
 been dropped on line 1 of Algorithm~\ref{mechanism} had she reported a higher
 cost). In the case where $S_G$ is the allocated set, threshold payments'
 characterization from Singer \cite{singer-mechanisms} gives a formula to
-effectively compute these payments.
+ compute these payments.
 
 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 
+    The allocation described in Algorithm~\ref{mechanism}, along with threshold payments, is truthful, individiually rational 
     and budget feasible. Furthermore, for any $\varepsilon>0$, the mechanism
     has  complexity $O\left(\text{poly}(n, d,
     \log\log \varepsilon^{-1})\right)$ and returns a set $S^*$ such that:
@@ -180,13 +181,13 @@ In addition, we prove the following lower bound.
 \begin{theorem}\label{thm:lowerbound}
 There is no $2$-approximate, truthful, budget feasible, individionally rational mechanism for EDP. 
 \end{theorem}
-\stratis{move the proof as appropriate}
+%\stratis{move the proof as appropriate}
 \begin{proof}
 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}}\label{sec:proofofmainthm}
-\stratis{individual rationality???}
+%\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}. Truthfulness and individual
 rationality follows from monotonicity and threshold payments.  Monotonicity and
@@ -301,11 +302,11 @@ Using this lemma, we can complete the proof of Theorem~\ref{thm:main} by showing
     If the condition on line 3 of the algorithm holds, then:
     \begin{displaymath}
         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} 
+        \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,
     \begin{displaymath}
-        OPT(V,\mathcal{N},B) \leq OPT(V,\mathcal{N}\setminus\{i\}, B) + V(i^*)
+        OPT(V,\mathcal{N},B) \leq OPT(V,\mathcal{N}\setminus\{i^*\}, B) + V(i^*)
     \end{displaymath}
     Hence:
     \begin{equation}\label{eq:bound1}
-- 
cgit v1.2.3-70-g09d2

