path: root/approximation.tex

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{}, 
the monotonicity property  precludes using traditional approximation algorithms.

In the first 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 that a  solver of the relaxed problem can be used to construct a solver that is ``almost'' monotone. In Section~\ref{sec:main}, we show that 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
%we will see in Section~\ref{sec:mechanism}, will involve being able to find an approximation of its optimal value
%$OPT$ defined in \eqref{eq:non-strategic}. In addition to being computable in
%polynomial time and having a bounded approximation ratio to $OPT$, we will also
%require this approximation to be non-increasing in the following sense:

%\begin{definition}
%Let $f$ be a function from $\reals^n$ to $\reals$. We say that $f$ is
%\emph{non-decreasing (resp. non-increasing) along the $i$-th coordinate} iff:
%\begin{displaymath}
%\forall x\in\reals^n,\;
%t\mapsto f(x+ te_i)\; \text{is non-decreasing (resp. non-increasing)}
%\end{displaymath}
%where $e_i$ is the $i$-th canonical basis vector of $\reals^n$. 

%We say that $f$ is \emph{non-decreasing} (resp. \emph{non-increasing}) iff it
%is non-decreasing (resp. non-increasing) along all coordinates.
%\end{definition}


%Such an approximation will be obtained by introducing a concave optimization
%problem with a constant approximation ratio to \EDP{}
%(Proposition~\ref{prop:relaxation}) and then showing how to approximately solve
%this problem in a monotone way.

\subsection{A Convex Relaxation of \EDP}\label{sec:concave}

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 combinatorial problems through \emph{pipage rounding}, a technique proposed by \citeN{pipage}. Crucially for our purposes, such relaxations in general preserve monotonicity which, as discussed, is required in mechanism design.

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  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],\quad \lambda\in[0,1]^n.
\end{equation}
Function $F$ is an extension of $V$ to the domain  $[0,1]^n$, as it equals $V$ on 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}. 
Contrary to problems such as \textsc{Knapsack}, the
multi-linear extension \eqref{eq:multi-linear} cannot be optimized in
polynomial time for  the value function $V$  we study here, given by \eqref{modified}. Hence, we introduce an extension $L:[0,1]^n\to\reals$ s.t.~
\begin{equation}\label{eq:our-relaxation}
    \begin{split}
        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),
\quad \lambda\in[0,1]^n.
\end{split}
\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 is \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}

Our first technical lemma relates the concave extension $L$ to the multi-linear extension $F$:
\begin{lemma}\label{lemma:relaxation-ratio}
For all $\lambda\in[0,1]^{n},$
     $           \frac{1}{2}
        \,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,  exploiting the concavity of the $\log\det$ function over the set of positive semi-definite matrices, we first  bound the ratio of all partial derivatives of $F$ and $L$. 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 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
    $\bar{\lambda}\in \dom_c$ such that (a) $F(\lambda)\leq F(\bar{\lambda})$, and (b) at most one of the 
    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}. 
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}
$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}. As we discuss in the next section, $L^*_c$ can be computed by a poly-time algorithm at arbitrary accuracy. However, the outcome of this computation may not necessarily be monotone; we address this by converting this poly-time estimator of $L^*_c$ to one that is ``almost'' monotone.%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{Polynomial-Time, Almost-Monotone Approximation}\label{sec:monotonicity}
 The $\log\det$ objective function of \eqref{eq:primal} is strictly concave and \emph{self-concordant} \cite{boyd2004convex}. The maximization of a concave, self-concordant function subject to a set of linear constraints can be performed through the \emph{barrier method} (see, \emph{e.g.}, \cite{boyd2004convex} Section 11.5.5 for  general self-concordant optimization as well as \cite{vandenberghe1998determinant} for a detailed treatment of the $\log\det$ objective). The performance of the barrier method is summarized in our case by the following lemma:
