From 7f6b960702e38cf2e34d5594ba2b37a45f8a9520 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Thu, 12 Dec 2013 17:48:03 -0500
Subject: Reimport things from the appendix to the main part for the
 camera-ready version

---
 main.tex | 38 +++++++++++++++++++++++++++++++++++++-
 1 file changed, 37 insertions(+), 1 deletion(-)

(limited to 'main.tex')

diff --git a/main.tex b/main.tex
index 66ef875..ebb853f 100755
--- a/main.tex
+++ b/main.tex
@@ -2,6 +2,42 @@
 
 The $\delta$-decreasing, $\epsilon$-accurate algorithm solving the convex optimization problem \eqref{eq:primal} can be used to design a mechanism for \SEDP. The construction follows a methodology proposed in \cite{singer-mechanisms} and employed by \citeN{chen} and \citeN{singer-influence} to construct \junk{deterministic, truthful} mechanisms for \textsc{Knapsack} and \textsc{Coverage} respectively. The following theorem summarizes the properties of our merchanism.
 
+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 approximation of
+$OPT$ is computed over all elements excluding $i^*$. The outcome of this
+approximation 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 approximation used is
+within a constant from $OPT$, the above allocation can be shown to also yield
+a constant approximation to $OPT$. Furthermore, using Myerson's
+Theorem~\cite{myerson}, it can be shown that this allocation combined with
+\emph{threshold payments} (see Lemma~\ref{thm:myerson-variant} below)
+constitute a truthful mechanism. 
+
+The approximation algorithms used in \cite{chen,singer-influence} are LP
+relaxations, and thus their outputs are monotone and can be computed exactly in
+polynomial time. We show 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, by
+being incorporated in the same framework.
+
+To obtain this result, we use the following modified version of Myerson's theorem \cite{myerson}, whose proof we provide in \cite{arxiv}.
+
+\begin{lemma}\label{thm:myerson-variant}
+ A normalized mechanism $\mathcal{M} = (S,p)$ for a single parameter auction is
+$\delta$-truthful if:
+(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)
+ 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}
+Lemma~\ref{thm:myerson-variant} allows us to incorporate our relaxation in the
+above framework, yielding the following theorem:
 
 %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.
 
@@ -20,7 +56,7 @@ The $\delta$-decreasing, $\epsilon$-accurate algorithm solving the convex optimi
 Furthemore, there is no $2$-approximate, truthful, budget feasible, individually rational
 mechanism for EDP. 
 \end{theorem}
-The detailed description of our proposed mechanism (Algorithm~\ref{mechanism}), as well as the proof of the theorem can be found in Appendix~\ref{sec:proofofmainthm}.
+The detailed description of our proposed mechanism as well as the proof of the theorem can be found in \cite{arxiv}.
 
 
 
-- 
cgit v1.2.3-70-g09d2

