Rewriting of main section up to the beginning of the proof

1 files changed, 152 insertions, 199 deletions

diff --git a/main.tex b/main.tex
index 8fb9666..1f92091 100644
--- a/main.tex
+++ b/main.tex
@@ -1,210 +1,139 @@
 \label{sec:main}
-%\subsection{Truthful, Constant Approximation Mechanism}
 
-In this section we present a mechanism for \EDP.
+In this section we present our mechanism for \EDP. Prior approaches to budget
+feasible mechanisms build upon the full information case which we discuss
+first.
 
-\paragraph{Prior approach to submodular optimization problems} 
- Previous works~\cite{nemhauser, sviridenko-submodular,singer-mechanisms,chen, singer-influence}
-%
-%on maximizing submodular functions \cite{nemhauser, sviridenko-submodular} and designing
-%auction mechanisms for submodular value functions \cite{singer-mechanisms,
-%chen, singer-influence} 
-%
-rely on a greedy algorithm. In this algorithm, elements
-are added to the solution set according to the following greedy selection rule.
-Assume that $S\subseteq \mathcal{N}$ is the solution set constructed thus far; then, the next element $i$ to be
-included in $S$ is the one with the highest \emph{marginal-value-per-cost}:
+\paragraph{Full information submodular maximization}
+
+The best known approximation ratio $\frac{e}{e-1}$ for maximizing a submodular
+set function under a cardinality constraint is attained by using a greedy
+algorithm~\cite{nemhauser}. In this algorithm, elements are added to the
+solution set according to the following greedy selection rule. Assume that
+$S\subseteq \mathcal{N}$ is the solution set constructed thus far; then, the
+next element $i$ to be included in $S$ is the one with the highest
+\emph{marginal-value}: $V(S\cup\{i\}) - V(S)$. This process terminates when the
+cardinality of $S$ reaches the cardinality limit.
+
+For submodular maximization under a budget constraint \eqref{eq:non-strategic},
+the greedy algorithm can be generalized: if $S\subset\mathcal{N}$ is the set
+constructed thus far, the element $i$ to be included is the one which maximizes
+the \emph{marginal-value-per-cost}:
 \begin{align}
     i = \argmax_{j\in\mathcal{N}\setminus S}\frac{V(S\cup\{i\}) - V(S)}{c_i}\label{greedy}
 \end{align}
-This process terminates when no more items can be added to $S$ using \eqref{greedy} under budget $B$. This is the generalization of the \emph{value-per-cost} ratio used in the greedy approximation
-algorithm for \textsc{Knapsack}. However, in contrast to \textsc{Knapsack}, for general submodular
-functions, the marginal value  of an element in \eqref{greedy} depends on the set to which the element is added.
-Similarly, the value of an element depends on the set in which it is
-considered. 
-%However, in the following, the value of an element $i$ will refer to
-%its value as a singleton set: $V(\{i\})$. If there is no ambiguity, we will write
-%$V(i)$ instead of $V(\{i\})$.
-Unfortunately, even for the full information case, the greedy algorithm gives an
-unbounded approximation ratio. Instead, 
-\junk{
- Let  $i^*
-= \argmax_{i\in\mathcal{N}} V(i)$ be the element of maximum value.
-% (as a singleton set).
-%It has been noted by Khuller \emph{et al.}~\cite{khuller} that 
-For the maximum
-coverage problem, taking the maximum between the greedy solution and $V(i^*)$ (shorthand for $V(\{i\})$)
-gives a $\frac{2e}{e-1}$ approximation ratio ~\cite{khuller}. In the general sub modular case, 
-\junk{we have the
-following result from Singer \cite{singer-influence} which follows from
-Chen \emph{et al.}~\cite{chen}: \stratis{Is it Singer or Chen? Also, we need to introduce $V(i)$ somewhere...}
-}
-}
+This is repeated until the sum of costs of elements in $S$ reaches the budget
+constraint $B$. Unfortunately, the greedy algorithm alone has an unbounded
+approximation ratio~\cite{khuller}.  However, let $i^*
+= \argmax_{i\in\mathcal{N}} V(\{i\})$  be the element of maximum value, and
+$S_G$ the set computed by the greedy algorithm, taking the maximum between
+$V(S_G)$ and $V(i^*)$ yields a bounded approximation ratio. Formally, the
+following lemma holds.
 \begin{lemma}~\cite{chen}\label{lemma:greedy-bound}
 Let $S_G$ be the set computed by the greedy algorithm and let 
