From d5f4afbbf188d745439e0e15b1857fb696477d70 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Mon, 24 Jun 2013 23:01:34 +0200
Subject: Unifying pass over the whole paper

---
 main.tex | 65 ++++++++++++++++++++++++++++++++++++++++++++++------------------
 1 file changed, 47 insertions(+), 18 deletions(-)

(limited to 'main.tex')

diff --git a/main.tex b/main.tex
index 21260e1..0e8457c 100644
--- a/main.tex
+++ b/main.tex
@@ -50,7 +50,7 @@ in the full-information case, cannot be computed in poly-time when the
 underlying problem is NP-hard (unless P=NP), as is the case for \SEDP{}.
 
 Instead, \citeN{singer-mechanisms} and \citeN{chen}
-suggest to replace $OPT_{-i^*}$ by a quantity $OPT'_{-i^*}$ satisfying the
+suggest to approximate $OPT_{-i^*}$ by a quantity $OPT'_{-i^*}$ satisfying the
 following properties:
 \begin{itemize}
     \item $OPT'_{-i^*}$ must not depend on agent $i^*$'s reported
@@ -61,27 +61,52 @@ following properties:
     \item $OPT'_{-i^*}$ must be computable in polynomial time.
 \end{itemize}
 
-
 One of the main technical contributions of \citeN{chen} and
-\citeN{singer-influence} is to come up with appropriate such relaxations for
-\textsc{Knapsack} and \textsc{Coverage}, respectively.
+\citeN{singer-influence} is to come up with appropriate such quantity by
+considering relaxations of \textsc{Knapsack} and \textsc{Coverage},
+respectively.
 
 \subsection{Our Approach}
 
+Using the results from Section~\ref{sec:approximation}, we come up with
+a suitable approximation $OPT_{-i^*}'$ of $OPT_{-i^*}$. Our approximation being
+$\delta$-decreasing, the resulting mechanism will be $\delta$-truthful as
+defined below.
 
-\begin{comment}
-The main challenge
-will be to prove that $OPT'_{-i^*}$, for our relaxation $L$, is close to
-$OPT_{-i^*}$. 
-We show this by establishing that $L$ is within a constant factor from the so-called multi-linear relaxation of  \eqref{modified}, which in turn can be related to \eqref{modified} through pipage rounding. We establish the constant factor to the multi-linear relaxation by bounding  the partial derivatives of these two functions; we obtain the latter bound by exploiting convexity properties of matrix functions over the convex cone of positive semidefinite matrices.
-\end{comment}
+\begin{definition}
+Let $\mathcal{M}= (S, p)$ a mechanism, and let $s$ denote the indicator
+function of $S$ ($s_i(c) = \id_{i\in S(c)}$). We say that $\mathcal{M}$ is
+$\delta$-truthful iff:
+\begin{displaymath}
+\forall c\in\reals_+^n,\;
+\forall\mu\geq\delta,\;
+\forall i\in\{1,\ldots,n\},\;
+p(c)-s_i(c)\cdot c_i \geq p(c+\mu e_i) - s_i(c+\mu e_i)\cdot c_i
+\end{displaymath}
+where $e_i$ is the $i$-th basis vector of $\reals^n$.
+\end{definition}
+
+$\delta$-truthfulness will follow from $\delta$-monotonicity by the following
+variant of Myerson's theorem.
+
+\begin{lemma}\label{thm:myerson-variant}
+\sloppy A normalized mechanism $\mathcal{M} = (S,p)$ for a single parameter auction is
+$\delta$-truthful iff:
+(a) $S$ is $\delta$-decreasing, \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)
+ 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\}$
     \State $i^* \gets \argmax_{j\in\mathcal{N}}V(j)$
-    \State $OPT'_{-i^*} \gets \max_{\lambda\in[0,1]^{n}} \{L(\lambda)
+    \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\}$
         \Statex
         \If{$OPT'_{-i^*} < C \cdot V(i^*)$} \label{c}
@@ -100,7 +125,7 @@ We show this by establishing that $L$ is within a constant factor from the so-ca
 \end{algorithm}
 
 \fussy
-In summary, the resulting mechanism for \EDP{} is composed of
+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
@@ -114,11 +139,13 @@ be found in~\cite{singer-mechanisms}.
 We can now state our main result:
 \begin{theorem}\label{thm:main}
     \sloppy
-    The allocation described in Algorithm~\ref{mechanism}, along with threshold
-    payments, is truthful, individually rational and budget feasible.
-    Furthermore, there exists an absolute constant $C$ such that, for any
-    $\varepsilon>0$, the mechanism runs in time  $O\left(\text{poly}(n, d,
-    \log\log \varepsilon^{-1})\right)$ and returns a set $S^*$ such that:
+    For any $\delta$, the allocation described in Algorithm~\ref{mechanism},
+    along with threshold payments, is $\delta$-truthful, individually rational
+    and budget feasible.  Furthermore, there exists an absolute constant $C$
+    such that, for any $\varepsilon>0$, the mechanism runs in time
+    $O\big(poly(n, d, \log\log\frac{1}{b\varepsilon\delta})\big)$
+    and returns
+    a set $S^*$ such that:
     \begin{align*}
         OPT
         & \leq \frac{10e-3 + \sqrt{64e^2-24e + 9}}{2(e-1)} V(S^*)+
@@ -129,7 +156,9 @@ We can now state our main result:
 The value of the constant $C$ is given by \eqref{eq:constant} in
 Section~\ref{sec:proofofmainthm}.
 In addition, we prove the following simple lower bound.
+
 \begin{theorem}\label{thm:lowerbound}
-There is no $2$-approximate, truthful, budget feasible, individually rational mechanism for EDP. 
+There is no $2$-approximate, truthful, budget feasible, individually rational
+mechanism for EDP. 
 \end{theorem}
 
-- 
cgit v1.2.3-70-g09d2

