From 0e9a9b8bf0104b573d04cca4438b905022a4ea06 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Tue, 30 Oct 2012 16:48:49 +0100
Subject: Cleanup of the main section

---
 main.tex | 137 +++++++++++++++++++++++++++++++++------------------------------
 1 file changed, 72 insertions(+), 65 deletions(-)

(limited to 'main.tex')

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}
-
-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, 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:
+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.
+
+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.
+
+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}
+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}.
 
-\begin{proof}
-
-\end{proof}
-
-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}
-- 
cgit v1.2.3-70-g09d2


From bc7134421f286f3ae497c202a45c83d19f585b46 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Tue, 30 Oct 2012 18:40:17 +0100
Subject: Some cleanup of the relaxation part

---
 main.tex | 37 ++++++++++++++++++++-----------------
 1 file changed, 20 insertions(+), 17 deletions(-)

(limited to 'main.tex')

diff --git a/main.tex b/main.tex
index 44be4e8..44851c1 100644
--- a/main.tex
+++ b/main.tex
@@ -241,22 +241,18 @@ gives the result of the theorem.
 
 \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
-multilinear extension which presents a \emph{cross-convexity} like behavior
-which allows for rounding of fractional solution without decreasing the value
-of the objective function and thus ensures a constant approximation of the
-value function. The difficulty resides in showing that the ratio of the two
-relaxations is bounded.
-
-We say that $R_\mathcal{N}:[0,1]^{|\mathcal{N}|}\rightarrow\reals$ is a relaxation of the
-value function $V$ over $\mathcal{N}$ if it coincides with $V$ at binary
-points. Formally, for any $S\subseteq\mathcal{N}$, let $\mathbf{1}_S$ denote the
-indicator vector of $S$. $R_\mathcal{N}$ is a relaxation of $V$ over
-$\mathcal{N}$ iff:
+To prove lemma~\ref{lemma:relaxation}, we use a general method called pipage
+rounding introduced in \cite{pipage}. This method relies on \emph{piping} two
+relaxations of the value function, one being the \emph{multilinear extension}
+introduced below, the other one being the relaxation $L_\mathcal{N}$ already
+introduced in our mechanism. At each position of the pipe, we show that we keep
+a bounded approximation ratio to the original value function.
+
+We say that $R_\mathcal{N}:[0,1]^{|\mathcal{N}|}\rightarrow\reals$ is
+a relaxation of the value function $V$ over $\mathcal{N}$ if it coincides with
+$V$ at binary points. Formally, for any $S\subseteq\mathcal{N}$, let
+$\mathbf{1}_S$ denote the indicator vector of $S$. $R_\mathcal{N}$ is
+a relaxation of $V$ over $\mathcal{N}$ iff:
 \begin{displaymath}
     \forall S\subseteq\mathcal{N},\; R_\mathcal{N}(\mathbf{1}_S) = V(S)
 \end{displaymath}
@@ -321,6 +317,13 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
     \end{multline*}
 \end{proof}
 
+It has been observed already that the multilinear extension presents the
+cross-convexity property: it is convex along any direction $e_i-e_j$ where $e_i$
+and $e_j$ are two elements of the canonical basis. This property allows to
+trade between two fractional components of a point without diminishing the
+value of the relaxation. The following lemma follows from the same idea but
+also ensures that the points remain feasible during the trade. 
+
 \begin{lemma}[Rounding]\label{lemma:rounding}
     For any feasible $\lambda\in[0,1]^{|\mathcal{N}|}$, there exists a feasible
     $\bar{\lambda}\in[0,1]^{|\mathcal{N}|}$ such that at most one of its component is
@@ -519,7 +522,7 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
     \end{align*}
 \end{proof}
 
-We can now prove lemma TODO from previous section.
+We can now prove lemma~\ref{lemma:relaxation} from previous section.
 
 \begin{proof}
     Let us consider a feasible point $\lambda^*\in[0,1]^{|\mathcal{N}|}$ such that $L_\mathcal{N}(\lambda^*)
-- 
cgit v1.2.3-70-g09d2


From 8f788bc40d01316c47713028c2e4cce94b65de49 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Tue, 30 Oct 2012 19:45:00 +0100
Subject: Add a missing piece of the proof

---
 main.tex | 30 +++++++++++++++++++-----------
 1 file changed, 19 insertions(+), 11 deletions(-)

(limited to 'main.tex')

