diff options
| -rw-r--r-- | main.tex | 207 | ||||
| -rw-r--r-- | notes.bib | 25 | ||||
| -rw-r--r-- | problem.tex | 2 |
3 files changed, 148 insertions, 86 deletions
@@ -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^*) @@ -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: |