diff options
Diffstat (limited to 'main.tex')
| -rw-r--r-- | main.tex | 133 |
1 files changed, 70 insertions, 63 deletions
@@ -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} |