diff options
Diffstat (limited to 'appendix.tex')
| -rwxr-xr-x | appendix.tex | 49 |
1 files changed, 3 insertions, 46 deletions
diff --git a/appendix.tex b/appendix.tex index 6926e00..63a8dd8 100755 --- a/appendix.tex +++ b/appendix.tex @@ -264,14 +264,7 @@ 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. We achieve this by restricting the optimization over a subset of $\dom_c$ at which the concave relaxation $L$ is ``sufficiently'' concave. Formally, for $\alpha\geq 0$ let $$\textstyle\dom_{c,\alpha} \defeq \{\lambda \in [\alpha,1]^n: \sum_{i\in \mathcal{N}}c_i\lambda_i \leq B\}\subseteq \dom_c . $$ -Note that $\dom_c=\dom_{c,0}.$ Consider the following perturbation of the concave relaxation \eqref{eq:primal}: -\begin{align}\tag{$P_{c,\alpha}$}\label{eq:perturbed-primal} -\begin{split} \text{Maximize:} &\qquad L(\lambda)\\ -\text{subject to:} & \qquad\lambda \in \dom_{c,\alpha} -\end{split} -\end{align} - +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. @@ -594,31 +587,6 @@ Formally, there must exist some $\alpha\geq 1$ and $\beta>0$ \section{Description of our mechanism for \EDP{} and proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm} -We begin by a description of the methodology used to construct our mechanism. -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 approximation of -$OPT$ is computed over all elements excluding $i^*$. The outcome of this -approximation 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 approximation used is -within a constant from $OPT$, the above allocation can be shown to also yield -a constant approximation to $OPT$. Furthermore, using Myerson's -Theorem~\cite{myerson}, it can be shown that this allocation combined with -\emph{threshold payments} (see Lemma~\ref{thm:myerson-variant} below) -constitute a truthful mechanism. - -The approximation algorithms used in \cite{chen,singer-influence} are LP -relaxations, and thus their outputs are monotone and can be computed exactly in -polynomial time. We show that the convex relaxation \eqref{eq:primal}, which -can be solved by an $\epsilon$-accurate, $\delta$-decreasing algorithm, can be -used to construct a $\delta$-truthful, constant approximation mechanism, by -being incorporated in the same framework. - -To obtain this result, we use the following modified version of Myerson's theorem \cite{myerson}, whose proof we provide in Appendix~\ref{sec:myerson}. % %Instead, \citeN{singer-mechanisms} and \citeN{chen} %suggest to approximate $OPT_{-i^*}$ by a quantity $OPT'_{-i^*}$ satisfying the @@ -665,17 +633,6 @@ To obtain this result, we use the following modified version of Myerson's theore %$\delta$-truthfulness will follow from $\delta$-monotonicity by the following %variant of Myerson's theorem. -\begin{lemma}\label{thm:myerson-variant} - A normalized mechanism $\mathcal{M} = (S,p)$ for a single parameter auction is -$\delta$-truthful if: -(a) $S$ is $\delta$-monotone, \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} -Lemma~\ref{thm:myerson-variant} allows us to incorporate our relaxation in the -above framework, yielding Theorem~\ref{thm:main}. \begin{algorithm}[!t] \caption{Mechanism for \SEDP{}}\label{mechanism} @@ -706,11 +663,11 @@ above framework, yielding Theorem~\ref{thm:main}. \end{algorithm} -We now present the proof of Theorem~\ref{thm:main}. +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. In the case where $\{i^*\}$ is the +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 |