-%define $i^*$:
-%\begin{displaymath}
-$i^* = \argmax_{i\in\mathcal{N}} V(i).$
-%\end{displaymath}
-We have:
-% the following inequality holds:
+$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}
-Thus, 
-taking the maximum between $V(S_G)$ and $V(i^*)$ yields an approximation
-ratio of $\frac{5e}{e-1}$.  However, 
-this approach breaks incentive compatibility and therefore cannot be directly
-applied to the strategic case~\cite{singer-influence}.
-\junk{
-Indeed, suppose this allocation mechanism is used, and consider a case where
-the allocates  the greedy set ($V(S_G) \geq V(i^*)$). If an
-agent $i$ from $S_G$ reduces her cost, it could happen that $V(S_G)$
-becomes smaller than $V(i^*)$. In this case the mechanism's allocation becomes
-$i^*$, and $i$ is excluded from the allocated set. This violates the monotonicity of
-the allocation function and hence also truthfulness, by Myerson's Theorem.
-}
+This lemma immediately proves an approximation ratio of $\frac{5e}{e-1}$ for
+the afore-mentioned approach. A more sophisticated
+algorithm~\cite{sviridenko-submodular} can attain the optimal $\frac{e}{e-1}$
+approximation ratio
 
-For the strategic case, 
-\begin{itemize}
-\item
-When the underlying
-full information problem \eqref{eq:non-strategic} can be solved in
-polynomial time, Chen \emph{et al.}~\cite{chen} prove that  
-%$OPT_{-i^*}$, the optimal solution to \eqref{eq:non-strategic} when $i^*$ is excluded from set $\mathcal{N}$, can play the %role of this quantity: that is, 
-allocating to $i^*$ when
-$V(i^*) \geq C\cdot OPT_{-i^*}$ (for some constant $C$)
-and to $S_G$ otherwise yields a 8.34-approximation mechanism. However, this is not a poly-time mechanism when the underlying problem is NP hard (unless P=NP), as is the case for \EDP.
-
-\item
-For  NP-hard 
-problems, consider 
-the optimal value of a \emph{fractional relaxation} of the function $V$ over the set
-$\mathcal{N}$. A function $R:[0, 1]^{n}\to\reals_+$ defined on the hypercube  $[0, 1]^{n}$ is a fractional relaxation of $V$
-over the set $\mathcal{N}$ if %(a) $R$ is a function defined on the hypercube $[0, 1]^{n}$ and (b) 
-  $R(\id_S) = V(S)$ for all $S\subseteq\mathcal{N}$, where
-$\id_S$ denotes the indicator vector of $S$. The optimization program
-\eqref{eq:non-strategic} extends naturally to such relaxations:
-\begin{align}
-    OPT' = \argmax_{\lambda\in[0, 1]^{n}}
-    \left\{R(\lambda) \mid \sum_{i=1}^{n} \lambda_i c_i
-    \leq B\right\}\label{relax}
-\end{align}
-Substituting $OPT'_{-i^*}$ for $OPT_{-i^*}$ like before works for specific problems like \textsc{Knapsack}~\cite{chen} and 
-\textsc{Coverage}~\cite{singer-influence}. For other instances of submodular function, this overall technology
-has to be applied and extended.
-\end{itemize}
-
-
-\junk{
-To address this, Chen \emph{et al.}~\cite{chen} %and Singer~\cite{singer-influence},
- introduce a third quantity: if $V(i^*)$ is larger than this quantity, the
-mechanism allocates to $i^*$, otherwise it allocates to the greedy set $S_G$.
-This quantity must be provably close to $V(S_G)$, to keep a bounded
-approximation ratio, while maintaining the monotonicity of the allocation
-algorithm. Furthermore, it must be computable in polynomial time to keep an
-overall polynomial complexity for the allocation algorithm. 
+\fussy
+\paragraph{Strategic case}
+We could design the allocation function of our mechanism by following the full
+information approach: allocating to agent $i^*$ when $V(i^*)\geq V(S_G)$ and to
+$S_G$ otherwise. However, Singer~\cite{singer-influence} notes that this
+allocation function is not monotonous, and thus breaks incentive compatibility
+by Myerson's theorem (Theorem~\ref{thm:myerson}).
 
-\sloppy
-When the underlying
-full information problem \eqref{eq:non-strategic} can be solved in
-polynomial time, Chen et al. \cite{chen} prove that  $OPT_{-i^*}$, the optimal solution to \eqref{eq:non-strategic} when $i^*$ is excluded from set $\mathcal{N}$, can play the role of this quantity: that is, allocating to $i^*$ when
-$V(i^*) \geq C\cdot OPT_{-i^*}$ (for some constant $C$)
-and to $S_G$ otherwise yields a 8.34-approximation mechanism. However, this is not a poly-time mechanism when the underlying problem is NP hard (unless P=NP), as is the case for \EDP.
+Let us denote by $OPT_{-i^*}$ the optimal value achievable in the
+full-information case after removing $i^*$ from the set $\mathcal{N}$:
+\begin{equation}
+    OPT_{-i^*} \defeq \max_{S\subseteq\mathcal{N}\setminus\{i^*\}} \Big\{V(S) \;\Big| \;
+    \sum_{i\in S}c_i\leq B\Big\}
+\end{equation}
+Singer~\cite{singer-mechanisms} and Chen \emph{et al.}~\cite{chen} prove that
+allocating to $i^*$ when $V(i^*)\geq C.OPT_{-i^*}$ (for some constant $C$) and
+to $S_G$ otherwise yields a 8.34-approximation mechanism. However,
+$OPT_{-i^*}$, the solution of the full-information case, cannot be computed in
+poly-time when the underlying problem is NP-hard (unless P=NP), as is the case
+for \EDP{}.
 
+Instead, Singer~\cite{singer-mechanisms} and Chen \emph{et al.}~\cite{chen}
+suggest to replace $OPT_{-i^*}$ by a quantity $L^*$ satisfying the following
+properties:
+\begin{itemize}
+    \item $L^*$ must not depend on agent $i^*$'s reported
+    cost and must be monotonous: it can only increase when agents decrease
+    their costs. This is to ensure the monotonicity of the allocation function.
+    \item $L^*$ must be close to $OPT_{-i^*}$ to maintain a bounded
+    approximation ratio.
+    \item $L^*$ must be computable in polynomial time.
+\end{itemize}
 
-\fussy
-For  NP-hard 
-problems, Chen et al.~\cite{chen} %for \textsc{Knapsack} and Singer
-%\cite{singer-influence} for \textsc{Coverage} instead 
-propose comparing
-$V(i^*)$ to %$OPT(R_{\mathcal{N}\setminus\{i\}}, B)$, where $R$ denotes 
-the optimal value of a \emph{fractional relaxation} of the function $V$ over the set
-$\mathcal{N}$. A function $R:[0, 1]^{n}\to\reals_+$ defined on the hypercube  $[0, 1]^{n}$ is a fractional relaxation of $V$
-over the set $\mathcal{N}$ if %(a) $R$ is a function defined on the hypercube $[0, 1]^{n}$ and (b) 
-  $R(\id_S) = V(S)$ for all $S\subseteq\mathcal{N}$, where
-$\id_S$ denotes the indicator vector of $S$. The optimization program
+Such a quantity $L^*$ can be found by considering relaxations of the
+optimization problem. A function $R:[0, 1]^{n}\to\reals_+$ defined on the
+hypercube  $[0, 1]^{n}$ is a \emph{fractional relaxation} of $V$ over the set
+$\mathcal{N}$ if $R(\id_S) = V(S)$ for all $S\subseteq\mathcal{N}$, where $\id_S$
+denotes the indicator vector of $S$. The optimization program
 \eqref{eq:non-strategic} extends naturally to such relaxations:
 \begin{align}
     OPT' = \argmax_{\lambda\in[0, 1]^{n}}
     \left\{R(\lambda) \mid \sum_{i=1}^{n} \lambda_i c_i
     \leq B\right\}\label{relax}
 \end{align}
-To attain truthful constant approximation mechanism for \textsc{Knapsack},  Chen \emph{et al.}~\cite{chen}  substitute $OPT'_{-i^*}$ for $OPT_{-i^*}$ in the above program, where $R$ is a relaxation of the \textsc{Knapsack} objective.
-Similarly, Singer~\cite{singer-influence} follows the same approach to obtain a mechanism for \textsc{Coverage}.
-}
 
