diff options
Diffstat (limited to 'main.tex')
| -rwxr-xr-x | main.tex | 38 |
1 files changed, 37 insertions, 1 deletions
@@ -2,6 +2,42 @@ 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. The following theorem summarizes the properties of our merchanism. +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 \cite{arxiv}. + +\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 the following theorem: %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. @@ -20,7 +56,7 @@ The $\delta$-decreasing, $\epsilon$-accurate algorithm solving the convex optimi Furthemore, there is no $2$-approximate, truthful, budget feasible, individually rational mechanism for EDP. \end{theorem} -The detailed description of our proposed mechanism (Algorithm~\ref{mechanism}), as well as the proof of the theorem can be found in Appendix~\ref{sec:proofofmainthm}. +The detailed description of our proposed mechanism as well as the proof of the theorem can be found in \cite{arxiv}. |