moved algo to appendix

2 files changed, 66 insertions, 59 deletions

diff --git a/appendix.tex b/appendix.tex
index 5dce278..0f6e6b4 100644
--- a/appendix.tex
+++ b/appendix.tex
@@ -214,7 +214,7 @@ the proof of the lemma. \qed
     \end{displaymath}
     which is positive by submodularity of $V$. Hence, the maximum of
     $F_\lambda$ over the interval given in \eqref{eq:convex-interval} is
-    attained at one of its limit, at which either the $i$-th or $j$-th component of
+    attained at one of its limits, at which either the $i$-th or $j$-th component of
     $\lambda_\varepsilon$ becomes integral. \qed
 %\end{proof}
 \subsection{Proof of Proposition~\ref{prop:relaxation}}\label{proofofproprelaxation}
@@ -469,12 +469,12 @@ the inner inequality follows from Lemma~\ref{lemma:monotonicity}.
 
 \item the accuracy of the approximation $\hat{L}^*_{c,\alpha}$ is:
 \begin{displaymath}
-    A\defeq\frac{\varepsilon\delta b}{2^{n+1}(\delta + n^2B)}
+    \varepsilon' =\frac{\varepsilon\delta b}{2^{n+1}(\delta + n^2B)}
 \end{displaymath}
 
 Note that:
 \begin{displaymath}
