From 21f91d91b99fcb1cec8840137d929da88e42e65e Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Mon, 11 Feb 2013 10:47:04 -0800 Subject: Section titles capitalization and splitting section 4 --- main.tex | 434 +-------------------------------------------------------------- 1 file changed, 3 insertions(+), 431 deletions(-) (limited to 'main.tex') diff --git a/main.tex b/main.tex index f11c4ee..2986eb1 100644 --- a/main.tex +++ b/main.tex @@ -4,7 +4,7 @@ In this section we present our mechanism for \SEDP. Prior approaches to budget feasible mechanisms for sudmodular maximization build upon the full information case which we discuss first. -\subsection*{Submodular maximization in the full-information case} +\subsection{Submodular Maximization in the Full Information Case} In the full-information case, submodular maximization under a budget constraint \eqref{eq:non-strategic} relies on a greedy heuristic in which elements are @@ -32,7 +32,7 @@ This lemma immediately implies that the following algorithm: \end{equation} has an approximation ratio of $\frac{5e}{e-1}$. -\subsection*{Submodular maximization in the strategic case} +\subsection{Submodular Maximization in the Strategic Case} In the strategic case, Algorithm~\eqref{eq:max-algorithm} breaks incentive compatibility. Indeed, \citeN{singer-influence} notes that this allocation @@ -83,7 +83,7 @@ One of the main technical contribution of \citeN{chen} and \citeN{singer-influence} is to come up with appropriate relaxations for \textsc{Knapsack} and \textsc{Coverage} respectively. -\subsection*{Our approach} +\subsection{Our Approach} \sloppy We introduce a relaxation $L$ specifically tailored to the value function of @@ -156,431 +156,3 @@ In addition, we prove the following simple lower bound. There is no $2$-approximate, truthful, budget feasible, individually rational mechanism for EDP. \end{theorem} -\subsection{Proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm} - -We now present the proof of Theorem~\ref{thm:main}. Truthfulness and individual -rationality follow from monotonicity and threshold payments. Monotonicity and -budget feasibility follow the same steps as the analysis of \citeN{chen}; - for the sake of completeness, we restate their proof in the Appendix. - -The complexity of the mechanism is given by the following lemma. -\begin{lemma}[Complexity]\label{lemma:complexity} - For any $\varepsilon > 0$, the complexity of the mechanism is - $O(\text{poly}(n, d, \log\log \varepsilon^{-1}))$. -\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$. - The function $\log\det$ is concave and self-concordant (see - \cite{boyd2004convex}), so for any $\varepsilon$, its maximum can be found - to a precision $\varepsilon$ in $O(\log\log\varepsilon^{-1})$ of iterations of Newton's method. Each iteration can be - done in time $O(\text{poly}(n, d))$. Thus, line 3 of - Algorithm~\ref{mechanism} can be computed in time - $O(\text{poly}(n, d, \log\log \varepsilon^{-1}))$. 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 which establishes that $OPT'$, the optimal value \eqref{relax} of the fractional relaxation $L$ under the budget constraints - is not too far from $OPT$. -\begin{lemma}[Approximation]\label{lemma:relaxation} - $ OPT' \leq 2 OPT - + 2\max_{i\in\mathcal{N}}V(i)$ -\end{lemma} -The proof of Lemma~\ref{lemma:relaxation} is our main technical contribution, and can be found in Section \ref{sec:relaxation}. - -Using Lemma~\ref{lemma:relaxation} we can complete the proof of -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 $OPT_{-i^*}'$ be the true maximum value of $L$ subject to -$\lambda_{i^*}=0$, $\sum_{i\in \mathcal{N}\setminus{i^*}}c_i\leq B$. Assume -that on line 3 of algorithm~\ref{mechanism}, a quantity $\tilde{L}$ such that -$\tilde{L}-\varepsilon\leq OPT_{-i^*}' \leq \tilde{L}+\varepsilon$ has been -computed (Lemma~\ref{lemma:complexity} states that this is computed in time -within our complexity guarantee). If the condition on line 3 of the algorithm -holds, then: -\begin{displaymath} - V(i^*) \geq \frac{1}{C}OPT_{-i^*}'-\frac{\varepsilon}{C} \geq - \frac{1}{C}OPT_{-i^*} -\frac{\varepsilon}{C} -\end{displaymath} -as $L$ is a fractional relaxation of $V$. Also, $OPT \leq OPT_{-i^*} + V(i^*)$, -hence: -\begin{equation}\label{eq:bound1} - OPT\leq (1+C)V(i^*) + \varepsilon -\end{equation} -Note that $OPT_{-i^*}'\leq OPT'$. If the condition does not hold, from Lemmas -\ref{lemma:relaxation} and \ref{lemma:greedy-bound}: -\begin{align*} - V(i^*) & \stackrel{}\leq \frac{1}{C}OPT_{-i^*}' + \frac{\varepsilon}{C} - \leq \frac{1}{C} \big(2 OPT + 2 V(i^*)\big) + \frac{\varepsilon}{C}\\ - & \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{align*} -Thus, if $C$ is such that $C(e-1) -6e +2 > 0$, -\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 again Lemma~\ref{lemma:greedy-bound}, we get: -\begin{equation}\label{eq:bound2} - OPT(V, \mathcal{N}, B) \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} -To minimize the coefficients of $V_{i^*}$ and $V(S_G)$ in \eqref{eq:bound1} -and \eqref{eq:bound2} respectively, we wish to chose for $C=C^*$ such that: -\begin{displaymath} - C^* = \argmin_C - \max\left(1+C,\frac{3e}{e-1}\left( 1 + \frac{4e}{C (e-1) -6e +2} - \right)\right) -\end{displaymath} -This equation has two solutions. Only one of those is such that $C(e-1) -6e -+2 \geq 0$. This solution is: -\begin{displaymath} - C^* = \frac{8e-1 + \sqrt{64e^2-24e + 9}}{2(e-1)} \label{eq:c} -\end{displaymath} -For this solution, $\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 - -\subsection{Proof of Lemma~\ref{lemma:relaxation}}\label{sec:relaxation} - -We need to prove that for our relaxation $L$ given by -\eqref{eq:our-relaxation}, $OPT'$ is close to $OPT$ as stated in -Lemma~\ref{lemma:relaxation}. Our analysis follows the \emph{pipage rounding} -framework of \citeN{pipage}. - -This framework uses the \emph{multi-linear} extension $F$ of the submodular -function $V$. 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$: -\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$ is defined by: -\begin{displaymath} - 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) -\end{displaymath} - -For \EDP{} the multi-linear extension can be written: -\begin{equation}\label{eq:multi-linear-logdet} - F(\lambda) = \mathbb{E}_{S\sim - P_\mathcal{N}^\lambda}\bigg[\log\det \big(I_d + \sum_{i\in S} x_i\T{x_i}\big) \Big]. -\end{equation} -Note that the relaxation $L$ that we introduced in \eqref{eq:our-relaxation}, -follows naturally from the \emph{multi-linear} relaxation by swapping the -expectation and the $\log\det$ in \eqref{eq:multi-linear-logdet}: -\begin{displaymath} - L(\lambda) = \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{displaymath} - -The proof proceeds as follows: -\begin{itemize} -\item First, we prove that $F$ admits the following rounding 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}. This is stated and proven in -Lemma~\ref{lemma:rounding} and allows us to bound $F$ in terms of $OPT$. -\item Next, we prove the central result of bounding $L$ appropriately in terms -of the multi-linear relaxation $F$ (Lemma \ref{lemma:relaxation-ratio}). -\item Finally, we conclude the proof of Lemma~\ref{lemma:relaxation} by -combining Lemma~\ref{lemma:rounding} and Lemma~\ref{lemma:relaxation-ratio}. -\end{itemize} - -\begin{comment} -Formally, if we define: -\begin{displaymath} - \tilde{F}_\lambda(\varepsilon) \defeq F\big(\lambda + \varepsilon(e_i - - e_j)\big) -\end{displaymath} -where $e_i$ and $e_j$ are two vectors of the standard basis of -$\reals^{n}$, then $\tilde{F}_\lambda$ is convex. Hence its maximum over the interval: -\begin{displaymath} - I_\lambda = \Big[\max(-\lambda_i,\lambda_j-1), \min(1-\lambda_i, \lambda_j)\Big] -\end{displaymath} -is attained at one of the boundaries of $I_\lambda$ for which one of the $i$-th -or the $j$-th component of $\lambda$ becomes integral. -\end{comment} - -\begin{lemma}[Rounding]\label{lemma:rounding} - For any feasible $\lambda\in[0,1]^{n}$, there exists a feasible - $\bar{\lambda}\in[0,1]^{n}$ such that at most one of its components is - fractional %, that is, lies in $(0,1)$ and: - and $F_{\mathcal{N}}(\lambda)\leq F_{\mathcal{N}}(\bar{\lambda})$. -\end{lemma} -\begin{proof} - We give a rounding procedure which, given a feasible $\lambda$ with at least - two fractional components, returns some feasible $\lambda'$ with one less 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 limit, at which either the $i$-th or $j$-th component of - $\lambda_\varepsilon$ becomes integral. -\end{proof} - - -\begin{lemma}\label{lemma:relaxation-ratio} - % The following inequality holds: -For all $\lambda\in[0,1]^{n},$ - %\begin{displaymath} - $ \frac{1}{2} - \,L(\lambda)\leq - F(\lambda)\leq L(\lambda)$. - %\end{displaymath} -\end{lemma} -\begin{proof} - The bound $F_{\mathcal{N}}(\lambda)\leq L_{\mathcal{N}(\lambda)}$ follows by the concavity of the $\log\det$ function. - 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 - $\partial_i\, \cdot$ denotes the partial derivative with respect to the - $i$-th variable. - - Let us start by computing the 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} - The marginal contribution of $i$ to - $S$ can be written as -\begin{align*} -V(S\cup \{i\}) - V(S)& = \frac{1}{2}\log\det(I_d - + \T{X_S}X_S + x_i\T{x_i}) - - \frac{1}{2}\log\det(I_d + \T{X_S}X_S)\\ - & = \frac{1}{2}\log\det(I_d + x_i\T{x_i}(I_d + -\T{X_S}X_S)^{-1}) - = \frac{1}{2}\log(1 + \T{x_i}A(S)^{-1}x_i) -\end{align*} -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) = 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} - Finally: - \begin{displaymath} - \partial_i L(\lambda) - =\frac{1}{2} \T{x_i}\tilde{A}(\lambda)^{-1}x_i - \end{displaymath} - -For two symmetric matrices $A$ and $B$, we write $A\succ B$ ($A\succeq B$) if -$A-B$ is positive definite (positive semi-definite). This order allows us to -define the notion of a \emph{decreasing} as well as \emph{convex} matrix -function, similarly to their real counterparts. With this definition, matrix -inversion is decreasing and convex over symmetric positive definite matrices. -In particular, -\begin{gather*} - \forall S\subseteq\mathcal{N},\quad A(S)^{-1} \succeq A(S\cup\{i\})^{-1} -\end{gather*} - Observe that: - \begin{gather*} - \forall S\subseteq\mathcal{N}\setminus\{i\},\quad - P_{\mathcal{N}\setminus\{i\}}^\lambda(S)\geq - P_{\mathcal{N}\setminus\{i\}}^\lambda(S\cup\{i\})\\ - \forall S\subseteq\mathcal{N},\quad P_{\mathcal{N}\setminus\{i\}}^\lambda(S) - \geq P_\mathcal{N}^\lambda(S) - \end{gather*} - Hence: - \begin{align*} - \partial_i F(\lambda) - % & = \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)\\ - & \geq \frac{1}{4} - \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)\\ - &\hspace{-3.5em}+\frac{1}{4} - \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}} - P_{\mathcal{N}\setminus\{i\}}^\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: - \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 cases. - First, if the minimum of the ratio - $F(\lambda)/L(\lambda)$ is attained at a point interior to the hypercube, then it is - a critical point, \emph{i.e.}, $\partial_i \big(F(\lambda)/L(\lambda)\big)=0$ for all $i\in \mathcal{N}$; hence, at such a critical point: - \begin{equation}\label{eq:lhopital} - \frac{F(\lambda)}{L(\lambda)} - = \frac{\partial_i F(\lambda)}{\partial_i - L(\lambda)} \geq \frac{1}{2} - \end{equation} - Second, 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$. - Finally, if the minimum is attained on a face of the hypercube $[0,1]^n$ (a face is - defined as a subset of the hypercube where one of the variable is fixed to - 0 or 1), without loss of generality, we can assume that the minimum is - attained on the face where the $n$-th variable has been fixed - to 0 or 1. Then, either the minimum is attained at a point interior to the - face or on a boundary of the face. In the first sub-case, relation - \eqref{eq:lhopital} still characterizes the minimum for $i< n$. - In the second sub-case, by repeating the argument again by induction, we see - that all is left to do is to show that the bound holds for the vertices of - the cube (the faces of dimension 1). The vertices are exactly the binary - points, for which we know that both relaxations are equal to the value - function $V$. Hence, the ratio is equal to 1 on the vertices. -\end{proof} - -\begin{proof}[of Lemma~\ref{lemma:relaxation}] -Let us consider a feasible point $\lambda^*\in[0,1]^{n}$ such that $L(\lambda^*) - = OPT'$. 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 lemma. \hspace*{\stretch{1}}\qed -\end{proof} - -\subsection{Proof of Theorem \ref{thm:lowerbound}} - -\begin{proof} -Suppose, for contradiction, that such a mechanism exists. 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$. -\end{proof} - -- cgit v1.2.3-70-g09d2