-\paragraph{Our approach}
-We build on~\cite{chen,singer-influence}. 
-We introduce a relaxation specifically tailored to the value
-function of \EDP.
-$P_\mathcal{N}^\lambda(S)$ is the probability of choosing the set $S$ if
-we select each element $i$ in $\mathcal{N}$  independently with probability
-$\lambda_i$: %or to reject it with probability $1-\lambda_i$:
-\begin{displaymath}
-    P_\mathcal{N}^\lambda(S) = \prod_{i\in S} \lambda_i
-    \prod_{i\in\mathcal{N}\setminus S}( 1 - \lambda_i)
-\end{displaymath}
-Consider  the general \emph{multi-linear}
-extension:
-\begin{equation}\label{eq:multilinear}
-    F(\lambda) 
-    = \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\left[V(S)\right]
-    = \sum_{S\subseteq\mathcal{N}} P_\mathcal{N}^\lambda(S) V(S)
-\end{equation}
-\junk{
+In \cite{singer-mechanisms} and \cite{chen}, using $L^* = OPT'_{-i^*}$, when
+$R$ is the \emph{multilinear extension} of $V$ (see
+Section~\ref{sec:relaxation}) yields an constant-approximation mechanism for
+\textsc{Knapsack}.
 
-$P_\mathcal{N}^\lambda(S)$ is the probability of choosing the set $S$ if
-we select each element $i$ in $\mathcal{N}$  independently with probability
-$\lambda_i$: %or to reject it with probability $1-\lambda_i$:
-\begin{displaymath}
-    P_\mathcal{N}^\lambda(S) = \prod_{i\in S} \lambda_i
-    \prod_{i\in\mathcal{N}\setminus S}( 1 - \lambda_i)
-\end{displaymath}
-For \textsc{Knapsack}, Chen et al. \cite{chen} directly use the multi-linear extension, as in this case \eqref{relax} can be solved in polynomial time. % for the \textsc{Knapsack} objective.
- For \textsc{Coverage} however the
-optimal value of the multi-linear extension cannot be computed in polynomial
-time. Thus, Singer \cite{singer-influence} introduces a second relaxation of
-the value function. The latter is proved to be close to the multi-linear
-extension using the \emph{pipage rounding} method of Ageev and Sviridenko
-\cite{pipage}.
+In \cite{singer-influence}, the optimization program \eqref{relax}
+cannot be solved efficiently when $R$ is the multilinear extension of $V$.
+Consequently, Singer introduces a second relaxation which he relates to the
+multilinear extension through the \emph{pipage rounding} framework of Ageev and
+Sviridenko~\cite{pipage}.
 
-Here, following these ideas, we introduce a relaxation specifically tailored to the value
-function of \EDP. 
-}
-For \EDP\  the multi-linear extension 
-%of \eqref{modified} 
-can be written:
+\paragraph{Our approach}
+Following Chen \emph{et al.}~\cite{chen} and Singer~\cite{singer-influence},
+we in turn introduce a relaxation $L$ specifically tailored to the value
+function of \EDP:
 \begin{displaymath}