\begin{lemma}[\citeN{boyd2004convex}]\label{lemma:barrier}
For any $\varepsilon>0$, the barrier method computes  an 
approximation $\hat{L}^*_c$ that is $\varepsilon$-accurate, \emph{i.e.}, it satisfies $|\hat L^*_c- L^*_c|\leq \varepsilon$, in time $O\left(poly(n,d,\log\log\varepsilon^{-1})\right)$. The same guarantees apply when maximizing $L$ subject to an arbitrary set of $O(n)$ linear constraints.
\end{lemma}

 Clearly, the optimal value $L^*_c$ of \eqref{eq:primal} is monotone in $c$: formally, for any two $c,c'\in \reals_+^n$ s.t.~$c\leq c'$ coordinate-wise, $\dom_{c'}\subseteq \dom_c$ and thus $L^*_c\geq L^*_{c'}$. Hence, the map $c\mapsto L^*_c$ is non-increasing. Unfortunately, the same is not true for the output $\hat{L}_c^*$ of the barrier method: there is no guarantee that the $\epsilon$-accurate approximation $\hat{L}^*_c$ exhibits any kind of monotonicity.

Nevertheless, we prove that it is possible to use the barrier method to construct an approximation of $L^*_{c}$ that is ``almost'' monotone. More specifically, given $\delta>0$,  we say that $f:\reals^n\to\reals$ is
\emph{$\delta$-decreasing}  if
%\begin{equation}\label{eq:dd}
 $ f(x) \geq  f(x+\mu e_i)$, 
    for all $i\in \mathcal{N},x\in\reals^n, \mu\geq\delta,$
%\end{equation}
where $e_i$ is the $i$-th canonical basis vector of $\reals^n$.
In other words, $f$ is $\delta$-decreasing if increasing any coordinate by $\delta$ or more at input $x$ ensures that the output will be at most $f(x)$.

Our next technical result establishes that, using the barrier method, it is possible to construct an algorithm that computes $L^*_c$ at arbitrary accuracy in polynomial time \emph{and} is $\delta$-decreasing. We achieve this by restricting the optimization over a subset of $\dom_c$ at which the concave relaxation $L$ is ``sufficiently'' concave. Formally, for $\alpha\geq 0$ let $$\textstyle\dom_{c,\alpha} \defeq \{\lambda \in [\alpha,1]^n: \sum_{i\in \mathcal{N}}c_i\lambda_i \leq B\}\subseteq  \dom_c . $$ 
Note that $\dom_c=\dom_{c,0}.$ Consider the following perturbation of the concave relaxation \eqref{eq:primal}:
\begin{align}\tag{$P_{c,\alpha}$}\label{eq:perturbed-primal}
\begin{split}  \text{Maximize:} &\qquad L(\lambda)\\
\text{subject to:} & \qquad\lambda \in \dom_{c,\alpha}
\end{split}
\end{align}

%Note, that the feasible set in Problem~\eqref{eq:primal} increases (for the
%inclusion) when the cost decreases. 
%non-increasing.

%Furthermore, \eqref{eq:primal} being a convex optimization problem, using
%standard convex optimization algorithms (Lemma~\ref{lemma:barrier} gives
%a formal statement for our specific problem) we can compute
%a $\varepsilon$-accurate approximation of its optimal value as defined below.

%\begin{definition}
%$a$ is an $\varepsilon$-accurate approximation of $b$ iff $|a-b|\leq \varepsilon$.
%\end{definition}

%Note however that an $\varepsilon$-accurate approximation of a non-increasing
%function is not in general non-increasing itself. The goal of this section is
%to approximate $L^*_c$ while preserving monotonicity. The estimator we
%construct has a weaker form of monotonicity that we call
%\emph{$\delta$-monotonicity}.

