wording, proof, algo

1 files changed, 14 insertions, 17 deletions

diff --git a/main.tex b/main.tex
index cfcc97d..29056c7 100644
--- a/main.tex
+++ b/main.tex
@@ -1,15 +1,15 @@
 \label{sec:main}
 
-In this section we present our mechanism for \SEDP, uses the $\delta$-decreasing, $\epsilon$-accurate algorithm solving the convex optimization problem \eqref{eq:primal}. The construction follows a methodology employed by \citeN{Chen} and \citeN{singer-influence} to construct deterministic, truthful mechanisms for \textsc{Knapsack} and \textsc{Coverage} respectively, which we first describe below.
+In this section we use the $\delta$-decreasing, $\epsilon$-accurate algorithm solving the convex optimization problem \eqref{eq:primal} to design a mechanism for \SEDP. The construction follows a methodology employed by \citeN{chen} and \citeN{singer-influence} to construct deterministic, truthful mechanisms for \textsc{Knapsack} and \textsc{Coverage} respectively. We briefly outline this below.
 
 
 %In the strategic case, Algorithm~\eqref{eq:max-algorithm} breaks incentive compatibility. Indeed, \citeN{singer-influence} notes that this allocation function is not monotone, which implies by Myerson's theorem (Theorem~\ref{thm:myerson}) that the resulting mechanism is not truthful.
 
 Recall from Section~\ref{sec:fullinfo} that $i^*\defeq \arg\max_{i\in \mathcal{N}} V(\{i\})$ is the element of maximum value, and $S_G$ is a set constructed greedily, by selecting elements of maximum marginal value per cost. The general framework used by \citeN{chen}  and by \citeN{singer-influence} for the \textsc{Knapsack}   and \textsc{Coverage} value functions contructs an allocation as follows. First, a polynomial-time, monotone relaxation of $OPT$ is computed over all elements excluding $i^*$. The outcome of this relaxation is compared to $V(\{i^*\})$: if it exceeds $V(\{i^*\})$, then the mechanism constructs an allocation $S_G$ greedily; otherwise, the only item allocated is the singleton $\{i^*\}$.
 
-Provided that the relaxation used within a constant approximation of $OPT$, the above allocation can be shown to have a constant approximation. 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 can be solved exactly in weakly polynomial time. The challenge in our setting is dealing with a convex relaxationsolved by an $\epsilon$-accurate, $\delta$-decreasing algorithm. In our setting, this yields a $\delta$-truthful, constant approximation mechanism. 
+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, whose proof can be found in Appendix~\note{FIXME!!!}
+To obtain this result, we use the following modified version of Myerson's theorem \cite{myerson}, whose proof can be found in Appendix~\note{FIXME!!!}
 %
 %Instead, \citeN{singer-mechanisms} and \citeN{chen}
 %suggest to approximate $OPT_{-i^*}$ by a quantity $OPT'_{-i^*}$ satisfying the
@@ -59,7 +59,7 @@ To obtain this result, we use the following modified version of Myerson's theore
 \begin{lemma}\label{thm:myerson-variant}
 \sloppy A normalized mechanism $\mathcal{M} = (S,p)$ for a single parameter auction is
 $\delta$-truthful if:
-(a) $S$ is $\delta$-decreasing, \emph{i.e.}, for any agent $i$ and $c_i' \leq
+(a) $S$ is $\delta$-monotone, \emph{i.e.}, for any agent $i$ and $c_i' \leq
 c_i-\delta$, for any
 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)
@@ -68,18 +68,17 @@ c_{-i})$ implies $i\in S(c_i', c_{-i})$, and (b)
 \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\}$
+    %\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 $\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\}$
+    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}
-            \State \textbf{return} $\{i^*\}$ 
+        \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}$
-            \State $S_G \gets \emptyset$
+            \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}
@@ -92,15 +91,13 @@ c_{-i})$ implies $i\in S(c_i', c_{-i})$, and (b)
 
 \fussy
 Our mechanism for \EDP{} is composed of
-\begin{itemize}
-\item the allocation function presented in Algorithm~\ref{mechanism}, and 
-\item the payment function which pays each allocated agent $i$ her threshold
+(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).
+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}.
-\end{itemize}
 
 We can now state our main result, which is proved in Appendix~\ref{sec:proofofmainthm}:
 \begin{theorem}\label{thm:main}