diff --git a/main.tex b/main.tex
index 44851c1..b089dcc 100644
--- a/main.tex
+++ b/main.tex
@@ -18,11 +18,12 @@ 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
+a $\frac{2e}{e-1}$ approximation ratio. 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.
+approximation ratio of $\frac{5e}{e-1}$ (see lemma~\ref{lemma:greedy-bound}
+below). However, Singer \cite{singer-influence} notes that this approach breaks
+incentive compatibility and therefore cannot be directly applied to the
+strategic case.
 
 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
@@ -168,7 +169,18 @@ readibility, the proof is postponed to section~\ref{sec:relaxation}.
     \end{displaymath}
 \end{lemma}
 
-\begin{lemma}
+Let us recall here the following lemma from \cite{chen} which we use in the
+proof of lemma~\ref{lemma:approx}. This lemma shows, as mentioned above, that
+taking the maximum between the greedy solution and the point of maximum value
+gives a $\frac{5e}{e-1}$ approximation ratio.
+\begin{lemma}\label{lemma:greedy-bound}
+The following inequality holds:
+\begin{displaymath}
+    OPT(V,\mathcal{N},B) \leq \frac{5e}{e-1}\max\big( V(S_M), V(i^*)\big)
+\end{displaymath}
+\end{lemma}
+
+\begin{lemma}\label{lemma:approx}
     Let us denote by $S_M$ the set returned by the mechanism. Let us also
     write:
     \begin{displaymath}
@@ -183,6 +195,7 @@ readibility, the proof is postponed to section~\ref{sec:relaxation}.
     \end{displaymath}
 \end{lemma}
 
+
 \begin{proof}
 
     If the condition on line 3 of the algorithm holds, then:
@@ -215,12 +228,7 @@ readibility, the proof is postponed to section~\ref{sec:relaxation}.
         V(i^*) \leq \frac{6e}{C\cdot C_\mu(e-1)- 5e + 1} V(S_M)
     \end{align*}
 
-    Finally, using again that:
-    \begin{displaymath}
-        OPT(V,\mathcal{N},B) \leq \frac{e}{e-1}\big(3 V(S_M) + 2 V(i^*)\big)
-    \end{displaymath}
-    
-    We get:
+    Finally, using again lemma~\ref{lemma:greedy-bound}, we get:
     \begin{displaymath}
         OPT(V, \mathcal{N}, B) \leq \frac{e}{e-1}\left( 3 + \frac{12e}{C\cdot
         C_\mu(e-1) -5e  +1}\right) V(S_M)
-- 
cgit v1.2.3-70-g09d2


From 460f799b52b7a4679df9eb843ec22d98b0283dcb Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Tue, 30 Oct 2012 19:58:33 +0100
Subject: Proof of the budget feasibility

---
 main.tex | 23 +++++++++++++++++++++--
 1 file changed, 21 insertions(+), 2 deletions(-)

(limited to 'main.tex')

diff --git a/main.tex b/main.tex
index b089dcc..0c2b633 100644
--- a/main.tex
+++ b/main.tex
@@ -151,10 +151,29 @@ The mechanism is monotone.
 The mechanism is budget feasible.
 \end{lemma}
 
-The proof is the same as in Chen and is given here for the sake of
-completeness.
 \begin{proof}
+Let us denote by $S_M$ the set selected by the greedy heuristic in the
+mechanism of Algorithm~\ref{mechanism}. Let $i\in S_M$, let us also denote by
+$S_i$ the solution set that was selected by the greedy heuristic before $i$ was
+added. Recall from \cite{chen} that the following holds for any submodular
+function: if the point $i$ was selected by the greedy heuristic, then:
+\begin{equation}\label{eq:budget}
+    c_i \leq \frac{V(S_i\cup\{i\}) - V(S)}{V(S_M)} B
+\end{equation}
+
+Assume now that our mechanism selects point $i^*$. In this case, his payement
+his $B$ and the mechanism is budget-feasible.
+
+Otherwise, the mechanism selects the set $S_M$. In this case, \eqref{eq:budget}
+shows that the threshold payement of user $i$ is bounded by:
+\begin{displaymath}
+\frac{V(S_i\cup\{i\}) - V(S_i)}{V(S_M)} B
+\end{displaymath}
 
+Hence, the total payement is bounded by:
+\begin{displaymath}
+    \sum_{i\in S_M} \frac{V(S_i\cup\{i\}) - V(S_i)}{V(S_M)} B \leq B
+\end{displaymath}
 \end{proof}
 
 The following lemma proves that the relaxation $L_\mathcal{N}$ that we are
-- 
cgit v1.2.3-70-g09d2