-    F(\lambda) = \mathbb{E}_{S\sim
-    P_\mathcal{N}^\lambda}\Big[\log\det \big(I_d + \sum_{i\in S} x_i\T{x_i}\big) \Big].
+\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),
 \end{displaymath}
-%As in the case of \textsc{Coverage}, 
-\eqref{relax} is not a convex optimization problem, and is not easy to solve directly. %As in ~\cite{singer-influence},
-We consider an additional relaxation $L$ that 
-follows naturally by swapping the expectation and the $\log\det$
-in the above formula:
-\begin{align}\label{eq:concave}
-    L(\lambda) & \defeq \log\det\Big(\mathbb{E}_{S\sim
-    P_\mathcal{N}^\lambda}\big[I_d + \sum_{i\in S} x_i\T{x_i}\big]\Big)\notag \\
-    &= \log\det\left(I_d + \sum_{i\in\mathcal{N}}
-    \lambda_i x_i\T{x_i}\right)
-\end{align}
-This function is well-known to be concave and even self-concordant (see \emph{e.g.},
+and then use $L^* = OPT'_{-i^*}$ with $R=L$ in our mechanism. The function $L$
+is well-known to be concave and even self-concordant (see \emph{e.g.},
 \cite{boyd2004convex}). In this case, the analysis of Newton's method for
-self-concordant functions in \cite{boyd2004convex}, shows that it is possible
-to find the maximum of $L$ to any precision $\varepsilon$ in
-a number of iterations $O(\log\log\varepsilon^{-1})$. 
-The main challenge will
-be to prove that $OPT'$ in~\eqref{relax}, for the relaxation $R=L$, is close to $V(S_G)$, which we will address later and is the technical
-bulk of the 
-paper. 
-\junk{
-To do so, our
-main technical contribution is to prove that $L$ has a bounded
-approximation ratio to the value function $V$ (Lemma~\ref{lemma:relaxation}).
-}
+self-concordant functions in \cite{boyd2004convex}, shows that finding the
+maximum of $L$ to any precision $\varepsilon$ can be done in
+$O(\log\log\varepsilon^{-1})$ iterations. Being the solution to a maximization
+problem, $L^*$ satisfies the required monotonicity property. The main challenge
+will be to prove that $OPT'_{-i^*}$, for the relaxation $R=L$, is close to
+$OPT$. As in~\cite{singer-influence} this will be done by using the
+\emph{pipage rounding} framework of~\cite{pipage} and forms the technical bulk
+of the paper.
+
+The resulting mechanism for \EDP{} is composed of
+\begin{itemize}
+\item
+ the allocation function
+presented in Algorithm~\ref{mechanism}, and 
+\item
+the payment function which pays each
+allocated agent $i$ her threshold payment as described in Myerson's Theorem. 
+%The constant $C$ is an absolute
+%constant that determined in Section~\ref{sec:proofofmainthm}
+%(see \eqref{eq:c}). 
+ 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 payment when $S_G$ is the allocated
+set can be found in~\cite{singer-mechanisms}.
+\end{itemize}
 
 \begin{algorithm}[!t]
     \caption{Mechanism for \EDP{}}\label{mechanism}
@@ -228,26 +157,6 @@ approximation ratio to the value function $V$ (Lemma~\ref{lemma:relaxation}).
         \EndIf
     \end{algorithmic}
 \end{algorithm}
-
-The resulting mechanism for \EDP{} is composed of
-\begin{itemize}
-\item
- the allocation function
-presented in Algorithm~\ref{mechanism}, and 
-\item
-the payment function which pays each
-allocated agent $i$ her threshold payment as described in Myerson's Theorem. 
-%The constant $C$ is an absolute
-%constant that determined in Section~\ref{sec:proofofmainthm}
-%(see \eqref{eq:c}). 
- 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). In the case where $S_G$ is the allocated set, threshold payments'
-characterization from~\cite{singer-mechanisms} gives a formula to
- compute these payments.
- \end{itemize}
-
 We can now state our main result:
 \begin{theorem}\label{thm:main}
     \sloppy
