Strating addressing Stratis' comments

1 files changed, 41 insertions, 64 deletions

diff --git a/main.tex b/main.tex
index c1db3fc..f799410 100644
--- a/main.tex
+++ b/main.tex
@@ -18,33 +18,27 @@ One possible interpretation of \eqref{modified} is that, prior to the auction, t
 In this section we present a mechanism for \EDP. Previous works on maximizing
 submodular functions \cite{nemhauser, sviridenko-submodular} and designing
 auction mechanisms for submodular utility functions \cite{singer-mechanisms,
-chen, singer-influence} rely on a greedy heuristic. In this heuristic, points
+chen, singer-influence} rely on a greedy heuristic. In this heuristic, elements
 are added to the solution set according to the following greedy selection rule:
-assume that you have already selected a set $S$ of point, then the next point
-to be selected is:
+assume that you have already selected a set $S$, then the next element to be
+included in the solution set is:
 \begin{displaymath}
     i = \argmax_{j\in\mathcal{N}\setminus S}\frac{V(S\cup\{i\}) - V(S)}{c_i}
 \end{displaymath}
 This is the generalization of the \emph{value-per-cost} ratio used in greedy
-heuristic for knapsack  problems. However note that for general submodular
-functions, the value of a point depends on the set of points which have already
-been selected.
-
-
-\stratis{what is a ``point''? Use consistent notation for elements in $\mathcal{N}$ throughout the paper. We called them ``experiments'' earlier-if you are talking about general set functions, just call these ``elements''.}
+heuristic for knapsack  problems. However, note that for general submodular
+functions, the value of an element depends on the set to which it is added.
 
 Unfortunately, even for the non-strategic case, the greedy heuristic gives an
-unbounded approximation ratio. It has been noted by Khuller et al.
-\cite{khuller} that for the maximum coverage problem, taking the maximum
-between the greedy solution and the point of maximum value gives
-a $\frac{2e}{e-1}$ approximation ratio. In the general case, let us recall
-lemma 3.1 from \cite{singer-influence} which follows from \cite{chen}:
-
-\stratis{not clear what ``point of maximum value'' yet.}
+unbounded approximation ratio. Let us introduce $i^*
+= \argmax_{i\in\mathcal{N}} V(i)$, the element of maximum value (as a singleton
+set). It has been noted by Khuller et al. \cite{khuller} that for the maximum
+coverage problem, taking the maximum between the greedy solution and $V(i^*$)
+gives a $\frac{2e}{e-1}$ approximation ratio. In the general case, we have the
+following result from \cite{singer-influence} which follows from \cite{chen}:
 
 \begin{lemma}[Singer \cite{singer-influence}]\label{lemma:greedy-bound}
-Let $S_G$ be the set computed by the greedy heuristic and $i^*$ the point of
-maximum value:
+Let $S_G$ be the set computed by the greedy heuristic and let us define $i^*$:
 \begin{displaymath}
     i^* = \argmax_{i\in\mathcal{N}} V(i)
 \end{displaymath}
@@ -54,36 +48,40 @@ OPT(V,\mathcal{N},B) \leq \frac{e}{e-1}\big( 3 V(S_G) + 2 V(i^*)\big)
 \end{displaymath}
 \end{lemma}
 
-Hence, taking the maximum between the greedy set and the point of maximum value
-yields an approximation ratio of $\frac{5e}{e-1}$. However, Singer
-\cite{singer-influence} notes that this approach breaks incentive compatibility
-and therefore cannot be directly applied to the strategic case. \stratis{why? If this is worth mentioning, elaborate.}
-
-Two approaches have been studied to deal with the strategic case and rely on
-comparing the point of maximum value to a quantity which can be proven to be
-not too far from the greedy solution and maintains incentive compatibility.\stratis{too long sentence. Also, write prose, not bullets.}
-\begin{itemize}
-\item In \cite{chen}, the authors suggest using 
-$OPT(V,\mathcal{N}\setminus\{i^*\}, B)$ where $i^*$ is the point of maximum
-value. While this yields an approximation ratio of 8.34, in the general case,
-the optimal value cannot be computed in polynomial time. \stratis{Not clear what ``using'' means here. Not clear what $OPT(\cdot,\cdot,\cdot)$ means (introduce it wherever appropriate). From a technical standpoint, \cite{chen} also use a relaxation, to solve knapsack, no?}
-\item For the set coverage problem, Singer \cite{singer-influence} uses
-a relaxation of the value function which can be proven to have a constant
-approximation ratio to the value function. \stratis{To do what?}
-\end{itemize}
-
+Hence, taking the maximum between $V(S_G)$ and $V(i^*)$ yields an approximation
+ratio of $\frac{5e}{e-1}$. However, Singer \cite{singer-influence} notes that
+this approach breaks incentive compatibility and therefore cannot be directly
+applied to the strategic case. Indeed, assume that we are in a situation where
+the mechanism has allocated to the greedy set ($V(S_G) \geq V(i^*)$). If an
+agent $i$ from the greedy set reduces her cost, it could happen that $V(S_G)$
+becomes smaller than $V(i^*)$. In this case the mechanism will allocate to
+$i^*$ and $i$ will be out of the allocated set. This breaks the monotonicity of
+the allocation rule.
 
