paper

2 files changed, 3 insertions, 4 deletions

diff --git a/approximation.tex b/approximation.tex
index 670352b..7c3c47d 100644
--- a/approximation.tex
+++ b/approximation.tex
@@ -1,4 +1,4 @@
-Previous approaches towards designing truthful, budget feasible mechanisms for \textsc{Knapsack}~\cite{chen} and the \textsc{Coverage}~\cite{singer-influence} build upon polynomial-time algorithms that compute an approximation of $OPT$, the optimal value in the full information case. Crucially, to be used in designing a truthful mechanism, such algorithms need also to be \emph{monotone}, in the sense that decreasing any of the costs $c_i$ leads to an increase of the estimate of $OPT$. Both in the cases of \textsc{Knapsack}~\cite{chen} and~\textsc{Coverage}, as well as in the case of \EDP{}, the monotonicity requirement prevents using traditional approximation algorithms for approximating any of the above problems.
+Previous approaches towards designing truthful, budget feasible mechanisms for \textsc{Knapsack}~\cite{chen} and \textsc{Coverage}~\cite{singer-influence} build upon polynomial-time algorithms that compute an approximation of $OPT$, the optimal value in the full information case. Crucially, to be used in designing a truthful mechanism, such algorithms need also to be \emph{monotone}, in the sense that decreasing any of the costs $c_i$ leads to an increase of the estimate of $OPT$. In the cases of \textsc{Knapsack} and~\textsc{Coverage}, as well as in the case of \EDP{},  monotonicity  prevents using traditional approximation algorithms.
 
 We address this issue by designing a convex relaxation of \EDP{}, and showing that it well approximates $OPT$. 
 
diff --git a/problem.tex b/problem.tex
index c35780c..4e31ac1 100644
--- a/problem.tex
+++ b/problem.tex
@@ -208,10 +208,10 @@ Ideally, we would like the allocation $S$ to be of maximal value; however, truth
     %time in the number of agents $n$. %\thibaut{Should we say something about the black-box model for $V$?  Needed to say something in general, but not in our case where the value function can be computed in polynomial time}.
 \end{itemize}
 
+\begin{comment}
 As noted in \cite{singer-mechanisms, chen}, budget feasible reverse auctions are  \emph{single parameter} auctions: each agent has only one
 private value (namely, $c_i$). As such, Myerson's Theorem \cite{myerson} gives
 a characterization of truthful mechanisms. We use the following variant of the theorem: %NEEDS TO BE FIXED
-\begin{comment}
 \begin{lemma}[\citeN{myerson}]\label{thm:myerson}
 \sloppy A normalized mechanism $\mathcal{M} = (S,p)$ for a single parameter auction is
 truthful iff:
@@ -224,7 +224,6 @@ 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{enumerate}
 \end{lemma}
-\end{comment}
 
 \begin{lemma}[\citeN{myerson}]\label{thm:myerson-variant}
 \sloppy A normalized mechanism $\mathcal{M} = (S,p)$ for a single parameter auction is
@@ -241,7 +240,7 @@ Myerson's Theorem
 % is particularly useful when designing a budget feasible truthful mechanism, as it 
 allows us to focus on designing a monotone allocation function $S$. Then, the
 mechanism will be truthful as long as we give each agent her threshold payment---the caveat being that the latter need to sum to a value below $B$.
-
+\end{comment}
 \begin{comment}
 \subsection{Budget Feasible Experimental Design}