diff options
Diffstat (limited to 'approximation.tex')
| -rw-r--r-- | approximation.tex | 70 |
1 files changed, 37 insertions, 33 deletions
diff --git a/approximation.tex b/approximation.tex index 20af216..ccd063a 100644 --- a/approximation.tex +++ b/approximation.tex @@ -1,6 +1,6 @@ -Previous approaches towards designing truthful, budget feasible mechanisms for \textsc{Knapsack}~\cite{chen} and \textsc{Coverage}~\cite{singer-influence} build upon polynomial-time algorithms that compute an approximation of $OPT$, the optimal value in the full information case. Crucially, to be used in designing a truthful mechanism, such algorithms need also to be \emph{monotone}, in the sense that decreasing any cost $c_i$ leads to an increase of in the estimation of $OPT$. In the cases of \textsc{Knapsack} and~\textsc{Coverage}, as well as in the case of \EDP{}, monotonicity precludes using traditional approximation algorithms. +Previous approaches towards designing truthful, budget feasible mechanisms for \textsc{Knapsack}~\cite{chen} and \textsc{Coverage}~\cite{singer-influence} build upon polynomial-time algorithms that compute an approximation of $OPT$, the optimal value in the full information case. Crucially, to be used in designing a truthful mechanism, such algorithms need also to be \emph{monotone}, in the sense that decreasing any cost $c_i$ leads to an increase in the estimation of $OPT$. In the cases of \textsc{Knapsack} and~\textsc{Coverage}, as well as in the case of \EDP{}, monotonicity precludes using traditional approximation algorithms. -In the fist part of this section, we address this issue by designing a convex relaxation of \EDP{}, and showing that its solution well approximates $OPT$. The objective of this relaxation is concave and self-concordant \cite{boyd2004convex}, and, as such, the exists an algorithm that solves this relaxed problem with arbitrary accuracy in polynomial time. Unfortunately, the output of this algorithm may not necessarily be monotone. Nevertheless, in the second part of this section, we show how a solver of the relaxed problem can be used to construct a solver that is ``almost'' monotone: in Section~\ref{sec:main}, we show how this algorithm can be used to design a $\delta$-truthful mechanism for \EDP. +In the fist part of this section, we address this issue by designing a convex relaxation of \EDP{}, and showing that its solution can be used to approximate $OPT$. The objective of this relaxation is concave and self-concordant \cite{boyd2004convex} and, as such, there exists an algorithm that solves this relaxed problem with arbitrary accuracy in polynomial time. Unfortunately, the output of this algorithm may not necessarily be monotone. Nevertheless, in the second part of this section, we show how a solver of the relaxed problem can be used to construct a solver that is ``almost'' monotone: in Section~\ref{sec:main}, we show how this algorithm can be used to design a $\delta$-truthful mechanism for \EDP. %As noted above, \EDP{} is NP-hard. Designing a mechanism for this problem, as @@ -33,35 +33,33 @@ In the fist part of this section, we address this issue by designing a convex re A classical way of relaxing combinatorial optimization problems is \emph{relaxing by expectation}, using the so-called \emph{multi-linear} extension of the objective function $V$ (see, \emph{e.g.}, \cite{calinescu2007maximizing,vondrak2008optimal,dughmi2011convex}). -This is because this extension can yield approximation guarantees for a wide class of optimization problems through \emph{pipage rounding}, a technique proposed by \citeN{pipage}. +This is because this extension can yield approximation guarantees for a wide class of combinatorial problems through \emph{pipage rounding}, a technique proposed by \citeN{pipage}. Crucially for our purposes, such relaxations preserve monotonicity which, as we discussed, is necessary for our mechanism design. -Let $P_\mathcal{N}^\lambda(S)$ be the probability of choosing the -set $S$ if we select each element $i$ in $\mathcal{N}$ independently with -probability $\lambda_i$, \emph{i.e.}, +Formally, let $P_\mathcal{N}^\lambda$ be a probability distribution over $\mathcal{N}$ parametrized by $\lambda\in [0,1]^n$, where a set $S\subseteq \mathcal{N}$ sampled from $P_\mathcal{N}^\lambda$ is constructed as follows: each $i\in \mathcal{N}$ is selected to be in $S$ independently with probability $\lambda_i$, \emph{i.e.}, %\begin{displaymath} $ P_\mathcal{N}^\lambda(S) \defeq \prod_{i\in S} \lambda_i \prod_{i\in\mathcal{N}\setminus S}( 1 - \lambda_i).$ %\end{displaymath} Then, the \emph{multi-linear} extension $F:[0,1]^n\to\reals$ of $V$ is defined as the -expectation of $V$ under the probability distribution $P_\mathcal{N}^\lambda$: +expectation of $V$ under the distribution $P_\mathcal{N}^\lambda$: \begin{equation}\label{eq:multi-linear} F(\lambda) \defeq \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\big[V(S)\big] % = \sum_{S\subseteq\mathcal{N}} P_\mathcal{N}^\lambda(S) V(S) = \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\left[ \log\det\left( I_d + \sum_{i\in S} x_i\T{x_i}\right) \right] \end{equation} -Function $F$ is an extension of $V$ in the domain $[0,1]^n$, as it agrees with $V$ at integer inputs: $F(\id_S) = V(S)$ for all +Function $F$ is an extension of $V$ to the domain $[0,1]^n$, as it agrees with $V$ at integer inputs: $F(\id_S) = V(S)$ for all $S\subseteq\mathcal{N}$, where $\id_S$ denotes the indicator vector of $S$. %\citeN{pipage} have shown how to use this extension to obtain approximation guarantees for an interesting class of optimization problems through the \emph{pipage rounding} framework, which has been successfully applied in \citeN{chen, singer-influence}. -Unfortunately, for $V$ the information gain function that we study, the -multi-linear extension cannot be computed---let alone maximized---in -polynomial time. Hence, we introduce a new extention $L:[0,1]^n\to\reals$: +Unfortunately, for $V$ the value function given by \eqref{modified} that we study here, the +multi-linear extension \eqref{eq:multi-linear} cannot be computed---let alone maximized---in +polynomial time. Hence, we introduce a new extension $L:[0,1]^n\to\reals$: \begin{equation}\label{eq:our-relaxation} \forall\,\lambda\in[0,1]^n,\quad L(\lambda) \defeq \log\det\left(I_d + \sum_{i\in\mathcal{N}} \lambda_i x_i\T{x_i}\right)= \log\det\left(\mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\bigg[I_d + \sum_{i\in S} x_i\T{x_i} \bigg]\right). \end{equation} Note that $L$ also extends $V$, and follows naturally from the multi-linear extension by swapping the -expectation and $\log \det$ in \eqref{eq:multi-linear}. Crucially, it \emph{strictly concave} on $[0,1]^n$, a fact that, we exploit in the next section to maximize $L$ subject to the budget constraint in a polynomial time. +expectation and $\log \det$ in \eqref{eq:multi-linear}. Crucially, it \emph{strictly concave} on $[0,1]^n$, a fact that we exploit in the next section to maximize $L$ subject to the budget constraint in polynomial time. %\begin{displaymath} % L(\lambda) = %\end{displaymath} @@ -73,9 +71,9 @@ For all $\lambda\in[0,1]^{n},$ \,L(\lambda)\leq F(\lambda)\leq L(\lambda)$. \end{lemma} -The proof of this lemma can be found in Appendix~\ref{proofofrelaxation-ratio}. In short, we prove this by exploiting the concavity of the $\log\det$ function over the set of positive semidefinite matrices to bound the ratio of all partial derivatives of $F$ and $L$; we subsequently show that the bound on ratio of the derivatives also implies a bound over the ratio $F/L$ in $[0,1]$. +The proof of this lemma can be found in Appendix~\ref{proofofrelaxation-ratio}. In short, we prove this by exploiting the concavity of the $\log\det$ function over the set of positive semi-definite matrices to bound the ratio of all partial derivatives of $F$ and $L$; to conclude the proof, we then show that the bound on the ratio of the derivatives also implies a bound on the ratio $F/L$. -Armed with this result, we can then show using pipage rounding that any $\lambda$ that maximizes the multi-linear extension $F$ can be rounded to an ``almost'' integral solution. More specifically, given a set of costs $c\in \reals^n_+$, we say that a $\lambda\in [0,1]^n$ is feasible if it belongs to the set +Armed with this result, we subsequently use pipage rounding to show that any $\lambda$ that maximizes the multi-linear extension $F$ can be rounded to an ``almost'' integral solution. More specifically, given a set of costs $c\in \reals^n_+$, we say that a $\lambda\in [0,1]^n$ is feasible if it belongs to the set \begin{align}\dom_c =\{\lambda \in [0,1]^n: \sum_{i\in \mathcal{N}} c_i\lambda_i\leq B\}.\label{fdom}\end{align} Then, the following lemma holds: \begin{lemma}[Rounding]\label{lemma:rounding} For any feasible $\lambda\in \dom_c$, there exists a feasible @@ -83,27 +81,33 @@ Armed with this result, we can then show using pipage rounding that any $\lambd coordinates of $\bar{\lambda}$ is fractional. %, that is, lies in $(0,1)$ and: \end{lemma} The proof of this lemma is in Appendix \ref{proofoflemmarounding}, and follows the main steps of the pipage rounding method of \citeN{pipage}. % this rounding property is referred to in the literature as \emph{cross-convexity} (see, \emph{e.g.}, \cite{dughmi}), or $\varepsilon$-convexity by \citeN{pipage}. - - -The optimization program \eqref{eq:non-strategic} extends naturally to such -a relaxation. We define: -\begin{equation}\tag{$P_c$}\label{eq:primal} - L^*_c \defeq \max_{\lambda\in[0, 1]^{n}} - \left\{L(\lambda) \Big| \sum_{i=1}^{n} \lambda_i c_i - \leq B\right\} -\end{equation} - -The key property of our relaxation $L$ is that it has a bounded approximation -ratio to the multi-linear relaxation $F$. This is one of our main technical -contributions and is stated and proved in Lemma~\ref{lemma:relaxation-ratio} -found in Appendix. Moreover, the multi-linear relaxation $F$ has an exchange -property (see Lemma~\ref{lemma:rounding}) which allows us to relate its value to -$OPT$ through rounding. Together, these properties give the following -proposition which is also proved in the Appendix. - +Together, Lemma~\ref{lemma:relaxation-ratio} and Lemma~\ref{lemma:rounding} imply that $OPT$, the optimal value of \EDP, can be approximated by solving the following convex optimization problem: +\begin{align}\tag{$P_c$}\label{eq:primal} +\begin{split} \text{Maximize:} &\qquad L(\lambda)\\ +\text{subject to:} & \qquad\lambda \in \dom_c +\end{split} +\end{align} +In particular, for $L_c^*\defeq \max_{\lambda\in \dom_c} L(\lambda)$ the optimal value of \eqref{eq:primal}, the following holds: \begin{proposition}\label{prop:relaxation} -$L^*_c \leq 2 OPT + 2\max_{i\in\mathcal{N}}V(i)$. +$OPT\leq L^*_c \leq 2 OPT + 2\max_{i\in\mathcal{N}}V(i)$. \end{proposition} +The proof of this proposition can be found in Appendix~\ref{proofofproprelaxation}. Clearly, $L^*_c$ is monotone in $c$: $L^*_c\geq L^*_{c'}$ for any two $c,c'\in \reals_+^n$ s.t.~$c\leq c'$, coordinate-wise. + +%The optimization program \eqref{eq:non-strategic} extends naturally to such +%a relaxation. We define: +%\begin{equation}\tag{$P_c$}\label{eq:primal} +% L^*_c \defeq \max_{\lambda\in[0, 1]^{n}} +% \left\{L(\lambda) \Big| \sum_{i=1}^{n} \lambda_i c_i +% \leq B\right\} +%\end{equation} + +%The key property of our relaxation $L$ is that it has a bounded approximation +%ratio to the multi-linear relaxation $F$. This is one of our main technical +%contributions and is stated and proved in Lemma~\ref{lemma:relaxation-ratio} +%found in Appendix. Moreover, the multi-linear relaxation $F$ has an exchange +%property (see Lemma~\ref{lemma:rounding}) which allows us to relate its value to +%$OPT$ through rounding. Together, these properties give the following +%proposition which is also proved in the Appendix. \subsection{Solving a Convex Problem Monotonously}\label{sec:monotonicity} |