From 0f9dd86764035eec8a8f79cd0a457d08d2522dae Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Thu, 4 Jul 2013 15:24:11 -0700
Subject: mechanism

---
 main.tex | 170 ++++++++++++++++++++++++---------------------------------------
 1 file changed, 64 insertions(+), 106 deletions(-)

(limited to 'main.tex')

diff --git a/main.tex b/main.tex
index f44926b..cfcc97d 100644
--- a/main.tex
+++ b/main.tex
@@ -1,112 +1,70 @@
 \label{sec:main}
 
-In this section we present our mechanism for \SEDP. 
-\begin{comment}
-Prior approaches to budget
-feasible mechanisms for submodular maximization build upon the full information
-case, which we discuss first.
-
-\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
-added to the solution set according to the following greedy selection rule.
-Assume that $S\subseteq\mathcal{N}$ is the set constructed thus far, the next
-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 is repeated until the sum of costs of elements in $S$ reaches the budget
-constraint $B$. Denote by $S_G$ the set constructed by this heuristic and let
-$i^*=\argmax_{i\in\mathcal{N}} V(\{i\})$ be the element of maximum value. Then,
-the following algorithm:
-\begin{equation}\label{eq:max-algorithm}
-\textbf{if}\; V(\{i^*\}) \geq V(S_G)\; \textbf{return}\; \{i^*\}
-\;\textbf{else return}\; S_G
-\end{equation}
-has a constant approximation ratio \cite{singer-mechanisms}.
-\end{comment}
-
-\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
-function is not monotone, which implies by Myerson's theorem
-(Theorem~\ref{thm:myerson}) that the resulting mechanism is not truthful.
-
-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}\label{eq:opt-reduced}
-    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}
-\citeN{singer-mechanisms} and \citeN{chen} prove that the following
-allocation:
-\begin{displaymath}
-\textbf{if}\; V(\{i^*\}) \geq C \cdot OPT_{-i^*}\; \textbf{return}\; \{i^*\}
-\;\textbf{else return}\; S_G
-\end{displaymath}
-yields a 8.34-approximation mechanism for an appropriate $C$ (see also
-Algorithm~\ref{mechanism}). However, $OPT_{-i^*}$, the maximum value attainable
-in 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 \SEDP{}.
-
-Instead, \citeN{singer-mechanisms} and \citeN{chen}
-suggest to approximate $OPT_{-i^*}$ by a quantity $OPT'_{-i^*}$ satisfying the
-following properties:
-\begin{itemize}
-    \item $OPT'_{-i^*}$ must not depend on agent $i^*$'s reported cost and must
-    be decreasing with respect to the costs. This is to ensure the monotonicity
-    of the allocation function.
-    \item $OPT'_{-i^*}$ must be close to $OPT_{-i^*}$ to maintain a bounded
-    approximation ratio.
-    \item $OPT'_{-i^*}$ must be computable in polynomial time.
-\end{itemize}
-
-One of the main technical contributions of \citeN{chen} and
-\citeN{singer-influence} is to come up with appropriate such quantity by
-considering relaxations of \textsc{Knapsack} and \textsc{Coverage},
-respectively.
-
-\subsection{Our Approach}
-
-Using the results from Section~\ref{sec:approximation}, we come up with
-a suitable approximation $OPT_{-i^*}'$ of $OPT_{-i^*}$. Our approximation being
-$\delta$-decreasing, the resulting mechanism will be $\delta$-truthful as
-defined below.
-
-\begin{definition}
-Let $\mathcal{M}= (S, p)$ a mechanism, and let $s_i$ denote the indicator
-function of $i\in S(c)$, $s_i(c) \defeq \id_{i\in S(c)}$. We say that $\mathcal{M}$ is
-$\delta$-truthful iff:
-\begin{displaymath}
-\forall c\in\reals_+^n,\;
-\forall\mu\;\text{with}\; |\mu|\geq\delta,\;
-\forall i\in\{1,\ldots,n\},\;
-p(c)-s_i(c)\cdot c_i \geq p(c+\mu e_i) - s_i(c+\mu e_i)\cdot c_i
-\end{displaymath}
-where $e_i$ is the $i$-th canonical basis vector of $\reals^n$.
-\end{definition}
-
-Intuitively, $\delta$-truthfulness implies that agents have no incentive to lie
-by more than $\delta$ about their reported costs. In practical applications,
-the bids being discretized, if $\delta$ is smaller than the discretization
-step, the mechanism will be truthful in effect.
-
-$\delta$-truthfulness will follow from $\delta$-monotonicity by the following
-variant of Myerson's theorem.
+In this section we present our mechanism for \SEDP, uses the $\delta$-decreasing, $\epsilon$-accurate algorithm solving the convex optimization problem \eqref{eq:primal}. The construction follows a methodology employed by \citeN{Chen} and \citeN{singer-influence} to construct deterministic, truthful mechanisms for \textsc{Knapsack} and \textsc{Coverage} respectively, which we first describe below.
+
+
+%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.
+
+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 constructed greedily, by selecting elements of maximum marginal value per cost. The general framework used by \citeN{chen}  and by \citeN{singer-influence} for the \textsc{Knapsack}   and \textsc{Coverage} value functions contructs an allocation as follows. First, a polynomial-time, monotone relaxation of $OPT$ is computed over all elements excluding $i^*$. The outcome of this relaxation is compared to $V(\{i^*\})$: if it exceeds $V(\{i^*\})$, then the mechanism constructs an allocation $S_G$ greedily; otherwise, the only item allocated is the singleton $\{i^*\}$.
+
+Provided that the relaxation used within a constant approximation of $OPT$, the above allocation can be shown to have a constant approximation. Furthermore, this allocation combined with \emph{threshold payments}, the mechanism can be shown to be truthful when the relaxation is monotone. The relaxations used in \cite{chen,singer-influence} are linear programs, and can be solved exactly in weakly polynomial time. The challenge in our setting is dealing with a convex relaxationsolved by an $\epsilon$-accurate, $\delta$-decreasing algorithm. In our setting, this yields a $\delta$-truthful, constant approximation mechanism. 
+
+To obtain this result, we use the following modified version of Myerson's theorem, whose proof can be found in Appendix~\note{FIXME!!!}
+%
+%Instead, \citeN{singer-mechanisms} and \citeN{chen}
+%suggest to approximate $OPT_{-i^*}$ by a quantity $OPT'_{-i^*}$ satisfying the
+%following properties:
+%\begin{itemize}
+%    \item $OPT'_{-i^*}$ must not depend on agent $i^*$'s reported cost and must
+%    be decreasing with respect to the costs. This is to ensure the monotonicity
+%    of the allocation function.
+%    \item $OPT'_{-i^*}$ must be close to $OPT_{-i^*}$ to maintain a bounded
+%    approximation ratio.
+%    \item $OPT'_{-i^*}$ must be computable in polynomial time.
+%\end{itemize}
+%
+%One of the main technical contributions of \citeN{chen} and
+%\citeN{singer-influence} is to come up with appropriate such quantity by
+%considering relaxations of \textsc{Knapsack} and \textsc{Coverage},
+%respectively.
+%
+%\subsection{Our Approach}
+%
+%Using the results from Section~\ref{sec:approximation}, we come up with
+%a suitable approximation $OPT_{-i^*}'$ of $OPT_{-i^*}$. Our approximation being
+%$\delta$-decreasing, the resulting mechanism will be $\delta$-truthful as
+%defined below.
+%
+%\begin{definition}
+%Let $\mathcal{M}= (S, p)$ a mechanism, and let $s_i$ denote the indicator
+%function of $i\in S(c)$, $s_i(c) \defeq \id_{i\in S(c)}$. We say that $\mathcal{M}$ is
+%$\delta$-truthful iff:
+%\begin{displaymath}
+%\forall c\in\reals_+^n,\;
+%\forall\mu\;\text{with}\; |\mu|\geq\delta,\;
+%\forall i\in\{1,\ldots,n\},\;
+%p(c)-s_i(c)\cdot c_i \geq p(c+\mu e_i) - s_i(c+\mu e_i)\cdot c_i
+%\end{displaymath}
+%where $e_i$ is the $i$-th canonical basis vector of $\reals^n$.
+%\end{definition}
+%
+%Intuitively, $\delta$-truthfulness implies that agents have no incentive to lie
+%by more than $\delta$ about their reported costs. In practical applications,
+%the bids being discretized, if $\delta$ is smaller than the discretization
+%step, the mechanism will be truthful in effect.
+
+%$\delta$-truthfulness will follow from $\delta$-monotonicity by the following
+%variant of Myerson's theorem.
 
 \begin{lemma}\label{thm:myerson-variant}
 \sloppy A normalized mechanism $\mathcal{M} = (S,p)$ for a single parameter auction is
