diff options
Diffstat (limited to 'appendix.tex')
| -rw-r--r-- | appendix.tex | 670 |
1 files changed, 0 insertions, 670 deletions
diff --git a/appendix.tex b/appendix.tex index 63a8dd8..fc32f10 100644 --- a/appendix.tex +++ b/appendix.tex @@ -26,156 +26,7 @@ Sylvester's determinant identity~\cite{sylvester}. Monotonicity therefore follow and submodularity also follows, as a function is submodular if and only if the marginal contributions are non-increasing in $S$. \qed -\section{Proofs of Statements in Section~\ref{sec:concave}} -\subsection{Proof of Lemma~\ref{lemma:relaxation-ratio}}\label{proofofrelaxation-ratio} %\begin{proof} - The bound $F(\lambda)\leq L(\lambda)$ follows by the concavity of the $\log\det$ function and Jensen's inequality. - To show the lower bound, - we first prove that $\frac{1}{2}$ is a lower bound of the ratio $\partial_i - F(\lambda)/\partial_i L(\lambda)$, where we use - $\partial_i\, \cdot$ as a shorthand for $\frac{\partial}{\partial \lambda_i}$, the partial derivative with respect to the - $i$-th variable. - - Let us start by computing the partial derivatives of $F$ and - $L$ with respect to the $i$-th component. - Observe that - \begin{displaymath} - \partial_i P_\mathcal{N}^\lambda(S) = \left\{ - \begin{aligned} - & P_{\mathcal{N}\setminus\{i\}}^\lambda(S\setminus\{i\})\;\textrm{if}\; - i\in S, \\ - & - P_{\mathcal{N}\setminus\{i\}}^\lambda(S)\;\textrm{if}\; - i\in \mathcal{N}\setminus S. \\ - \end{aligned}\right. - \end{displaymath} - Hence, - \begin{displaymath} - \partial_i F(\lambda) = - \sum_{\substack{S\subseteq\mathcal{N}\\ i\in S}} - P_{\mathcal{N}\setminus\{i\}}^\lambda(S\setminus\{i\})V(S) - - \sum_{\substack{S\subseteq\mathcal{N}\\ i\in \mathcal{N}\setminus S}} - P_{\mathcal{N}\setminus\{i\}}^\lambda(S)V(S). - \end{displaymath} - Now, using that every $S$ such that $i\in S$ can be uniquely written as - $S'\cup\{i\}$, we can write: - \begin{displaymath} - \partial_i F(\lambda) = - \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}} - P_{\mathcal{N}\setminus\{i\}}^\lambda(S)\big(V(S\cup\{i\}) - - V(S)\big). - \end{displaymath} -Recall from \eqref{eq:marginal_contrib} that the marginal contribution of $i$ to $S$ is given by -$$V(S\cup \{i\}) - V(S) =\frac{1}{2}\log(1 + \T{x_i}A(S)^{-1}x_i), $$ -where $A(S) = I_d+ \T{X_S}X_S$. -% $ V(S\cup\{i\}) - V(S) = \frac{1}{2}\log\left(1 + \T{x_i} A(S)^{-1}x_i\right)$. -Using this, - \begin{displaymath} - \partial_i F(\lambda) = \frac{1}{2} - \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}} - P_{\mathcal{N}\setminus\{i\}}^\lambda(S) - \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big) - \end{displaymath} - The computation of the derivative of $L$ uses standard matrix - calculus: writing $\tilde{A}(\lambda) \defeq I_d+\sum_{i\in - \mathcal{N}}\lambda_ix_i\T{x_i}$, - \begin{displaymath} - \det \tilde{A}(\lambda + h\cdot e_i) = \det\big(\tilde{A}(\lambda) - + hx_i\T{x_i}\big) - =\det \tilde{A}(\lambda)\big(1+ - h\T{x_i}\tilde{A}(\lambda)^{-1}x_i\big). - \end{displaymath} - Hence, - \begin{displaymath} - \log\det\tilde{A}(\lambda + h\cdot e_i)= \log\det\tilde{A}(\lambda) - + h\T{x_i}\tilde{A}(\lambda)^{-1}x_i + o(h), - \end{displaymath} - which implies - \begin{displaymath} - \partial_i L(\lambda) - =\frac{1}{2} \T{x_i}\tilde{A}(\lambda)^{-1}x_i. - \end{displaymath} -Recall from \eqref{eq:inverse} that the monotonicity of the matrix inverse over positive definite matrices implies -\begin{gather*} - \forall S\subseteq\mathcal{N},\quad A(S)^{-1} \succeq A(S\cup\{i\})^{-1} -\end{gather*} -as $A(S)\preceq A(S\cup\{i\})$. Observe that since $1\leq \lambda_i\leq 1$, -$P_{\mathcal{N}\setminus\{i\}}^\lambda(S) \geq P_\mathcal{N}^\lambda(S)$ and -$P_{\mathcal{N}\setminus\{i\}}^\lambda(S)\geq P_{\mathcal{N}}^\lambda(S\cup\{i\})$ -for all $S\subseteq\mathcal{N}\setminus\{i\}$. Hence, -\begin{align*} - \partial_i F(\lambda) - & \geq \frac{1}{4} - \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}} - P_{\mathcal{N}}^\lambda(S) - \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big)\\ - &+\frac{1}{4} - \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}} - P_{\mathcal{N}}^\lambda(S\cup\{i\}) - \log\Big(1 + \T{x_i}A(S\cup\{i\})^{-1}x_i\Big)\\ - &\geq \frac{1}{4} - \sum_{S\subseteq\mathcal{N}} - P_\mathcal{N}^\lambda(S) - \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big). -\end{align*} -Using that $A(S)\succeq I_d$ we get that $\T{x_i}A(S)^{-1}x_i \leq -\norm{x_i}_2^2 \leq 1$. Moreover, $\log(1+x)\geq x$ for all $x\leq 1$. -Hence, -\begin{displaymath} - \partial_i F(\lambda) \geq - \frac{1}{4} - \T{x_i}\bigg(\sum_{S\subseteq\mathcal{N}}P_\mathcal{N}^\lambda(S)A(S)^{-1}\bigg)x_i. -\end{displaymath} -Finally, using that the inverse is a matrix convex function over symmetric -positive definite matrices (see Appendix~\ref{app:properties}): -\begin{displaymath} - \partial_i F(\lambda) \geq - \frac{1}{4} - \T{x_i}\bigg(\sum_{S\subseteq\mathcal{N}}P_\mathcal{N}^\lambda(S)A(S)\bigg)^{-1}x_i - = \frac{1}{4}\T{x_i}\tilde{A}(\lambda)^{-1}x_i - = \frac{1}{2} - \partial_i L(\lambda). -\end{displaymath} - -Having bound the ratio between the partial derivatives, we now bound the ratio -$F(\lambda)/L(\lambda)$ from below. Consider the following three cases. - -First, if the minimum is attained as $\lambda$ converges to zero in, -\emph{e.g.}, the $l_2$ norm, by the Taylor approximation, one can write: -\begin{displaymath} - \frac{F(\lambda)}{L(\lambda)} - \sim_{\lambda\rightarrow 0} - \frac{\sum_{i\in \mathcal{N}}\lambda_i\partial_i F(0)} - {\sum_{i\in\mathcal{N}}\lambda_i\partial_i L(0)} - \geq \frac{1}{2}, -\end{displaymath} -\emph{i.e.}, the ratio $\frac{F(\lambda)}{L(\lambda)}$ is necessarily bounded -from below by 1/2 for small enough $\lambda$. - -Second, if the minimum of the ratio $F(\lambda)/L(\lambda)$ is attained at -a vertex of the hypercube $[0,1]^n$ different from 0. $F$ and $L$ being -relaxations of the value function $V$, they are equal to $V$ on the vertices -which are exactly the binary points. Hence, the minimum is equal to 1 in this -case; in particular, it is greater than $1/2$. - -Finally, if the minimum is attained at a point $\lambda^*$ with at least one -coordinate belonging to $(0,1)$, let $i$ be one such coordinate and consider -the function $G_i$: -\begin{displaymath} - G_i: x \mapsto \frac{F}{L}(\lambda_1^*,\ldots,\lambda_{i-1}^*, x, - \lambda_{i+1}^*, \ldots, \lambda_n^*). -\end{displaymath} -Then this function attains a minimum at $\lambda^*_i\in(0,1)$ and its -derivative is zero at this point. Hence: -\begin{displaymath} - 0 = G_i'(\lambda^*_i) = \partial_i\left(\frac{F}{L}\right)(\lambda^*). -\end{displaymath} -But $\partial_i(F/L)(\lambda^*)=0$ implies that -\begin{displaymath} - \frac{F(\lambda^*)}{L(\lambda^*)} = \frac{\partial_i - F(\lambda^*)}{\partial_i L(\lambda^*)}\geq \frac{1}{2} -\end{displaymath} -using the lower bound on the ratio of the partial derivatives. This concludes -the proof of the lemma. \qed %\end{proof} %We now prove that $F$ admits the following exchange property: let $\lambda$ be a feasible element of $[0,1]^n$, it is possible to trade one fractional component of $\lambda$ for another until one of them becomes integral, obtaining a new element $\tilde{\lambda}$ which is both feasible and for which $F(\tilde{\lambda})\geq F(\lambda)$. Here, by feasibility of a point $\lambda$, we mean that it satisfies the budget constraint $\sum_{i=1}^n \lambda_i c_i \leq B$. 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}. @@ -186,74 +37,8 @@ the proof of the lemma. \qed % fractional %, that is, lies in $(0,1)$ and: % and $F_{\mathcal{N}}(\lambda)\leq F_{\mathcal{N}}(\bar{\lambda})$. %\end{lemma} -\subsection{Proof of Lemma~\ref{lemma:rounding}}\label{proofoflemmarounding} %\begin{proof} - We give a rounding procedure which, given a feasible $\lambda$ with at least - two fractional components, returns some feasible $\lambda'$ with one fewer fractional - component such that $F(\lambda) \leq F(\lambda')$. - - Applying this procedure recursively yields the lemma's result. - Let us consider such a feasible $\lambda$. Let $i$ and $j$ be two - fractional components of $\lambda$ and let us define the following - function: - \begin{displaymath} - F_\lambda(\varepsilon) = F(\lambda_\varepsilon) - \quad\textrm{where} \quad - \lambda_\varepsilon = \lambda + \varepsilon\left(e_i-\frac{c_i}{c_j}e_j\right) - \end{displaymath} - It is easy to see that if $\lambda$ is feasible, then: - \begin{equation}\label{eq:convex-interval} - \forall\varepsilon\in\Big[\max\Big(-\lambda_i,(\lambda_j-1)\frac{c_j}{c_i}\Big), \min\Big(1-\lambda_i, \lambda_j - \frac{c_j}{c_i}\Big)\Big],\; - \lambda_\varepsilon\;\;\textrm{is feasible} - \end{equation} - Furthermore, the function $F_\lambda$ is convex; indeed: - \begin{align*} - F_\lambda(\varepsilon) - & = \mathbb{E}_{S'\sim P_{\mathcal{N}\setminus\{i,j\}}^\lambda(S')}\Big[ - (\lambda_i+\varepsilon)\Big(\lambda_j-\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{i,j\})\\ - & + (\lambda_i+\varepsilon)\Big(1-\lambda_j+\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{i\})\\ - &+ (1-\lambda_i-\varepsilon)\Big(\lambda_j-\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{j\})\\ - & + (1-\lambda_i-\varepsilon)\Big(1-\lambda_j+\varepsilon\frac{c_i}{c_j}\Big)V(S')\Big] - \end{align*} - Thus, $F_\lambda$ is a degree 2 polynomial whose dominant coefficient is: - \begin{displaymath} - \frac{c_i}{c_j}\mathbb{E}_{S'\sim - P_{\mathcal{N}\setminus\{i,j\}}^\lambda(S')}\Big[ - V(S'\cup\{i\})+V(S'\cup\{i\})\\ - -V(S'\cup\{i,j\})-V(S')\Big] - \end{displaymath} - which is positive by submodularity of $V$. Hence, the maximum of - $F_\lambda$ over the interval given in \eqref{eq:convex-interval} is - attained at one of its limits, at which either the $i$-th or $j$-th component of - $\lambda_\varepsilon$ becomes integral. \qed %\end{proof} -\subsection{Proof of Proposition~\ref{prop:relaxation}}\label{proofofproprelaxation} -The lower bound on $L^*_c$ follows immediately from the fact that $L$ extends $V$ to $[0,1]^n$. For the upper bound, let us consider a feasible point $\lambda^*\in \dom_c$ such that -$L(\lambda^*) = L^*_c$. By applying Lemma~\ref{lemma:relaxation-ratio} and -Lemma~\ref{lemma:rounding} we get a feasible point $\bar{\lambda}$ with at most -one fractional component such that -\begin{equation}\label{eq:e1} - L(\lambda^*) \leq 2 F(\bar{\lambda}). -\end{equation} - Let $\lambda_i$ denote the fractional component of $\bar{\lambda}$ and $S$ - denote the set whose indicator vector is $\bar{\lambda} - \lambda_i e_i$. - By definition of the multi-linear extension $F$: - \begin{displaymath} - F(\bar{\lambda}) = (1-\lambda_i)V(S) +\lambda_i V(S\cup\{i\}). - \end{displaymath} - By submodularity of $V$, $V(S\cup\{i\})\leq V(S) + V(\{i\})$. Hence, - \begin{displaymath} - F(\bar{\lambda}) \leq V(S) + V(i). - \end{displaymath} - Note that since $\bar{\lambda}$ is feasible, $S$ is also feasible and - $V(S)\leq OPT$. Hence, - \begin{equation}\label{eq:e2} - F(\bar{\lambda}) \leq OPT + \max_{i\in\mathcal{N}} V(i). - \end{equation} -Together, \eqref{eq:e1} and \eqref{eq:e2} imply the proposition.\qed - -\section{Proof of Proposition~\ref{prop:monotonicity}}\label{proofofpropmonotonicity} %The $\log\det$ function is concave and self-concordant (see %\cite{boyd2004convex}), in this case, the analysis of the barrier method in @@ -264,7 +49,6 @@ Together, \eqref{eq:e1} and \eqref{eq:e2} imply the proposition.\qed %For any $\varepsilon>0$, the barrier method computes an $\varepsilon$-accurate %approximation of $L^*_c$ in time $O(poly(n,d,\log\log\varepsilon^{-1})$. %\end{lemma} -We begin by a description of Algorithm~\ref{alg:monotone} which computes an approximation of $L^*_c$, which is arbitrarily accurate \emph{and} $\delta$-decreasing. %Note, that the feasible set in Problem~\eqref{eq:primal} increases (for the %inclusion) when the cost decreases. %non-increasing. @@ -311,243 +95,6 @@ We begin by a description of Algorithm~\ref{alg:monotone} which computes an appr %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}. We proceed by showing that the optimal value of \eqref{eq:perturbed-primal} is close to the -optimal value of \eqref{eq:primal} (Lemma~\ref{lemma:proximity}) while being -well-behaved with respect to changes of the cost -(Lemma~\ref{lemma:monotonicity}). These lemmas together imply -Proposition~\ref{prop:monotonicity}. - -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. - -Note that the choice of $\alpha$ given in Algorithm~\ref{alg:monotone} implies -that $\alpha<\frac{1}{n}$. This in turn implies that the feasible set -$\mathcal{D}_{c, \alpha}$ of \eqref{eq:perturbed-primal} is non-empty: it -contains the strictly feasible point $\lambda=(\frac{1}{n},\ldots,\frac{1}{n})$. - -\begin{lemma}\label{lemma:derivative-bounds} - Let $\partial_i L(\lambda)$ denote the $i$-th derivative of $L$, for $i\in\{1,\ldots, n\}$, then: - \begin{displaymath} - \forall\lambda\in[0, 1]^n,\;\frac{b}{2^n} \leq \partial_i L(\lambda) \leq 1 - \end{displaymath} -\end{lemma} - -\begin{proof} - Recall that we had defined: - \begin{displaymath} - \tilde{A}(\lambda)\defeq I_d + \sum_{i=1}^n \lambda_i x_i\T{x_i} - \quad\mathrm{and}\quad - A(S) \defeq I_d + \sum_{i\in S} x_i\T{x_i} - \end{displaymath} - Let us also define $A_k\defeq A(\{x_1,\ldots,x_k\})$. - We have $\partial_i L(\lambda) = \T{x_i}\tilde{A}(\lambda)^{-1}x_i$. Since - $\tilde{A}(\lambda)\succeq I_d$, $\partial_i L(\lambda)\leq \T{x_i}x_i \leq 1$, which - is the right-hand side of the lemma. - For the left-hand side, note that $\tilde{A}(\lambda) \preceq A_n$. Hence - $\partial_iL(\lambda)\geq \T{x_i}A_n^{-1}x_i$. - Using the Sherman-Morrison formula \cite{sm}, for all $k\geq 1$: - \begin{displaymath} - \T{x_i}A_k^{-1} x_i = \T{x_i}A_{k-1}^{-1}x_i - - \frac{(\T{x_i}A_{k-1}^{-1}x_k)^2}{1+\T{x_k}A_{k-1}^{-1}x_k} - \end{displaymath} - By the Cauchy-Schwarz inequality: - \begin{displaymath} - (\T{x_i}A_{k-1}^{-1}x_k)^2 \leq \T{x_i}A_{k-1}^{-1}x_i\;\T{x_k}A_{k-1}^{-1}x_k - \end{displaymath} - Hence: - \begin{displaymath} - \T{x_i}A_k^{-1} x_i \geq \T{x_i}A_{k-1}^{-1}x_i - - \T{x_i}A_{k-1}^{-1}x_i\frac{\T{x_k}A_{k-1}^{-1}x_k}{1+\T{x_k}A_{k-1}^{-1}x_k} - \end{displaymath} - But $\T{x_k}A_{k-1}^{-1}x_k\leq 1$ and $\frac{a}{1+a}\leq \frac{1}{2}$ if - $0\leq a\leq 1$, so: - \begin{displaymath} - \T{x_i}A_{k}^{-1}x_i \geq \T{x_i}A_{k-1}^{-1}x_i - - \frac{1}{2}\T{x_i}A_{k-1}^{-1}x_i\geq \frac{\T{x_i}A_{k-1}^{-1}x_i}{2} - \end{displaymath} - By induction: - \begin{displaymath} - \T{x_i}A_n^{-1} x_i \geq \frac{\T{x_i}x_i}{2^n} - \end{displaymath} - Using that $\T{x_i}{x_i}\geq b$ concludes the proof of the left-hand side - of the lemma's inequality. -\end{proof} -Let us introduce the Lagrangian of problem \eqref{eq:perturbed-primal}: - -\begin{displaymath} - \mathcal{L}_{c, \alpha}(\lambda, \mu, \nu, \xi) \defeq L(\lambda) - + \T{\mu}(\lambda-\alpha\mathbf{1}) + \T{\nu}(\mathbf{1}-\lambda) + \xi(B-\T{c}\lambda) -\end{displaymath} -so that: -\begin{displaymath} - L^*_{c,\alpha} = \min_{\mu, \nu, \xi\geq 0}\max_\lambda \mathcal{L}_{c, \alpha}(\lambda, \mu, \nu, \xi) -\end{displaymath} -Similarly, we define $\mathcal{L}_{c}\defeq\mathcal{L}_{c, 0}$ the lagrangian of \eqref{eq:primal}. - -Let $\lambda^*$ be primal optimal for \eqref{eq:perturbed-primal}, and $(\mu^*, -\nu^*, \xi^*)$ be dual optimal for the same problem. In addition to primal and -dual feasibility, the Karush-Kuhn-Tucker (KKT) conditions \cite{boyd2004convex} give $\forall i\in\{1, \ldots, n\}$: -\begin{gather*} - \partial_i L(\lambda^*) + \mu_i^* - \nu_i^* - \xi^* c_i = 0\\ - \mu_i^*(\lambda_i^* - \alpha) = 0\\ - \nu_i^*(1 - \lambda_i^*) = 0 -\end{gather*} - -\begin{lemma}\label{lemma:proximity} -We have: -\begin{displaymath} - L^*_c - \alpha n^2\leq L^*_{c,\alpha} \leq L^*_c -\end{displaymath} -In particular, $|L^*_c - L^*_{c,\alpha}| \leq \alpha n^2$. -\end{lemma} - -\begin{proof} - $\alpha\mapsto L^*_{c,\alpha}$ is a decreasing function as it is the - maximum value of the $L$ function over a set-decreasing domain, which gives - the rightmost inequality. - - Let $\mu^*, \nu^*, \xi^*$ be dual optimal for $(P_{c, \alpha})$, that is: - \begin{displaymath} - L^*_{c,\alpha} = \max_\lambda \mathcal{L}_{c, \alpha}(\lambda, \mu^*, \nu^*, \xi^*) - \end{displaymath} - - Note that $\mathcal{L}_{c, \alpha}(\lambda, \mu^*, \nu^*, \xi^*) - = \mathcal{L}_{c}(\lambda, \mu^*, \nu^*, \xi^*) - - \alpha\T{\mathbf{1}}\mu^*$, and that for any $\lambda$ feasible for - problem \eqref{eq:primal}, $\mathcal{L}_{c}(\lambda, \mu^*, \nu^*, \xi^*) - \geq L(\lambda)$. Hence, - \begin{displaymath} - L^*_{c,\alpha} \geq L(\lambda) - \alpha\T{\mathbf{1}}\mu^* - \end{displaymath} - for any $\lambda$ feasible for \eqref{eq:primal}. In particular, for $\lambda$ primal optimal for $\eqref{eq:primal}$: - \begin{equation}\label{eq:local-1} - L^*_{c,\alpha} \geq L^*_c - \alpha\T{\mathbf{1}}\mu^* - \end{equation} - - Let us denote by the $M$ the support of $\mu^*$, that is $M\defeq - \{i|\mu_i^* > 0\}$, and by $\lambda^*$ a primal optimal point for - $\eqref{eq:perturbed-primal}$. From the KKT conditions we see that: - \begin{displaymath} - M \subseteq \{i|\lambda_i^* = \alpha\} - \end{displaymath} - - - Let us first assume that $|M| = 0$, then $\T{\mathbf{1}}\mu^*=0$ and the lemma follows. - - We will now assume that $|M|\geq 1$. In this case $\T{c}\lambda^* - = B$, otherwise we could increase the coordinates of $\lambda^*$ in $M$, - which would increase the value of the objective function and contradict the - optimality of $\lambda^*$. Note also, that $|M|\leq n-1$, otherwise, since - $\alpha< \frac{1}{n}$, we would have $\T{c}\lambda^*\ < B$, which again - contradicts the optimality of $\lambda^*$. Let us write: - \begin{displaymath} - B = \T{c}\lambda^* = \alpha\sum_{i\in M}c_i + \sum_{i\in \bar{M}}\lambda_i^*c_i - \leq \alpha |M|B + (n-|M|)\max_{i\in \bar{M}} c_i - \end{displaymath} - That is: - \begin{equation}\label{local-2} - \max_{i\in\bar{M}} c_i \geq \frac{B - B|M|\alpha}{n-|M|}> \frac{B}{n} - \end{equation} - where the last inequality uses again that $\alpha<\frac{1}{n}$. From the - KKT conditions, we see that for $i\in M$, $\nu_i^* = 0$ and: - \begin{equation}\label{local-3} - \mu_i^* = \xi^*c_i - \partial_i L(\lambda^*)\leq \xi^*c_i\leq \xi^*B - \end{equation} - since $\partial_i L(\lambda^*)\geq 0$ and $c_i\leq 1$. - - Furthermore, using the KKT conditions again, we have that: - \begin{equation}\label{local-4} - \xi^* \leq \inf_{i\in \bar{M}}\frac{\partial_i L(\lambda^*)}{c_i}\leq \inf_{i\in \bar{M}} \frac{1}{c_i} - = \frac{1}{\max_{i\in\bar{M}} c_i} - \end{equation} - where the last inequality uses Lemma~\ref{lemma:derivative-bounds}. - Combining \eqref{local-2}, \eqref{local-3} and \eqref{local-4}, we get that: - \begin{displaymath} - \sum_{i\in M}\mu_i^* \leq |M|\xi^*B \leq n\xi^*B\leq \frac{nB}{\max_{i\in\bar{M}} c_i} \leq n^2 - \end{displaymath} - This implies that: - \begin{displaymath} - \T{\mathbf{1}}\mu^* = \sum_{i=1}^n \mu^*_i = \sum_{i\in M}\mu_i^*\leq n^2 - \end{displaymath} - which along with \eqref{eq:local-1} proves the lemma. -\end{proof} - -\begin{lemma}\label{lemma:monotonicity} - If $c'$ = $(c_i', c_{-i})$, with $c_i'\leq c_i - \delta$, we have: - \begin{displaymath} - L^*_{c',\alpha} \geq L^*_{c,\alpha} + \frac{\alpha\delta b}{2^nB} - \end{displaymath} -\end{lemma} - -\begin{proof} - Let $\mu^*, \nu^*, \xi^*$ be dual optimal for $(P_{c', \alpha})$. Noting that: - \begin{displaymath} - \mathcal{L}_{c', \alpha}(\lambda, \mu^*, \nu^*, \xi^*) \geq - \mathcal{L}_{c, \alpha}(\lambda, \mu^*, \nu^*, \xi^*) + \lambda_i\xi^*\delta, - \end{displaymath} - we get similarly to Lemma~\ref{lemma:proximity}: - \begin{displaymath} - L^*_{c',\alpha} \geq L(\lambda) + \lambda_i\xi^*\delta - \end{displaymath} - for any $\lambda$ feasible for \eqref{eq:perturbed-primal}. In particular, for $\lambda^*$ primal optimal for \eqref{eq:perturbed-primal}: - \begin{displaymath} - L^*_{c',\alpha} \geq L^*_{c,\alpha} + \alpha\xi^*\delta - \end{displaymath} - since $\lambda_i^*\geq \alpha$. - - Using the KKT conditions for $(P_{c', \alpha})$, we can write: - \begin{displaymath} - \xi^* = \inf_{i:\lambda^{'*}_i>\alpha} \frac{\T{x_i}S(\lambda^{'*})^{-1}x_i}{c_i'} - \end{displaymath} - with $\lambda^{'*}$ optimal for $(P_{c', \alpha})$. Since $c_i'\leq B$, - using Lemma~\ref{lemma:derivative-bounds}, we get that $\xi^*\geq - \frac{b}{2^nB}$, which concludes the proof. -\end{proof} - -%\subsection*{End of the proof of Proposition~\ref{prop:monotonicity}} -We are now ready to conclude the proof of Proposition~\ref{prop:monotonicity}. -Let $\hat{L}^*_{c,\alpha}$ be the approximation computed by -Algorithm~\ref{alg:monotone}. -\begin{enumerate} - \item using Lemma~\ref{lemma:proximity}: -\begin{displaymath} - |\hat{L}^*_{c,\alpha} - L^*_c| \leq |\hat{L}^*_{c,\alpha} - L^*_{c,\alpha}| + |L^*_{c,\alpha} - L^*_c| - \leq \frac{\alpha\delta}{B} + \alpha n^2 = \varepsilon -\end{displaymath} -which proves the $\varepsilon$-accuracy. - -\item for the $\delta$-decreasingness, let $c' = (c_i', c_{-i})$ with $c_i'\leq - c_i-\delta$, then: -\begin{displaymath} - \hat{L}^*_{c',\alpha} \geq L^*_{c',\alpha} - \frac{\alpha\delta b}{2^{n+1}B} - \geq L^*_{c,\alpha} + \frac{\alpha\delta b}{2^{n+1}B} - \geq \hat{L}^*_{c,\alpha} -\end{displaymath} -where the first and last inequalities follow from the accuracy of the approximation, and -the inner inequality follows from Lemma~\ref{lemma:monotonicity}. - -\item the accuracy of the approximation $\hat{L}^*_{c,\alpha}$ is: -\begin{displaymath} - \varepsilon' =\frac{\varepsilon\delta b}{2^{n+1}(\delta + n^2B)} -\end{displaymath} - -Note that: -\begin{displaymath} - \log\log (\varepsilon')^{-1} = O\bigg(\log\log\frac{B}{\varepsilon\delta b} + \log n\bigg) -\end{displaymath} -Using Lemma~\ref{lemma:barrier} concludes the proof of the running time.\qed -\end{enumerate} - \section{Budget Feasible Reverse Auction Mechanisms}\label{app:budgetfeasible} We review in this appendix the formal definition of a budget feasible reverse auction mechanisms, as introduced by \citeN{singer-mechanisms}. We depart from the definitions in \cite{singer-mechanisms} only in considering $\delta$-truthful, rather than truthful, mechanisms. @@ -582,10 +129,6 @@ Formally, there must exist some $\alpha\geq 1$ and $\beta>0$ should be computable in time polynomial in various parameters. %time in the number of agents $n$. %\thibaut{Should we say something about the black-box model for $V$? Needed to say something in general, but not in our case where the value function can be computed in polynomial time}. \end{itemize} -\section{Proof of Lemma~\ref{thm:myerson-variant}}\label{sec:myerson} -\input{myerson} - -\section{Description of our mechanism for \EDP{} and proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm} % %Instead, \citeN{singer-mechanisms} and \citeN{chen} @@ -634,216 +177,3 @@ Formally, there must exist some $\alpha\geq 1$ and $\beta>0$ %variant of Myerson's theorem. -\begin{algorithm}[!t] - \caption{Mechanism for \SEDP{}}\label{mechanism} - \begin{algorithmic}[1] - %\State $\mathcal{N} \gets \mathcal{N}\setminus\{i\in\mathcal{N} : c_i > B\}$ - \Require{ $B\in \reals_+$,$c\in[0,B]^n$, $\delta\in (0,1]$, $\epsilon\in (0,1]$ } - \State $i^* \gets \argmax_{j\in\mathcal{N}}V(j)$ - \State \label{relaxexec}$OPT'_{-i^*} \gets$ using Proposition~\ref{prop:monotonicity}, - compute a $\varepsilon$-accurate, $\delta$-decreasing - approximation of $$\textstyle L^*_{c_{-i^*}}\defeq\max_{\lambda\in[0,1]^{n}} \{L(\lambda) - \mid \lambda_{i^*}=0,\sum_{i \in \mathcal{N}\setminus\{i^*\}}c_i\lambda_i\leq B\}$$ - %\Statex - \State $C \gets \frac{8e-1 + \sqrt{64e^2-24e + 9}}{2(e-1)}$ - - \If{$OPT'_{-i^*} < C \cdot V(i^*)$} \label{c} - \State \textbf{return} $\{i^*\}$ - \Else - \State $i \gets \argmax_{1\leq j\leq n}\frac{V(j)}{c_j}$ - \State $S_G \gets \emptyset$ - \While{$c_i\leq \frac{B}{2}\frac{V(S_G\cup\{i\})-V(S_G)}{V(S_G\cup\{i\})}$} - \State $S_G \gets S_G\cup\{i\}$ - \State $i \gets \argmax_{j\in\mathcal{N}\setminus S_G} - \frac{V(S_G\cup\{j\})-V(S_G)}{c_j}$ - \EndWhile - \State \textbf{return} $S_G$ - \EndIf - \end{algorithmic} -\end{algorithm} - - -We present here the proof of Theorem~\ref{thm:main}. -Our mechanism for \EDP{} is composed of -(a) the allocation function presented in Algorithm~\ref{mechanism}, and -(b) the payment function which pays each allocated agent $i$ her threshold -payment as described in Myerson's Theorem (see Lemma~\ref{thm:myerson-variant}). In the case where $\{i^*\}$ is the -allocated set, her threshold payment is $B$. %(she would be have been dropped on -%line 1 of Algorithm~\ref{mechanism} had she reported a higher cost). -A closed-form formula for threshold payments when $S_G$ is the allocated set can -be found in~\cite{singer-mechanisms}. - - -We use the notation $OPT_{-i^*}$ to denote the optimal value of \EDP{} when the maximum value element $i^*$ is excluded. We also use $OPT'_{-i^*}$ to denote the approximation computed by the $\delta$-decreasing, $\epsilon$-accurate approximation of $L^*_{c_{-i^*}}$, as defined in Algorithm~\ref{mechanism}. - - -The properties of $\delta$-truthfulness and -individual rationality follow from $\delta$-monotonicity and threshold -payments. $\delta$-monotonicity and budget feasibility follow similar steps as the -analysis of \citeN{chen}, adapted to account for $\delta$-monotonicity: -\begin{lemma}\label{lemma:monotone} -Our mechanism for \EDP{} is $\delta$-monotone and budget feasible. -\end{lemma} - -\begin{proof} - Consider an agent $i$ with cost $c_i$ that is - selected by the mechanism, and suppose that she reports - a cost $c_i'\leq c_i-\delta$ while all other costs stay the same. - Suppose that when $i$ reports $c_i$, $OPT'_{-i^*} \geq C V(i^*)$; then, as $s_i(c_i,c_{-i})=1$, $i\in S_G$. - By reporting cost $c_i'$, $i$ may be selected at an earlier iteration of the greedy algorithm. - %using the submodularity of $V$, we see that $i$ will satisfy the greedy - %selection rule: - %\begin{displaymath} - % i = \argmax_{j\in\mathcal{N}\setminus S} \frac{V(S\cup\{j\}) - % - V(S)}{c_j} - %\end{displaymath} - %in an earlier iteration of the greedy heuristic. - Denote by $S_i$ - (resp. $S_i'$) the set to which $i$ is added when reporting cost $c_i$ - (resp. $c_i'$). We have $S_i'\subseteq S_i$; in addition, $S_i'\subseteq S_G'$, the set selected by the greedy algorithm under $(c_i',c_{-i})$; if not, then greedy selection would terminate prior to selecting $i$ also when she reports $c_i$, a contradiction. Moreover, we have - \begin{align*} - c_i' & \leq c_i \leq - \frac{B}{2}\frac{V(S_i\cup\{i\})-V(S_i)}{V(S_i\cup\{i\})} - \leq \frac{B}{2}\frac{V(S_i'\cup\{i\})-V(S_i')}{V(S_i'\cup\{i\})} - \end{align*} - by the monotonicity and submodularity of $V$. Hence $i\in S_G'$. By - $\delta$-decreasingness of - $OPT'_{-i^*}$, under $c'_i\leq c_i-\delta$ the greedy set is still allocated and $s_i(c_i',c_{-i}) =1$. - Suppose now that when $i$ reports $c_i$, $OPT'_{-i^*} < C V(i^*)$. Then $s_i(c_i,c_{-i})=1$ iff $i = i^*$. - Reporting $c_{i^*}'\leq c_{i^*}$ does not change $V(i^*)$ nor - $OPT'_{-i^*} \leq C V(i^*)$; thus $s_{i^*}(c_{i^*}',c_{-i^*})=1$, so the mechanism is monotone. - -To show budget feasibility, suppose that $OPT'_{-i^*} < C V(i^*)$. Then the mechanism selects $i^*$. Since the bid of $i^*$ does not affect the above condition, the threshold payment of $i^*$ is $B$ and the mechanism is budget feasible. -Suppose that $OPT'_{-i^*} \geq C V(i^*)$. -Denote by $S_G$ the set selected by the greedy algorithm, and for $i\in S_G$, denote by -$S_i$ the subset of the solution set that was selected by the greedy algorithm just prior to the addition of $i$---both sets determined for the present cost vector $c$. -%Chen \emph{et al.}~\cite{chen} show that, -Then for any submodular function $V$, and for all $i\in S_G$: -%the reported cost of an agent selected by the greedy heuristic, and holds for -%any submodular function $V$: -\begin{equation}\label{eq:budget} - \text{if}~c_i'\geq \frac{V(S_i\cup\{i\}) - V(S)}{V(S_G)} B~\text{then}~s_i(c_i',c_{-i})=0 -\end{equation} -In other words, if $i$ increases her cost to a value higher than $\frac{V(S_i\cup\{i\}) - V(S)}{V(S_G)}$, she will cease to be in the selected set $S_G$. As a result, -\eqref{eq:budget} -implies that the threshold payment of user $i$ is bounded by the above quantity. -%\begin{displaymath} -%\frac{V(S_i\cup\{i\}) - V(S_i)}{V(S_G)} = B -%\end{displaymath} -Hence, the total payment is bounded by the telescopic sum: -\begin{displaymath} - \sum_{i\in S_G} \frac{V(S_i\cup\{i\}) - V(S_i)}{V(S_G)} B = \frac{V(S_G)-V(\emptyset)}{V(S_G)} B=B\qedhere -\end{displaymath} -\end{proof} - -The complexity of the mechanism is given by the following lemma. - -\begin{lemma}[Complexity]\label{lemma:complexity} - For any $\varepsilon > 0$ and any $\delta>0$, the complexity of the mechanism is - $O\big(poly(n, d, \log\log\frac{B}{b\varepsilon\delta})\big)$ -\end{lemma} - -\begin{proof} - The value function $V$ in \eqref{modified} can be computed in time - $O(\text{poly}(n, d))$ and the mechanism only involves a linear - number of queries to the function $V$. - By Proposition~\ref{prop:monotonicity}, line \ref{relaxexec} of Algorithm~\ref{mechanism} - can be computed in time - $O(\text{poly}(n, d, \log\log \frac{B}{b\varepsilon\delta}))$. Hence the allocation - function's complexity is as stated. - %Payments can be easily computed in time $O(\text{poly}(n, d))$ as in prior work. -\junk{ - Using Singer's characterization of the threshold payments - \cite{singer-mechanisms}, one can verify that they can be computed in time - $O(\text{poly}(n, d))$. - } -\end{proof} - -Finally, we prove the approximation ratio of the mechanism. -We use the following lemma from \cite{chen} which bounds $OPT$ in terms of -the value of $S_G$, as computed in Algorithm \ref{mechanism}, and $i^*$, the -element of maximum value. - -\begin{lemma}[\cite{chen}]\label{lemma:greedy-bound} -Let $S_G$ be the set computed in Algorithm \ref{mechanism} and let -$i^*=\argmax_{i\in\mathcal{N}} V(\{i\})$. We have: -\begin{displaymath} -OPT \leq \frac{e}{e-1}\big( 3 V(S_G) + 2 V(i^*)\big). -\end{displaymath} -\end{lemma} - -Using Proposition~\ref{prop:relaxation} and Lemma~\ref{lemma:greedy-bound} we -can complete the proof of the approximation ratio of our mechanism -Theorem~\ref{thm:main} by showing that, for any $\varepsilon > 0$, if -$OPT_{-i}'$, the optimal value of $L$ when $i^*$ is excluded from -$\mathcal{N}$, has been computed to a precision $\varepsilon$, then the set -$S^*$ allocated by the mechanism is such that: -\begin{equation} \label{approxbound} -OPT -\leq \frac{10e\!-\!3 + \sqrt{64e^2\!-\!24e\!+\!9}}{2(e\!-\!1)} V(S^*)\! -+ \! \varepsilon . -\end{equation} -To see this, let $L^*_{c_{-i^*}}$ be the maximum value of $L$ subject to -$\lambda_{i^*}=0$, $\sum_{i\in \mathcal{N}\setminus{i^*}}c_i\leq B$. From line -\ref{relaxexec} of Algorithm~\ref{mechanism}, we have -$L^*_{c_{-i^*}}-\varepsilon\leq OPT_{-i^*}' \leq L^*_{c_{-i^*}}+\varepsilon$. - -If the condition on line \ref{c} of the algorithm holds then, from the lower bound in Proposition~\ref{prop:relaxation}, -\begin{displaymath} - V(i^*) \geq \frac{1}{C}L^*_{c_{-i^*}}-\frac{\varepsilon}{C} \geq - \frac{1}{C}OPT_{-i^*} -\frac{\varepsilon}{C}. -\end{displaymath} -Also, $OPT \leq OPT_{-i^*} + V(i^*)$, -hence, -\begin{equation}\label{eq:bound1} - OPT\leq (1+C)V(i^*) + \varepsilon. -\end{equation} -If the condition on line \ref{c} does not hold, by observing that $L^*_{c_{-i^*}}\leq L^*_c$ and -the upper bound of Proposition~\ref{prop:relaxation}, we get -\begin{displaymath} - V(i^*)\leq \frac{1}{C}L^*_{c_{-i^*}} + \frac{\varepsilon}{C} - \leq \frac{1}{C} \big(2 OPT + 2 V(i^*)\big) + \frac{\varepsilon}{C}. -\end{displaymath} -Applying Lemma~\ref{lemma:greedy-bound}, -\begin{displaymath} - V(i^*) \leq \frac{1}{C}\left(\frac{2e}{e-1}\big(3 V(S_G) - + 2 V(i^*)\big) + 2 V(i^*)\right) + \frac{\varepsilon}{C}. -\end{displaymath} -Note that $C$ satifies $C(e-1) -6e +2 > 0$, hence -\begin{align*} - V(i^*) \leq \frac{6e}{C(e-1)- 6e + 2} V(S_G) - + \frac{(e-1)\varepsilon}{C(e-1)- 6e + 2}. -\end{align*} -Finally, using Lemma~\ref{lemma:greedy-bound} again, we get -\begin{equation}\label{eq:bound2} - OPT \leq - \frac{3e}{e-1}\left( 1 + \frac{4e}{C (e-1) -6e +2}\right) V(S_G) - + \frac{2e\varepsilon}{C(e-1)- 6e + 2}. -\end{equation} -Our choice of $C$, namely, -\begin{equation}\label{eq:constant} - C = \frac{8e-1 + \sqrt{64e^2-24e + 9}}{2(e-1)}, -\end{equation} - is precisely to minimize the maximum among the coefficients of $V_{i^*}$ and $V(S_G)$ in \eqref{eq:bound1} -and \eqref{eq:bound2}, respectively. Indeed, consider: -\begin{displaymath} - \max\left(1+C,\frac{3e}{e-1}\left( 1 + \frac{4e}{C (e-1) -6e +2} - \right)\right). -\end{displaymath} -This function has two minima, only one of those is such that $C(e-1) -6e -+2 \geq 0$. This minimum is precisely \eqref{eq:constant}. -For this minimum, $\frac{2e\varepsilon}{C(e-1)- 6e + 2}\leq \varepsilon.$ -Placing the expression of $C$ in \eqref{eq:bound1} and \eqref{eq:bound2} -gives the approximation ratio in \eqref{approxbound}, and concludes the proof -of Theorem~\ref{thm:main}.\hspace*{\stretch{1}}\qed - -Finally, we prove the lower bound stated in Theorem~\ref{thm:main}. -Suppose, for contradiction, that such a mechanism exists. From Myerson's Theorem \cite{myerson}, a single parameter auction is truthful if and only if the allocation function is monotone and agents are paid theshold payments. Consider two -experiments with dimension $d=2$, such that $x_1 = e_1=[1 ,0]$, $x_2=e_2=[0,1]$ -and $c_1=c_2=B/2+\epsilon$. Then, one of the two experiments, say, $x_1$, must -be in the set selected by the mechanism, otherwise the ratio is unbounded, -a contradiction. If $x_1$ lowers its value to $B/2-\epsilon$, by monotonicity -it remains in the solution; by threshold payment, it is paid at least -$B/2+\epsilon$. So $x_2$ is not included in the solution by budget feasibility -and individual rationality: hence, the selected set attains a value $\log2$, -while the optimal value is $2\log 2$.\hspace*{\stretch{1}}\qed |