conflict

3 files changed, 148 insertions, 86 deletions

diff --git a/main.tex b/main.tex
index 148aedc..0c2b633 100644
--- a/main.tex
+++ b/main.tex
@@ -1,54 +1,58 @@
-
-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 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}$ (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.
 
-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 +69,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 +103,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.
+
+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}
+\begin{lemma}\label{lemma:monotone}
 The mechanism is monotone.
 \end{lemma}
 
@@ -132,30 +147,40 @@ 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}
 
-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}
 
-\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}
+Assume now that our mechanism selects point $i^*$. In this case, his payement
+his $B$ and the mechanism is budget-feasible.
 
-\begin{proof}
+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 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}
+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{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)
@@ -163,7 +188,18 @@ relaxation and will contain the proof of the following lemma:
     \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}
@@ -178,6 +214,7 @@ relaxation and will contain the proof of the following lemma:
     \end{displaymath}
 \end{lemma}
 
+
 \begin{proof}
 
     If the condition on line 3 of the algorithm holds, then:
@@ -210,12 +247,7 @@ relaxation and will contain the proof of the following lemma:
         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)
@@ -224,7 +256,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,24 +264,22 @@ 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 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.
+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:
+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}
@@ -299,7 +329,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}
@@ -314,6 +344,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
@@ -512,7 +549,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^*)
diff --git a/notes.bib b/notes.bib
index fd66bea..80ba51d 100644
--- a/notes.bib
+++ b/notes.bib
@@ -15,6 +15,17 @@
 }
 
 
+@article{myerson,
+  title={Optimal auction design},
+  author={Myerson, R.B.},
+  journal={Mathematics of operations research},
+  volume={6},
+  number={1},
+  pages={58--73},
+  year={1981},
+  publisher={INFORMS}
+}
+
 @article{inverse,
      jstor_articletype = {research-article},
      title = {On the Inverse of the Sum of Matrices},
@@ -186,6 +197,20 @@
      copyright = {Copyright © 1970 American Statistical Association},
 }
 
+@article{khuller,
+  author    = {Samir Khuller and
+               Anna Moss and
+               Joseph Naor},
+  title     = {The Budgeted Maximum Coverage Problem},
+  journal   = {Inf. Process. Lett.},
+  volume    = {70},
+  number    = {1},
+  year      = {1999},
+  pages     = {39-45},
+  ee        = {http://dx.doi.org/10.1016/S0020-0190(99)00031-9},
+  bibsource = {DBLP, http://dblp.uni-trier.de}
+}
+
 @article{pipage,
   author    = {Alexander A. Ageev and
                Maxim Sviridenko},
diff --git a/problem.tex b/problem.tex
index d7cf38c..81b7656 100644
--- a/problem.tex
+++ b/problem.tex
@@ -79,7 +79,7 @@ problem:
 This optimization, commonly known as \emph{ridge regression}, reduces to a least squares fit for $\mu=\infty$. For finite $\mu$, ridge regression
 acts as a sort of ``Occam's razor'', favoring a \emph{parsimonious} model for $\beta$: among two vectors with the same square error, the one with the smallest norm is preferred.   This is consistent with the Gaussian prior on $\beta$, which implies that vectors with small norms are more likely. %In practice, ridge regression is known to give better prediction results over new data than model parameters computed through a least squares fit.
 
-\subsection{A Budgeted Auction}
+\subsection{A Budgeted Auction}\label{sec:auction}
 
 TODO Explain the optimization problem, why it has to be formulated as an auction
 problem. Explain the goals: