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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
|
\label{sec:main}
In this section we present our mechanism for \SEDP. Prior approaches to budget
feasible mechanisms for submodular maximization build upon the full information
case, which we discuss first.
\subsection{Submodular Maximization in the Full Information Case}
In the full-information case, submodular maximization under a budget constraint
\eqref{eq:non-strategic} relies on a greedy heuristic in which elements are
added to the solution set according to the following greedy selection rule.
Assume that $S\subseteq\mathcal{N}$ is the set constructed thus far, the next
element $i$ to be included is the one which maximizes the
\emph{marginal-value-per-cost}:
\begin{align}
i = \argmax_{j\in\mathcal{N}\setminus S}\frac{V(S\cup\{i\}) - V(S)}{c_i}\label{greedy}
\end{align}
This is repeated until the sum of costs of elements in $S$ reaches the budget
constraint $B$. Denote by $S_G$ the set constructed by this heuristic and let
$i^*=\argmax_{i\in\mathcal{N}} V(\{i\})$ be the element of maximum value. Then,
the following algorithm:
\begin{equation}\label{eq:max-algorithm}
\textbf{if}\; V(\{i^*\}) \geq V(S_G)\; \textbf{return}\; \{i^*\}
\;\textbf{else return}\; S_G
\end{equation}
has a constant approximation ratio \cite{singer-mechanisms}.
\subsection{Submodular Maximization in the Strategic Case}
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.
Let us denote by $OPT_{-i^*}$ the optimal value achievable in the
full-information case after removing $i^*$ from the set $\mathcal{N}$:
\begin{equation}\label{eq:opt-reduced}
OPT_{-i^*} \defeq \max_{S\subseteq\mathcal{N}\setminus\{i^*\}} \Big\{V(S) \;\Big| \;
\sum_{i\in S}c_i\leq B\Big\}
\end{equation}
\citeN{singer-mechanisms} and \citeN{chen} prove that the following
allocation:
\begin{displaymath}
\textbf{if}\; V(\{i^*\}) \geq C \cdot OPT_{-i^*}\; \textbf{return}\; \{i^*\}
\;\textbf{else return}\; S_G
\end{displaymath}
yields a 8.34-approximation mechanism for an appropriate $C$ (see also
Algorithm~\ref{mechanism}). However, $OPT_{-i^*}$, the maximum value attainable
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 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 monotone: it can only increase when agents decrease
their 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$ 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{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$ 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}
\State \textbf{return} $\{i^*\}$
\Else
\State $i \gets \argmax_{1\leq j\leq n}\frac{V(j)}{c_j}$
\State $S_G \gets \emptyset$
\While{$c_i\leq \frac{B}{2}\frac{V(S_G\cup\{i\})-V(S_G)}{V(S_G\cup\{i\})}$}
\State $S_G \gets S_G\cup\{i\}$
\State $i \gets \argmax_{j\in\mathcal{N}\setminus S_G}
\frac{V(S_G\cup\{j\})-V(S_G)}{c_j}$
\EndWhile
\State \textbf{return} $S_G$
\EndIf
\end{algorithmic}
\end{algorithm}
\fussy
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
payment as described in Myerson's Theorem. In the case where $\{i^*\}$ is the
allocated set, her threshold payment is $B$ (she would be have been dropped on
line 1 of Algorithm~\ref{mechanism} had she reported a higher cost).
A closed-form formula for threshold payments when $S_G$ is the allocated set can
be found in~\cite{singer-mechanisms}.
\end{itemize}
We can now state our main result:
\begin{theorem}\label{thm:main}
\sloppy
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^*)+
\varepsilon
\simeq 12.98V(S^*) + \varepsilon
\end{align*}
\end{theorem}
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.
\end{theorem}
|
