Cleanup of the main section

1 files changed, 70 insertions, 63 deletions

diff --git a/main.tex b/main.tex
index 148aedc..44be4e8 100644
--- a/main.tex
+++ b/main.tex
@@ -1,54 +1,57 @@
-
-All the budget feasible mechanisms studied recently (TODO ref Singer Chen)
-rely on using a greedy heuristic extending the idea of the greedy heuristic for
-the knapsack problem. In knapsack, objects are selected based on their
-\emph{value-per-cost} ratio. The quantity which plays a similar role for
-general submodular functions is the \emph{marginal-contribution-per-cost}
-ratio: let us assume that you have already selected a set of points $S$, then
-the \emph{marginal-contribution-per-cost} ratio per cost of a new point $i$ is
-defined by:
+In this section we present a mechanism for the problem described in
+section~\ref{sec:auction}. Previous works on maximizing submodular functions
+\cite{nemhauser, sviridenko-submodular} and desiging auction mechanisms for
+submodular utility functions \cite{singer-mechanisms, chen, singer-influence}
+rely on a greedy heuristic. In this heuristic, points which maximize the
+\emph{marginal-contribution-per-cost} ratio are greedily added to the solution
+set. The \emph{marginal-contribution-per-cost} ratio of a point $i$ with cost
+$c_i$ to the set $S$ is defined by:
 \begin{displaymath}
     \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.
 
-The greedy heuristic then simply repeatedly selects the point whose
-marginal-contribution-per-cost ratio is the highest until it reaches the budget
-limit. Mechanism considerations aside, this is known to have an unbounded
-approximation ratio. However, lemma TODO ref in Chen or Singer shows that the
-maximum between the greedy heuristic and the point with maximum value (as
-a singleton set) provides a $\frac{5e}{e-1}$ approximation ratio.
+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 ration. In the general case, lemma 3.1 from
+\cite{singer-influence} which follows from \cite{chen}, shows that this has 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.
 
-Unfortunately, TODO Singer 2011 points out that taking the maximum between the
-greedy heuristic and the most valuable point is not incentive compatible.
-Singer and Chen tackle this issue similarly: instead of comparing the most
-valuable point to the greedy solution, they compare it to a solution which is
-close enough to keep a constant approximation ratio:
+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.
 \begin{itemize}
-    \item Chen suggests using $OPT(V,\mathcal{N}\setminus\{i\}, B)$.
-        Unfortunately, in the general case, this cannot be computed exactly in
-        polynomial time.
-    \item Singer uses using the optimal value of a relaxed objective function
-        which can be proven to be close to the optimal of the original
-        objective function. The function used is tailored to the specific
-        problem of coverage.
+\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.
+\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.
 \end{itemize}
 
-Here, we use a relaxation of the objective function which is tailored to the
-problem of ridge regression. We define:
+Here, we will use a specific relaxation of the value function \eqref{vs}. 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 + \mu\sum_{i\in\mathcal{N}} \lambda_i x_i \T{x_i}\right)
 \end{displaymath}
 
-We can now present the mechanism we use, which has a same flavor to Chen's and
-Singer's
+Our mechanism for ridge regression is presented in Algorithm~\ref{mechanism}.
 
-\begin{algorithm}\label{mechanism}
-    \caption{Mechanism for ridge regression}
+\begin{algorithm}
+    \caption{Mechanism for ridge regression}\label{mechanism}
     \begin{algorithmic}[1]
     \State $i^* \gets \argmax_{j\in\mathcal{N}}V(j)$
     \State $x^* \gets \argmax_{x\in[0,1]^{|\mathcal{N}|}} \{L_{\mathcal{N}\setminus\{i^*\}}(x)
-                                    \,|\, c(x)\leq B\}$
+                                    \mid c(x)\leq B\}$
         \Statex
         \If{$L(x^*) < CV(i^*)$}
             \State \textbf{return} $\{i^*\}$
@@ -65,16 +68,21 @@ Singer's
     \end{algorithmic}
 \end{algorithm}
 
-Notice, that the stopping condition in the while loop is more sophisticated
-than just ensuring that the sum of the costs does not exceed the budget. This
-is because the selected users will be payed more than their costs, and this
-stopping condition ensures budget feasibility when the users are paid their
-threshold payment.
+\emph{Remarks}
+\begin{enumerate}
+    \item the function $L_\mathcal{N}$ is concave (see
+        lemma~\ref{lemma:concave}) thus the maximization step on line 2 of the
+        mechanism can be computed in polynomial time, which proves that the
+        mechanism overall has a polynomial complexity.
+    \item the stopping rule in the while loop is more sophiticated than just
+        checking against the budget constraint ($c(S) \leq B$). This is to
+        ensure budget feasibility (see lemma~\ref{lemma:budget-feasibility}).
+\end{enumerate}
 
 We can now state the main result of this section:
 \begin{theorem}
