Reduce section 5, currate appendices, reduce bib

1 files changed, 5 insertions, 69 deletions

diff --git a/main.tex b/main.tex
index a7dc8ba..a01d780 100644
--- a/main.tex
+++ b/main.tex
@@ -1,72 +1,11 @@
 \label{sec:main}
 
-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 proposed in \cite{singer-mechanisms} and 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 (see also Algorithm~\ref{mechanism} in Appendix~\ref{sec:proofofmainthm} for a detailed description).
+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.
 
 
 %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 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 Appendix~\ref{sec:myerson}.
-%
-%Instead, \citeN{singer-mechanisms} and \citeN{chen}
-%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 cost and must
-%    be decreasing with respect to the costs. This is to ensure the monotonicity
-%    of the allocation function.
-%    \item $OPT'_{-i^*}$ must be close to $OPT_{-i^*}$ to maintain a bounded
-%    approximation ratio.
-%    \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 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{definition}
-%Let $\mathcal{M}= (S, p)$ a mechanism, and let $s_i$ denote the indicator
-%function of $i\in S(c)$, $s_i(c) \defeq \id_{i\in S(c)}$. We say that $\mathcal{M}$ is
-%$\delta$-truthful iff:
-%\begin{displaymath}
-%\forall c\in\reals_+^n,\;
-%\forall\mu\;\text{with}\; |\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 canonical basis vector of $\reals^n$.
-%\end{definition}
-%
-%Intuitively, $\delta$-truthfulness implies that agents have no incentive to lie
-%by more than $\delta$ about their reported costs. In practical applications,
-%the bids being discretized, if $\delta$ is smaller than the discretization
-%step, the mechanism will be truthful in effect.
-
-%$\delta$-truthfulness will follow from $\delta$-monotonicity by the following
-%variant of Myerson's theorem.
-
-\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:
-\begin{theorem}\label{thm:main}
+\begin{theorem}\label{thm:main}\label{thm:lowerbound}
     For any $\delta\in(0,1]$, and any $\epsilon\in (0,1]$,  there exists a $\delta$-truthful, individually rational
     and budget feasible mechanim for \EDP{} that runs in time
     $O\big(poly(n, d, \log\log\frac{B}{b\varepsilon\delta})\big)$
@@ -78,14 +17,11 @@ Lemma~\ref{thm:myerson-variant} allows us to incorporate our relaxation in the a
         \varepsilon
          \simeq 12.98V(S^*) + \varepsilon.
      \end{displaymath}
-\end{theorem}
-The proof of the theorem, as well as our proposed mechanism, can be found in Appendix~\ref{sec:proofofmainthm}.
-In addition, we prove the following simple lower bound, proved in Appendix~\ref{proofoflowerbound}.
-
-\begin{theorem}\label{thm:lowerbound}
-There is no $2$-approximate, truthful, budget feasible, individually rational
+Furthemore, there is no $2$-approximate, truthful, budget feasible, individually rational
 mechanism for EDP. 
 \end{theorem}
+The detailed description of our proposed mechanism (see Algorithm~\ref{mechanism}), as well as the proof of the theorem can be found in Appendix~\ref{sec:proofofmainthm}.
+