From a8038aaa6c32a43e95b2730a3b8f63a286193a09 Mon Sep 17 00:00:00 2001 From: Stratis Ioannidis Date: Sat, 6 Jul 2013 21:58:31 -0700 Subject: moved algo to appendix --- main.tex | 34 +--------------------------------- 1 file changed, 1 insertion(+), 33 deletions(-) (limited to 'main.tex') diff --git a/main.tex b/main.tex index a751621..859c8f4 100644 --- a/main.tex +++ b/main.tex @@ -9,7 +9,7 @@ Recall from Section~\ref{sec:fullinfo} that $i^*\defeq \arg\max_{i\in \mathcal{N Provided that the relaxation used within a constant from $OPT$, the above allocation can be shown to also yield a constant approximation to $OPT$. 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 thus their optimal values are monotone and can be computed exactly in weakly polynomial time. In contrast, we extend these results by showing 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. -To obtain this result, we use the following modified version of Myerson's theorem \cite{myerson}, whose proof can be found in Appendix~\ref{sec:myerson}. +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 @@ -65,39 +65,7 @@ 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] - %\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 $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 - \If{$OPT'_{-i^*} < C \cdot V(i^*)$} \label{c} \textbf{return} $\{i^*\}$ - \Else - \State $i \gets \argmax_{1\leq j\leq n}\frac{V(j)}{c_j}$; $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} - \fussy -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 -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}. We can now state our main result, which is proved in Appendix~\ref{sec:proofofmainthm}: \begin{theorem}\label{thm:main} -- cgit v1.2.3-70-g09d2