1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
\label{sec:main}
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.
%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.
\begin{theorem}\label{thm:main}\label{thm:lowerbound}
For any $\delta\in(0,1]$, and any $\epsilon\in (0,1]$, there exists a $\delta$-truthful, individually rational
and budget feasible mechanim for \EDP{} that runs in time
$O\big(poly(n, d, \log\log\frac{B}{b\varepsilon\delta})\big)$
and allocates
a set $S^*$ such that
\begin{displaymath}
OPT
\leq \frac{10e-3 + \sqrt{64e^2-24e + 9}}{2(e-1)} V(S^*)+
\varepsilon
\simeq 12.98V(S^*) + \varepsilon.
\end{displaymath}
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}.
|