@@ -276,6 +185,50 @@ There is no $2$-approximate, truthful, budget feasible, individually rational me
 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}
 
+\begin{comment}
+$P_\mathcal{N}^\lambda(S)$ is the probability of choosing the set $S$ if
+we select each element $i$ in $\mathcal{N}$  independently with probability
+$\lambda_i$: %or to reject it with probability $1-\lambda_i$:
+\begin{displaymath}
+    P_\mathcal{N}^\lambda(S) = \prod_{i\in S} \lambda_i
+    \prod_{i\in\mathcal{N}\setminus S}( 1 - \lambda_i)
+\end{displaymath}
+Consider  the general \emph{multi-linear}
+extension:
+\begin{equation}\label{eq:multilinear}
+    F(\lambda) 
+    = \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\left[V(S)\right]
+    = \sum_{S\subseteq\mathcal{N}} P_\mathcal{N}^\lambda(S) V(S)
+\end{equation}
+\junk{
+
+$P_\mathcal{N}^\lambda(S)$ is the probability of choosing the set $S$ if
+we select each element $i$ in $\mathcal{N}$  independently with probability
+$\lambda_i$: %or to reject it with probability $1-\lambda_i$:
+\begin{displaymath}
+    P_\mathcal{N}^\lambda(S) = \prod_{i\in S} \lambda_i
+    \prod_{i\in\mathcal{N}\setminus S}( 1 - \lambda_i)
+\end{displaymath}
+
+For \EDP\  the multi-linear extension 
+%of \eqref{modified} 
+can be written:
+\begin{displaymath}
+    F(\lambda) = \mathbb{E}_{S\sim
+    P_\mathcal{N}^\lambda}\Big[\log\det \big(I_d + \sum_{i\in S} x_i\T{x_i}\big) \Big].
+\end{displaymath}
+%As in the case of \textsc{Coverage}, 
+\eqref{relax} is not a convex optimization problem, and is not easy to solve directly. %As in ~\cite{singer-influence},
+We consider an additional relaxation $L$ that 
+follows naturally by swapping the expectation and the $\log\det$
+in the above formula:
+\begin{align}\label{eq:concave}
+    L(\lambda) & \defeq \log\det\Big(\mathbb{E}_{S\sim
+    P_\mathcal{N}^\lambda}\big[I_d + \sum_{i\in S} x_i\T{x_i}\big]\Big)\notag \\
+    &= \log\det\left(I_d + \sum_{i\in\mathcal{N}}
+    \lambda_i x_i\T{x_i}\right)
+\end{align}
+\end{comment}
 \subsection{Proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm}
 %\stratis{individual rationality???}
 %The proof of the properties of the mechanism is broken down into lemmas.