%\begin{definition}
%Let $f$ be a function from $\reals^n$ to $\reals$, we say that $f$ is
%\emph{$\delta$-increasing along the $i$-th coordinate} iff:
%\begin{equation}\label{eq:dd}
%    \forall x\in\reals^n,\;
%    \forall \mu\geq\delta,\;
%    f(x+\mu e_i)\geq f(x)
%\end{equation}
%where $e_i$ is the $i$-th canonical basis vector of $\reals^n$. By extension,
%$f$ is $\delta$-increasing iff it is $\delta$-increasing along all coordinates.

%We define \emph{$\delta$-decreasing} functions by reversing the inequality in
%\eqref{eq:dd}.
%\end{definition}

%We consider a perturbation of \eqref{eq:primal} by introducing:
%\begin{equation}\tag{$P_{c, \alpha}$}\label{eq:perturbed-primal}
%    L^*_{c,\alpha} \defeq \max_{\lambda\in[\alpha, 1]^{n}}
%    \left\{L(\lambda) \Big| \sum_{i=1}^{n} \lambda_i c_i
%    \leq B\right\}
%\end{equation}
%Note that we have $L^*_c = L^*_c(0)$.  We will also assume that
%$\alpha<\frac{1}{nB}$ so that \eqref{eq:perturbed-primal} has at least one
%feasible point: $(\frac{1}{nB},\ldots,\frac{1}{nB})$. By computing
%an approximation of $L^*_{c,\alpha}$ as in Algorithm~\ref{alg:monotone}, we
%obtain a $\delta$-decreasing approximation of $L^*_c$.

\begin{algorithm}[t]
    \caption{}\label{alg:monotone}
    \begin{algorithmic}[1]
	\Require{ $B\in \reals_+$, $c\in[0,B]^n$, $\delta\in (0,1]$, $\epsilon\in (0,1]$ }
        \State $\alpha \gets \varepsilon (\delta/B+n^2)^{-1}$ 
        \State Use the barrier method to solve \eqref{eq:perturbed-primal} with
        accuracy $\varepsilon'=\frac{1}{2^{n+1}B}\alpha\delta b$; denote the output by $\hat{L}^*_{c,\alpha}$
	\State \textbf{return} $\hat{L}^*_{c,\alpha}$
    \end{algorithmic}
\end{algorithm}

Our construction of a $\delta$-decreasing, $\varepsilon$-accurate approximator of $L_c^*$ proceeds as follows: first, it computes an appropriately selected lower bound $\alpha$; using this bound, it solves the perturbed problem \eqref{eq:perturbed-primal} using the barrier method, also at an appropriately selected accuracy $\varepsilon'$, obtaining thus a $\varepsilon'$-accurate approximation of $L^*_{c,\alpha}\defeq \max_{\lambda\in \dom_{c,\alpha}} L(\lambda)$ . The corresponding output is returned as an approximation of $L^*_c$. A summary of the algorithm and the specific choices of $\alpha$ and $\varepsilon'$ are given in Algorithm~\ref{alg:monotone}. The following proposition, which is proved in Appendix~\ref{proofofpropmonotonicity}, establishes that this algorithm has both properties we desire:
\begin{proposition}\label{prop:monotonicity}
    For any $\delta\in(0,1]$ and any $\varepsilon\in(0,1]$,
    Algorithm~\ref{alg:monotone} computes a $\delta$-decreasing,
    $\varepsilon$-accurate approximation of $L^*_c$. The running time of the
    algorithm is $O\big(poly(n, d, \log\log\frac{B}{b\varepsilon\delta})\big)$.
\end{proposition}
We note that the execution of the barrier method on the restricted set $\dom_{c,\alpha}$ is necessary. The algorithm's output when executed over the entire domain may not necessarily be $\delta$-decreasing, even when the approximation accuracy is small. This is because costs become saturated when the optimal $\lambda\in \dom_c$ lies at the boundary: increasing them has no effect on the objective. Forcing the optimization to happen ``off'' the boundary ensures that this does not occur, while taking $\alpha$ to be small ensures that this perturbation does not cost much in terms of approximation accuracy.