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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
\label{sec:main}
In this section we use the $\delta$-decreasing, $\epsilon$-accurate algorithm solving the convex optimization problem \eqref{eq:primal} to design a mechanism for \SEDP. The construction follows a methodology employed by \citeN{chen} and \citeN{singer-influence} to construct deterministic, truthful mechanisms for \textsc{Knapsack} and \textsc{Coverage} respectively. We briefly outline this below.
%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.
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 relaxation of $OPT$ is computed over all elements excluding $i^*$. The outcome of this relaxation 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 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 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
%following properties:
%\begin{itemize}
% \item $OPT'_{-i^*}$ must not depend on agent $i^*$'s reported cost and must
% be decreasing with respect to the costs. This is to ensure the monotonicity
% of the allocation function.
% \item $OPT'_{-i^*}$ must be close to $OPT_{-i^*}$ to maintain a bounded
% approximation ratio.
% \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 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_i$ denote the indicator
%function of $i\in S(c)$, $s_i(c) \defeq \id_{i\in S(c)}$. We say that $\mathcal{M}$ is
%$\delta$-truthful iff:
%\begin{displaymath}
%\forall c\in\reals_+^n,\;
%\forall\mu\;\text{with}\; |\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 canonical basis vector of $\reals^n$.
%\end{definition}
%
%Intuitively, $\delta$-truthfulness implies that agents have no incentive to lie
%by more than $\delta$ about their reported costs. In practical applications,
%the bids being discretized, if $\delta$ is smaller than the discretization
%step, the mechanism will be truthful in effect.
%$\delta$-truthfulness will follow from $\delta$-monotonicity by the following
%variant of Myerson's theorem.
\begin{lemma}\label{thm:myerson-variant}
\sloppy 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}
\fussy
We can now state our main result, which is proved in Appendix~\ref{sec:proofofmainthm}:
\begin{theorem}\label{thm:main}
\sloppy
For any $\delta>0$, and any $\epsilon>0$, 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 returns
a set $S^*$ such that
% \begin{align*}
$ OPT
\leq \frac{10e-3 + \sqrt{64e^2-24e + 9}}{2(e-1)} V(S^*)+
\varepsilon
\simeq 12.98V(S^*) + \varepsilon.$
% \end{align*}
\end{theorem}
In addition, we prove the following simple lower bound, proved in Appendix~\ref{proofoflowerbound}.
\begin{theorem}\label{thm:lowerbound}
There is no $2$-approximate, truthful, budget feasible, individually rational
mechanism for EDP.
\end{theorem}
|
