moved algo to appendix

1 files changed, 65 insertions, 26 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