diff options
Diffstat (limited to 'main.tex')
| -rw-r--r-- | main.tex | 34 |
1 files changed, 1 insertions, 33 deletions
@@ -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} |