-Here, we will use the following relaxation of the value function \eqref{vs}. 
-Let us define the function $L_\mathcal{N}$:
+To address this issue, \cite{chen, singer-influence} compare $V(i^*)$ to
+a quantity which can be proven to be close from $V(S_G)$ while keeping
+keeping monotonicity. In \cite{chen}, the authors suggest comparing $V(i^*)$ to
+$OPT(V,\mathcal{N}\setminus\{i^*\}, B)$. While this yields an approximation
+ratio of 8.34, in the general case, this quantity cannot be computed in
+polynomial time. In \cite{chen, singer-influence}, for the specific problems of
+maximum set coverage and knapsack, the authors compare $V(i^*)$ to
+a  fractional relaxation of the optimization program \eqref{eq:non-strategic}.
 
-\stratis{Not clear how what we do relates to chen or singer: what is it that they do exactly? What we do we use? What is novel compared to what they do? What is the main technical contribution/challenge that we overcome?} 
+Here, following the same path as in \cite{chen, singer-influence}, we choose to
+introduce the following relaxation of the  value function.  Let us define the
+function $L_\mathcal{N}$:
 \begin{displaymath}
     \forall\lambda\in[0,1]^{|\mathcal{N}|}\,\quad L_{\mathcal{N}}(\lambda) \defeq
     \log\det\left(I_d + \sum_{i\in\mathcal{N}} \lambda_i x_i \T{x_i}\right)
 \end{displaymath}
+Our mechanism will thus consist in comparing $V(i^*)$ to $OPT(L_\mathcal{N},
+B)$ to decide whether we should allocate to $i^*$ or the greedy set $S_G$. The
+main challenge will be to prove that $OPT(L_\mathcal{N}, B)$ is close to
+$V(S_G)$. To do so, our main technical contribution is to prove that
+$L_\mathcal{N}$ has a bounded approximation ratio to the value function $V$
+(lemma~\ref{lemma:relaxation}).
 
-Our mechanism for \EDP{} is presented in Algorithm~\ref{mechanism}.
-
+The mechanism for \EDP{} is presented in algorithm \ref{mechanism}.
 \begin{algorithm}
     \caption{Mechanism for \EDP{}}\label{mechanism}
     \begin{algorithmic}[1]
@@ -133,30 +131,9 @@ We can now state the main result of this section:
 \stratis{Add lowerbound here too. Remove ``pseudo proof'' below. Start new subsection called proof of Thm... }
 
 
-\begin{proof}
-\emph{Truthfulness.} The algorithm only describes the allocation rule.
-However, it suffices to prove that the mechanism is monotone, then Myerson's
-theorem (see theorem~\ref{thm:myerson}) ensures us that by paying each
-allocated user his threshold payment yields a truthful mechanism. The proof of
-the monotonicity has already been done in \cite{singer-influence} and is given
-here in lemma~\ref{lemma:monotone} below for the sake of completeness.
-
-\emph{Budget feasibility.} Thanks to the analysis of the threshold
-payment in \cite{chen}, the budget feasibility follows easily. The
-proof is given in lemma~\ref{lemma:budget-feasibility} below. 
-
-\emph{Approximation ratio.} The proof of the approximation ratio follows the
-same path as in \cite{chen} and is done in lemma~\ref{lemma:approx}. Our main
-contribution is to prove that the relaxation $L_\mathcal{N}$ has a constant
-approximation ratio to the optimal solution (lemma~\ref{lemma:relaxation}). This
-follows from the \emph{pipage rounding} method described in \cite{pipage} where
-$L_\mathcal{N}$ is first compared to the \emph{multilinear relaxation} of the
-value function (lemma~\ref{lemma:relaxation-ratio}) for which it is possible to
-round solutions (making fractional components integral) while maintaining
-feasibility (lemma~\ref{lemma:rounding}).
-\end{proof}
+\subsection{Proof of theorem~\ref{thm:main}}
 
-\stratis{start subsection here. Explain what are the main steps in the proof}
+\stratis{Explain what are the main steps in the proof}
 \begin{lemma}\label{lemma:monotone}
 The mechanism is monotone.
 \end{lemma}