-    \log\log A^{-1} = O\bigg(\log\log\frac{B}{\varepsilon\delta b} + \log n\bigg)
+    \log\log (\varepsilon')^{-1} = O\bigg(\log\log\frac{B}{\varepsilon\delta b} + \log n\bigg)
 \end{displaymath}
 Using Lemma~\ref{lemma:barrier} concludes the proof of the running time.\qed
 \end{enumerate}
@@ -482,7 +482,7 @@ Using Lemma~\ref{lemma:barrier} concludes the proof of the running time.\qed
 \section{Budget Feasible Reverse Auction Mechanisms}\label{app:budgetfeasible}
 We review in this appendix the formal definition of a budget feasible reverse auction mechanisms, as introduced by \citeN{singer-mechanisms}. We depart from the definitions in \cite{singer-mechanisms} only in considering $\delta$-truthful, rather than truthful, mechanisms.
 
-Given a budget $B$ and a value function $V:2^{\mathcal{N}}\to\reals_+$, a \emph{mechanism} $\mathcal{M} = (S,p)$ comprises (a) an \emph{allocation function}\footnote{Note that $S$ would be more aptly termed as a \emph{selection} function, as this is a reverse auction, but we retain the term ``allocation'' to align with the familiar term from standard auctions.}
+Given a budget $B$ and a value function $V:2^{\mathcal{N}}\to\reals_+$, a \emph{mechanism} $\mathcal{M} = (S,p)$ comprises (a) an \emph{allocation function} 
 $S:\reals_+^n \to 2^\mathcal{N}$ and (b) a \emph{payment function}
 $p:\reals_+^n\to \reals_+^n$. 
  Let $s_i(c) = \id_{i\in S(c)}$ be the binary indicator of  $i\in S(c)$. We seek mechanisms that have the following properties \cite{singer-mechanisms}:
@@ -516,8 +516,48 @@ Formally, there must exist some $\alpha\geq 1$
 
 
 \section{Proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm}
+\begin{algorithm}[!t]
+    \caption{Mechanism for \SEDP{}}\label{mechanism}
+    \begin{algorithmic}[1]
+    %\State $\mathcal{N} \gets \mathcal{N}\setminus\{i\in\mathcal{N} : c_i > B\}$
+	\Require{ $B\in \reals_+$,$c\in[0,B]^n$, $\delta\in (0,1]$, $\epsilon\in (0,1]$ }
+    \State $i^* \gets \argmax_{j\in\mathcal{N}}V(j)$
+    \State \label{relaxexec}$OPT'_{-i^*} \gets$ using Proposition~\ref{prop:monotonicity},
+    compute a $\varepsilon$-accurate, $\delta$-decreasing
+    approximation of $$\textstyle L^*_{c_{-i^*}}\defeq\max_{\lambda\in[0,1]^{n}} \{L(\lambda)
+                                    \mid \lambda_{i^*}=0,\sum_{i \in \mathcal{N}\setminus\{i^*\}}c_i\lambda_i\leq B\}$$
+        %\Statex
+     \State $C \gets \frac{8e-1 + \sqrt{64e^2-24e + 9}}{2(e-1)}$
+
+        \If{$OPT'_{-i^*} < C \cdot V(i^*)$} \label{c} 
+       \State \textbf{return} $\{i^*\}$ 
+        \Else
+            \State $i \gets \argmax_{1\leq j\leq n}\frac{V(j)}{c_j}$
+	    \State $S_G \gets \emptyset$
+            \While{$c_i\leq \frac{B}{2}\frac{V(S_G\cup\{i\})-V(S_G)}{V(S_G\cup\{i\})}$}
+                \State $S_G \gets S_G\cup\{i\}$ 
+ \State $i \gets \argmax_{j\in\mathcal{N}\setminus S_G}
+                \frac{V(S_G\cup\{j\})-V(S_G)}{c_j}$
+            \EndWhile
+            \State \textbf{return} $S_G$
+        \EndIf
+    \end{algorithmic}
+\end{algorithm}
+
+
+We now present the proof of Theorem~\ref{thm:main}. 
+Our mechanism for \EDP{} is composed of
+(a) the allocation function 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.  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).
+A closed-form formula for threshold payments when $S_G$ is the allocated set can
+be found in~\cite{singer-mechanisms}. 
+
+
+We use the notation $OPT_{-i^*}$ to denote the optimal value of \EDP{} when the maximum value element $i^*$ is  excluded. We also use $OPT'_{-i^*}$ to denote the approximation computed by the $\delta$-decreasing, $\epsilon$-accurate approximation of $L^*_{c_{-i^*}}$, as defined in Algorithm~\ref{mechanism}.
 
-We now present the proof of Theorem~\ref{thm:main}. We use the notation $OPT_{-i^*}$ to denote the optimal value of \EDP{} when the maximum value element $i^*$ is  excluded. We also use $OPT'_{-i^*}$ the approximation computed by the $\delta$-decreasing, $\epsilon$-accurate approximation of $L^*_{c_{-i^*}}$, as defined in Algorithm~\ref{mechanism}.
 
 The properties of $\delta$-truthfulness and
 individual rationality follow from $\delta$-monotonicity and threshold
@@ -574,7 +614,7 @@ implies that the threshold payment of user $i$ is bounded by the above quantity.
 %\end{displaymath}
 Hence, the total payment is bounded by the telescopic sum:
 \begin{displaymath}
-    \sum_{i\in S_G} \frac{V(S_i\cup\{i\}) - V(S_i)}{V(S_G)} B = \frac{V(S_G)-V(\emptyset)}{V(S_G)} B=B\qed
+    \sum_{i\in S_G} \frac{V(S_i\cup\{i\}) - V(S_i)}{V(S_G)} B = \frac{V(S_G)-V(\emptyset)}{V(S_G)} B=B\qedhere
 \end{displaymath}
 \end{proof}
 
@@ -589,7 +629,6 @@ The complexity of the mechanism is given by the following lemma.
     The value function $V$ in \eqref{modified} can be computed in time
     $O(\text{poly}(n, d))$ and the mechanism only involves a linear
     number of queries to the function $V$. 
-
     By Proposition~\ref{prop:monotonicity}, line 3 of Algorithm~\ref{mechanism}
     can be computed in time
     $O(\text{poly}(n, d, \log\log \frac{B}{b\varepsilon\delta}))$. Hence the allocation
@@ -626,26 +665,25 @@ OPT
 \leq \frac{10e\!-\!3 + \sqrt{64e^2\!-\!24e\!+\!9}}{2(e\!-\!1)} V(S^*)\!
 + \! \varepsilon .
 \end{equation}
-To see this, let $L^*_{-i^*}$ be the true maximum value of $L$ subject to
-$\lambda_{i^*}=0$, $\sum_{i\in \mathcal{N}\setminus{i^*}}c_i\leq B$. From line
-3 of Algorithm~\ref{mechanism}, we have
-$L^*_{-i^*}-\varepsilon\leq OPT_{-i^*}' \leq L^*_{-i^*}+\varepsilon$.
+To see this, let $L^*_{c_{-i^*}}$ be the true maximum value of $L$ subject to
+$\lambda_{c_{-i^*}}=0$, $\sum_{i\in \mathcal{N}\setminus{i^*}}c_i\leq B$. From line
+\ref{relaxexec} of Algorithm~\ref{mechanism}, we have
+$L^*_{c_{-i^*}}-\varepsilon\leq OPT_{-i^*}' \leq L^*_{c_{-i^*}}+\varepsilon$.
 
-If the condition on line 4 of the algorithm holds, then
+If the condition on line \ref{c} of the algorithm holds then, from the lower bound in Proposition~\ref{prop:relaxation},
 \begin{displaymath}
-    V(i^*) \geq \frac{1}{C}L^*_{-i^*}-\frac{\varepsilon}{C} \geq
+    V(i^*) \geq \frac{1}{C}L^*_{c_{-i^*}}-\frac{\varepsilon}{C} \geq
     \frac{1}{C}OPT_{-i^*} -\frac{\varepsilon}{C}.
 \end{displaymath}
-Indeed, $L^*_{-i^*}\geq OPT_{-i^*}$ as $L$ is a fractional relaxation of $V$. Also, $OPT \leq OPT_{-i^*} + V(i^*)$,
+Also, $OPT \leq OPT_{-i^*} + V(i^*)$,
 hence,
 \begin{equation}\label{eq:bound1}
     OPT\leq (1+C)V(i^*) + \varepsilon.
 \end{equation}
-
-If the condition  does not hold, by observing that $L^*_{-i^*}\leq L^*_c$ and
-applying Proposition~\ref{prop:relaxation}, we get
+If the condition on line \ref{c} does not hold, by observing that $L^*_{c_{-i^*}}\leq L^*_c$ and
+the upper bound of Proposition~\ref{prop:relaxation}, we get
 \begin{displaymath}
-    V(i^*)\leq \frac{1}{C}L^*_{-i^*} + \frac{\varepsilon}{C}
+    V(i^*)\leq \frac{1}{C}L^*_{c_{-i^*}} + \frac{\varepsilon}{C}
     \leq \frac{1}{C} \big(2 OPT + 2 V(i^*)\big) + \frac{\varepsilon}{C}.
 \end{displaymath}
 Applying Lemma~\ref{lemma:greedy-bound},
@@ -653,7 +691,7 @@ Applying Lemma~\ref{lemma:greedy-bound},
     V(i^*) \leq \frac{1}{C}\left(\frac{2e}{e-1}\big(3 V(S_G)
     + 2 V(i^*)\big) + 2 V(i^*)\right) + \frac{\varepsilon}{C}.
 \end{displaymath}
-Thus, if $C$ is such that $C(e-1) -6e  +2 > 0$,
+Note that $C$ satifies $C(e-1) -6e  +2 > 0$, hence
 \begin{align*}
     V(i^*) \leq \frac{6e}{C(e-1)- 6e + 2} V(S_G) 
     + \frac{(e-1)\varepsilon}{C(e-1)- 6e + 2}.
@@ -664,18 +702,19 @@ Finally, using Lemma~\ref{lemma:greedy-bound} again, we get
     \frac{3e}{e-1}\left( 1 + \frac{4e}{C (e-1) -6e  +2}\right) V(S_G)
     + \frac{2e\varepsilon}{C(e-1)- 6e + 2}.
 \end{equation}
-To minimize the coefficients of $V_{i^*}$  and $V(S_G)$  in \eqref{eq:bound1}
-and \eqref{eq:bound2} respectively, we wish to chose $C$ that minimizes
+Our choice of $C$, namely,
+\begin{equation}\label{eq:constant}
+    C =  \frac{8e-1 + \sqrt{64e^2-24e + 9}}{2(e-1)},
+\end{equation}
+ is precisely to minimize the maximum among the coefficients of $V_{i^*}$  and $V(S_G)$  in \eqref{eq:bound1}
+and \eqref{eq:bound2}, respectively. Indeed, consider:
 \begin{displaymath}
     \max\left(1+C,\frac{3e}{e-1}\left( 1 + \frac{4e}{C (e-1) -6e  +2}
             \right)\right).
 \end{displaymath}
 This function has two minima, only one of those is such that $C(e-1) -6e
-+2 \geq 0$. This minimum is
-\begin{equation}\label{eq:constant}
-    C =  \frac{8e-1 + \sqrt{64e^2-24e + 9}}{2(e-1)}.
-\end{equation}
-For this minimum, $\frac{2e\varepsilon}{C^*(e-1)- 6e + 2}\leq \varepsilon.$
++2 \geq 0$. This minimum is precisely \eqref{eq:constant}.
+For this minimum, $\frac{2e\varepsilon}{C(e-1)- 6e + 2}\leq \varepsilon.$
 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
diff --git a/main.tex b/main.tex
index a751621..859c8f4 100644
--- a/main.tex
+++ b/main.tex
@@ -9,7 +9,7 @@ Recall from Section~\ref{sec:fullinfo} that $i^*\defeq \arg\max_{i\in \mathcal{N
 
 Provided that the relaxation used within a constant from $OPT$, the above allocation can be shown to also yield a constant approximation to $OPT$. Furthermore, this allocation combined with \emph{threshold payments}, the mechanism can be shown to be truthful when the relaxation is monotone. The relaxations used in \cite{chen,singer-influence} are linear programs, and thus their optimal values are monotone and can be computed exactly in weakly polynomial time. In contrast, we extend these results by showing that the convex relaxation \eqref{eq:primal}, which can be solved by an $\epsilon$-accurate, $\delta$-decreasing algorithm, can be used to construct a $\delta$-truthful, constant approximation mechanism. 
 
-To obtain this result, we use the following modified version of Myerson's theorem \cite{myerson}, whose proof can be found in Appendix~\ref{sec:myerson}.
+To obtain this result, we use the following modified version of Myerson's theorem \cite{myerson}, whose proof we provide in Appendix~\ref{sec:myerson}.
 %
 %Instead, \citeN{singer-mechanisms} and \citeN{chen}
 %suggest to approximate $OPT_{-i^*}$ by a quantity $OPT'_{-i^*}$ satisfying the
@@ -65,39 +65,7 @@ fixed costs $c_{-i}$ of agents in $\mathcal{N}\setminus\{i\}$, $i\in S(c_i,
 c_{-i})$ implies $i\in S(c_i', c_{-i})$, and (b)
  agents are paid \emph{threshold payments}, \emph{i.e.}, for all $i\in S(c)$, $p_i(c)=\inf\{c_i': i\in S(c_i', c_{-i})\}$.
 \end{lemma}
-\begin{algorithm}[t]
-    \caption{Mechanism for \SEDP{}}\label{mechanism}
-    \begin{algorithmic}[1]
-    %\State $\mathcal{N} \gets \mathcal{N}\setminus\{i\in\mathcal{N} : c_i > B\}$
-	\Require{ $B\in \reals_+$,$c\in[0,B]^n$, $\delta\in (0,1]$, $\epsilon\in (0,1]$ }
-    \State $i^* \gets \argmax_{j\in\mathcal{N}}V(j)$
-    \State $OPT'_{-i^*} \gets$ using Proposition~\ref{prop:monotonicity},
-    compute a $\varepsilon$-accurate, $\delta$-decreasing
-    approximation of $$\textstyle L^*_{c_{-i^*}}\defeq\max_{\lambda\in[0,1]^{n}} \{L(\lambda)
-                                    \mid \lambda_{i^*}=0,\sum_{i \in \mathcal{N}\setminus\{i^*\}}c_i\lambda_i\leq B\}$$
-        \Statex
-        \If{$OPT'_{-i^*} < C \cdot V(i^*)$} \label{c} \textbf{return} $\{i^*\}$ 
-        \Else
-            \State $i \gets \argmax_{1\leq j\leq n}\frac{V(j)}{c_j}$; $S_G \gets \emptyset$
-            \While{$c_i\leq \frac{B}{2}\frac{V(S_G\cup\{i\})-V(S_G)}{V(S_G\cup\{i\})}$}
-                \State $S_G \gets S_G\cup\{i\}$
-                \State $i \gets \argmax_{j\in\mathcal{N}\setminus S_G}
-                \frac{V(S_G\cup\{j\})-V(S_G)}{c_j}$
-            \EndWhile
-            \State \textbf{return} $S_G$
-        \EndIf
-    \end{algorithmic}
-\end{algorithm}
-
 \fussy
-Our mechanism for \EDP{} is composed of
-(a) the allocation function 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.  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).
-A closed-form formula for threshold payments when $S_G$ is the allocated set can
-be found in~\cite{singer-mechanisms}.
 
 We can now state our main result, which is proved in Appendix~\ref{sec:proofofmainthm}:
 \begin{theorem}\label{thm:main}