diff options
Diffstat (limited to 'main.tex')
| -rw-r--r-- | main.tex | 65 |
1 files changed, 47 insertions, 18 deletions
@@ -50,7 +50,7 @@ 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 replace $OPT_{-i^*}$ by a quantity $OPT'_{-i^*}$ satisfying the +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 @@ -61,27 +61,52 @@ following properties: \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 relaxations for -\textsc{Knapsack} and \textsc{Coverage}, respectively. +\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$ denote the indicator +function of $S$ ($s_i(c) = \id_{i\in S(c)}$). We say that $\mathcal{M}$ is +$\delta$-truthful iff: +\begin{displaymath} +\forall c\in\reals_+^n,\; +\forall\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 basis vector of $\reals^n$. +\end{definition} + +$\delta$-truthfulness will follow from $\delta$-monotonicity by the following +variant of Myerson's theorem. -\begin{comment} -The main challenge -will be to prove that $OPT'_{-i^*}$, for our relaxation $L$, is close to -$OPT_{-i^*}$. -We show this by establishing that $L$ is within a constant factor from the so-called multi-linear relaxation of \eqref{modified}, which in turn can be related to \eqref{modified} through pipage rounding. We establish the constant factor to the multi-linear relaxation by bounding the partial derivatives of these two functions; we obtain the latter bound by exploiting convexity properties of matrix functions over the convex cone of positive semidefinite matrices. -\end{comment} +\begin{lemma}\label{thm:myerson-variant} +\sloppy A normalized mechanism $\mathcal{M} = (S,p)$ for a single parameter auction is +$\delta$-truthful iff: +(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] \State $\mathcal{N} \gets \mathcal{N}\setminus\{i\in\mathcal{N} : c_i > B\}$ \State $i^* \gets \argmax_{j\in\mathcal{N}}V(j)$ - \State $OPT'_{-i^*} \gets \max_{\lambda\in[0,1]^{n}} \{L(\lambda) + \State $OPT'_{-i^*} \gets$ using Proposition~\ref{prop:monotonicity}, + compute a $\varepsilon$-accurate, $\delta$-decreasing + approximation of $\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} @@ -100,7 +125,7 @@ We show this by establishing that $L$ is within a constant factor from the so-ca \end{algorithm} \fussy -In summary, the resulting mechanism for \EDP{} is composed of +Our mechanism for \EDP{} is composed of \begin{itemize} \item the allocation function presented in Algorithm~\ref{mechanism}, and \item the payment function which pays each allocated agent $i$ her threshold @@ -114,11 +139,13 @@ be found in~\cite{singer-mechanisms}. We can now state our main result: \begin{theorem}\label{thm:main} \sloppy - The allocation described in Algorithm~\ref{mechanism}, along with threshold - payments, is 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\left(\text{poly}(n, d, - \log\log \varepsilon^{-1})\right)$ and returns a set $S^*$ such that: + For any $\delta$, 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^*)+ @@ -129,7 +156,9 @@ We can now state our main result: The value of the constant $C$ is given by \eqref{eq:constant} in Section~\ref{sec:proofofmainthm}. In addition, we prove the following simple lower bound. + \begin{theorem}\label{thm:lowerbound} -There is no $2$-approximate, truthful, budget feasible, individually rational mechanism for EDP. +There is no $2$-approximate, truthful, budget feasible, individually rational +mechanism for EDP. \end{theorem} |