-    The mechanism in \ref{mechanism} is truthful, individually rational, budget
-    feasible. Furthermore, choosing:
+    The mechanism described in Algorithm~\ref{mechanism} is truthful,
+    individually rational, budget feasible. Furthermore, choosing:
     \begin{multline*}
         C = C^* =  \frac{5e-1 + C_\mu(2e+1)}{2C_\mu(e-1)}\\
         + \frac{\sqrt{C_\mu^2(1+2e)^2
@@ -94,11 +102,17 @@ We can now state the main result of this section:
 
 The proof will consist of the claims of the theorem broken down into lemmas.
 
-Because the user strategy is parametrized by a single parameter, truthfulness
-is equivalent to monotonicity (TODO ref). The proof here is the same as in TODO
-and is given for the sake of completeness.
+Note that this is a single parameter mechanism. Hence, by using Myerson's
+characterization of truthful mechanisms \cite{myerson}, proving truthfulness
+amounts to proving the monotonicity of the mechanism: if a user is selected by
+the mechanism when reporting a cost $c_i$, then he is still selected when
+reporting another cost $c_i'\leq c_i$ provided that the remaining users do not
+change their costs.
 
-\begin{lemma}
+We prove the monotonicity of the mechanism in lemma~\ref{lemma:monotone} below.
+The proof is similar to the one of lemma 3.2 in \cite{singer-influence}.
+
+\begin{lemma}\label{lemma:monotone}
 The mechanism is monotone.
 \end{lemma}
 
@@ -132,7 +146,7 @@ The mechanism is monotone.
     reporting a different cost.
 \end{proof}
 
-\begin{lemma}
+\begin{lemma}\label{lemma:budget-feasibility}
 The mechanism is budget feasible.
 \end{lemma}
 
@@ -142,20 +156,11 @@ completeness.
 
 \end{proof}
 
-Using the characterization of the threshold payments from Singer TODO, we can
-prove individual rationality similarly to Chen TODO.
-\begin{lemma}
-The mechanism is individually rational
-\end{lemma}
-
-\begin{proof}
-
-\end{proof}
+The following lemma proves that the relaxation $L_\mathcal{N}$ that we are
+using has a bounded approximation ratio to the value function $V$. For
+readibility, the proof is postponed to section~\ref{sec:relaxation}.
 
-The following lemma requires to have a careful look at the relaxation function
-we chose in the mechanism. The next section will be dedicated to studying this
-relaxation and will contain the proof of the following lemma:
-\begin{lemma}
+\begin{lemma}\label{lemma:relaxation}
     We have:
     \begin{displaymath}
         OPT(L_\mathcal{N}, B) \leq \frac{1}{C_\mu}\big(2 OPT(V,\mathcal{N},B)
@@ -224,7 +229,7 @@ relaxation and will contain the proof of the following lemma:
 
 The optimal value for $C$ is:
 \begin{displaymath}
-    C^* = \arg\min C_{\textrm{max}}
+    C^* = \argmin_C C_{\textrm{max}}
 \end{displaymath}
 
 This equation has two solutions. Only one of those is such that:
@@ -232,10 +237,12 @@ This equation has two solutions. Only one of those is such that:
     C\cdot C_\mu(e-1) -5e  +1 \geq 0
 \end{displaymath}
 which is needed in the proof of the previous lemma. Computing this solution,
-we can state the main result of this section.
+gives the result of the theorem.
 
-\subsection{Relaxations of the value function}
+\subsection{Relaxations of the value function}\label{sec:relaxation}
 
+To prove lemma~\ref{lemma:relaxation}, we use a general called pipage rounding
+introduced in \cite{pipage}.
 To prove lemma TODO, we will use a general method called pipage rounding,
 introduced in TODO. Two consecutive relaxations are used: the one that we are
 interested in, whose optimization can be computed efficiently, and the
@@ -299,7 +306,7 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
         \end{align*}
 \end{itemize}
 
-\begin{lemma}
+\begin{lemma}\label{lemma:concave}
     The \emph{concave relaxation} $L_\mathcal{N}$ is concave\footnote{Hence
     this relaxation is well-named!}.
 \end{lemma}