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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
\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. We briefly outline this below (see \cite{arxiv} for a detailed description).
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, Myerson's
Theorem~\cite{myerson} implies 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}, solved
by an $\epsilon$-accurate, $\delta$-decreasing algorithm, can be used to
construct a $\delta$-truthful, constant approximation \mbox{mechanism.}
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.
\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 as well as the proof of the theorem can be found in \cite{arxiv}.
|
