From 310718cb00370138b8d6f0e8a8222e5ecdda843c Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Mon, 29 Feb 2016 19:39:56 -0500
Subject: Change to ACM style and inlining of the proofs

---
 main.tex | 239 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 230 insertions(+), 9 deletions(-)

(limited to 'main.tex')

diff --git a/main.tex b/main.tex
index 0354ad6..e3f557b 100644
--- a/main.tex
+++ b/main.tex
@@ -1,6 +1,6 @@
 \label{sec:main}
 
-The $\delta$-decreasing, $\epsilon$-accurate algorithm solving the convex optimization problem \eqref{eq:primal} can be used to design a mechanism for \SEDP. The construction follows a methodology proposed in \cite{singer-mechanisms} and employed by \citeN{chen} and \citeN{singer-influence} to construct \junk{deterministic, truthful} mechanisms for \textsc{Knapsack} and \textsc{Coverage} respectively. We briefly outline this below (see \cite{arxiv} for a detailed description).
+The $\delta$-decreasing, $\epsilon$-accurate algorithm solving the convex optimization problem \eqref{eq:primal} can be used to design a mechanism for \SEDP. The construction follows a methodology proposed in \cite{singer-mechanisms} and employed by \citeN{chen} and \citeN{singer-influence} to construct \junk{deterministic, truthful} mechanisms for \textsc{Knapsack} and \textsc{Coverage} respectively. 
 
 Recall from Section~\ref{sec:fullinfo} that $i^*\defeq \arg\max_{i\in
 \mathcal{N}} V(\{i\})$ is the element of maximum value, and $S_G$ is a set
@@ -24,7 +24,7 @@ polynomial time. We show that the convex relaxation \eqref{eq:primal}, solved
 by an $\epsilon$-accurate, $\delta$-decreasing algorithm, can be used to
 construct a $\delta$-truthful, constant approximation \mbox{mechanism.}
 
-To obtain this result, we use the following modified version of Myerson's theorem \cite{myerson}, whose proof we provide in \cite{arxiv}.
+To obtain this result, we use the following modified version of Myerson's theorem \cite{myerson}.
 
 \begin{lemma}\label{thm:myerson-variant}
  A normalized mechanism $\mathcal{M} = (S,p)$ for a single parameter auction is
@@ -35,14 +35,51 @@ fixed costs $c_{-i}$ of agents in $\mathcal{N}\setminus\{i\}$, $i\in S(c_i,
 c_{-i})$ implies $i\in S(c_i', c_{-i})$, and (b)
  agents are paid \emph{threshold payments}, \emph{i.e.}, for all $i\in S(c)$, $p_i(c)=\inf\{c_i': i\in S(c_i', c_{-i})\}$.
 \end{lemma}
-Lemma~\ref{thm:myerson-variant} allows us to incorporate our relaxation in the
-above framework, yielding the following theorem:
+\input{myerson}
+
+\begin{algorithm}
+    \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)}$
 
-%In the strategic case, Algorithm~\eqref{eq:max-algorithm} breaks incentive compatibility. Indeed, \citeN{singer-influence} notes that this allocation function is not monotone, which implies by Myerson's theorem (Theorem~\ref{thm:myerson}) that the resulting mechanism is not truthful.
+        \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}
+
+Lemma~\ref{thm:myerson-variant} allows us to incorporate our relaxation in the
+above framework. 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}. The guarantees of the resulting mechanism
+are summarized in the following Theorem.
 
 \begin{theorem}\label{thm:main}\label{thm:lowerbound}
-    For any $\delta\in(0,1]$, and any $\epsilon\in (0,1]$,  there exists a $\delta$-truthful, individually rational
-    and budget feasible mechanim for \EDP{} that runs in time
+    For any $\delta\in(0,1]$, and any $\epsilon\in (0,1]$,  the mechanism
+    described in Algorithm~\ref{mechanism} is $\delta$-truthful, individually rational
+    and budget feasible mechanim for \EDP{}. Furthermore, it runs in time
     $O\big(poly(n, d, \log\log\frac{B}{b\varepsilon\delta})\big)$
     and allocates
     a set $S^*$ such that
@@ -52,11 +89,195 @@ above framework, yielding the following theorem:
         \varepsilon
          \simeq 12.98V(S^*) + \varepsilon.
      \end{displaymath}
-Furthemore, there is no $2$-approximate, truthful, budget feasible, individually rational
+\end{theorem}
+
+A corresponding lower bound is given by the following theorem.
+
+\begin{theorem}
+There is no $2$-approximate, truthful, budget feasible, individually rational
 mechanism for EDP. 
 \end{theorem}
-The detailed description of our proposed mechanism as well as the proof of the theorem can be found in \cite{arxiv}.
 
+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{alg:monotone}.
+
+
+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}
+    The mechanism for \EDP{} described in Algorithm~\ref{mechanism} 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 described in Algorithm~\ref{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}
 
+\begin{proof}
+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
+\end{proof}
 
+\begin{proof}
+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
+\end{proof}
-- 
cgit v1.2.3-70-g09d2