-$\delta$-truthful iff:
+$\delta$-truthful if:
 (a) $S$ is $\delta$-decreasing, \emph{i.e.}, for any agent $i$ and $c_i' \leq
 c_i-\delta$, for any
 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}
-
 \begin{algorithm}[t]
     \caption{Mechanism for \SEDP{}}\label{mechanism}
     \begin{algorithmic}[1]
@@ -144,25 +102,25 @@ A closed-form formula for threshold payments when $S_G$ is the allocated set can
 be found in~\cite{singer-mechanisms}.
 \end{itemize}
 
-We can now state our main result:
+We can now state our main result, which is proved in Appendix~\ref{sec:proofofmainthm}:
 \begin{theorem}\label{thm:main}
     \sloppy
-    For any $\delta$, the allocation described in Algorithm~\ref{mechanism},
+    For any $\delta>0$ the allocation described in Algorithm~\ref{mechanism},
     along with threshold payments, is $\delta$-truthful, individually rational
     and budget feasible.  Furthermore, there exists an absolute constant $C$
     such that, for any $\varepsilon>0$, the mechanism runs in time
     $O\big(poly(n, d, \log\log\frac{1}{b\varepsilon\delta})\big)$
     and returns
     a set $S^*$ such that:
-    \begin{align*}
-        OPT
-        & \leq \frac{10e-3 + \sqrt{64e^2-24e + 9}}{2(e-1)} V(S^*)+
+%    \begin{align*}
+       $ OPT
+         \leq \frac{10e-3 + \sqrt{64e^2-24e + 9}}{2(e-1)} V(S^*)+
         \varepsilon
-         \simeq 12.98V(S^*) + \varepsilon
-    \end{align*}
+         \simeq 12.98V(S^*) + \varepsilon.$
+%    \end{align*}
 \end{theorem}
 The value of the constant $C$ is given by \eqref{eq:constant} in
-Section~\ref{sec:proofofmainthm}.
+Appendix~\ref{sec:proofofmainthm}.
 In addition, we prove the following simple lower bound.
 
 \begin{theorem}\label{thm:lowerbound}
-- 
cgit v1.2.3-70-g09d2

